劉永海

摘要：最小編輯距離能直接反映兩個字符串的相似程度，而字符串的相似度比較在數(shù)據(jù)挖掘和數(shù)據(jù)查詢方面多有應用。通過相似度比對，可更自動化地整理、規(guī)范文本，提高信息模糊查詢的命中率。本文詳細介紹了“LD”算法的原理，并完成了PowerBuilder環(huán)境下的具體編碼。

關鍵詞：LD算法；字符串相似度；PowerBuilder；源碼

中圖分類號：TP311.52 文獻標識碼：A 文章編號：1007-9416（2017）03-0140-02

引言

在數(shù)據(jù)挖掘中，經(jīng)常需要分類整理相似字符串；在模糊檢索、文本智能糾錯等方面也要進行字符串相似度比對。常見的算法包括編輯距離、最長公共子串、RKR-GST等算法。本文介紹了最小編輯距離算法（下稱LD算法）在PowerBuilder環(huán)境中的實現(xiàn)。

1 算法分析

最小編輯距離算法最早是由俄羅斯科學家Levenshtein提出，因此也稱“LD”算法。該算法是計算兩個字符串之間，將一個字符串通過替換、插入、刪除等方式轉變?yōu)榱硪粋€字符串所需要的最少步驟數(shù)。如將“青島市衛(wèi)計委”轉變?yōu)椤扒鄭u衛(wèi)生局”的編輯距離是3。本文中，字符串S、T的最小編輯距離用表示。（見表1）

編輯距離與最大字符串長度的比值同字符串的相似度成負相關。字符串的相似度定義為。

字符串S，T相似度越高，LD就越小，當完全相同時值最?。海嗨贫葹?00%；當完全不同時值最大，

，相似度為0%。因此，。

根據(jù)LD的原理，存在如下公式：

公式1：當一個字符串為空時，LD等于不為空字符串的長度，即；

公式2：兩個字符串位置對調不影響LD的值，即

；

公式3：同時在兩個字符串的“頭”或“尾”部連接相同的字符串，其LD不變，即

；

設S由組成，T由組成，長度分別為n和m。當S或T某一個為空時，根據(jù)公式1可計算LD值。當S和T都不為空時，引入i和k做為S和T的下標變量，取值范圍是。子字符串。若字符元素，依據(jù)公式3，子字符串；若，取增加、刪除和修改三種方式的最小LD值加1，由此得出：

公式4：時，；時，。

運用公式4，將i和k從1分別計算至n和m后，即可求出。

2 算法實現(xiàn)

根據(jù)上述分析，應構造矩陣進行計算。舉例說明，設S=“青島市衛(wèi)計委”，T=“青島衛(wèi)生局”，構造矩陣如下：

上圖將S和T字符串分別作為矩陣的列和行。其中，第一行是T為空時，的值；第一列是S為空時，的值。按照算法，首先計算，由于“青”字相同，因此

，將值填入對應位置；再計算，可以看到，，在圖中可以看出，分別是的“上側”、“左側”和“左上側”的值。這時最小值是0，因此，將值填入矩陣…；以此類推，計算完成整個矩陣后最右下角的數(shù)據(jù)即為的值。

上例。字符串的相似度為。

3 源代碼

構建計算矩陣一般使用數(shù)組實現(xiàn)。在PB中選用了特有的DataStore對象來實現(xiàn)。DataStore是PB中特有的數(shù)據(jù)容器，它數(shù)據(jù)操控方便，代碼維護量小，又是非可視對象，占用資源少，效率更高。具體算法如下：

//切分字符串為字符元素

Int li_1，mALen，mBLen

String ls_tmp，S，T//目標字符串S，T

Char mCharA[]，mCharB[]

If Len（S）

ls_tmp=S；S=T；T=ls_tmp；

End If

For li_1=1 TomALen

mCharA[li_1]=Mid（S，li_1，1）

Next

For li_1=1 TomBLen

mCharB[li_1]=Mid（T，li_1，1）

Next

//動態(tài)創(chuàng)建數(shù)據(jù)存儲

Intli_ret=0

String ls_sql，err_syn，err_crt，new_syn

Datasore ds_1

ds_1=Create Datasore //創(chuàng)建實例

For li_1=1 To mBLen+1//組成SQL語句

ls_tmp=ls_tmp+0 as col+String（li_1）+，

Next

ls_tmp=Left（ls_tmp，Len（ls_tmp）-1）//去掉最后的逗號

ls_sql=Select + ls_tmp+From dual//Oracle用法

new_syn=sqlca.SyntaxFromSQL（ls_sql，style（type=grid），err_syn）

ds_1.Create（new_syn，err_crt）//創(chuàng)建實例

//在DataStore中進行LD計算

Long ll_row

Integer li_2，li_zs，li_left，ls_top，li_tmp

Dec ld_ret

ds_1.InsertRow（0）//新增第一行，填充0，1，2…

For li_1=1 TomBLen+1

ds_1.SetItem（1，li_1，li_1-1）

Next

For li_1=1 to mALen

ll_row=ds_1.InsertRow（0）//填充第一列數(shù)據(jù)

ds_1.SetItem（ll_row，1，li_1）

Next

//計算LD

For li_1=1 TomBLen

For li_2=1 TomALen

li_zs=ds_1.GetItemNumber（li_2，li_1）

If mCharB[li_1]<>mCharA[li_2] Thenli_zs++

li_left=ds_1.GetItemNumber（li_2+1，li_1）+1

li_top=ds_1.GetItemNumber（li_2，li_1+1）+1

li_tmp=Min（li_zs，li_left）//Min只能兩兩比較

li_tmp=Min（li_tmp，li_top）

ds_1.SetItem（li_2+1，li_1+1，li_tmp）//設置單元的值

Next

Next

ld_ret=1-li_tmp*1.0/mALen//得到相似度

4 總結

基于LD的字符串相似度算法實現(xiàn)比較簡單。在對比短長度的字符串時，其空間復雜度低，具有良好的實時性。測試表明，在普通PC機中PowerBuilder編寫的LD算法執(zhí)行速度達到200～300對/秒（字符串長度在5～20之間）。在進行中文機構名稱和簡稱模糊匹配時，命中率接近80%。

但該算法也有明顯缺陷，它無語義關聯(lián)。例如進行“青島市衛(wèi)計委”、“青島衛(wèi)生局”、“青島市統(tǒng)計局”機構名稱匹配時，就得不到正確結果。因此，后期改進時，應考慮加入語義解析，比如用“分詞”技術先拆分成詞組，再用分詞字典對詞進行標準化轉換后再計算相似度時就可以得到正確結果。

參考文獻

[1]杜軍強，楊波.云計算中加密數(shù)據(jù)的模糊關鍵字搜索方法.計算機工程與應用，2015，51（5）：146-152.

[2]黃林晟，鄧志鴻，唐世渭，王文清，陳凌.基于編輯距離的中文組織機構名簡稱-全稱匹配算法.山東大學學報（理學版），2012，47（5）：46-51.

[3]米琳.基于q-gram的字符串相似性查詢研究.現(xiàn)代計算機，2014（4）：12-16.