我需要實現一個字符串匹配算法來確定哪些字符串最匹配。我知道當可以獲得這個固定長度時，漢明距離是一個很好的匹配算法。用於相同長度字符串的最佳方式字符串匹配算法？
是否有匹配的，如果我要使用萊文斯坦距離公式，而不是質量的優勢在哪裏？我知道這種方法效率較低，因爲它考慮了可變長度的字符串，但我真正關心的是匹配的質量。另外，有沒有更好的算法，我可能想考慮？如果這有什麼區別，我在Java中工作。
http://en.wikipedia.org/wiki/Levenshtein_distance
http://en.wikipedia.org/wiki/Hamming_distance
由於大部分
考慮字符串： 「ABCDEFG」 和 「bcdefgh」。
的Levenshtein距離爲2的漢明距離（文字上運行，而不是位）7
所以這真的取決於你是否想要把這些字符串爲類似，還是不行。海明距離有其適當的用途，但「這些字符串是否會與人類相似？」不是其中之一。
我明白了。這聽起來像海明距離，因爲你的例子使得Levenshtein看起來更合適。你有沒有其他的算法可以考慮？ – Cuga 2009-12-07 16:42:10
你在另一個評論中說，你想要d（「aaaaa」，「kaaaa」）> d（「aaaaa」，「baaaa」）。 Levenshtein沒有這樣做，在兩種情況下都是1。恐怕我不知道任何其他相關的算法。但也許通過將每個角色分成（比如說）2位塊，並計算Levenshtein在這些塊上的距離而不是過多的字符，你可能會得到更接近你想要的東西的東西。儘管如此，還是不對的，因爲變化O→P翻轉的位數多於變化P→Q. – 2009-12-07 17:20:50
啊，這個怎麼樣：你可以計算相應字符之間的均方根距離。 （'a' - 'k'）^ 2爲100，（'a' - 'b'）^ 2僅爲1.這意味着「abc」比「amz」更接近「cba」 zam「，但是，所以你仍然可能得不到你喜歡的結果。 – 2009-12-07 17:25:45
你可能會感興趣的Bitap algorithm.
的bitap算法（也被稱爲 移，或者按住Shift鍵和或 巴埃薩 - 耶茨 - 貢內特算法）是 模糊字符串搜索算法。所述 算法告訴給定文本 是否包含一個子是 「近似等於」給定 模式，其中近似相等是的Levenshtein 距離來定義的 - 如果子和 圖案是在給定距離k內 彼此，那麼算法 認爲它們相等。該算法開始 通過預先計算一組包含一個位的圖案的每個 元件 位掩碼。然後它是 能夠做大部分的工作與 按位操作，這是 非常快。
你能描述一下你會如何級比賽的質量？這是一個主觀的措施，所以如果你能描述你的目標，你會得到更好的答案。 – 2009-12-07 16:28:31
對於2個字符串，比如AHDJD和KDLOS，我想判斷它們是如何「接近」的。所以AAAAA和AAAAA將是100％的比賽。 BAAAA和AAAAA將分別爲97％，KAAAA和AAAAA將接近93％...... BJKDZ和AAAAA幾乎不會一樣......這有幫助嗎？ – Cuga 2009-12-07 16:35:14