[發明專利]一種Web環境下的字符串相似度的分析方法

無效

• 申請號: 200910011738.7
• 申請日: 2009-05-27
• 公開（公告）號: CN101561813A
• 公開（公告）日: 2009-10-21
• 發明（設計）人: 于戈;申德榮;朱命冬;寇月;聶鐵錚;王振華
• 申請（專利權）人: 東北大學
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06F17/22
• 代理公司: 沈陽東大專利代理有限公司
• 代理人: 李運萍

1.一種Web環境下的字符串相似度分析方法，其特征在于：該方法包括如下步驟：

步驟1.定義基本操作代價，基本操作代價由刪除字符代價、插入字符代價、替換字符代價組成；

步驟2.字符串預處理，識別詞首字符和去除非實義字符；所述的詞首字符是指字符串中第一個實義字符或字符串中非實義字符后的第一個實義字符；非實義字符是指不具有實際意義的字符，包括空格、逗號、括號；

步驟3.計算編輯距離，通過創建匹配索引實現字符串中字符位置的交換，進而優化編輯距離；其中匹配索引是指將一個字符串以最小代價的編輯操作序列轉換成另一個字符串的過程中，原本被插入或刪除的字符通過改變字符順序能夠以更小的代價進行替換的字符的索引；所述的匹配索引，在進行字符串交換之前，需要先計算一下兩個字符串的距離變化，只有當距離變化小于0時才進行位置交換；

具體公式如下：

ed′(x，y)＝ed(x，y)+distanceChange

distanceChange=Σi∈I1cost(xi′)-Σi∈I1cost(xi)+Σj∈Pρ*disj---(1)]]>

其中，ed′(x，y)是指交換后兩個字符串的距離；ed(x，y)是指交換前兩個字符串的距離；distanceChange指距離所發生的變化，如果distanceChange小于0，則是距離變小，反之是變大；cost(x_i′)是指字符x_i交換為字符x_i′后匹配的代價；cost(x_i)是指字符x_i在交換前匹配的代價；ρ是由用戶設定的交換代價系數；dis_j是指需要交換位置的第j個編輯操作序列對在編輯操作序列中的距離；I₁為在所要處理的匹配索引中涉及到字符串x中字符的位置集合；P為針對匹配索引需要進行交換處理的編輯操作序列對的集合；

創建匹配索引的方法如下：

A.計算兩個字符串的距離矩陣；

B.將所有代價為0的字符對添加到匹配索引中；

C.通過距離矩陣選出一個代價最小的替換方案；

D.過濾匹配索引中在轉換方案中已經采用的代價為0的替換方案；

E.過濾匹配索引中包含在其他索引對中出現的字符的索引對；

F.結束；

步驟4.判斷是否為縮寫詞，首先判斷兩個字符串是否是縮寫關系；如果是縮寫關系則進行距離優化；其中，縮寫關系由2個因素決定：①判斷兩者是否有相似度，有相似度時有縮寫關系；②判斷兩者的詞首字符是否被匹配，詞首字符匹配時有縮寫關系；縮寫詞距離優化，通過減少連續插入字符和連續刪除字符的代價實現，所述的判斷縮寫詞的公式如下：

sim(x,y)=ed′(x,y)Max(|x|,|y|)]]>

Pxy=λ*sim(x,y)+(1-λ)*Px+Py2---(2)]]>

其中，sim(x，y)指字符串相似度；ed′(x，y)是指步驟3中交換字符后兩個字符串的距離；|x|，|y|分別指字符字符串x，y的長度；P_xy指字符串x，y之間有一個是另一個的縮寫詞的可能性；λ指因素①的權重，P_x，P_y分別指串x，串y詞首字符被以0的代價進行替換的比例；

所述的縮寫詞距離優化具體公式如下所示：

ed″(x，y)＝ed′(x，y)+distanceOptimized

distanceOptimized=Σd∈DcostD(count(d))+Σi∈IcostI(count(i))]]>

costD(n)=Σi=0n-1cost(a→ϵ)*ηi-Σd∈Dcost(a→ϵ)count(d)---(3)]]>

costI(n)=Σi=0n-1costI(ϵ→a)*ηi-Σi∈Icost(ϵ→a)count(i)]]>

其中，ed″(x，y)是指縮寫詞優化后兩個字符串的距離；ed′(x，y)是指步驟3中交換字符后兩個字符串的距離；distanceOptimized指優化后距離所發生的變化；集合D，I分別指匹配中出現連續刪除和連續插入的集合；costD(n)，costI(n)分別指連續刪除、連續插入n個字符的代價；count(d)，count(i)分別指d，i中連續刪除和插入字符的個數；η是代價衰減系數；d，i分別指集合中的某個連續插入和刪除操作，其中，d，i∈{0，…，n-1}，n為連續刪除或連續插入的個數。