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

本文关键字：数组 字符串 模糊 比较 大型 两个 | 更新日期: 2023-09-27 17:56:29

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

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..." ]

我一直在研究将Levenshtein Distance Algorithm用于问题的"模糊"部分，以及将 LINQ 用于迭代。但是，A * B通常会导致超过1,5十亿次比较。

我应该怎么做？有没有办法快速"几乎比较"两个字符串列表？

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

也许简单地比较子字符串就足够了，这会更有效：

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

似乎是后缀Trie的一个很好的用法。

后缀 Trie 是没有有效负载的树。它索引给定字符串或句子的所有后缀，以便可以在 O（n） 时间内搜索它们。因此，如果您在A中的输入是"hello"，它将索引"hello"，"ello"，"llo"，"lo"和"o"，从而允许立即有效地查找任何这些子字符串，而无需对A集进行任何额外的枚举。

基本上，获取A中的所有值并将它们处理成后缀Trie，这是一个O(n * m)操作，只需执行一次，其中n是A中的元素数，m是元素的长度。然后，对于B的每个元素，请在后缀Trie中检查它，这也是一个O(n * m)操作，其中n是B中的元素数，m是元素的长度。

我想你可能另有想法：

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中的结果数）

相关文章：