劉永海

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

關(guān)鍵詞：LD算法；字符串相似度；PowerBuilder；源碼

中圖分類(lèi)號(hào)：TP311.52 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2017）03-0140-02

引言

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

1 算法分析

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

編輯距離與最大字符串長(zhǎng)度的比值同字符串的相似度成負(fù)相關(guān)。字符串的相似度定義為。

字符串S，T相似度越高，LD就越小，當(dāng)完全相同時(shí)值最?。?，相似度為100%；當(dāng)完全不同時(shí)值最大，

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

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

公式1：當(dāng)一個(gè)字符串為空時(shí)，LD等于不為空字符串的長(zhǎng)度，即；

公式2：兩個(gè)字符串位置對(duì)調(diào)不影響LD的值，即

；

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

；

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

公式4：時(shí)，；時(shí)，。

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

2 算法實(shí)現(xiàn)

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

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

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

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

3 源代碼

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

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

Int li_1，mALen，mBLen

String ls_tmp，S，T//目標(biāo)字符串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

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

Intli_ret=0

String ls_sql，err_syn，err_crt，new_syn

Datasore ds_1

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

For li_1=1 To mBLen+1//組成SQL語(yǔ)句

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

Next

ls_tmp=Left（ls_tmp，Len（ls_tmp）-1）//去掉最后的逗號(hào)

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)建實(shí)例

//在DataStore中進(jìn)行LD計(jì)算

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

//計(jì)算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）//設(shè)置單元的值

Next

Next

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

4 總結(jié)

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

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

參考文獻(xiàn)

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

[2]黃林晟，鄧志鴻，唐世渭，王文清，陳凌.基于編輯距離的中文組織機(jī)構(gòu)名簡(jiǎn)稱(chēng)-全稱(chēng)匹配算法.山東大學(xué)學(xué)報(bào)（理學(xué)版），2012，47（5）：46-51.

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