昨兒突發(fā)奇想，想做一個(gè)關(guān)于英文單詞按“形近詞”分組的app，這個(gè)app最關(guān)鍵的就是這個(gè)“形近詞”判斷，經(jīng)過(guò)思考和查資料，開(kāi)始有了些眉目，看到了visionfans寫(xiě)的博客使用Matlab實(shí)現(xiàn)英文單詞的"形近詞"查找（http://blog.csdn.net/visionfans/article/details/6618652）就參照他的把算法用java實(shí)現(xiàn)了一下，效果出來(lái)了，但是很擔(dān)心整個(gè)算法的效率問(wèn)題，剛剛接觸，對(duì)算法效率了解的甚少，還請(qǐng)大牛指點(diǎn)。

這個(gè)對(duì)兩個(gè)單詞“形近度”的判別是建立在一個(gè)矩陣上的，以本文為例，將兩個(gè)單詞存儲(chǔ)在兩個(gè)數(shù)組s1,s2中，然后根據(jù)兩個(gè)數(shù)組的長(zhǎng)度建立一個(gè)s2.length行s1.length列的矩陣，并將矩陣初始化，如圖

下一步就是按照算法將這個(gè)矩陣中的數(shù)值填入，再填入之前，為了比較的時(shí)候方便，我們?cè)谶@個(gè)矩陣外圍把存在數(shù)組中的值加上，注意，僅僅是為了理解方便，真正的數(shù)組矩陣中不添加這一項(xiàng)，如下圖藍(lán)色區(qū)域：

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

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

自己寫(xiě)了一個(gè)Java版的算法如下：

package englishword;public class Ledit {public static void main(String[] args) {char[] s1={'a','r','i','m'}; //預(yù)置單詞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;}//算法開(kāi)始，向矩陣中添加數(shù)值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;} }

在理解了這個(gè)算法的運(yùn)用時(shí)，遇到了一個(gè)疑問(wèn)，就是這些矩陣中的每一個(gè)數(shù)字代表了什么，尤其是給矩陣初始化時(shí)填充的數(shù)字的用途。后來(lái)想到了一種解釋，分享一下，如有錯(cuò)誤歡迎指正。

我認(rèn)為，矩陣的初始化的數(shù)字相當(dāng)于標(biāo)記了每個(gè)單詞的位置，每個(gè)字母與同詞的其他字母的相對(duì)位置是不變的，這個(gè)位置有什么用呢，我認(rèn)為兩個(gè)單詞的編輯距離有2個(gè)分類(lèi)，一個(gè)是相同位置但是字母不一樣，需要一次編輯，另一個(gè)是相同字母不同位置，也需要一次編輯。

這里關(guān)于+1或者+temp我還沒(méi)有研究出來(lái)，只是猜想的是字母匹配成功所要付出的代價(jià)“移位”、“插入”所需要的編輯次數(shù)，只是還沒(méi)有研究明白，希望可以得到指點(diǎn)。萬(wàn)分感謝。

總結(jié)

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

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。