基于編輯距離和相似度改進的漢字字符串匹配

邵　清，葉　琨

(上海理工大學 光電信息與計算機工程學院，上海 200093)

?

基于編輯距離和相似度改進的漢字字符串匹配

邵清，葉琨

(上海理工大學 光電信息與計算機工程學院，上海 200093)

為解決中文字符串匹配精度較低的問題，提出了一種基于編輯距離和相似度改進的漢字字符串近似匹配算法，針對漢字字符串特點，使用漢字拼音和五筆編碼計算；通過改進動態規劃算法，能夠有效提高編輯距離的計算準確度以及執行效率；再引入考慮交換問題的歸一化算法，以語義編輯距離與長句長度的比值作為歸一化結果，以此來提高近似匹配算法的準確度。實驗結果表明，改進后算法計算的相似度質量要優于改進前的算法結果，且對提高算法效率和查全率、查準率和時間性能等指標均有明顯改善，證明該算法的可行性和有效性。

編輯距離；相似度；歸一化；中文字符串；近似匹配

隨著信息技術的廣泛應用，作為基礎性研究的字符串匹配面對越來越多的挑戰[1]。從20世紀70年代開始，字符串匹配問題的研究[2]就得到許多學者的關注，并且研究成果已廣泛應用于生物、醫學、犯罪取證等領域。目前，計算字符串相似度的算法有多種，其中編輯距離算法作為常用的字符串相似度求解算法，具有應用廣泛、查找有效和時間復雜度較低等優勢。文獻[3]將整條記錄看作一個字符串，計算兩個字符串的編輯距離，從而判斷兩條記錄的相似匹配程度，但是由于字符串長短不一，可能存在冗余屬性對；……