寻找更快速的方式来执行字符串搜索

我必须认识到一大群网址（几百万行）属于一个特定的类别或不。我有另一个具有子字符串的列表，如果该URL存在属于该类别的话。例如，类别A.寻找更快速的方式来执行字符串搜索

要检查的子字符串列表大约有10k个这样的子字符串。我所做的只是在子字符串文件中一行一行地查找匹配项，并且如果找到该URL属于类别A的话。我在测试中发现这很耗时。

我不是计算机科学专业的学生，所以没有太多有关优化算法的知识。但是有没有办法让这个更快？只是简单的想法。编程语言不是一个大问题，但Java或Perl会更好。

要匹配的子字符串列表不会有太大变化。然而，我会收到不同的URL列表，所以每次得到它时都要运行它。瓶颈似乎是网址，因为它们可能会变得很长。

来源

2011-04-13 sfactor

你可以使用一些信息检索系统（即Lucene的 - 在Java中）索引的URL，然后搜索字符串，索引会费时，但可以为每个“查询”节省时间 - 无需遍历整个列表。 – amit 2011-04-13 07:41:24

10K次，比如说1000万是什么，1000亿？是的，不管语言如何，这都需要一些时间。如果A类中有某物，这是否意味着它们不能在其他类别中？如果是这样，你可以从大列表中删除所有分配给 – 2011-04-13 07:44:40

的大列表。子列表的列表是恒定的，没有理由需要很长时间，查看我的答案列表的长度只影响所用的大小内存的自动机，甚至可能会很小 – Asaf 2011-04-13 07:46:31

是的，我在java中使用了Aho-Corasick algorithm算法来解决你所提出的问题，它显示了对天真实现（你在做什么）x180的一致改进。网上有几种实现可用，但我会调整它们以获得更好的性能。请注意，解决方案的复杂性是由单词的长度（在你的情况下的URL），而不是子字符串的数量。此外，它只需要一次平均匹配。

P.S-我们曾经在面试时将这个问题提供给人们，所以有很多方法可以解决这个问题。我提供的是我们在生产代码中使用的那个，它（现在）击败所有其他解决方案。

编辑：写错算法名称以前，固定......

来源

2011-04-13 07:44:50 Asaf

嘿谢谢，Aho-Corasick算法就像一个魅力。天真的实现获得了约50倍的改进。只是多一个好奇心，KMP算法的性能如何？那会更快吗？ :) – sfactor 2011-04-13 11:44:44

那，忘了KMP。这是我犯的一个错误（从错误的电子邮件中复制名称）Aho-Corasick算法在输入长度上是线性的，并且易于理解/实现，除非真的必要，否则我不会为更多优化而烦恼。我做了什么来加速它只是使用数组无处不在来表示节点之间的边界（而不是地图），并且原始算法返回匹配的位置。如果你挥动这个能力，你可以加快速度。 – Asaf 2011-04-13 11:57:00

您可以将子字符串压缩成共享相同前缀的类。这应该使时间缩短很多。

如果您通过每次迭代将字符串移位1来查找匹配项，则可以使用更好的算法（与正则表达式一样）提高您的速度。

来源

2011-04-13 07:42:35 bdares

如果您将所有子字符串放入一个正则表达式中，前缀优化会自动完成，至少通过合理优化的常规表达引擎。 – jmg 2011-04-13 07:45:55

我建议使用古老的Grep，而不是使用编程语言来完成此任务。它使用快速Boyer-Moore string searching algorithm，这应该足够几百万行。

来源

2011-04-13 07:43:20 darioo

我不确定grep在这里会有效率，如果不可能匹配，算法会跳跃到前面，如果你有10k个单词，那么grep可能会很难在前面跳过（或返回取决于优化），因为会有很多通用的前缀（或后缀） – Asaf 2011-04-13 07:50:21

不同的方法当然可以优化这一点。关于你的背景，我会画一个简单的草图。这假定子字符串列表不会经常更改。

从所有子字符串生成一个巨大的正则表达式。
编译该正则表达式，请参阅。例如Java中的类Pattern。将refrence存储到编译的正则表达式。
使用相同的编译正则表达式来匹配每个url。

来源

2011-04-13 07:44:25 jmg

我会打赌这将表现得很差，你有没有试过用10k字符串做这样的事情？子弹（1）将非常难以有效地取消，其余的最终效果几乎与天真实施一样低效 – Asaf 2011-04-13 07:52:39

@Asaf：如果你的regexp引擎不好，或者如果你不预编译正则表达式。但除此之外，它应该创建一个几乎与KMP算法一样好的自动机。我想给一个适用于没有深厚计算机科学知识的方法。否则，KMP是显而易见的解决方案。 – jmg 2011-04-13 08:04:30

@jmg，我同意KMP有点复杂，我的意思是Aho-Corasick并相应地解决了我的答案（我用KMP来解决不同的问题）。 Aho-Corasick有许多现成的[实现]（https://hkn.eecs.berkeley.edu/~dyoo/java/index.html），我感觉相对容易理解。此外，假设你会以某种方式从10k字符串中构建出“完美”的正则表达式，我认为这是一个更难的算法问题，然后是原始问题，但我没有看到该解决方案不会如何依赖（复杂性明智）的子字符串 – Asaf 2011-04-13 08:09:42

Perl是在正则表达式优化备用字符串的长列表（达到一定的整体编译正则表达式的长度，它恢复到很好效率较低的机制）。你应该能够构建一个正则表达式匹配某一类别，如：

$catAre = join('|', map quotemeta, @catAstrings); 
$catAre = qr/$catAre/;

来源

2011-04-13 07:48:02 ysth

对于实现共同字符串搜索算法看到答案https://stackoverflow.com/questions/5564610/fast-alernative-for-stringindexofstring-str Java库。再加上并行化，你应该能够相当快地解析数百万个URL。这很容易做到;你应该尝试一下，看看时间是否可以接受，然后再进一步观察优化。

来源

2011-04-13 08:17:29 WhiteFang34

链接不工作 – therealprashant 2016-11-04 06:24:02

我第一次写它的评论，但后来我意识到，我认为这是作为一个答案
你可以使用一些信息检索系统（如Apache Lucene在Java中），并用它来索引网址，如文档更合适。
然后，在编制索引之后 - 您可以迭代查询，并搜索它们中的每一个，结果将是匹配的URL。
优先级：
*搜索不需要遍历每个查询的所有URl。
*如果您稍后将需要串/查询的交集或并集 - 库为您提供了这一功能
缺点：
*索引将需要一段时间...
*您可能需要在RAM一些额外的空间/磁盘索引。

我认为这是一个值得探讨的方法，也许是时间消耗，而索引搜索价值的增益。

来源

2011-04-13 08:37:06 amit

我在Perl中做过这样的事情，比较13K关键字〜清单针对从Twitter数据的输入流找到任何匹配这些关键字的所有推特（以及关键字匹配每一个）。在粗略估计，代码如下：

use Regexp::Assemble; 
my $ra = Regexp::Assemble->new; 
$ra->add(@keywords); 
my $regex = $ra->re; 

for my $tweet (@tweets) { 
    my @matches = $tweet =~ /$regex/g; 
    # do whatever with @matches... 
}

注意，这里使用Regexp::Assemble打造的正则表达式，这不是核心的Perl发行版的一部分，所以你需要安装，如果从CPAN如果你想修改此代码。

如果您使用的是perl 5.10或更高版本，还有“智能匹配”运算符（~~），它可以在不需要任何附加模块的情况下做类似的工作。

来源

2011-04-13 10:10:14

我目前正在研究这个问题。我得出这样的结论：同时使树

阿霍 - corasick会消耗更多的内存。如果没有记忆的问题比它的好。但是看一下HAT Trie吧。它是散列和特里（树）的组合。它将在某个级别生成一棵树，其余的字符将形成一个散列值，该散列值应该在哈希表中进行标记。

对不起更多的技术语言。但是如果您从URL列表中搜索特定的URL，我认为HAT trie是更好的选择。（我已经形成了HAT特里这将消耗12MB用于存储URL的6lacks。）

来源

2012-08-21 05:55:48

即使你可以根据你的需要调整它。（法律记忆或更快的表现） – 2012-08-21 05:56:46

寻找更快速的方式来执行字符串搜索

回答

相关问题