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

Question

我有一个必须扫描的文本正文，每行至少包含 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 位信息： 玩家是谁，该操作需要多少钱或什么牌......等等。

需要解析的示例文本：

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非常满意结果。

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

Answer 1

如果您使用 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 () 并且下一个匹配从相同的位置开始尝试不同的模式。

Answer 2

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

Answer 3

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

就我个人而言，我越来越喜欢 PEG。 也许需要一些时间才能适应它们，但我认为它们更易于维护，因此这是一个明显的胜利。 我发现当您在输入中发现新的边缘情况时，解析代码是许多意外错误的根源。 与循环和条件繁重的正则表达式代码相比，当发生这种情况时，带有非终结符的声明性语法更容易更新。 命名的力量是强大的。

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

Answer 4

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

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

regex1|regex2|regex3|...|regex15

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

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

Answer 5

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

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

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

Answer 6

如果您有一个漂亮的四核或八核服务器可以用于此目的，那么另一个想法是。

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

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

Answer 7

好的，这让事情变得更清晰（扑克手牌历史）。 我猜你正在制作一个统计工具（侵略因素、摊牌、自愿将美元放入彩池等）。 我不知道为什么你需要过高的速度； 即使您在 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 的哈希表。

Answer 8

对于这样的问题，我会闭上眼睛并使用 Lexer+Parser 生成器。 您可能可以通过手动优化来解决这个问题，但使用生成器要容易得多。 而且，当输入突然改变时，它会更加灵活。

Answer 9

我建议

• 提升精神或
• Antlr 如果语法复杂；
• Xpressive 如果它更简单一点，
• Tokenizer 和手工代码（如果它很简单）。

祝你好运

Answer 10

Boost.Spirit 是一个很棒的库，它允许您进行详细的解析器分析，并且由于解析器是生成的并且直接编译到您的代码中，应该比动态计算的解决方案快得多。 语法主要是通过表达式模板（许多重载运算符的一个奇特术语）完成的，这意味着您实际上将它们写入代码中。