16

編集 2:これが依然として重要である理由の実用的なデモンストレーションについては、 stackoverflow 自身の正規表現による停止 (2016-07-20) を参照してください。

編集：この質問は、私が最初に尋ねたときからかなり進化しました。2 つの高速で互換性があるが、完全な機能を備えていない実装については、以下を参照してください。より多くの、またはより優れた実装を知っている場合は、それらについて言及してください。ここにはまだ理想的な実装はありません!

確実に高速な正規表現の実装はどこにありますか?

.NETまたはネイティブで.NETから合理的に使用できる、通常の非バックトラッキング(バックトラック)線形時間正規表現の実装を知っている人はいますか? System.Text.RegularExpressions有用であるためには、次のことが必要です。

  • 正規表現の長さを m、入力の長さを n とすると、最悪の場合の正規表現評価の時間複雑度はO(m*n)になります。
  • O(n) の通常の時間の複雑さを持ちます。これは、正規表現が実際に指数状態空間をトリガーすることはほとんどないか、可能であれば、入力のわずかなサブセットでのみトリガーするためです。
  • 合理的な構築速度がある(つまり、潜在的に指数関数的な DFA がない)
  • 数学者ではなく、人間が使用することを意図したものにする - たとえば、Unicode 文字クラスを再実装したくない: .NET または PCRE スタイルの文字クラスはプラスです。

ボーナスポイント：

  • O（m）メモリではなくO（n + m）メモリを消費してネストを処理できるスタックベースの機能を実装する場合、実用性のボーナスポイント。
  • 部分式または置換をキャプチャするためのボーナス ポイント(部分式の一致の可能性が指数関数的に存在する場合、それらすべてを列挙することは本質的に指数関数的ですが、最初のいくつかを列挙することはすべきではなく、置換についても同様です)。他の機能を使用することで、どちらかの機能が欠けていることを回避できるため、どちらかがあれば十分です。
  • 正規表現をファーストクラスの値として扱うための多くのボーナスポイント（したがって、結合、交差、連結、否定を取ることができます-特に否定と交差は、正規表現定義の文字列操作によって行うのが非常に難しいため）
  • 遅延マッチング、つまり、すべてをメモリに入れずに無制限のストリームでマッチングすることはプラスです。ストリームがシークをサポートしていない場合、部分式や置換をキャプチャすることは (一般に) 1 回のパスでは不可能です。
  • 後方参照は outです。基本的に信頼できません。つまり、異常な入力ケースが与えられると、常に指数関数的な動作を示すことができます。

そのようなアルゴリズムは存在します (これは基本的なオートマトン理論です...) - しかし、.NET からアクセスできる実際に使用可能な実装はありますか?

背景: (これはスキップできます)

私は迅速で汚れたテキストのクリーンアップに Regex を使用するのが好きですが、perl/java/python/.NET で使用される一般的なバックトラッキング NFA 実装が指数関数的な動作を示すという問題に繰り返し遭遇しました。残念ながら、これらのケースは、正規表現の自動生成を開始するとすぐに、かなり簡単にトリガーされます。同じプレフィックスに一致する正規表現を交互に使用すると、指数関数的でないパフォーマンスでさえ非常に悪くなる可能性があります。たとえば、非常に基本的な例で、辞書を取得して正規表現に変換すると、ひどいパフォーマンスが予想されます。

より優れた実装が存在し、60 年代以降存在している理由の簡単な概要については、「正規表現の照合はシンプルかつ高速にできる」を参照してください。

あまり実用的ではないオプション:

  • ほぼ理想的: FSA ツールキット。正規表現を DFA + NFA の高速な C 実装にコンパイルでき、変換器 (!) も許可され、交差とパラメーター化の構文を含むファーストクラスの正規表現 (カプセル化 yay!) があります。 しかし、それはプロローグです...（この種の実用的な機能を備えたものが主流の言語で利用できないのはなぜですか???）
  • 高速ですが実用的ではありません: 優れたANTLRなどの完全なパーサーは、一般的に確実に高速な正規表現をサポートします。ただし、antlr の構文ははるかに冗長であり、もちろん、有効なパーサーを生成しない可能性のある構成を許可するため、安全なサブセットを見つける必要があります。

良い実装:

  • RE2 - 適切な PCRE 互換性から後方参照を除外することを目的とした Google オープン ソース ライブラリ。作者によると、これは plan9 の正規表現 lib の unix ポートの後継だと思います。
  • TRE - PCRE とほとんど互換性があり、逆参照も行いますが、それらを使用すると速度の保証が失われます。しかも超おまけマッチングモード搭載！

残念ながら、どちらの実装も C++ であり、.NET から使用するには相互運用が必要です。

4

5 に答える 5

11

まず、あなたの提案が可能であり、あなたは確かにあなたの主題を知っています. また、後方参照の実装を使用しないことのトレードオフがメモリであることもわかっています。環境を十分に制御している場合、これはおそらく合理的なアプローチです。

続行する前にコメントする唯一のことは、RegEx を使用するという選択について質問することをお勧めすることです。あなたは、特定の問題と解決しようとしていることを明らかによく知っているので、質問に答えることができるのはあなただけです。ANTLR が良い代替手段になるとは思いません。ただし、自作のルール エンジン (範囲が限られている場合) は、特定のニーズに合わせて高度に調整できます。それはすべて、特定の問題に依存します。

これを読んで「要点が分からない」人のために、背景情報を以下に示します。

同じサイトから、このページにリンクされている実装が多数あります。

上記の記事の全体的な議論の要点は、最善の答えは両方を使用することであるということです。そのために、私が知っている唯一の広く使用されている実装は、TCL 言語で使用されているものです。私が理解しているように、もともとはヘンリー スペンサーによって書かれ、このハイブリッド アプローチを採用しています。それをacライブラリに移植する試みがいくつかありましたが、広く使用されているものは知りません. Walter Waldo とThomas Lackner の両方が言及され、ここにリンクされています。実装についてはわかりませんが、ブーストライブラリについても言及されています。TCL コード自体 (サイトからリンク) を見て、そこから作業することもできます。

要するに、TREまたはPlan 9を使用します。どちらも積極的にサポートされているからです。

明らかに、これらのどれも C#/.Net ではなく、私はそれを認識していません。

于 2009-11-24T01:29:35.857 に答える
3

アンセーフ コードの使用 (およびライセンスの問題) を処理できる場合は、この TRE Windows ポートから実装を取得できます。

これを 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;

次に、null が埋め込まれた文字列を処理できるエクスポートを使用します (ワイド文字のサポートあり)。

/* 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 構築をシミュレートできるからといって、NFA-DFA 変換の作業を行っていないわけではありません。違いは、検索自体に労力を分散していることです。つまり、最悪の場合のパフォーマンスは変わりません。

于 2010-01-06T20:22:31.710 に答える
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 に答える