16

编辑 2：对于为什么这仍然很重要的实际演示，只需看看stackoverflow 自己的正则表达式导致的中断今天（2016-07-20）！

编辑：自从我第一次提出这个问题以来，这个问题已经有了很大的发展。请参阅下面的两个快速+兼容但不完全功能的实现。如果您知道更多或更好的实现，请提及它们，这里还没有理想的实现！

我在哪里可以找到可靠快速的正则表达式实现？

有谁知道.NET或本机的正常非回溯（回溯）线性时间正则表达式实现，并且可以从.NET合理使用？System.Text.RegularExpressions为了有用，它需要：

  • 正则表达式评估的最坏情况时间复杂度为O ( m*n)，其中 m 是正则表达式的长度，n 是输入的长度。
  • 具有O(n) 的正常时间复杂度，因为几乎没有正则表达式实际上触发指数状态空间，或者，如果可以，仅在输入的一分钟子集上这样做。
  • 具有合理的构建速度（即没有潜在的指数 DFA）
  • 旨在供人类使用，而不是数学家 - 例如，我不想重新实现 unicode 字符类： .NET 或 PCRE 样式字符类是一个加号。

奖励积分：

  • 如果它实现了基于堆栈的功能，可以让它以消耗 O(n+m) 内存而不是 O(m) 内存为代价来处理嵌套，那么它的实用性就会得到加分。
  • 捕获子表达式或替换的奖励积分（如果有可能的子表达式匹配的指数数量，那么枚举所有它们本质上是指数的 - 但枚举前几个不应该是，替换也是如此）。您可以通过使用另一个功能来解决缺少任何一个功能的问题，因此拥有一个就足够了。
  • 将正则表达式视为第一类值的很多奖励积分（因此您可以采用并集、交集、连接、否定 - 特别是否定和交集，因为这些很难通过正则表达式定义的字符串操作来实现）
  • 惰性匹配，即在无限流上匹配而不将其全部放入内存是一个优点。如果流不支持查找，则（通常）不可能一次捕获子表达式和/或替换。
  • 反向引用已经过时了，它们根本不可靠；即在给定病态输入案例的情况下，总是可以表现出指数行为。

存在这样的算法（这是基本的自动机理论......） - 但是是否有任何可从 .NET 访问的实际可用的实现？

背景：（可以跳过）

我喜欢使用正则表达式进行快速而肮脏的文本清理，但我反复遇到 perl/java/python/.NET 使用的常见回溯 NFA 实现显示指数行为的问题。不幸的是，一旦您开始自动生成正则表达式，这些情况就很容易触发。当您在匹配相同前缀的正则表达式之间交替使用时，即使是非指数性能也会变得非常差 - 例如，在一个非常基本的示例中，如果您将字典转换为正则表达式，预计性能会很糟糕。

要快速了解为什么存在以及自 60 年代以来存在更好的实现，请参阅正则表达式匹配可以简单快速。

不太实用的选择：

  • 几乎是理想的：FSA 工具包。可以将正则表达式编译为 DFA + NFA 的快速 C 实现，也允许转换器（！），具有一流的正则表达式（封装耶！），包括交集和参数化的语法。 但它在序言中......（为什么具有这种实用功能的东西在主流语言中不可用？？？）
  • 快速但不切实际：完整的解析器，例如优秀的ANTLR ，通常支持可靠的快速正则表达式。但是，antlr 的语法要冗长得多，并且当然允许可能无法生成有效解析器的构造，因此您需要找到一些安全的子集。

好的实现：

  • RE2 - 一个谷歌开源库，旨在实现合理的 PCRE 兼容性减去反向引用。我认为这是作者给出的 plan9 正则表达式库的 unix 端口的继承者。
  • TRE - 也主要与 PCRE 兼容，甚至可以进行反向引用，尽管使用那些你会失去速度保证。并且它有一个超级漂亮的近似匹配模式！

不幸的是，这两种实现都是 C++，并且需要从 .NET 使用互操作。

4

5 回答 5

11

首先，你的建议是可能的，你当然知道你的主题。您还知道不使用反向引用实现的代价是内存。如果您对环境进行了足够的控制，这可能是一种合理的方法。

在继续之前，我唯一要评论的是，我鼓励您质疑使用 RegEx 的选择。您显然更熟悉您的具体问题以及您试图解决的问题，因此只有您才能回答问题。我不认为 ANTLR 会是一个好的选择。但是，自制规则引擎（如果范围有限）可以根据您的特定需求进行高度调整。这完全取决于您的具体问题。

对于那些阅读本文并“错过重点”的人，这里有一些背景阅读：

从同一个站点，此页面上链接了许多实现。

上述文章的整个讨论的要点是，最好的答案是两者都使用。为此，我所知道的唯一广泛使用的实现是 TCL 语言使用的实现。据我了解，它最初是由 Henry Spencer 编写的，它采用了这种混合方法。有一些尝试将其移植到 ac 库，但我不知道有什么被广泛使用。Walter Waldo's 和Thomas Lackner's均在此处提及和链接。还提到了boost 库，尽管我不确定实现。您还可以查看 TCL 代码本身（从他们的网站链接）并从那里开始工作。

简而言之，我会选择TRE或Plan 9，因为它们都受到积极支持。

显然，这些都不是 C#/.Net，我不知道有一个。

于 2009-11-24T01:29:35.857 回答
3

如果您可以使用不安全的代码（和许可问题）来处理，您可以从此TRE windows port获取实施。

您可能可以直接将其与 P/Invoke 和显式布局结构一起使用，以实现以下目的：

typedef int regoff_t;
typedef struct {
  size_t re_nsub;  /* Number of parenthesized subexpressions. */
  void *value;     /* For internal use only. */
} regex_t;

typedef struct {
  regoff_t rm_so;
  regoff_t rm_eo;
} regmatch_t;


typedef enum {
  REG_OK = 0,       /* No error. */
  /* POSIX regcomp() return error codes.  (In the order listed in the
     standard.)  */
  REG_NOMATCH,      /* No match. */
  REG_BADPAT,       /* Invalid regexp. */
  REG_ECOLLATE,     /* Unknown collating element. */
  REG_ECTYPE,       /* Unknown character class name. */
  REG_EESCAPE,      /* Trailing backslash. */
  REG_ESUBREG,      /* Invalid back reference. */
  REG_EBRACK,       /* "[]" imbalance */
  REG_EPAREN,       /* "\(\)" or "()" imbalance */
  REG_EBRACE,       /* "\{\}" or "{}" imbalance */
  REG_BADBR,        /* Invalid content of {} */
  REG_ERANGE,       /* Invalid use of range operator */
  REG_ESPACE,       /* Out of memory.  */
  REG_BADRPT            /* Invalid use of repetition operators. */
} reg_errcode_t;

然后使用能够处理嵌入空值的字符串的导出（具有宽字符支持）

/* Versions with a maximum length argument and therefore the capability to
   handle null characters in the middle of the strings (not in POSIX.2). */
int regwncomp(regex_t *preg, const wchar_t *regex, size_t len, int cflags);

int regwnexec(const regex_t *preg, const wchar_t *string, size_t len,
      size_t nmatch, regmatch_t pmatch[], int eflags);

或者通过 C++/CLI 解决方案包装它，以便更轻松地翻译和更灵活（如果您对 C++/CLI 感到满意，我当然建议这是明智的）。

于 2009-11-24T09:50:35.640 回答
1

我在哪里可以找到稳健快速的正则表达式实现？

你不能。

有人不得不说，鉴于限制，这个问题的答案肯定是你不能 - 你不太可能找到与你的约束相匹配的实现。

顺便说一句，我确定您已经尝试过，但是您是否编译了正则表达式（带有输出到程序集的选项）-我说是因为：

如果您有一个复杂的正则表达式和数百万个短字符串要测试

于 2009-11-23T16:14:05.460 回答
0

考虑如何从正则表达式创建DFA ：

你从一个正则表达式开始。每个操作（concat、union、Kleene 闭包）代表 NFA 中状态之间的转换。得到的 DFA 状态代表 NFA 中状态的幂集。NFA 中的状态与正则表达式的大小成线性关系，因此 DFA 的状态与正则表达式的大小成指数关系。

所以你的第一个约束，

正则表达式评估的最坏情况时间复杂度为 O(m*n)，其中 m 是正则表达式的长度，n 是输入的长度

是不可能的。正则表达式需要编译为 2^m 状态 DFA（最坏情况），这不会在线性时间内完成。

除了最简单的正则表达式之外，所有情况都是如此。那些很简单的，你可以.contains更容易地写一个快速的表达。

于 2009-07-24T14:52:15.910 回答
0

快速评论：仅仅因为您可以通过模拟多个状态来模拟 DFA 构造并不意味着您没有进行 NFA-DFA 转换的工作。不同之处在于您将工作量分配给搜索本身。即，最坏情况下的性能不变。

于 2010-01-06T20:22:31.710 回答