字符串相似度

1、計(jì)算字符串相似度的矩陣算法李彬（武漢理工大學(xué)計(jì)算機(jī)學(xué)院 武漢 430070）摘 要：用兩個(gè)字符串滑動(dòng)比較時(shí)匹配的字符數(shù)和兩字符串滑動(dòng)比較的重疊率定義了相似度的衡量指標(biāo)，在確定一個(gè)字符串較另一個(gè)字符串較少的情況下，設(shè)計(jì)了一種算法，實(shí)現(xiàn)了在字符串匹配矩陣中確定插入空格的位置使相似度指標(biāo)達(dá)到最大值，可以用于信息的模糊檢索。關(guān)鍵詞：匹配率；相似度；匹配矩陣；信息量中圖法分類號(hào)：TP301.6 The Matrix Arithmetic of Computing Strings' Similar Degree LI Bin （ Department Of Computer Of Wuhan Un

2、iversity of Technology Wuhan 430070 China）Abstract：The similar degree is defined based on the number of matching chars and the overlaping ratio of two strings chars when two strings do comparison during gliding.Designing a arithmetic under the sistuation that making sure the length of one string is

3、smaller than another strings and makeing sure the position of inserting blank space in strings matching matrix makes similar degree gain the biggest value，this arithmetic can used for the misty index of the information.Key Words: Matching Ratio；Similar Degree；Matching Matrix；Information Quantity1引言隨

4、著現(xiàn)代科學(xué)技術(shù)的發(fā)展，生物學(xué)中的DAN序列的相似性的比較可以用于親子鑒定等，醫(yī)學(xué)中應(yīng)用病毒基因的相似性來(lái)診治疾病。與之相似，隨著計(jì)算機(jī)的發(fā)展，字符串的相似問題也成了計(jì)算科學(xué)中一個(gè)非常重要的問題，也提出了很多關(guān)于字符串匹配和相似度的算法，現(xiàn)有的計(jì)算字符串相似度的方法按照計(jì)算所依據(jù)的特征的不同,可以劃分為三種方法:基于字面相似的方法、基于統(tǒng)計(jì)關(guān)聯(lián)的方法、基于語(yǔ)義相似的方法。三種方法各有優(yōu)缺點(diǎn)，還有人提出了綜合考慮三種方法的多層特征方法2。其中,基于字面相似的計(jì)算方法主要有基于編輯距離的計(jì)算方法 3和基于相同字或詞的方法 4。字符串序列相似度計(jì)算在異構(gòu)數(shù)據(jù)庫(kù)操作、音樂樂譜分析、基因序列分析1，信息檢

5、索等方面有較好的應(yīng)用。本文通過(guò)定義的字符串相似度的衡量指標(biāo)，利用匹配矩陣對(duì)字符串的相似度進(jìn)行計(jì)算。對(duì)于長(zhǎng)度不相等的字符串，通過(guò)插入空格的方法使字符串的長(zhǎng)度相等，根據(jù)設(shè)計(jì)的算法確定空格的位置，使相似度的值達(dá)到最大，可以使模糊檢索的信息更有意義。2計(jì)算字符串相似度的算法.構(gòu)造字符串相似程度的指標(biāo)給定兩個(gè)長(zhǎng)度相等的任意字符串Str1=“abcddacbcb”和Str2=“aadaccbddc”，對(duì)兩個(gè)字符串在任意的位置比對(duì)： （字符中間沒有空格）。字符串的長(zhǎng)度記為n（這里n=10），相同字母(d、a、c)的個(gè)數(shù)記為m(這里m=3)，兩字符串重疊的個(gè)數(shù)記為r(這里r=8)。根據(jù)上面給出的數(shù)據(jù)，我們給出

6、下面的定義： 定義1重疊率 兩個(gè)長(zhǎng)度相等的（包括在長(zhǎng)度的短的字符串中加入空格，使其長(zhǎng)度相等的情況）字符串在字符串移動(dòng)匹配的過(guò)程中，重疊字符串的個(gè)數(shù)與字符串的長(zhǎng)度的比率，即。 定義2 匹配率 兩個(gè)長(zhǎng)度相等的（包括在長(zhǎng)度的短的字符串中加入空格，使其長(zhǎng)度相等的情況）字符串在字符串移動(dòng)匹配的過(guò)程中，對(duì)應(yīng)位置字符相同的個(gè)數(shù)與字符串長(zhǎng)度的比率，即。 定義3 相似度 匹配率的平方與重疊率的乘積，即。這樣定義相似度的目的是為了在匹配率相同的情況下，利用重疊率衡量相似度，同時(shí)減小重疊率對(duì)相似度的影響，因?yàn)橄嗨贫仁菓?yīng)該依賴于匹配率的。.算法設(shè)計(jì)與分析.算法原理鑒于以上相似度指標(biāo)Q的定義，我們只要考慮如何使匹配率最

7、大，這樣就可以得到最大的相似度。如，我們保持上面的字符串不動(dòng)，把下面的字符串自左向右移動(dòng)，每到一個(gè)位置時(shí)計(jì)算Q值，然后取Q的最大值。Str1的長(zhǎng)度記為n1，Str2的長(zhǎng)度記為n2，當(dāng)Str2的尾字母和Str1的首字母對(duì)齊的情況下計(jì)算相似度指標(biāo)為Q1，Str2右移一位計(jì)算的相似度指標(biāo)為Q2，當(dāng)Str2的首字母和Str1的尾字母對(duì)齊的情況下計(jì)算相似度指標(biāo)為Qm(m=n2+n1-1)，然后計(jì)算最大相似度Qmax=maxQ1、Q2、Qm。.算法實(shí)現(xiàn)下面我們用兩個(gè)字符串實(shí)現(xiàn)具體的算法。字符串S1的長(zhǎng)度為n1，字符串S2的長(zhǎng)度為n2，設(shè)n1>n2，記S=n1-n2；具體的令S1=“abcddacbc

8、bdadcabbdca”,S2=“aadaccbddcabacd”，則n1=20，n2=15，S=5。下面所用的S1，S2，n1，n2，S都與這里的設(shè)置一致。（） 如圖1所示，我們將兩個(gè)字符串按如下方式填寫： 圖1 匹 配 圖圖中橫向(首行)為字符串S1，縱向(首列)為字符串S2，矩陣中元素 (交叉點(diǎn))為1，表示相匹配，否則為0(圖中只表示出非零元素)。矩陣中劃了一些斜線，斜線所經(jīng)過(guò)的單元格表示S1與S2相匹配的位置和匹配的情況。第一條斜線必須覆蓋字符串S2與S1的前n2個(gè)字母匹配的情況，依次下去，一共有S條斜線。下面的圖2，圖3表示的是第一條斜線與第二條斜線的表示的情況，其余的斜線表示的情況

9、依次類推。 圖2 第一條斜線表示的情況 圖3 第二條斜線表示的情況拿第二條斜線說(shuō)明一下：如圖3表示S2的首字母和S1的第二個(gè)對(duì)齊。該斜線經(jīng)過(guò)的單元格有四個(gè)元素不為零，說(shuō)明有四個(gè)元素匹配，即是有底線的字母。斜線的間距（相鄰的兩條斜線的距離為）表示字符串滑動(dòng)的距離，也表示在兩個(gè)字符串均不動(dòng)的情況下，在字符串S2中加入空格所能影響到的距離。如第一條斜線和第二條斜線：從上面圖2，圖3中可以看出在S2中加入一個(gè)空格，在移動(dòng)匹配中只能到第二條斜線所能表示的情況，依次類推。因此，在S2中加入的空格數(shù)所能達(dá)到的最遠(yuǎn)匹配可以用斜線的條數(shù)來(lái)表示。在S2中加入S個(gè)空格，可以在當(dāng)前匹配的斜線后再劃S條斜線。（）我們的

10、目的是為了在加入空格后達(dá)到最大的匹配率，因此可以在n1 -n2+1條斜線中找到一條含非零值最多的路徑，但要遵循一個(gè)原則：路徑的查找必須遵循自左向右的原則，因?yàn)槊恳苿?dòng)一條斜線相當(dāng)于插入一個(gè)空格，插入空格以后不能向回匹配只能向后匹配。現(xiàn)在我們要解決的問題就是在S+1條斜線中按照自左向右、自上向下的原則找一條含非零值最多的路徑。如圖1所示，我們以S1和S2為例說(shuō)明一下具體過(guò)程，這里字符串S1有20個(gè)字符，字符串S2有15個(gè)字符，斜線的條數(shù)等于20-15+1=6。這里我們將斜線覆蓋的范圍為轉(zhuǎn)化為矩陣的形式，我們把他寫成矩陣R1。矩陣R1的第一行代表左邊第一條斜線，依次類推。矩陣元素表示斜線經(jīng)過(guò)的單元格

11、中的數(shù)值，也就是字符是否匹配。按照上面的原則：自左而右、自上而下，找到一條含1最多的路徑。為方便其見，我們把1換成該行的行號(hào)。寫成矩陣R2。（）我們現(xiàn)在就需要找到一條含非零值最多的路徑。我們定義非零值的個(gè)數(shù)為信息量，記為In。算法準(zhǔn)則：因?yàn)樽駨淖宰蠖摇⒆陨隙碌脑瓌t，所以第i行可以包含第i+1行的信息量，也就是說(shuō)從第i行和第i+1行選取部分元素可以使第i行達(dá)到這兩行的最大信息量。我們從矩陣R2倒數(shù)第二行反向遞推到第一行，那么第一行就含有下面所有行的最大信息量，也就是找到了最優(yōu)路徑。下面就上面的矩陣R2進(jìn)行處理，用窮舉法兩兩尋找最優(yōu)劃分(選取第i行左面元素和第i+1行右面的元素達(dá)到信息量最大)

12、。下面就以字符串S1和S2為例尋找信息量最大的路徑。、先在倒數(shù)第二行取一個(gè)元素，再在倒數(shù)第一行取n2-1個(gè)元素（有底線的為所取的數(shù)值），計(jì)算信息量為3；、在倒數(shù)第二行取兩個(gè)元素，再在倒數(shù)第一行取n2-2個(gè)元素，計(jì)算信息量為；、依次窮舉計(jì)算，得到信息量最大的劃分： ，信息量為； 、將取得的倒數(shù)第二行元素和倒數(shù)第三行，重復(fù)步驟、，直到第一行為止。得到所有的劃分結(jié)果為圖4： 圖4劃分圖圖5改進(jìn)的劃分圖e、將劃分的右上角元素置零，將右下角元素替代右上角元素，保留左上角元素。比如步驟的劃分變?yōu)椋?，則整個(gè)劃分變?yōu)閳D5。、在數(shù)值增大的地方加入空格，空格的個(gè)數(shù)為前后變化的數(shù)值的差值，(元素零除外)。S2插入空

13、格如圖所示。 圖6相似度最大匹配圖、計(jì)算匹配率為（12/20）2，重疊率為1，則Q15=0.38。如果插入的空格少于n1-n2，可以依據(jù)重疊率較大的情況在字符前或字符后插入。同樣可以計(jì)算Q1、Q2Qm,在其中找到最大值。. 算法步驟這里我們假設(shè)字符串s1的長(zhǎng)度大于s2的長(zhǎng)度，即n1>n2，記S=n1-n2。第一步：將字符串s1的字符依次寫成一行，將字符串s2的字符依次寫成一列，然后依次比對(duì)，字符相同的就記為1，不同的就記為0，生成矩陣R，矩陣元素Ri，j表示s2的第i個(gè)元素與s1的第j個(gè)元素是否相同；第二步：生成矩陣R1，R1的行數(shù)等于S+1，列數(shù)等于n2，R1i，j=Rj，j+i-1；

14、第三步：將矩陣R1的非零元素?fù)Q成所在行的數(shù)字，生成矩陣R2。第四步： 從矩陣R2倒數(shù)第二行反向遞推到第一行，那么第一行就含有下面所有行的最大信息量，也就是找到了最優(yōu)路徑。下面就上面的矩陣R2進(jìn)行處理，用窮舉法兩兩尋找最優(yōu)劃分(選取第i行左面元素和第i+1行右面的元素達(dá)到信息量最大)。、先在R2的倒數(shù)第二行取一個(gè)元素，再在倒數(shù)第一行取n2-1個(gè)元素，計(jì)算這n2個(gè)元素的信息量；、在倒數(shù)第二行取兩個(gè)元素，再在倒數(shù)第一行取n2-2個(gè)元素，同樣計(jì)算這n2個(gè)元素的信息量；、依次窮舉計(jì)算，得到信息量最大的劃分；、對(duì)倒數(shù)第二行元素和倒數(shù)第三行，重復(fù)步驟、，直到第一行為止；e 、將劃分的右上角元素置零，將右下角

15、元素替代右上角元素，保留左上角元素；、取得整個(gè)劃分，在數(shù)值增大的地方加入空格，空格的個(gè)數(shù)為前后變化的數(shù)值的差值，(元素零除外)。.4算法性能分析 下面按照一般的算法分析對(duì)此算法進(jìn)行分析5。（1）構(gòu)造匹配矩陣為：n1*n2（2）進(jìn)行移動(dòng)匹配的次數(shù)為: n1+n2-1（3）構(gòu)造尋優(yōu)路徑矩陣：(n1-n2+1)*n1（4）尋找最優(yōu)路徑計(jì)算Q：n1*(n1-n2)（5）尋找最大的Q值。算法的空間效率為：n1*n2+(n1-n2+1)*n1+2*n1+n2-2算法的計(jì)算次數(shù)為：(n1+n2-1)*n1*(n1-n2) 算法的計(jì)算次數(shù)比窮舉法的次數(shù)減少了很多，像文中的例子，利用窮舉法是O()，當(dāng)然如果再增

16、大的話，會(huì)更大，因?yàn)楦F舉法的次數(shù)是O()。本文中的算法的計(jì)算次數(shù)是O()。特別的，當(dāng)時(shí)，就不必進(jìn)行這樣的計(jì)算，只需要進(jìn)行移動(dòng)匹配就可以了。 3結(jié)論 文中用兩個(gè)字符串滑動(dòng)比較時(shí)匹配的字符數(shù)和兩字符串滑動(dòng)比較的重疊率定義了相似度的衡量指標(biāo)，在確定一個(gè)字符串較另一個(gè)字符串較少的情況下，設(shè)計(jì)了一種算法，實(shí)現(xiàn)了在字符串匹配矩陣中確定插入空格的位置使相似度指標(biāo)達(dá)到最大值，算法的計(jì)算次數(shù)明顯的減少了，可以使模糊信息檢索高效有意義。參考文獻(xiàn)1孫嘯,陸祖宏,謝建明.生物信息學(xué)基礎(chǔ)M.清華大學(xué)出版社,2005.2章成志.基于多層特征的字符串相似度計(jì)算模型J.情報(bào)學(xué)報(bào)2005 ,24(6):696-701.3Monge AE , Elkan CP. The field2matching problem: algorithm and applications. In : Proceedings of the Second Internet Conference on Knowledge Discovery and Data Mining ,Oregon , Portland , 1996 , 8:26