昨兒突發奇想，想做一個關于英文單詞按“形近詞”分組的app，這個app最關鍵的就是這個“形近詞”判斷，經過思考和查資料，開始有了些眉目，看到了visionfans寫的博客使用Matlab實現英文單詞的"形近詞"查找（http://blog.csdn.net/visionfans/article/details/6618652）就參照他的把算法用java實現了一下，效果出來了，但是很擔心整個算法的效率問題，剛剛接觸，對算法效率了解的甚少，還請大牛指點。

這個對兩個單詞“形近度”的判別是建立在一個矩陣上的，以本文為例，將兩個單詞存儲在兩個數組s1,s2中，然后根據兩個數組的長度建立一個s2.length行s1.length列的矩陣，并將矩陣初始化，如圖

下一步就是按照算法將這個矩陣中的數值填入，再填入之前，為了比較的時候方便，我們在這個矩陣外圍把存在數組中的值加上，注意，僅僅是為了理解方便，真正的數組矩陣中不添加這一項，如下圖藍色區域：

比較過程：我們以橙色區域的數字為編號，“0”的坐標為（0,0）以此類推左上角第一個白色方塊坐標為（1,1）……按咧進行匹配（即先將“a”分別同這一列的"s","a","r","r","n"進行比較，然后再以此向右進行）如果第一個單詞的第一個字母（本例中的"a"）與第二個單詞的第一個字母（本例中的"s"）相同，則定義的temp變量的值賦“0”否則賦“1”，然后這兩個字母交集的區域（本例中坐標為（1,1））的數值取與之相鄰的左，上，左上分別+1,+1,+temp如圖：

然后向這三個值中的最小值賦給空白區域，作為其數值，按照這個方式把整個矩陣填滿，然后矩陣中最后一個元素即最右下角的元素的數組就是兩個單詞的編輯距離也就是“區別度”，這個是指一個字符串A需要經過多少次編輯可以得到字符串B。

自己寫了一個Java版的算法如下：

package englishword;public class Ledit {public static void main(String[] args) {char[] s1={'a','r','i','m'}; //預置單詞char[] s2={'s','a','r','r','n'};int m=s2.length+1,n=s1.length+1; //矩陣int[][] table=new int[m][n];// 矩陣的初始化for(int i=0;i<n;i++){ table[0][i]=i;}for(int i=0;i<m;i++){table[i][0]=i;}//算法開始，向矩陣中添加數值for(int i=0;i<n-1;i++){for(int j=0;j<m-1;j++){int temp=0;if(s1[i]!= s2[j])temp=1;elsetemp=0;table[j+1][i+1]=Min(table[j][i]+temp,table[j+1][i]+1,table[j][i+1]+1);}}//輸出矩陣for(int i=0;i<m;i++){for(int j=0;j<n;j++){System.out.print(table[i][j]);System.out.print(",");}System.out.println();}}private static int Min(int i, int j, int k) {// TODO Auto-generated method stubint[] tempSequence={i,j,k};int min=i;for(int n=0;n<3;n++){if(tempSequence[n]<min){min=tempSequence[n];}}return min;} }

在理解了這個算法的運用時，遇到了一個疑問，就是這些矩陣中的每一個數字代表了什么，尤其是給矩陣初始化時填充的數字的用途。后來想到了一種解釋，分享一下，如有錯誤歡迎指正。

我認為，矩陣的初始化的數字相當于標記了每個單詞的位置，每個字母與同詞的其他字母的相對位置是不變的，這個位置有什么用呢，我認為兩個單詞的編輯距離有2個分類，一個是相同位置但是字母不一樣，需要一次編輯，另一個是相同字母不同位置，也需要一次編輯。

這里關于+1或者+temp我還沒有研究出來，只是猜想的是字母匹配成功所要付出的代價“移位”、“插入”所需要的編輯次數，只是還沒有研究明白，希望可以得到指點。萬分感謝。

總結

以上是生活随笔為你收集整理的Levenshtein Distance算法java实现，英文单词相似度的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。