问题 我可以使用交替链接多少个正则表达式?


我有一些大文件(数百MB),我需要搜索几千〜20个字符的唯一字符串。

我发现使用管道交替元字符来匹配正则表达式 (string1|string2|string3) 加快搜索过程 很多 (而不是一次搜索一个字符串)。

这种扩展的限制是什么?我可以像这样链接多少个表达式?它会在某些时候引起某种溢出吗?有一个更好的方法吗?

编辑

为了使我的问题简短,我没有强调我已经使用这种交替方法实现了代码的事实,我发现它有用:在具有典型数据集的测试用例中,运行时间从87分钟到18秒 - 加速290倍,显然是O(n)而不是O(n * m)。

我的问题涉及当其他用户将来使用包含更大文件和更多搜索术语的更大数据集运行此代码时,如何使用此方法。原始的O(n * m)代码是已经使用了13年的现有代码,最近指出它的缓慢,因为它最近运行的基因组相关数据集已经变得更大了。


7473
2018-02-26 22:41


起源

你为什么不尝试并告诉我们结果呢? - Kevin
这很奇怪:我的结果正好相反,确实如此 许多 更快地进行多次单独搜索,而不仅仅是一次更换。我建议你多说一点你的代码吗? - raina77ow
使用其中一个 正则表达式::组装, 正则表达式::特里, 正则表达式:: PreSuf 组装更有效的改造 - obmib
不必要: p3rl.org/... - daxim
是的,正如daxim所说,最好的方法将取决于字符串中常见的前缀有多常见。一般来说,正则表达式引擎比你聪明,现在不会爆炸,所以你最好只是尝试看看会发生什么。 - Alex


答案:


如果你有一个简单的正则表达式,如(word1 | word2 | ... | wordn),正则表达式引擎将构造一个状态机,只需将输入传递一次以查找字符串是否匹配。

旁注:在理论计算机科学中,“正则表达式”的定义方式使得单次传递总是足够的。但是,实际的正则表达式实现添加了允许构造正则表达式模式的功能,这些模式不能总是作为单个传递实现(看这个例子)。

同样,对于正则表达式模式,引擎几乎肯定会使用一次传递。这可能比从内存中多次读取数据要快得多......而且几乎肯定比从磁盘多次读取数据快得多。


6
2018-02-26 23:47





如果你要正式表达形式(word1 | word2 | .... | wordn),为什么不创建一个相关的布尔数组。那应该非常快。

编辑

# before the loop, set up the hash

%words = (
   cat => 1,
   dog => 1,
   apple => 1,
    .... etc
);

# A the loop to check a sentence

foreach $aword (split(/ /, $sentence))
   if ($words{$aword}) print "Found $aword\n";

3
2018-02-26 23:15



请为此添加代码示例。 - daxim
@daxim - 代码的骨骼。 - Ed Heal
我认为这种方法适用于在搜索之前完全加载到内存中的较小数据集。 - rmtheis


正则表达式的范围没有理论上的限制,但实际上它必须符合特定平台和安装的限制。你必须凭经验找出你的计划是否有效,而且我很高兴看到你的结果。

我要说的一件事是你应该在继续使用之前单独编译表达式。无论是那个还是应用的 /o 只编译一次的选项(即保证表达式的内容不会改变)。像这样的东西

my $re = join '|', @strings;

foreach my $file (@files) {
  my $fh = IO::File->new($file, '<') or die "Can't open $file: $!";
  while (<$fh>) {
    next unless /\b(?:$re)\b/io;
    chomp;
    print "$_ found in $file\n";
    last;
  }
}

2
2018-02-27 05:24