【NLP】经典文本匹配算法_关键词匹配长文本算法

文本匹配主要是将两段文本进行相似度计算，以选择最匹配的内容，如搜索场景下选择相似的内容、问答场景下在问题库中匹配最相近的问题并返回对应的回答等。也可延伸用于序列形式的匹配，如地址匹配、路径序列等。

本文主要整理一下经典的文本匹配/相似度计算算法，包括Jaccard相似度、Levenshtein编辑距离、Simhash、TF-IDF、BM25。

Jaccard相似度

参考链接：https://en.wikipedia.org/wiki/Jaccard_index

Jaccard相似度，是用于比较有限样本集合的相似性的统计量，定义为两个集合的交集与并集的比例。
$$\begin{gathered} J(A,B)=\frac{|A\cap B|}{|A\cup B|}=\frac{|A\cap B|}{|A|+|B|-|A\cap B|} \\ 0\le J(A,B)\le 1 \end{gathered}$$
对应的Jaccard距离为:
$$d_J(A,B)=1-J(A,B)=\frac{|A\cup B|-|A\cap B|}{|A\cup B|}$$

Levenshtein编辑距离

参考链接：

https://zh.wikipedia.org/wiki/%E8%90%8A%E6%96%87%E6%96%AF%E5%9D%A6%E8%B7%9D%E9%9B%A2

https://zhuanlan.zhihu.com/p/43009353

Levenshtein距离，是编辑距离的一种，指两个字符串之间，由一个转换成另一个所需的最少编辑次数。其中编辑操作包括：插入、删除、替换。编辑操作可以有不同权重，这里以等权为例。求解算法通常为动态规划。

定义a、b两个字符串，则其编辑距离如下：

其中，${\text{lev}}_{a,b}(i,j)$表示$a$字符串的前$i$个字符，与$b$字符串的前$j$个字符的编辑距离；$1_{\left(a_i\ne b_j\right)}$是指示函数，当二者相同时为1，否则为0。$\min$运算中的3个公式，分别表示对字符串$a$执行删除、插入、替换操作。

具体求解编辑距离通常用动态规划算法，伪代码如下。首先构造一个距离矩阵，其中第一行第一列表示两个空串，每个交叉点表示对应的编辑距离，最右下角的编辑距离即是整个字符串的编辑距离。

• 示例如下：
  

• 实现上可调包：

pip install python-Levenshtein
import Levenshtein
1
2

Simhash

参考链接：https://www.cnblogs.com/maybe2030/p/5203186.html

Simhash是一种将文本hash编码之后，仍然能保持一定的相似度计算能力的hash编码。基本思路是将词进行hash编码后，得到64位01串，对每个词中0改为-1并对整体加权，最后将所有词求和作为句子的表示。

具体流程包括：

1. 分词。有意义则分词，否则直接分到字
2. hash。将词转为01串，如10101111
3. 加权。如果有单词的权重信息，则加权，如2 -2 2 -2 2 2 2 2
4. 合并。将句子的所有词求和
5. 降维。对合并后的结果中，>0的设置为1，<0的设置为0
1
2
3
4
5

示例如下：

TF-IDF

参考：

https://zhuanlan.zhihu.com/p/113017752

https://zh.wikipedia.org/wiki/Tf-idf

https://zhuanlan.zhihu.com/p/348412847

TF-IDF是衡量一个文档集中每个文档中每个词的重要性。TF，一个词在当前文档中出现的次数越多越重要；IDF，文档集中，一个词出现的文档数越少越重要。
$$tf\times idf(i,j)=t{f}_{ij}\times id{f}_i=\frac{n_{ij}}{{\sum }_k{n}_{kj}}\times \log (\frac{|D|}{1+|D_i|})$$
在求文本相似度时，基本思路是找出字符串之间共现的词，并用tfidf做加权。即
$$Scor{e}_{tfidf}(Q,D)=\sum _i^{n}ID{F}_i\ast TF(q_i,D)$$

BM25

参考：

https://zhuanlan.zhihu.com/p/113224707
https://en.wikipedia.org/wiki/Okapi_BM25

BM25是搜索中的经典算法，与TFIDF做相似度类似，只是优化的每项的计算方式。
$$\text{score}(D,Q)=\sum _{i=1}^n\text{IDF}(q_i)\cdot \frac{f(q_i,D)\cdot (k_1+1)}{f(q_i,D)+k_1\cdot \left(1-b+b\cdot \frac{|D|}{\text{avgdl}}\right)}$$
其中$D$表示候选句，$Q$表示查询句， Q = { q 1 , . . . , q n } Q=\{q_1,...,q_n\} Q={q1​,...,qn​}。$IDF$表示词的权重或重要性，逆文档率的一种形式，如下所示$N$表示总文档数，$n(q_i)$表示包含改词的文档数
$$\text{IDF}(q_i)=\ln (\frac{N-n(q_i)+0.5}{n(q_i)+0.5}+1)$$
公式的右半部分表示词频信息，主要是查询词和候选句之间的关系。$f(q_i,D)$表示改词在该文档中出现的次数，$|D|$为该文档的总词数，$\text{avgdl}$表示文档集中文档的平均词数，$k_1,b$是超参数，通常取值$k_1\in [1.2,2.0],b=0.75$。

• 如上面的参考链接，还有一种写法如下，多加了一个查询词和查询句的关系。

其他

其他还有如LCS（最长公共子序列）、SSK（字符串核）等。有机会在补上吧。