针对每行上的多个（15+）正则表达式解析文本正文的最佳方法是什么？

StackOverflow https://stackoverflow.com/questions/303830

题

我有一个必须扫描的文本正文，每行至少包含 2 个部分，有时包含 4 个部分的信息。问题是每行可以是 15-20 个不同操作中的 1 个。

在 ruby​​ 中，当前代码看起来有点像这样：

text.split("\n").each do |line|  #around 20 times..

..............

      expressions['actions'].each do |pat, reg| #around 20 times

.................

这显然是“问题”。我确实设法通过将所有正则表达式合并为一个来使其更快（在 C++ 中提高了 50%），但这仍然不是我需要的速度——我需要快速解析数千个这样的文件！

现在我用正则表达式来匹配它们——然而这太慢了。我从 ruby​​ 开始，然后跳到 C++，希望能够提高速度，但它并没有发生。

我偶然读过 PEG 和基于语法的解析，但它看起来有点难以实现。这是我应该前进的方向还是有不同的路线？

基本上我正在解析扑克手牌历史记录，手牌历史记录的每一行通常包含我需要收集的 2-3 位信息：玩家是谁，多少钱或该行动需要什么牌。ETC..

需要解析的示例文本：

buriedtens posts $5
The button is in seat #4
*** HOLE CARDS ***
Dealt to Mayhem 31337 [8s Ad]
Sherwin7 folds
OneMiKeee folds
syhg99 calls $5
buriedtens raises to $10

在我收集这些信息后，每个操作都会变成一个 xml 节点。

现在我的 ruby​​ 实现比我的 C++ 快得多，但这是有可能的。只是因为我已经 4-5 年没有写过 C 代码了

更新：我不想在这里发布所有代码，但到目前为止我的手/秒看起来如下：

588 hands/second -- boost::spirit in c++
60 hands/second -- 1 very long and complicated regex in c++ (all the regexen put together)
33 hands/second -- normal regex style in ruby

我目前正在测试antlr，看看我们是否可以更进一步，但截至目前，我对spirit 的结果非常非常满意。

相关问题： 针对多个正则表达式高效查询一个字符串。

有帮助吗？

解决方案

我会建议

祝你好运

其他提示

Boost.Spirit 是一个非常出色的库，可以让您进行详细的解析器分析，并且自解析器以来生成并编译到您的代码中，应该比动态计算的解决方案快得多。语法主要使用表达式模板（许多重载运算符的一个奇特术语）来完成，这意味着您实际上将它们写入代码中。

如果你使用Perl，这是一种方法。
从 perldoc perlfaq6 

while (<>) {
    chomp;
    PARSER: {
        m/ \G( \d+\b    )/gcx   && do { print "number: $1\n";  redo; };
        m/ \G( \w+      )/gcx   && do { print "word:   $1\n";  redo; };
        m/ \G( \s+      )/gcx   && do { print "space:  $1\n";  redo; };
        m/ \G( [^\w\d]+ )/gcx   && do { print "other:  $1\n";  redo; };
    }
}

对于每一行，PARSER循环首先尝试匹配一系列数字后跟一个单词边界。此匹配必须从最后一场比赛停止的位置（或第一场比赛中的字符串的开头）开始。由于m/ \G( \d+\b )/gcx使用c标志，如果字符串与该正则表达式不匹配，则perl不会重置pos()，并且下一个匹配从同一位置开始尝试不同的模式。

请参阅正则表达式匹配可以简单快速 （但在Java，Perl，PHP，Python，Ruby等方面都很慢）。根据数据量和正则表达式的复杂程度，编写自己的解析逻辑可能会更快。

  

我随便读了关于PEG和基于语法的解析，但看起来有点难以实现。这是我应该走的方向还是有不同的路线？

就个人而言，我已经爱上了PEG。它可能需要一点时间来适应它们，但是我认为它们更易于维护，这是一个明显的胜利。当你在输入中找到新的边缘情况时，我发现解析代码是许多意外错误的根源。与循环和条件重正则表达式代码相比，具有非终结符的声明式语法更容易在发生这种情况时进行更新。命名很有用。

在Ruby中有 Treetop ，这是一个使用PEG的解析器生成器。我最近发现用一个简短的语法替换正则表达式重手写的解析器非常愉快。

正则表达式匹配是否重叠？也就是说，当两个或多个正则表达式匹配同一行时，它们是否总是匹配行的不同部分（没有重叠）？

如果匹配从不重叠，请使用一个结合了现在15个正则表达式的正则表达式运行搜索：

regex1|regex2|regex3|...|regex15

如果您需要确定15个正则表达式中的哪个匹配，请使用捕获组。

搜索一次长期正则表达式的数据将比搜索15次更快。更快的速度取决于您正在使用的正则表达式引擎以及正则表达式的复杂性。

尝试用 Perl 进行一个简单的测试。了解“学习”功能。我可能尝试的是：

  • 读取整个文件或大量行（如果这些文件非常大）到单个字符串中
  • 随时在每行的开头添加行号。
  • “研究”字符串。这会按字符构建一个查找表，可以很大。
  • 对字符串运行正则表达式匹配，以换行符为界（使用 m 和 s 正则表达式修饰符）。表达式应提取行号和数据。
  • 将按行号索引的数组项设置为该行上找到的数据，或者执行更智能的操作。
  • 最后就可以处理数组中存储的数据了。

我没有尝试过，但可能会很有趣。

另一个想法是，如果你有一个spiffy quad或oct核心服务器用于此目的。

构建一个分割工作的处理管道。第一阶段可以将文件切割成一个游戏或每个游戏，然后将每个文件写入八个第二阶段管道中的一个，这两个管道读取数据，处理它并以某种方式产生输出，可能是另一台机器上的数据库。

根据我的经验，这些基于管道的多工艺设计几乎与多线程设计一样快速且更容易调试。使用网络套接字而不是管道来设置一组机器也很容易。

好的，这让事情更清晰（扑克手牌历史）。我猜你正在制作一个统计工具（攻击因素，去摊牌，自愿把$放到底池等）。我不确定为什么你需要过快的速度;即使您使用16个桌子进行多重操作，手也只能以适中的速度进行。

我不知道Ruby，但是在Perl中我会做一个小的switch语句，同时将重要的部分分成$ 1，$ 2等。根据我的经验，这并不比进行字符串比较慢然后用其他方法分割线。

HAND_LINE: for ($Line)
    { /^\*\*\* ([A-Z ]+)/ and do 
        { # parse the string that is captured in $1
          last HAND_LINE; };
      /^Dealt to (.+) \[(.. ..)\]$/ and do
        { # $1 contains the name, $2 contains the cards as string
          last HAND_LINE; };
      /(.+) folds$/ and do
        { # you get the drift
          last HAND_LINE; }; };

我认为你不能真正让它变得更快。将检查发生在第一个位置最多的行（可能是折叠语句）和那些最后只出现稀疏的行（开始新手，"*** NEXT PHASE ***"）。

如果您发现实际文件读取是瓶颈，您可以查看可用于处理大文件的模块;对于Perl，我想起了Tie::File。

确保只阅读每只手一次。每手牌后不要再读取所有数据，而是保持不变。已解析的手ID的哈希表。

对于这样的问题，我只是闭上眼睛并使用Lexer + Parser生成器。您可以通过手动优化来击败它，但使用发电机要容易得多。此外，当输入突然改变时，它会更灵活。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top