我需要实现一个字符串匹配算法来确定哪些字符串最匹配。我知道当可以获得这个固定长度时，汉明距离是一个很好的匹配算法。用于相同长度字符串的最佳方式字符串匹配算法？
是否有匹配的，如果我要使用莱文斯坦距离公式，而不是质量的优势在哪里？我知道这种方法效率较低，因为它考虑了可变长度的字符串，但我真正关心的是匹配的质量。另外，有没有更好的算法，我可能想考虑？如果这有什么区别，我在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