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

Question

我需要比较两个字符串并计算它们之间的相似度，以便筛选出最相似的字符串列表。

例如搜索“dog”将返回：

1. dog
2. doggone
3. bog
4. fog
5. foggy

例如搜索“crack”将返回：

1. crack
2. wisecrack
3. rack
4. jack
5. quack

我已经了解到以下算法：

• QuickSilver
• LiquidMetal

还有哪些字符串相似性算法？

- Robin Rodricks

---

因为你的问题没有标准答案，所以采用了社区维基模式。 - Joe Phillips

可能是 可变长度字符串的更好相似性排名算法 的重复问题。 - j_random_hacker

已经有很多关于这个主题的问题了。在提问之前，请先搜索一下。 - j_random_hacker

@j_random_hacker：有很多问题，你说？给我一个展示至少一种新技术的问题链接？而且你提供的那个链接我已经看过了，在发布我的问题之前。我不是想做简单的排名或排序，而是想要一个非常准确的相似度算法，如果我在搜索字典数据库，它将返回我显示的结果。 - Robin Rodricks

有很多方法可以衡量相似度，而你并没有明确解释你正在寻找哪种类型的相似度，但根据你的示例和你不喜欢Levenshtein距离的事实，我认为你正在寻找某种近似子字符串匹配算法。你的问题的变体是“算法”标签下最受欢迎的话题。以下是一些链接： - j_random_hacker

Answer 1

Levenshtein距离算法是我推荐的算法，它可以计算将一个字符串转换为另一个字符串所需的最小操作次数。操作次数越少表示这两个字符串越相似...

- Peter

---

莱文斯坦距离及其所有排列（如Dam-Lev）的效果非常差，即使在最基本的比较中，QuickSilver也比它表现更好。请参见https://dev59.com/FHA75IYBdhLWcg3wW3sZ - Robin Rodricks

@Jenko：你说Levenshtein距离算法效果“很差”，但你没有给出任何评判好坏的标准。考虑到Levenshtein距离是几乎典型的“字符串相似度算法”，你应该让你的问题更具体。 - j_random_hacker

@j_random_hacker：编辑了你的帖子以向你展示原因。我给你提供了包含相同结果的问题链接，为什么你没有阅读我不理解。 - Robin Rodricks

@Jenko：（1）这不是我的帖子。（2）“Erratic”不是有意义的标准。我理解你对结果不满意，但你需要精确说明你要寻找哪些类型的相似性。顺便说一下，你通常会设置Lev距离的上限，以便在你的示例中只返回答案1-3。 - j_random_hacker

我目前正在使用Levenshtein距离来完成一个项目，但它并不是最理想的用例。我发现知道有多少个连续的字母匹配和按相同顺序匹配字符串中相同的字母一样重要，这基本上就是编辑距离所做的。 - MetaStack

Answer 2

看起来您需要一种模糊匹配。这里是一些相似度评估度量的Java实现http://www.dcs.shef.ac.uk/~sam/stringmetrics.html。 这里有更详细的字符串相似度度量解释http://www.cs.cmu.edu/~wcohen/postscript/ijcai-ws-2003.pdf，具体取决于您实现的模糊程度和速度要求。

- Mojo Risin

---

@PascalKlein 在Wayback Machine上有一个存档页面。我已经更新了链接到http://web.archive.org/web/20081224234350/http://www.dcs.shef.ac.uk/~sam/stringmetrics.html。 - Rob W

有Levenshtein算法，您可以尝试使用类似Wu-Palmer（wup）的相似度评分进行修剪，该算法使用了著名的Wordnet。对于Java，Stanford NLP是一个不错的选择。Python方面，还有pattern、scipy、numpy和gensim等工具可供使用。计算Levenshtein最好通过矩阵的对角线来完成。 - Andrew Scott Evans

Answer 3

如果重点在于性能，我会实现一个基于 trie 结构的算法（可用于在文本中查找单词或帮助更正单词，但在您的情况下，您可以快速找到包含给定单词或除一个字母外的所有单词）。请先查看上面的维基百科链接。Tries 是最快的单词排序方法（n 个单词，搜索 s，创建 trie 的时间复杂度为 O(n)，搜索 s 的时间复杂度为 O(1)（或者如果 a 是平均长度，则 trie 的时间复杂度为 O(an)，搜索的时间复杂度为 O(s)）。

一个快速且易于实现（待优化）的解决方案（相似单词）包括：

- 使用单词列表制作 trie，将所有字母前后索引化（请参见下面的示例） - 要搜索 s，请从 s[0] 开始迭代，以在 trie 中查找单词，然后是 s[1] 等等。 - 在 trie 中，如果找到的字母数为 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

严格地寻找car，字典树可以从1.开始访问，您会找到car（您还会发现以car开头的任何内容，但也有可能包含任意包含“car”的内容-这在示例中没有出现-但例如vicar将从c>i>v<a<R找到）。为了容忍1个错误或缺失的字母进行搜索，您可以从s的每个字母开始迭代，并计算您从字典树中得到的连续的字母数-或通过跳过一个字母-。

寻找car，

• c：在字典树中搜索c < a和c < r（s中的字母缺失）。要接受单词w中的错误字母，请尝试在每次迭代时跳过错误字母，以查看是否在其后面有ar，这是O（w）的。对于两个字母，O（w²）等等......但是可以向字典树添加另一级索引，以考虑跳过字母-使字典树复杂化并贪婪地占用内存。
• a，然后r：与上述相同，但也可以反向搜索

这只是提供一个原理的想法-上面的示例可能有一些问题（明天我会再次检查）。

- Déjà vu

Answer 4

你可以这样做：

对于 haystack 中的每个 string 执行以下操作：
    offset := -1;
    matchedCharacters := 0;
    对于 needle 中的每个 char 执行以下操作：
        offset := PositionInString(string, char, offset+1);
        如果 offset = -1 那么
            退出循环;
        结束;
        matchedCharacters := matchedCharacters + 1;
    结束;
    如果 matchedCharacters > 0 那么
       // 找到（部分）匹配
    结束;
结束;

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

- Gumbo

---

@Jenko：你是什么意思？搜索是线性的，所以会对字符串列表中的每个字符串进行测试。 - Gumbo

PositionInString 是什么意思？ - Moritz Schmitz v. Hülst

@MoritzSchmitzv.Hülst PositionInString 是一个函数，它返回从 offset 开始的 string 中 char 的索引位置。 - Gumbo

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

- Indrit Kello

---

我认为他正在询问算法而非解决方案的实现。 - Giulio Caccin

Answer 6

我使用了Levenshtein距离和Soundex索引，试图找到与拼写错误的药品名称相匹配的模糊匹配。这些药品名称通常很长而且笨拙。Soundex有点偏向英语，所以对于其他语言你需要使用其他方法。

- Matthew V Carey