各行の複数の（15+）正規表現に対してテキストの本文を解析する最良の方法は何ですか？

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

質問

スキャンする必要があるテキストの本文があり、各行には少なくとも2つ、時には4つの情報部分が含まれています。問題は、各行が15〜20の異なるアクションのうちの1つになる可能性があることです。

ルビーでは、現在のコードは次のようになります。

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

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

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

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

これは明らかに「問題」です。 すべての正規表現を1つにまとめることで（C ++では50％マージンで）高速化することができましたが、それでも必要な速度ではありません-これらの数千のファイルを高速で解析する必要があります！

今、私はそれらを正規表現と照合します-しかし、これは非常に遅いです。私はルビーで始めて、スピードを上げてそれが起こらないことを期待して、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をテストして、さらに先に進むことができるかどうかを確認していますが、現時点では、精神の結果に非常に満足しています。

関連する質問：複数の正規表現に対して1つの文字列を効率的に照会します。

役に立ちましたか？

解決

お勧めします

幸運

他のヒント

Boost.Spirit は、詳細なパーサー分析を行うことができる素晴らしいライブラリです。生成され、コードに直接コンパイルされます。動的に計算されたソリューションよりもはるかに高速です。構文の大部分は式テンプレート（多くのオーバーロードされた演算子の派手な用語）を使用して行われます。つまり、実際にコードに直接記述します。

Perlを使用している場合、これを行う1つの方法があります。
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を使用するパーサージェネレータです。私は最近、正規表現の重い手書きパーサーを短い文法に置き換えるのがとても楽しいと感じました。

正規表現の一致は重複しますか？つまり、2つ以上の正規表現が同じ行に一致する場合、それらは常に行の異なる部分に一致しますか（重複なし）？

一致が重複しない場合は、現在の15個の正規表現を組み合わせた1つの正規表現を使用して検索を実行します。

regex1|regex2|regex3|...|regex15

15個の正規表現のどれが一致したかを判別できるようにする必要がある場合は、キャプチャグループを使用します。

長い正規表現でデータを1回検索すると、15回検索するよりも高速になります。どれくらい速くなるかは、使用している正規表現エンジンと正規表現の複雑さに依存します。

Perlで簡単なテストを試してください。 「研究」について読む関数。私が試したいのは：

  • ファイル全体、またはこれらのファイルが単一の文字列に非常に大きい場合は多数の行を読み取ります
  • 各行の先頭に行番号を追加します。
  • ＆quot;研究＆quot;文字列。これにより、文字ごとにルックアップテーブルが作成され、大きくなることがあります。
  • 改行で区切られた文字列で正規表現一致を実行します（mおよびs正規表現修飾子を使用します）。式は、データとともに行番号を抽出する必要があります。
  • 行番号でインデックス付けされた配列項目をその行で見つかったデータに設定するか、さらに賢いことをします。
  • 最後に、配列に保存されたデータを処理できます。

試したことはありませんが、面白いかもしれません。

このために使用する派手なクアッドまたはオクトコアサーバーがある場合の別のアイデア。

作業を分割する処理パイプラインを構築します。ステージ1は、ファイルを1つのゲームに分割するか、それぞれに手渡し、データを読み取り、処理して何らかの方法で、おそらく別のマシンのデータベースに出力する8つのステージ2パイプの1つにそれぞれを書き込むことができます。

私の経験では、これらのパイプベースのマルチプロセス設計は、マルチスレッド設計とほぼ同じくらい速く、デバッグがはるかに簡単です。パイプの代わりにネットワークソケットを使用してマシンのクラスターをセットアップするのも簡単です。

OK、これは物事をより明確にします（ポーカーのハンド履歴）。統計ツールを作成していると思います（攻撃性、対決、自発的にポットに$を入れるなど）。そのために過度の速度が必要な理由がわかりません。 16個のテーブルでマルチテーブルをしている場合でも、手は中程度の速度でくすぐります。

Rubyはわかりませんが、Perlでは、重要な部分を$ 1、$ 2などに入れると同時に、小さなswitchステートメントを実行します。私の経験では、これは文字列の比較よりも遅くありません。そして、他の手段で行を分割します。

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; }; };

あなたが本当にもっと速くできるとは思いません。最初の位置で最も発生する行（おそらくfoldステートメント）と最後にまばらにしか発生しない行（新しいハンドの開始、＆quot; *** NEXT PHASE ***＆quot; ）。

実際のファイル読み取りがボトルネックであることがわかった場合は、大規模ファイルのアドレス指定に使用できるモジュールを確認できます。 Perlの場合、 Tie :: File が思い浮かびます。

各ハンドを一度だけ読むようにしてください。各ハンドの後にすべてのデータを再度読み取らないでください。代わりにすでに解析されたハンドIDのハッシュテーブル。

このような問題については、目を閉じてLexer + Parserジェネレーターを使用します。おそらく手で最適化することでそれを打ち負かすことができますが、ジェネレータを使用する方がはるかに簡単です。また、入力が突然変化したときの方がはるかに柔軟です。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top