C# - 两个大字符串数组的模糊比较

Question

我需要在A中找到所有部分存在于B中的字符串。

B = [ "Hello World!", "Hello Stack Overflow!", "Foo Bar!", "Food is nice...", "Hej" ]
A = [ "World", "Foo" ]
C = B.FuzzyCompare(A) // C = [ "Hello World!", "Foo Bar!", "Food is nice..." ]

我一直在研究使用莱文斯坦距离算法解决“模糊”问题，以及使用LINQ进行迭代。然而，A * B通常会导致超过15亿次比较。

我该怎么做？有没有一种快速“几乎比较”两个字符串列表的方法？

- Olian04

---

你的例子似乎不适合使用Levenshtein距离。它们更像是检查子字符串。 - juharr

@juharr 是的，这是一个理想的后缀 Trie 问题，详见我下面的回答。 - Haney

B和A通常有多少元素？B中的元素平均大小是多少，例如："Hello World!" == 12？此外，A中的元素只是单个单词吗？ - Jarrod Dixon

@JarrodDixon，A和B中的元素平均介于100到200个字符之间。 - Olian04

@Olian04 谢谢！这解决了我的问题！ - xenteros

Answer 1

也许只需比较子字符串就足够了，这样会更有效率：

var C = B.Where(s1 => A.Any(s2 => s1.IndexOf(s2, StringComparison.OrdinalIgnoreCase) >= 0)).ToList();

- Tim Schmelter

---

提供他想忽略大小写？ - Liam

@Liam：我认为如果他想要找到类似的字符串，大小写不重要。如果是这样，他可以简单地将其更改为不同的“StringComparison”。如果我展示了“String.Contains”，他就不会知道如何进行不区分大小写的比较。 - Tim Schmelter

@Rango，你能否看一下我遇到的类似问题，但实际上我正在传递相似性的阈值 https://stackoverflow.com/questions/54511595/optimize-matching-elements-from-two-large-data-sets-using-levenshtein-distance/54516063?noredirect=1#comment95866563_54516063 - Shahid Manzoor Bhat

@Rango，我们能否在这个查询中指定相似度的百分比？比如只选择与列表A中的单词相似度达到70%或更高的列表B中的单词？谢谢。 - Shahid Manzoor Bhat

@Rango 非常感谢，我尝试使用Levenshtein距离方法。但我面临的问题是二次缩放的问题，这是我所做的 https://stackoverflow.com/questions/54511595/optimize-matching-elements-from-two-large-data-sets-using-levenshtein-distance 你能建议我如何优化吗？ - Shahid Manzoor Bhat

Answer 2

这似乎是一个不错的使用后缀字典树的例子。

后缀字典树是一棵没有有效载荷的树。它索引了给定字符串或句子的所有后缀，以便可以在O(n)时间内搜索它们。所以，如果你的输入是A中的"hello"，则会将"hello"、"ello"、"llo"、"lo"和"o"进行索引，以便可以立即且高效地查找这些子字符串，而不需要对A集合进行额外的枚举。

基本上，将A中的所有值处理成后缀字典树即可，这是一个只需执行一次的O(n * m)操作，其中n是A中元素的数量，m是元素的长度。然后对于B的每个元素，在后缀字典树中检查它是否存在，这也是一个O(n * m)操作，其中n是B中元素的数量，m是元素的长度。

- Haney

---

我很想点赞这个，因为听起来很牛逼，但是我就是不懂... :) - Liam

@Liam 基本上，原始问题明确要求避免 15 亿次比较的 A * B 成本，而这个答案做到了，但我在这里看到的其他答案没有。 - Haney

你或许能帮我一下，我想更新我的回答以响应你的问题，但我不确定：https://dev59.com/rFoT5IYBdhLWcg3wpQyD - Liam

@Haney，你能帮我解决这个问题吗？https://codereview.stackexchange.com/questions/212823/the-process-to-calculate-the-levenshtien-distance-of-each-element-of-a-large-dat - Shahid Manzoor Bhat

Answer 3

我认为您可能想错了：

List<string> results = new List<string>();
foreach (string test in B)
{
   if (A.Any(a => test.Contains(a))
      results.Add(test);
}

顺便提一下，这个问题的复杂度在O(n)(最优情况)和O(n*m)(最坏情况)之间

（其中n是A中结果的数量，m是B中结果的数量）

- Liam