9

データ ストリームで動作する正規表現マッチングの実装を探しています。つまり、ユーザーが一度に 1 文字ずつ渡して、文字ストリームで一致が見つかったときにレポートできる API を備えています。これまでに見た。非常に基本的な (古典的な) 正規表現のみが必要なので、DFA/NFA ベースの実装が問題に適しているようです。

単一の線形スイープで DFA/NFA を使用して正規表現マッチングを実行できるという事実に基づいて、ストリーミングの実装が可能であるように思われます。

要件：

  • ライブラリは、一致を実行する前に文字列全体が読み取られるまで待機しようとすべきではありません。私が実際に持っているデータはストリーミングです。どのくらいのデータが到着するかを知る方法はありません。前方または後方にシークすることはできません。

  • ユーザーがどのようなパターンを探しているかは事前にわからないため、いくつかの特殊なケースに特定のストリーム マッチングを実装することはできません。

  • 言語: C/C++から使用可能

興味深いことに、私の使用例は次のとおりです。完全なシステム エミュレータ内でメモリ書き込みをインターセプトするシステムがあり、正規表現に一致するメモリ書き込みを識別する方法が必要です (たとえば、これを使用してURL がメモリに書き込まれるシステム内のポイントを見つけます)。

見つけた：

ストリームに正規表現を適用しますか?

Java I/O ストリームへの正規表現の適用

Code Guru - .NET Framework を使用した正規表現ストリーム検索の構築

ただし、これらはすべて、最初にストリームを文字列に変換してから、標準の正規表現ライブラリを使用しようとします。

もう 1 つの考えは、RE2 ライブラリを変更することでしたが、著者によると、文字列全体が同時にメモリ内にあるという前提に基づいて設計されています。

何も利用できない場合は、自分のニーズに合わせてこの車輪を再発明するという不幸な道を歩み始めることができますが、それを避けることができれば、本当にしたくありません. どんな助けでも大歓迎です！

4

4 に答える 4

5

私はまさにあなたが探しているものを持っています: https://github.com/agentzh/sregex http://agentzh.org/misc/slides/yapc-na-2013-sregex.pdf </p>

JavaScript を知っている (または JavaScript のバージョンが必要な) 場合は、既存の RE 実装を使用して簡単に実行できる演習があります: https://github.com/dhruvbird/regexp-js

于 2013-10-28T18:32:44.743 に答える
2

Intel は、必要なことを正確に実行するhyperscanライブラリをリリースしました。ここでは、その概要を簡単に説明します。

于 2016-05-25T09:11:10.713 に答える
0

残念ながら、これに対する「答え」は、これを行うためのビルド済みライブラリがないことです。代わりに、次の妥協案を選択しました。単純な文字列マッチャー (RE サポートなし) を実装しました。これは、ストリームごとおよび検索文字列ごとに 1 つのカウンターを使用して状態を保持し、そのストリームで一致した検索文字列の文字数を追跡します。正しい文字ごとにインクリメントされ、一致しない文字が見つかるとゼロにリセットされます。これは高速であり、メモリ オーバーヘッドもあまり必要としません。

より複雑な検索の場合は、代わりにすべてのストリームをディスクにダンプしてから、従来のツールを使用してそれらを検索します。非常に遅いですが、幸いなことに、ほとんどのユースケースは単純な文字列の一致だけでうまくいきます。

于 2013-03-06T03:22:07.677 に答える
0

Brian W. Kernighan と Rob Pike による、このような古い grep 実装を見てください。それらはバッファ内のテキストのストリームを処理し、BRE でさえない単純な正規表現ルールに適用します。

于 2012-11-15T23:31:33.360 に答える