☰

快速正则表达式检查 Vim 中某个字符在一行中出现的次数？

tag-icon • tag-icon vim gvim regex script word-count
快速正则表达式检查 Vim 中某个字符在一行中出现的次数？

假设我有一个竖线分隔的文本文件。我怀疑其中一列可能嵌入了竖线字符（“|”）。我知道文件中有 8 列，每行都应该有8-1 = 7竖线字符。因此，我需要查找所有包含 8 个或更多“|”字符的行。

下面的正则表达式应该可以找到所有这样的情况，但是太长返回我的 200,000 条记录文件：

^\(.*|.*\)\{8,}$

是否有我应该使用的更快的正则表达式？ 经过太长，我的意思是比我预期的要长——至少几分钟。这个文件不是很大（200K 条记录），所以我假设正则表达式本身效率不高。

一些示例数据：

SAMPLE_ID|GROUPS|ADDRESSSTRING|LATITUDE|LONGITUDE|COUNTRYCODE|LANGUAGECODE|ISO_2_LTR_CODE
7304094||Rhein-Galerie;Baden-Württemberg|49.48334|8.45007|DEU|ger|DE
7303851||Steigenberger Insel;Baden-Württemberg|47.69005|9.18812|DEU|ger|DE
7303850||Si-Suites;Baden-Württemberg|48.72309|9.16138|DEU|ger|DE

（我在 WinXP 上运行 gVim）

答案1

您的正则表达式很容易遇到 Vim（以及许多其他语言和环境）中使用的“回溯”正则表达式引擎的一些 O(N^2) 行为。

幸运的是，有办法编写不会导致过多回溯的等效表达式。例如：

/^\([^|]*|\)\{8}.*$

一般来说，你不需要匹配“八个或更多”，因为如果你已经知道如果有八个（无论是否更多），该行就会有问题。

如果您实际上需要匹配整行（例如因为它是:s操作的一部分），那么您将需要保留最后一部分（.*$）；如果您只是使用正则表达式来查找“八行或更多”行，那么您可以省略.*$结尾。

另外，我建议只尝试匹配您重复的组内的管道的一个“侧面”。这既简化了对正则表达式如何匹配行的思考，也简化了正则表达式引擎本身如何执行的思考（它消除了回溯的来源）。

现在，解释一下“回溯”的部分。假设您有一行包含八个竖线字符：

aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff|  gg  |  gg  |hhhhhh

以下段落描述了正则表达式引擎如何尝试将您的表达式与上面的行进行匹配（我在正则表达式行中添加了额外的空格，以（大致）显示正则表达式的各部分与行本身的字符匹配的位置）。

第一个.*是贪婪的，会将所有内容匹配到行尾，而管道字符则无法匹配。

  aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff|  gg  |  gg  |hhhhhh
^(.*                                                            |

最近的“可缩减”匹配放弃其匹配的部分并再次尝试正则表达式的其余部分。在本例中，这种情况一次发生一个字符（因为.将匹配任何单个字符）。这种回溯一直进行，直到表达式的其余部分可以匹配（或者直到它回溯到开头 - 这是它知道该行与表达式不匹配的唯一方法！）。

  aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff|  gg  |  gg  |hhhhhh
^(.*                                                     |.*    )(.*|

因此，第一组.*后退了足够多的距离，让其他组可以匹配，但第二组却没有什么可匹配的。是时候再回溯一下了。

  aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff|  gg  |  gg  |hhhhhh
^(.*                                              |.*           )(.*|

回溯找到了新的“停止”点，但现在.*第一组中的第二个正在进行贪婪匹配。第二组匹配失败。.*第一组中的第二个开始回溯。

  aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff|  gg  |  gg  |hhhhhh
^(.*                                              |.*)(.*|.*    )(.*|

第二组找到了匹配项，但第三组没有匹配项。再次回溯，从最近的匹配项开始。.*第二组中的第二个回溯到无匹配项。.*第二组中的第一个回溯到无匹配项。第一组中的第二个回溯到无匹配项。第一组中的.*第一个回溯成功。.*

  aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff|  gg  |  gg  |hhhhhh
^(.*                                       |.*                  )(.*|

但是，第二个.*又很贪婪，所以它没有给第二组留下任何东西。

  aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff|  gg  |  gg  |hhhhhh
^(.*                                       |.*       )(.*|.*    )(.*|
  aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff|  gg  |  gg  |hhhhhh
^(.*                                       |.*)(.*|.*)(.*|.*    )(.*|

最终，三组都匹配，但第四组失败。开始回溯。

  aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff|  gg  |  gg  |hhhhhh
^(.*                                |.*                         )(.*|
  aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff|  gg  |  gg  |hhhhhh
^(.*                                |.*              )(.*|.*    )(.*|
  aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff|  gg  |  gg  |hhhhhh
^(.*                                |.*       )(.*|.*)(.*|.*    )(.*|
  aaaaaa|bbbbbb|cccccc|dddddd|eeeeee|ffffff|  gg  |  gg  |hhhhhh
^(.*                                |.*)(.*|.*)(.*|.*)(.*|.*    )(.*|

您可以看到这是多么耗费时间（图表甚至跳过了实际发生的逐个字符回溯；上面只显示了“高点”）。问题来自于正则表达式的较早部分贪婪地匹配某些内容，而正则表达式的较后部分最终必须匹配这些内容才能获得正确的组重复次数。

在我的表达式中，每次重复 ( [^|]*) 都不会匹配后面元素 ( |) 会匹配的任何内容，因此回溯是纯线性的。一旦针对每个“可收缩”匹配开始回溯，它将（在线性时间内）发现后面的表达式没有更早的位置可以匹配；这会迫使回溯继续进行上一个“可收缩”匹配，直到没有匹配项，并且整行被判定为不匹配。

除了“零个或多个非管道，然后管道”（[^|]*|），还可以使用.显式非贪婪重复（\{-}在 Vim 中，但它会有所不同；其他正则表达式语言使用*?）。

^\(.\{-}|\)\{8}.*$

答案2

嗯，在我的电脑上这更快：

:%s/\(|.\{-}\)\{8,}//n

相关内容