我有一个大约 5000 个单词的列表。我想在给定单词的这些单词中找到最长的前缀匹配。例如,在我的列表中,我有:
1
121
12234
20345
21345
现在,如果我搜索 12134,结果将是 121(最长匹配)。我知道它可以通过不同的方式来完成。但是,最有效的方法应该是什么?
我有一个大约 5000 个单词的列表。我想在给定单词的这些单词中找到最长的前缀匹配。例如,在我的列表中,我有:
1
121
12234
20345
21345
现在,如果我搜索 12134,结果将是 121(最长匹配)。我知道它可以通过不同的方式来完成。但是,最有效的方法应该是什么?
#!/usr/bin/env perl
use strict;
use warnings;
my @prefixes = qw(
1
121
12234
20345
21345
);
my $num = '12134';
my ($longest) = sort { length $b <=> length $a } grep { 0 == index $num, $_ } @prefixes;
print "$longest\n";
输出
121
您可以让正则表达式引擎为您执行此操作。它应该非常快
我希望很明显,正则表达式模式只需要构建一次,然后就可以用来为任意数量的目标字符串找到最长的前缀
use strict;
use warnings;
use 5.010;
my @prefixes = qw/
1
121
12234
20345
21345
/;
my $target = 12134;
my $re = join '|', sort { length $b <=> length $a } @prefixes;
$re = qr/(?:$re)/;
say $1 if $target =~ /^($re)/;
121
或者,该Tree::Trie
模块可用于实现正则表达式引擎提供的 trie 搜索,如下所示
use strict;
use warnings;
use 5.010;
use Tree::Trie;
my @prefixes = qw/
1
121
12234
20345
21345
/;
my $target = 12134;
my $trie = Tree::Trie->new({ deepsearch => 'prefix' });
$trie->add(@prefixes);
say scalar $trie->lookup($target);
输出当然和前面的代码一样