C＃ – 两个大字符串数组的模糊比较

我需要在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通常会导致超过15亿次比较。

我该怎么办呢？ 有没有办法快速“几乎比较”两个字符串列表？

Answer 1

也许仅仅比较子串就足够了，这会更有效：

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

Answer 2

这似乎是一个很好的使用后缀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是元素的长度。

Answer 3

我想你可能还在考虑其他问题：

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

BTW的复杂性在O(n) （最好）和O(n*m) （最差）的区域 （其中n是A中结果的数字， m是B中结果的数量）