有哪些字符串相似度算法？

Question

我需要比较两个字符串并计算它们的相似度，以过滤出最相似字符串的列表。

搜索“dog”

1. dogdognebogfoggy
2. 返回
3. ，
4. 例如
5. 将

例如 搜索“crack”会返回

1. crack
2. smartcrackrack
3. jack
4. ：< a
5. quack

我遇到过的

• href="http://orderedlist.com/our-writing/blog/articles/live-search-with-quicksilver-style/" rel ="nofollow noreferrer">QuickSilver
• LiquidMetal

还有哪些其他字符串相似度算法？

Answer 1

我将 Levenshtein 距离与 soundex 索引结合使用，尝试对拼写错误的药物名称进行模糊匹配，这些名称总是相当冗长和尴尬。 Soundex 有点以英语为中心，因此您需要其他语言的东西。

Answer 2

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();
    }
}

Answer 3

您可以这样做：

Foreach string in haystack Do
    offset := -1;
    matchedCharacters := 0;
    Foreach char in needle Do
        offset := PositionInString(string, char, offset+1);
        If offset = -1 Then
            Break;
        End;
        matchedCharacters := matchedCharacters + 1;
    End;
    If matchedCharacters > 0 Then
       // (partial) match found
    End;
End;

使用 matchedCharacters 您可以确定匹配的“程度”。如果它等于needle的长度，则needle中的所有字符也在string中。如果还存储了第一个匹配字符的偏移量，那么还可以通过用最后一个匹配字符的偏移量减去第一个匹配字符的偏移量来按匹配字符的“密度”对结果进行排序 offset；差异越小，匹配越密集。

Answer 4

如果重点是性能，我会实现一个基于 trie 结构
（非常适合在文本中查找单词，或帮助纠正单词，但例如，在您的情况下，您可以快速找到包含给定单词的所有单词或除一个字母外的所有单词）。

请首先关注上面的维基百科链接。Tries 是最快的单词排序方法（n 个单词，搜索 s，O(n< /em>) 创建 trie，O(1) 搜索 s （或者如果您愿意，如果 a 是平均长度，则 O(an< /em>) 用于 trie 和 O(s) 用于搜索))。

（相似词）的快速且简单的实现（待优化）包括：

• 问题 em>trie 包含单词列表，所有字母都在前面和后面编入索引（请参见下面的示例）
• 要搜索 s，请从 s[0] 迭代到在 trie 中查找单词，然后 s[1] 等...
• 在 trie 中，如果找到的字母数为 len(s)-k 显示单词，其中 k 是容差（缺少 1 个字母，2...）。
• 该算法可以扩展到列表中的单词（见下文）

例如，单词car，vars。

构建特里树（大字母意味着一个单词在这里结束，而另一个单词可能继续）。 > 是后索引（前进），< 是前索引（后退）。在另一个例子中，我们可能还必须指示起始字母，为了清楚起见，这里没有显示它。
例如，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

严格查找car，特里树为您提供从 1. 开始的访问权限，并且您找到 car（您还会找到以 car 开头的所有内容，但是还有任何包含汽车的东西 - 它不在示例中 - 但例如可以从 c > i > v < a < R 中找到。

要在允许 1 个字母错误/缺失容差的情况下进行搜索，您可以从 s 的每个字母进行迭代，并计算从 s< 获得的连续字母（或跳过 1 个字母）的数量/em> 在特里树中。

寻找 car,

• c：在 trie 中搜索 c c a 和 c < r（s 中缺少字母）。要接受单词中的错误字母 w，请尝试在每次迭代时跳转到错误的字母，看看 ar 是否在后面，这是 O(w em>）。使用两个字母，O(w²) 等...但是可以将另一级索引添加到特里树中，以考虑字母上的跳转 - 制作特里树复杂，并且对记忆贪婪。
• a，然后 r：与上面相同，但也向后搜索

这只是为了提供有关原理的想法 - 上面的示例可能有一些故障（我将明天再检查一下）。

Answer 5

看来您需要某种模糊匹配。这是一些相似性度量集的java实现 http://www.dcs.shef.ac.uk/~sam/stringmetrics.html。以下是字符串指标的更详细说明 http://www. cs.cmu.edu/~wcohen/postscript/ijcai-ws-2003.pdf 这取决于您的实施必须有多模糊和多快。

Answer 6

Levenshtein 距离是我推荐的算法。它计算将一个字符串更改为另一个字符串所需执行的最少操作次数。变化越少意味着字符串越相似......