algorithm - 在 Perl 中，非常快速地检查许多字符串之一是否存在于许多其他字符串之一中

Question

假设我有一组 100,000 个字符串，每个字符串平均约 20-50 个字节。

然后假设我有另一组 100,000,000 个字符串，每个字符串平均也有 20-50 个字节左右。

我想遍历第二组中的所有 100,000,000 个字符串，并检查第一组中的任何一个字符串是否存在于第二组中的任何一个字符串中。

示例:第一组字符串:“abc”，第二组字符串:“123abc123” = 匹配!

我试过使用 Perl 的 index()，但速度不够快。有没有更好的方法来进行这种类型的匹配？

Answer 1

我找到了 Algorithm::AhoCorasik::XS在 CPAN 上，它实现了经典的、非常高效的多字符串搜索 Aho-Corasick algorithm (与 grep -F 使用的相同)，而且速度似乎相当快(大约是等效 grep 调用速度的一半):

示例脚本:

#!/usr/bin/env perl
use warnings;
use strict;
use autodie;
use feature qw/say/;
use Algorithm::AhoCorasick::XS;

open my $set1, "<", "set1.txt";
my @needles = <$set1>;
chomp @needles;
my $search = Algorithm::AhoCorasick::XS->new(\@needles);

open my $set2, "<", "set2.txt";
while (<$set2>) {
    chomp;
    say if defined $search->first_match($_);
}

并使用它(使用随机生成的测试文件):

$ wc -l set1.txt set2.txt
  10000 set1.txt
500000 set2.txt
510000 total
$ time perl test.pl | wc -l
458414

real    0m0.403s
user    0m0.359s
sys     0m0.031s
$ time grep -Ff set1.txt set2.txt | wc -l
458414

real    0m0.199s
user    0m0.188s
sys     0m0.031s