字符串相似度算法？

Question

我需要比較2個字符串並計算它們的相似性，以篩選最相似的字符串列表。

例如，搜索 「狗」 將返回

1. 狗
2. 該死
3. 沼澤
4. 霧
5. 霧

EG。尋找 「破解」 將返回

1. 裂紋
2. 俏皮話
3. 架
4. 插孔
5. 嘎嘎

我所遇到：

• QuickSilver
• LiquidMetal

你知道的更多的字符串相似性的算法？

Answer 1

看來你需要某種模糊匹配。這裏是一些相似性度量集http://www.dcs.shef.ac.uk/~sam/stringmetrics.html的java實現。以下是關於字符串指標http://www.cs.cmu.edu/~wcohen/postscript/ijcai-ws-2003.pdf的更詳細說明，它取決於您的實施必須多麼模糊和多快。

Answer 2

Levenshtein距離是我會推薦的算法。它會計算您將1個字符串更改爲另一個字符串所需執行的最小操作次數。這些變化意味着更少的字符串是更類似於...

Answer 3

你可以這樣做：

 
ForeachstringinhaystackDo 
    offset := -1; 
    matchedCharacters := 0; 
    ForeachcharinneedleDo 
     offset := PositionInString(string, char, offset+1); 
     Ifoffset = -1 Then 
      Break; 
     End; 
     matchedCharacters := matchedCharacters + 1; 
    End; 
    IfmatchedCharacters > 0 Then 
     // (partial) match found 
    End; 
End; 

隨着matchedCharacters可以確定本場比賽的「度」。如果它等於針的長度，針中的所有字符也都在字符串。如果還存儲第一個匹配字符的偏移量，則還可以通過從最後一個匹配字符的偏移量中減去第一個匹配字符的偏移量，將結果按匹配字符的「密度」排序。偏移量;差異越小，匹配越密集。

Answer 4

如果關注的是性能，我將實現基於一個trie結構
（效果很好找話的文字，或以幫助糾正一個單詞的算法，但在你的情況下，你可以迅速找到所有單詞包含一個給定的單詞或全部，但一個字母，例如）。

請首先按照上面的維基百科鏈接。Tries是最快的話排序方法（Ñ詞語，搜索小號，O（Ñ）來創建字典樹，O（1），以搜尋小號（或如果願意，如果一個是用於搜索的平均長度O（和））和用於搜索的O（的））。

的便捷實現您的問題（待優化）（類似的話）由

• 充分利用線索與單詞列表，讓所有字母索引的正面和背面（見下面的例子）
• 要搜索小號，從小號迭代[0]以找到字在字典樹，然後小號 [1]等...
• 如果找到的字母數是len（s） - k顯示該字，其中k是容差（1個字母缺失，2 ...）。
• 該算法可以擴展到該列表中的話（見下文）

實施例，用的話car，vars。

構建trie（大字母表示一個詞在這裏結束，而另一個可能會繼續）。 >是後索引（前進），<是前索引（後退）。在另一個例子中，我們可能不得不指出起始字母，爲了清晰起見，這裏沒有提供。
的<和C++例如將Mystruct *previous,*next，從a > c < r這意味着，你可以從a直接去c>，相反，還從a到R。

1. c < a < R 
    2. a > c < R 
    3. > v < r < S 
    4. R > a > c 
    5.  > v < S 
    6. v < a < r < S 
    7. S > r > a > v 

找嚴格的汽車線索讓你從1訪問，你會發現車（你會發現一切也開始車，也與車內的任何東西 - 它是沒有在這個例子中 - 但牧師，例如可以從c > i > v < a < R找到）。

要搜索同時允許1個字母的錯誤/缺少寬容，你的小號每個字母重複，並計算連續數 - 或跳過1個字母 - 你從小號在特里收到信件。

尋找car，

• c：尋找線索的c < a和c < r（失蹤小號字母）。若要接受錯誤的字母w，請嘗試在每次迭代時跳過錯誤的字母，看看ar是否落後，這是O（w）。有兩個字母，O（w²）等...但另一個級別的索引可以被添加到考慮到跳在字母上 - 使得複雜和貪婪的記憶。
• a，然後r：同上，但搜索倒着以及

這僅僅是提供關於原則的一個想法 - 上面的例子可能有一些小問題（我會再檢查明天）。

Answer 5

class Program 
{ 

static 
int ComputeLevenshteinDistance(string source, string target){ 
if ((source == null) || (target == null)) return 0; 
if ((source.Length == 0) || (target.Length == 0)) return 0; 
if (source == target) return source.Length; 

int sourceWordCount = source.Length; 
int targetWordCount = target.Length; 

int[,] distance = new int[sourceWordCount + 1, targetWordCount + 1]; 

// Step 2 
for (int i = 0; i <= sourceWordCount; distance[i, 0] = i++); 
for (int j = 0; j <= targetWordCount; distance[0, j] = j++); 

for (int i = 1; i <= sourceWordCount; i++) 
{ 
    for (int j = 1; j <= targetWordCount; j++) 
    { 
     // Step 3 
     int cost = (target[j - 1] == source[i - 1]) ? 0 : 1; 

     // Step 4 
     distance[i, j] = Math.Min(Math.Min(distance[i - 1, j] + 1, distance[i, j - 1] + 1), distance[i - 1, j - 1] + cost); 
    } 
} 

return distance[sourceWordCount, targetWordCount]; 
} 

static void Main(string[] args){ Console.WriteLine(ComputeLevenshteinDistance ("Stackoverflow","StuckOverflow")); 
Console.ReadKey(); 
} 
}