当前位置: 首页 > 面试题库 >

在C#中匹配两组大型字符串

匡旭东
2023-03-14
问题内容

情况如下:

我有一个已作为字符串抓取的网页。

我在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”。有什么想法吗?


问题答案:

在较大的文本中搜索多个字符串是一个容易理解的问题,并且已经进行了大量研究以使其快速化。两种最流行和最有效的方法是Aho-
Corasick算法
(我推荐这一方法)和Rabin-
Karp算法
。它们使用了一些预处理,但是比naieve方法要简单(数量级是最坏的情况O(m * n ^ 2 * p),其中m是长字符串的长度[ [n]是针的平均长度,p是针的数量)。Aho-
Corsaik是线性的。可以在CodeProject上免费找到它的AC#实现。

编辑:糟糕,我错了Aho-Corasick的复杂性-
输入字符串的数量和长度+所分析的字符串的大小[抓取的文本]加上匹配的数量是线性的。但是它仍然是线性的,线性比三次方(-)好得多。



 类似资料:
  • 问题内容: 我试图用来匹配包含两个不同字符串的行。我尝试了以下内容,但是这匹配包含 string1 或 string2的 行,而不是我想要的行。 那么,如何只与包含 两个字符串 的行匹配? 问题答案: 您可以使用 要么,

  • 反正有这样做的吗?

  • 我需要匹配一个字符串有单词而不是数字,我需要匹配特殊字符,如 $!:{} _如果它们是单词的一部分,但忽略其他。 我有一个正则表达式,它匹配单词并忽略数字,但如果特殊字符是单词的一部分,则无法计算出如何匹配,否则忽略。 这是我的正确答案-

  • 问题 你想要匹配两个或多个字符串。 解决方案 计算把一个字符串转换成另一个字符串所需的编辑距离或操作数。 levenshtein = (str1, str2) -> l1 = str1.length l2 = str2.length prevDist = [0..l2] nextDist = [0..l2] for i in [1..l1] by 1

  • 本文向大家介绍java实现字符串匹配求两个字符串的最大公共子串,包括了java实现字符串匹配求两个字符串的最大公共子串的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了java实现求两个字符串最大公共子串的方法。分享给大家供大家参考,具体如下: 最近在项目工作中有一个关于文本对比的需求,经过这段时间的学习,总结了这篇博客内容:求两个字符串的最大公共子串。 算法思想:基于图计算两字符串的公共子

  • 我有两张桌子: 聊天室: 聊天参与者: 我想: 找到一个聊天室,其中是创建者,是唯一的参与者。 到目前为止我得到了什么: 问题: 我有两组数字,我想匹配相等。Set是我的输入,我希望将它与匹配,以求相等,而不管它们在各自的集合中的顺序如何。 我在上面做的是字符串比较,这显然不是正确的方法。 谢谢大家。