浅谈文本的相似度问题
今天要研究的問題是如何計算兩個文本的相似度。正如上篇文章描述，計算文本的相似度在工程中有著重要的應用，
比如文本去重，搜索引擎網頁判重，論文的反抄襲，ACM競賽中反作弊等等。
?
上篇文章介紹的SimHash算法是比較優秀的文檔判重算法，它能處理海量文本的判重，Google搜索引擎也正是用這
個算法來處理網頁的重復問題。實際上，僅拿文本的相似度計算來說，有很多算法都能解決這個問題，并且都達到比
較滿意的效果。最常見的幾種方法如下
?
?? （1）基于最長公共子串
?? （2）基于最長公共子序列
?? （3）基于最少編輯距離
?? （4）基于海明距離
?? （5）基于余弦值
?? （6）基于Jaccard相似度
?
由于前2種方法很經典，在實際中也用得不多，就不用多講了。接下來主要介紹后面4種方法。
?
首先來研究基于最少編輯距離的方法。最少編輯距離是這樣定義的：指兩個字符串之間，由一個轉化為另一個所需
要的最少編輯操作次數，允許的操作包括3種：將一個字符替換為另一個字符；插入一個字符；刪除一個字符。
?
比如將kitten轉換為sitting，則進行如下3步操作
?
??? sitten? （k -> s）
??? sittin? （e -> i）
??? sitting （? + g?）
?
所以kitten與sitting的最少編輯距離就是3。編輯距離又稱Levenshtein距離，也叫做Edit Distance，是俄
羅斯科學家Vladimir Levenshtein在1965年提出的。編程之美上的字符串相似度問題實際上就是求最少編輯距
離問題。
?
那么，如何求兩個字符串的最少編輯距離？很明顯這是一個DP問題，設表示字符串和字符串
的最少編輯距離，那么狀態轉移方程如下
?
???????
?
初始化為
?
代碼：
#include <iostream> #include <string.h> #include <stdio.h>using namespace std; const int N = 1005;int dp[N][N]; char S[N],T[N];int Lenv(char S[],char T[]) {int n = strlen(S);int m = strlen(T);for(int i=0; i<=n; i++)dp[i][0] = i;for(int i=0; i<=m; i++)dp[0][i] = i;for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + 1;if(S[i-1] == T[j-1])dp[i][j] = min(dp[i][j],dp[i-1][j-1]);elsedp[i][j] = min(dp[i][j],dp[i-1][j-1] + 1);}}return dp[n][m]; }int main() {while(scanf("%s%s",S,T)!=EOF)printf("%d\n",Lenv(S,T));return 0; }
計算出兩個文本的最少編輯距離之后，如果這個數字越小，那么說明這兩篇文章越相似，但是很明顯，通過這種方法
計算的時間復雜度為，而且需要兩兩進行計算，所以只適合處理小數據的文本。
?
對于基于海明距離的文本處理方法，有比較優秀的SimHash算法，上篇文章已經介紹過，不再贅述。
?
接下來研究基于余弦值的方法，其實基于余弦值的方法是依賴于向量空間模型的，它是先把文本進行分詞，提取特征
向量，得到一個N維的文本向量，然后統計每個詞在文中出現次數，把這個次數作為這個詞的權值，某個詞出現次數
越多，表示它越重要，得到的權值向量用表示。
?
如果要計算兩個文本的相似度，那么應該先得到它們的權值向量和，進而相似度為
?
????????
?
所以基于余弦值的相似度計算步驟大致如下
?
???
?
基于Jaccard相似度的度量也是先得到文本向量，這個向量可以看成是詞的集合，那么兩個集合之間的Jaccard相
似度等于交集大小與并集大小的比例。公式如下
?
???????
?
當然在實際處理中計算交集與并集可以用紅黑樹等數據結構，在C++中直接可以考慮用set集合容器處理。
?
總結
以上是生活随笔為你收集整理的浅谈文本的相似度问题的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 组合数取模终极版
- 下一篇： SVD原理及其应用导论