在C#中匹配两个大的字符串集合

Question

以下是情况：

我有一个网页，已被爬取为字符串。

我有几个字段在MSSQL数据库中。例如，汽车型号，它有一个ID和一个名称，如Mustang或Civic。它已经填充了大多数汽车型号。

我想找到我的模型表中任何行的任何匹配项。因此，如果我的模型表中有Civic、Mustang和E350，我希望找到我已经爬取的页面上任何一个的出现。

在C#中，有什么高效的方法可以做到这一点。我正在使用LINQ to SQL与数据库进行交互。

创建所有模型的字典，对页面进行标记化并迭代标记是否有意义？还是应该遍历标记，并使用WHERE子句询问数据库是否存在匹配项？

    //Dictionary dic contains all models from the DB, with the name being the key and the id being the value...
    foreach(string pageToken in pageTokens)
    {
         if(dic.ContainsKey(pageToken)) 
         {
              //Do what I need to do
         }
    }

这两种方法对我来说都不太好。有什么建议吗？我想用一些集合交集的方法可能会很好。

这两种方法都没有解决模型名称超过一个单词的情况，比如“F150 Extended Cab”。你有什么想法吗？

- Jason

---

你已经分解文本以确定哪一部分是汽车了吗？例如，页面是否按可预测的方式结构化以提取匹配项？还是这是一个未经评估的巨大文本块？ - Ahmad Mageed

这是一大段文本。Craigslist。标题很可能包含型号。但是型号问题只是为了举例说明。我还有很多其他东西需要找到。 - Jason

Answer 1

在更大的文本中搜索多个字符串是一个众所周知的问题，已经进行了大量研究以使其更快。其中最流行和最有效的两种方法是Aho-Corasick算法（我推荐这个）和Rabin-Karp算法。它们需要一些预处理，但比朴素方法（朴素方法的最坏情况为O(m*n^2*p)，其中m是长字符串的长度[您爬取的网页]，n是针的平均长度，p是针的数量）复杂度低得多且速度更快。Aho-Corsaik是线性的。可以在CodeProject免费找到它的C#实现。 编辑：哎呀，我关于Aho-Corasick复杂度的说法是错误的——它是与输入字符串的数量和长度+被分析的字符串的大小[爬取的文本]+匹配的数量成正比的。但它仍然是线性的，而线性远比立方体好多了 :-）。

- Robert Fraser

---

我决定在后期进行处理，这样可以消除性能问题。虽然如此，这是非常有用的信息。 - Jason

Answer 2

我的第一个方法非常简单：

foreach(string carModel in listOfCarModelsFromDatabase) {
    if(pageText.Contains(carModel) {
        // do something
    }
}

如果以上速度还不够快，我才会开始担心加速。汽车型号列表不可能如此之大（<10000？），而且只有一页文本。

- jason

---

对于模型列表较大的情况，这种方法效率会变得相当低下，但对于小型列表而言则可行。 - Brett Allen

我有大约1500个对象需要与文本进行比较。 - Jason

在计算机科学中，从字典中进行字符串匹配是一个众所周知的问题；这个答案就像建议使用冒泡排序一样。 - Robert Fraser

@Aequitarum Custos：“我有一个网页，已经被爬取成字符串了。” 这是单个页面，不是100,000个。不要无谓地概括问题。 - jason

@Casoninabox：问题是，这种方法编码非常简单，易于正确实现。如果速度足够快，就可以继续前进，在其他方面创造价值。如果不行，那么再考虑更复杂的方法。 - jason

Answer 3

你应该使用正则表达式，而不是基于空格进行分词。

使用正则表达式，你可以使用空格并且效果很好，我相信它比基于可能值的分词和循环更快。

但是如何构建这个正则表达式我不确定。

最简单的方法是，你可以简单地构建一个包含每个模型的正则表达式。

(Model 1|Model 2|Model 3) 

但我相信在正则表达式中有更有效的方法来做到这一点。

- Brett Allen

---

如果有很多模型，正则表达式模式会非常大...我不确定那样的效率会如何。 - Thomas Levesque

是的，确实是一个有趣的问题。 - Brett Allen

一些正则表达式引擎可能会进行优化，但是一个传统的具有如此多分支的NFA / DFA将会很慢且内存效率极低。我预计正则表达式的性能会比naieve搜索更差。 - Robert Fraser

是的，这里有Aho-Corasick、naieve搜索（IndexOf）和正则表达式的比较：http://www.codeproject.com/KB/recipes/ahocorasick.aspx。正则表达式的性能非常糟糕。 - Robert Fraser

Answer 4

如果您需要一个非常简单的解决方案来进行子字符串匹配（并且性能表现良好），您可以使用参数化的 SQL 查询，例如：

select ModelID, ModelName
from Model
where ? like '%' + ModelName + '%'

其中?是一个参数，它将被整个网页文本替换。

- D'Arcy Rittich

---

-1：这是一个天真、显而易见的解决方案。它在道德上等同于作者发布的“糟糕”解决方案。虽然它可能足够快以满足他的需求，但他也要求提供另一种选择。 - Brian

正在使用哪个数据库引擎？一些数据库引擎会自动实现良好的搜索方法，这比手动实现Aho-Corasick或Rabin-Karp更好（更易维护、更优化、数据传输更少等）。 - Robert Fraser

正如我在答案中所说，这是一个非常简单的解决方案。我认为可能对一些人有趣的是LIKE的倒置使用-许多人不知道可以这样做。 - D'Arcy Rittich