回答

收藏

在C#匹配两组大字符串

技术问答 技术问答 250 人阅读 | 0 人回复 | 2023-09-14

情况如下:1 _1 \/ ~% `! M0 u5 V
我有一个网页被用作字符串捕获。
- j( q+ M7 `+ B. h3 |8 y我在MSSQL数据库中有几个字段。例如,汽车模型有ID和名,比如Mustang或Civic。它预装了大多数型号的汽车。
  ^0 _3 h& \3 m. \8 L我想在我的模型表中找到任何匹配的行。因此,如果我的模型表中有一个Civic,Mustang和E350,我想在我抓取的页面上找到这三个页面中的任何一个。5 `$ f( Z8 g; h$ z
在C#执行此操作的有效方法是什么?我正在使用它LINQ to SQL与数据库接口。( O4 i2 h' {3 T9 g- I
创建所有模型的字典来标记页面和遍历是否有意义?还是我应该遍历令牌并使用它WHERE问问数据库是否有匹配项。
% i+ [2 W7 ]* y7 `                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       这两种方法对我来说都很糟糕。关于我应该做什么的建议?我想象的交集可能很好吗?2 ?7 q! W; o' o+ c4 G3 `3 g
这两种方法都不能解决超过一个单词的模型名称,例如 F150 Extended Cab.有什么想法吗?
5 a: D# N! k6 T9 }! H- `) K- q                                                                + t8 K, t7 j; w1 W
    解决方案:                                                                / P5 R+ D/ J* P* U: D9 S
                                                                在更大的文本中搜索多个字符串是一个容易理解的问题,并进行了大量的研究,以使其快速发展。两种最流行和最有效的方法是Aho-$ ~& n3 P% U. x5 z0 Z: }
Corasick算法(我推荐这一方法)和Rabin-% U5 d( m1 W$ k/ W, |" w- o
Karp算法。它们使用了一些预处理,但naieve方法简单(数量级是最坏的情况)O(m * n ^ 2 *p),其中m是长字符串的长度[ [n]针的平均长度,p针的数量)。Aho-
. K2 q. B4 K8 {$ K/ u. t2 O4 }6 lCorsaik是线性的。可以在CodeProject免费找到AC#实现。9 \2 X# G1 J& `
编辑:不好,我错了Aho-Corasick的复杂性-8 ]! ]& O6 v9 o1 m
输入字符串的数量和长度 分析的字符串的大小[捕获的文本]和匹配的数量是线性的。但它仍然是线性的,线性比三次方形(-)好得多。
分享到:
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则