0

文字列「abacabacabadcdcdcd」があり、単純なルールセットを適用したいとします。

アバカ->a

dcd-> d

左から右に向かって、文字列は「abad」になります。この出力は、決定を下すために使用されます。ルールが適用された後、出力文字列が「abad」などのプリセット文字列と一致しない場合、元の文字列は破棄されます。元。すべての弦は「abad」まで蒸留する必要があります。そうでない場合はキックします。

現在、これを正規表現としてハードコーディングしていますが、これらの小さなルールセットのインスタンスは多数あります。一連の単純なルールを取り、文字列をフィードして結果を取得できるものにコンパイル（または関数だけ？）するものを探しています。ルールセットは互いに独立しています。

入力は厳密に制御され、使用されるルールは単純になります。スピードは最も重要な側面です。

バイソンとANTLRを見てきましたが、それほど強力なものは必要ないと思います...

私は何を探していますか？

編集：文字列は2文字で構成されていることに言及する必要があります。通常は5、つまり「abcde」です。スペースなどはありません。文字だけです。

4

1 に答える 1

1

迅速に処理する場合は、ルールを文字列のキーと値のペアとして含むマップから始めることができます。次に、このマップをある種のステート マシン、char キーを持つツリーにコンパイルできます。関連付けられた値は、置換文字列または別のツリーのいずれかです。

次に、文字列を 1 文字ずつ処理します。ツリーで現在の文字を検索します。別の木を見つけたら、その木で次の文字を調べます。ある時点で、次のいずれかを行います。

  1. ルックアップは失敗し、これまで見てきた文字列がどのルールのプレフィックスでもないことがわかります。現在のキャラクターをスキップして、次のキャラクターに進むことができます。
  2. または、置換文字列を取得します。その場合、現在の文字と最後に検索した文字の間の文字を置換文字列で置き換えることができます。

唯一の問題は、置換自体が置換するパターンの一部である場合です。例：

ab -> e
cd -> b

入力:

acd -> ab (by rule 2)
ab   -> e (by rule 1) ????

ここで問題は、ab を e にするために再考するかどうかです。

その場合、交換のたびに最初からやり直す必要があります。さらに、右辺が左辺よりも短いという規則がすべてある場合を除いて、置換が終了するかどうかを判断するのは困難です。その場合、有限の文字列は有限の時間で縮小されます。

しかし、再考する必要がなければ、上記のアルゴリズムは文字列をそのまま処理します。

于 2013-03-12T22:04:01.070 に答える