一種基于PowerBuilder環境字符串相似度算法

劉永海

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

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

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

引言

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

1 算法分析

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

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

字符串S，T相似度越高，LD就越小，當完全相同時值最小：，相似度為100%；當完全不同時值最大，

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

根據LD的原理，存在如下公式：

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

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

；

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

；

設S由組成，T由組成，長度分別為n和m。……