A Survey Of Text Similarity Approach

（本文翻译自上述文献）

• 方法分为四种string-based，corpus-based，knowledge-based，Hybrid Similarity Measure

Introduction:

​ lexical similarity: string-based

​ semantic similarity: corpus-based, knowledge-based

---

String-based

• character-based

1. longest common substring. 连续最长公共子串

2. Damerau-Levenshtein: 编辑距离

3. Jaro: 以公共字符的数量和顺序为基础，主要运用在Record Linkage( Record linkage (RL) refers to the task of finding records in a data set that refer to the same entity across different data sources (e.g., data files, books, websites, databases)
   $\begin{aligned}&Jaro\quad Distance\\ &给定两个字符串S_1,S_2,二者之间的Jaro Distance由下面公式给出：\\ &d_j = \frac{1}{3}(\frac{m}{|S_1|}+\frac{m}{|S_2|}+\frac{m-t}{m})\\ &其中m表示两个字符串匹配的字符数目(不考虑顺序，A中的字符只要出现在B\\&中,就认为匹配。t代表需要不同顺序匹配字符数的一半。例如martha和marhta\\&，m=6，t=2/2=1) \end{aligned}$​JaroDistance给定两个字符串S1​,S2​,二者之间的JaroDistance由下面公式给出：dj​=31​(∣S1​∣m​+∣S2​∣m​+mm−t​)其中m表示两个字符串匹配的字符数目(不考虑顺序，A中的字符只要出现在B中,就认为匹配。t代表需要不同顺序匹配字符数的一半。例如martha和marhta，m=6，t=2/2=1)​

4. Jaro-Winkler：Jaro距离的扩展，其基本思想是如果两个字符串的起始部位匹配，则应该给与更高的分数。
   $\begin{aligned} &d_w = d_j + (lp(1-d_j))\\ &l代表前缀相同的长度，规定最大为4，p是一个用于调整的常数，一般设置为0.1. \end{aligned}$​dw​=dj​+(lp(1−dj​))l代表前缀相同的长度，规定最大为4，p是一个用于调整的常数，一般设置为0.1.​

5. Needleman-Wunsch: 一个动态规划算法，适用于具有相似长度的两个序列，其两个序列的内容也比较相似。目的：得到两个序列的全部序列匹配。
   $\begin{aligned} &假设对比的两个序列为A和B，lcs(i,j)代表（a_1a_2..a_i,b_1b_2..b_j）的最长公共子串\\ &H_{ij}=max\left\{ \begin{aligned} &lcs(i-1,j-1)+1\quad if a_i=b_j\\ &max(lcs(i-1,j-1),lcs(i-1,j),lcs(i,j-1))\quad if a_i\neq b_j \end{aligned} \right. \end{aligned}$​假设对比的两个序列为A和B，lcs(i,j)代表（a1​a2​..ai​,b1​b2​..bj​）的最长公共子串Hij​=max{​lcs(i−1,j−1)+1ifai​=bj​max(lcs(i−1,j−1),lcs(i−1,j),lcs(i,j−1))ifai​​=bj​​​
   然后开始回溯，方法同6一样。不在赘述。
   

6. Simith-waterman: 局部序列对齐，找出两个序列中具有高相似度的片段
   $\begin{aligned} &假设对比的两个序列为A和B，s(a,b)表示字符a和字符b的相似分数，H代表\\&匹配分数矩阵，W_1表示空位罚分。\\ &H_{ij}=max\left\{ \begin{aligned} &H_{i-1,j-1}+s(A_i,B_j)\\&H_{i-1,j}-W_1\\&H_{i,j-1}-W_1\\&0 \end{aligned} \right. &s(a_i,b_j)=\left\{ \begin{aligned} &3\quad if a_i=bj\\&-3\quad ifa_i\neq b_j \end{aligned} \right. \end{aligned}$​假设对比的两个序列为A和B，s(a,b)表示字符a和字符b的相似分数，H代表匹配分数矩阵，W1​表示空位罚分。Hij​=max⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​​Hi−1,j−1​+s(Ai​,Bj​)Hi−1,j​−W1​Hi,j−1​−W1​0​​s(ai​,bj​)={​3ifai​=bj−3ifai​​=bj​​​
   得到矩阵后，对H矩阵进行回溯，从H矩阵中最大的数开始回溯。根据回溯路径写出匹配字符串。若回溯到左上角，则将$a_i和b_j$ai​和bj​添加到$A_o和B_o$Ao​和Bo​中；若回顾到左边，则将$“\_”$“_”添加到$A_o$Ao​，将$b_j$bj​添加到$B_o$Bo​；同理，若回顾到上边，则将$“\_”$“_”添加到$B_o$Bo​，将$a_i$ai​添加到$A_o$Ao​；

五和六两种方法的区别：五是找出全局的匹配序列，六是找出局部最匹配的序列。

7. n_gram:比较两个字符串的n_gram中相似的个数（要除以总共的n-gram数目归一化）

---

• Term Based

1. Block Distance: 也就是曼哈顿距离
2. Cosine Similarity: cos相似度
3. Dice’s Coefficient: $2\frac{A\cap B}{|A|+|B|}$2∣A∣+∣B∣A∩B​
4. Euclidean Distance：欧几里得距离
5. Jaccard Similarity: $\frac{A\cap B}{A\cup B}$A∪BA∩B​
6. Matching Coefficient:
7. Overlap Coefficient: 类似于Dice’s distance，不过认为子集也是匹配的

---

Corpus based similarity: 从大规模语料中获取语义相似度

1. Hyperspace Analogue to Language （HAL）: 前提：语义相似的词总是共同出现。基于共现矩阵，A[i,j]代表第i个单词和第j个单词距离的得分，距离越近，则分数越高
2. LSA：隐性语义分析，也就是LSI(隐性语义索引)。其假设是语义相近的两个单词往往会出现在相同的文本片段中。利用SVD进行降维，然后利用cos相似度比较是否相似。
3. Generalized Latent Semantic Analysis(GLSA): 这是LSA的扩展，不仅仅局限在term-documnet矩阵上面，也不仅仅局限在SVD降维的方法上。（应该是比较通用的LSA）
4. Explicit Semantic Analysis(ESA): 矩阵的每一项代表对应term和相应文档的tf-idf值，两个term的相似度用cos来度量。
5. The Cross-language explicit analysis: 将文档表示为独立于语言的向量（具体做法未知）
6. Pointwise mutual information-information retrival: 测定词对之间的相似性，其基本思想是统计两个词语同时出现的概率。$PMI(word1,word2)=log\frac{p(word1 \&word2)}{p(word1)p(word2)}$PMI(word1,word2)=logp(word1)p(word2)p(word1&word2)​ 。
7. Second order pointwise mutual information：是PMI的扩展，其优点在于考虑词语对的邻居。如果词语对存在相同的邻居，即使两个词语没有同时出现过，则也可以测量他们的互信息。
8. Normalized Google distance: 利用谷歌搜索引擎的返回网页对term的相似度进行测量。

$NGD(x,y)=\frac{max(logf(x),logf(y))-logf(x,y)}{logM-min(logf(x),logf(y))}$NGD(x,y)=logM−min(logf(x),logf(y))max(logf(x),logf(y))−logf(x,y)​

其中M代表谷歌搜索引擎的网页池的数量，f(x)代表搜索词向x返回的网页数量。

---

Knowledge based similarity: 用语义网络（semantic networks）中获取的信息测量相似度。例如wordNet就是最常用的semantic wordnet，其实就是一个词典，每个词语可能对应多个语义，每个语义又可能对应多个词语。

具体方法有很多，可以参考wordNet的使用

---

Hybrid Similarity measures: 混合模型，将以上的模型的结果共同作为最后的结果或者参考。

义，每个语义又可能对应多个词语。

具体方法有很多，可以参考wordNet的使用

---