1、 計算字符串相似度的矩陣算法李彬(武漢理工大學計算機學院湖北武漢430070摘要:用2個字符串滑動比較時匹配的字符數和2字符串滑動比較的重疊率定義了相似度的衡量指標, 在確定一個字符串比另一個字符串少的情況下, 設計了一種算法, 試驗結果表明該算法實現了在字符串匹配矩陣中確定插入空格的位置使相似度指標達到最大值, 并且算法的計算次數也明顯地減少。該算法可以用于信息的模糊檢索。關鍵詞:匹配率; 相似度; 匹配矩陣; 信息量中圖分類號:TP301. 6文獻標識碼:B文章編號:10042373X (2007 242106203Matrix Arithmetic of Computing String

2、s Similar DegreeL I Bin(School of Computer Science ,Wuhan University of Technology ,Wuhan ,430070,China Abstract :The similar degree is defined based on the number of matching chars and the ratio of two strings chars when two strings do comparison during gliding. Designing a the sure the length of o

3、ne string is smaller than another strings and the position of in matrix makes similar degree gain the biggest value ,and the be used for the misty in 2dex of the information.K eywords matrix ;information quantity收稿日期:20072062071引言隨著現代科學技術的發(fā)展, 生物學中的DAN 序列的相似性比較可以用于親子鑒定等, 醫(yī)學中應用病毒基因的相似性來診治疾病。與之相似, 隨著計算

4、機的發(fā)展, 字符串的相似問題也成了計算科學中一個非常重要的問題, 也提出了很多關于字符串匹配和相似度的算法, 現有的計算字符串相似度的方法按照計算所依據的特征的不同, 可以劃分為3種方法:基于字面相似的方法、基于統(tǒng)計關聯的方法、基于語義相似的方法。3種方法各有優(yōu)缺點, 還有人提出了綜合考慮3種方法的多層特征方法1。其中, 基于字面相似的計算方法主要有基于編輯距離的計算方法2和基于相同字或詞的方法3。字符串序列相似度計算在異構數據庫操作、音樂樂譜分析、基因序列分析4、信息檢索等方面有較好的應用。本文通過定義的字符串相似度的衡量指標, 利用匹配矩陣對字符串的相似度進行計算。對于長度不相等的字符串,

5、 通過插入空格的方法使字符串的長度相等, 根據設計的算法確定空格的位置, 使相似度的值達到最大, 可以使模糊檢索的信息更有意義。2計算字符串相似度的算法2. 1構造字符串相似程度的指標給定2個長度相等的任意字符串Str1=“abcddacbcb ”和Str2=“aadaccbddc ”, 對2個字符串在任意的位置比對:a b c d d a c b c ba a d a c c b d d c(字符中間沒有空格 。字符串的長度記為n (這里n =10 , 相同字母(d ,a ,c 的個數記為m (這里m =3 , 兩字符串重疊的個數記為r (這里r =8 。根據上面給出的數據, 這里給出下面的

6、定義:定義1重疊率2個長度相等的(包括在長度短的字符串中加入空格, 使兩個字符串長度相等的情況 字符串在字符串移動匹配的過程中, 重疊字符串的個數與字符串的長度的比率, 即L =r/n 。定義2匹配率2個長度相等的(包括在長度的短的字符串中加入空格, 使其長度相等的情況 字符串在字符串移動匹配的過程中, 對應位置字符相同的個數與字符串長度的比率, 即M =m/n 。定義3相似度匹配率的平方與重疊率的乘積, 即:Q =M 2L =(2n2 n 601軟件技術李彬:計算字符串相似度的矩陣算法 這樣定義相似度是為了在匹配率相同的情況下, 利用重疊率衡量相似度, 同時減小重疊率對相似度的影響, 因為相

7、似度是應該依賴于匹配率的。2. 2算法設計與分析2. 2. 1算法原理鑒于以上相似度指標Q 的定義, 只需要考慮如何使匹配率最大, 這樣就可以得到最大的相似度。如:abcddacbcbaadaccbddc aadaccbddc保持上面的字符串不動, 把下面的字符串自左向右移動, 每到一個位置時計算Q 值, 然后取Q 的最大值。Str1的長度記為n 1, Str2的長度記為n 2, 當Str2的尾字母和Str1的首字母對齊的情況下計算相似度指標為Q 1, Str2右移一位計算的相似度指標為Q 2, 當Str2的首字母和Str1的尾字母對齊的計算相似度指標為Q m (m =n 2+n 1-1 ,

8、然后計算最大相似度Q max =max Q 1, Q 2, , Q m 。2. 2. 2算法實現下面用2個字符串實現具體的算法。字符串S1的長度為n 1, 字符串S2的長度為n 2, 設n 1>n 2, 記S =n 1-n 2; 具體的令S1=“abcddacbcbdadcabbdca ”, S2=“dcabacd ”, 則n 1=20, n 2S1n 1, n 2, S (1 如圖1所示, :圖1匹配圖圖1中橫向(首行 為字符串S1, 縱向(首列 為字符串S2, 矩陣中元素(交叉點 為“1”, 表示相匹配, 否則為“0”(圖1中只表示出非零元素 。矩陣中劃了一些斜線, 斜線所經過的單元

9、格表示S1與S2相匹配的位置和匹配的情況。第一條斜線必須覆蓋字符串S2與S1的前n 2個字母匹配的情況, 依次下去, 一共有S +1條斜線。圖2, 圖3是第1條斜線與第2條斜線的表示的情況, 其余的斜線表示的情況依次類推。用第2條斜線為例說明:如圖3表示S2的首字母和S1的第2個對齊。該斜線經過的單元格有4個元素不為零, 說明有4個元素匹配, 即是有底線的字母。斜線的間距(相鄰的2條斜線的距離為1 表示字符串滑動的距離, 也表示在2個字符串均不動的情況下, 在字符串S2中加入空格所能影響到的距離。如第1條斜線和第2條斜線:從圖2, 圖3中可以看出在S2中加入1個空格, 在移動匹配中只能到第2條

10、斜線所能表示的情況, 依次類推。因此, 在S2中加入的空格數所能達到的最遠匹配可以用斜線的條數來表示。在S2中加入S 個空格, 可以在當前匹配的斜線后再劃S 條斜線。圖2第一條斜線表示的情況圖3第二條斜線表示的情況(2 這里的目的是為了在加入空格后達到最大的匹配率, 因此可以在n 1-n 2+1條斜線中找到1條含非零值最多的路徑, 但要遵循一個原則:路徑的查找必須遵循自左向右的原則, 因為每移動一條斜線相當于插入1個空格, 插入空格以后不能向回匹配只能向后匹配?，F在要解決的問題就是在S +1條斜線中按照自左向右、自上向下的原則找一條含非零值最多的路徑。如圖1所示, 以S1和S2為例說明具體過程

11、, 這里字符串S1有20個字符, 字符串S2有15個字符, 斜線的條數等于2015+1=, R 1R 1的第一行代表左, , 也就是字符是否匹配。按照上面的原則:自左而右、自上而下, 找到一條含“1”最多的路徑。為方便其見, 把“1”換成該行的行號。寫成矩陣R 2。R 1= 01 0002002200020000003330003000300000004440000004050050005555000600000060006060(3 現在需要找到一條含非零值最多的路徑。定義非零值的個數為信息量, 記為I n 。算法準則:因為遵從自左而右、自上而下的原則, 所以第i 行可以包含第i +1行的信

12、息量, 也就是說從第i 行和第i +1行選取部分元素可以使第i 行達到這2行的最大信息量。從矩陣R 2中的倒數第2行反向遞推到第1行, 那么第一行就含有下面所有行的最大信息量, 也就是找到了最優(yōu)路徑。就上面的矩陣R 2進行處理, 用窮舉法兩兩尋找最優(yōu)劃分(選取第i 行左面元素和第i +1行右面的元素達到信息量最大 。以字符串S1和S2為例尋找信息量最大的路徑。701現代電子技術2007年第24期總第263期 嵌入式與單片機 先在倒數第2行取1個元素, 再在倒數第1行取n 2-1個元素(有底線的為所取的數值 :6|, 計算信息量為3;在倒數第2行取2個元素, 再從倒數第1行取n 2-2個元素:6

13、0|, 計算信息量為4;依次窮舉計算, 得到信息量最大的劃分:600000 060006|, 信息量為7;將取得的倒數第2行元素和倒數第3行元素, 重復步驟, , 直到第1行為止。得到所有的劃分結果如圖4所示。4(5 0, 用右下角元素替代右上角元素, 保留左上角元素。如步驟的劃分變?yōu)?600000060006|, 則整個劃分變?yōu)閳D5。(6 在數值增大的地方加入空格, 空格的個數為前后變化的數值的差值(元素零除外 。S2插入空格如圖6所示。(7 計算匹配率為(12/20 2, 重疊率為1, 則Q 15=0. 38。如果插入的空格少于n 1-n 2, 可以依據重疊率較大的情況在字符前或字符后插入

14、。同樣可以計算Q 1, Q 2, ,Q m , 可在其中找到最大值。2. 2. 3算法步驟這里假設字符串S1的長度大于S2的長度, 即n 1>n 2, 記S =n 1-n 2。(1 將字符串S1的字符依次寫成一行, 將字符串S2的字符依次寫成一列, 然后依次比對, 字符相同的記為1, 不同的記為0, 生成矩陣R, 矩陣元素R i , j 表示S2的第i 個元素與S1的第j 個元素是否相同;(2 生成矩陣R 1, R 1的行數等于S +1, 列數等于n 2,R 1i , j =R j , j +i -1;(3 將矩陣R 1的非零元素換成所在行的數字, 生成矩陣R 2。(4 從矩陣R 2倒數

15、第 2行反向遞推到第1行, 那么第1行就含有下面所有行的最大信息量, 也就是找到了最優(yōu)路徑。就上面的矩陣R 2進行處理, 用窮舉法兩兩尋找最優(yōu)劃分(選取第i 行左面元素和第i +1行右面的元素達到信息量最大 。圖5改進的劃分圖圖6相似度最大匹配圖先在R 2的倒數第21個元素, 再在倒數第1行取2-1, 2;1行取n 2-22個元素的信息量;, 得到信息量最大的劃分;對倒數第2行元素和倒數第3行, 重復步驟(1 ,(2 , (3 直到第一行為止;將劃分的右上角元素置零, 將右下角元素替代右上角元素, 保留左上角元素;取得整個劃分, 在數值增大的地方加入空格, 空格的個數為前后變化的數值的差值(元

16、素0除外 。2. 2. 4算法性能分析下面按照一般的算法分析對此算法進行分析5。(1 構造匹配矩陣為:n 1×n 2;(2 進行移動匹配的次數為:n 1+n 2-1; (3 構造尋優(yōu)路徑矩陣:(n 1-n 2+1 ×n 1; (4 尋找最優(yōu)路徑計算Q :n 1×(n 1-n 2 ; (5 尋找最大的Q 值。算法的空間效率為:n 1×n 2+(n 1-n 2+1 ×n 1+2×n 1+n 2-2; 算法的計算次數為:(n 1+n 2-1 ×n 1×(n 1-n 2 ; 算法的計算次數比窮舉法C n 1-n 2n 1+

17、1的次數減少了很多,如文中的例子, 利用窮舉法是O (n 15 , 當然如果n 1-n 2再增大的話, 其會更大, 因為窮舉法的次數是O (n 1(n 1-n 2。本文中的算法的計算次數是O (n 12 。特別的, 當n 1=n 2時, 就不必進行這樣的計算, 只需要進行移動匹配就可以。3結語文中用2個字符串滑動比較時匹配的字符數和2字符串滑動比較的重疊率定義了相似度的衡量指標, 在確定(下轉第111頁 801軟件技術李彬:計算字符串相似度的矩陣算法 中斷服務子程序DDFS 2isr :movccap4h ,Data ; 輸出新數據到DAC clr ccf3; 清中斷標志inc ccap3h

18、clr ea ; 關中斷push acc push psw push dph push dpl ; 一次相位累加運算mov a ,pLadd a ,Phase 2accL mov phase 2accL ,a mov a ,p Haddc a ,Phase_accHmov phase 2acc H ,a ; 查找L U Tmov d #Sin Tab ; PWM =sine (hi (Phase_Acc movc a , a +dptr ; 增益調整mov b ,a mov a , G mul ab ; 輸出數據mov Data ,a pop dpl pop dph pop psw pop a

19、cc setb ea reti正弦波L Urr , 共16行256個, 由其他程序離線產生并以下述形式插入此源程序中。sintab :DB080H ,083H ,086H ,089H ,08CH ,090H ,093H , 096H DB 099H ,09CH ,09F H ,0A2H ,0A5H ,0A8H ,0AB H ,0A EH DB 067H ,06A H ,06D H ,070H ,074H ,077H ,07A H ,07D H End5結語基于DDFS 的變頻控制方法, 并以MCS 51系列單片機為例, 介紹了這種方法的具體實現。這種方法解決了分頻方法存在的精度低、頻率頻進不均

20、勻等問題, 并抑制了噪聲。這種變頻控制方法可廣泛用于變頻調速等各種變頻控制系統(tǒng)。參考文獻1張岳勻, 謝運祥, 何志偉. 交流傳動系統(tǒng)PWM 技術的近期發(fā)展及展望J.微電機,1999,32(1 :28231.2王力, , 彭星明. SPWM 變頻調速系.作者簡介崔樹清男, , 講師, 計算機控制技術。(上接第105頁的數據源; 將所需要查看和分析的維度和數據拖入Excel 電子表格中, 按行與列拖動維度可分析數據。3結語數據集市的建立可以充分地利用這些油礦勘探數據。靈活地分析大量勘探數據, 可在更大程度上滿足高層次決策分析的需求。通過油礦勘探數據集市的應用, 發(fā)現雖然圍繞數據獲取的很多復雜問題并

21、沒有減少, 但是基于多維模型的數據集市易于開發(fā)和使用, 建設效率高, 具有傳統(tǒng)數據組織結構沒有的優(yōu)點。參考文獻1Inmin W H. Building the Data Warehouse M .New Y ork :John Wiley &Sons,1996.2Ralph K imball , The Data Warehouse Lifecycle Toolkit. 3邵紅全, 趙茜. 運用多維數據模型實現數據集市J.河北省科學院學報,2003(2 :992102.作者簡介孫吉赟男,1982年出生, 浙江杭州人, 碩士研究生。研究方向為管理信息系統(tǒng)與計算機網絡、數據庫、數據倉庫。楊兆進男,1969年出生, 山東膠州人, 工程師, 應