2

特定のルールに応じて入力テキストをトークン化するプログラムを作成しています。これにはC++を使用しています。

ルール

Letter 'a' should be converted to token 'V-A'
Letter 'p' should be converted to token 'C-PA'
Letter 'pp' should be converted to token 'C-PPA'
Letter 'u' should be converted to token 'V-U'

これは単なるサンプルであり、リアルタイムでこのような約 500 以上のルールがあります。「 appu 」として入力を提供している場合、「 VA + C-PPA + VU 」のようにトークン化する必要があります。これを行うためのアルゴリズムを実装しましたが、正しいことをしていることを確認したかったのです。

アルゴリズム

すべてのルールは、対応するトークンへのマッピングとともに XML ファイルに保持されます。何かのようなもの

<rules>
  <rule pattern="a" token="V-A" />
  <rule pattern="p" token="C-PA" />
  <rule pattern="pp" token="C-PPA" />
  <rule pattern="u" token="V-U" />
</rules>

1 - アプリケーションの開始時に、この xml ファイルを読み取り、値を「std::map」に保持します。これは、アプリケーションの終了 (シングルトン パターンの実装) まで使用できます。

2 - 入力テキスト文字を繰り返します。各文字について、一致するものを探します。見つかった場合は、より貪欲になり、入力テキストから次の文字を取得して、より多くの一致を探します。一致しない状態になるまでこれを行います。したがって、入力テキスト ' appu ' については、まず ' a 'に一致するものを探します。見つかった場合は、入力テキストから次の文字を取得して、さらに一致するようにします。そのため、' ap ' との一致を試みますが、一致するものは見つかりませんでした。だからそれはただ戻ってくる。

3 - トークンを取得したので、入力テキストの文字「a」を置き換えます。

4 - 入力テキストの残りの文字で手順 2 と 3 を繰り返します。

手順のより簡単な説明は次のとおりです

input-text = 'appu'
tokens-generated=''

// First iteration
character-to-match = 'a'
pattern-found = true

// since pattern found, going recursive and check for more matches
character-to-match = 'ap'
pattern-found = false

tokens-generated = 'V-A'

// since no match found for 'ap', taking the first success and replacing it from input text
input-text = 'ppu'

// second iteration
character-to-match = 'p'
pattern-found = true

// since pattern found, going recursive and check for more matches
character-to-match = 'pp'
pattern-found = true

// since pattern found, going recursive and check for more matches
character-to-match = 'ppu'
pattern-found = false

tokens-generated = 'V-A + C-PPA'

// since no match found for 'ppu', taking the first success and replacing it from input text
input-text = 'u'

// third iteration
character-to-match = 'u'
pattern-found = true

tokens-generated = 'V-A + C-PPA + V-U'  // we'r done!

質問

1 - このアルゴリズムはこの問題に適しているように見えますか、それともこの問題に対処するためのより良い方法はありますか?

2 - これが正しい方法である場合、std::map はここで適切な選択ですか? または、独自のキー/値コンテナーを作成する必要がありますか?

3 - 上記のように文字列をトークン化できるライブラリはありますか?

どんな助けでもいただければ幸いです

:)

4

5 に答える 5

3

では、マップ内のすべてのトークンを調べて一致を探していますか? そこでは、リストまたは配列を使用することもできます。とにかく非効率な検索になります。

マッチの開始または継続に適したトークンだけを見つけるより効率的な方法は、それらをtrieとして保存することです。そこにある文字を検索すると、その文字を最初の文字として持つトークンのみを含むサブトライが得られ、可能な限り下方向に検索を続けます。

編集：これについてもう少し説明させてください。

最初に、名前を超えてこれらの C++ に精通していないことを説明する必要がstd::mapあります。これは、特定のプログラミング言語の特定のライブラリの詳細だけでなく、このようなものの理論を学ぶ理由の完璧な例です:ライブラリは「マップ」という名前をひどく誤用しています (これはかなりありそうもないことですが)、名前自体がデータ構造の特性について多くのことを教えてくれます。たとえば、単一のキーとマップが与えられると、そのキーに関連付けられた値を非常に効率的に検索して返す関数が存在すること、およびリストを提供する関数も存在する可能性が高いことを知っています。 /array/すべてのキーのうち、独自のコードを使用して自分で検索できます。

あなたのデータ構造の私の解釈は、キーがパターンと呼ばれるものであり、キーが文字のリスト（または配列、またはその性質のもの）であり、値がトークンであるマップがあるということです。したがって、完全なパターンがあれば、それに関連付けられているトークンをすばやく見つけることができます。

残念ながら、このようなマップは XML 入力形式を内部データ構造に変換するのには適していますが、必要な検索には適していません。パターン全体を検索するのではなく、パターンの最初の文字を検索して、可能なトークンのセットを生成し、その後、その最初の検索によって生成されたパターンのセット内からパターンの 2 番目の文字を検索することに注意してください。すぐ。

したがって、本当に必要なのは単一のマップではなく、それぞれが単一の文字でキー設定されたマップのマップのマップです。pトップレベルで「p」を検索すると、トークンを生成する とC-PPAトークンを生成する「その他」の2 つのキーを持つ新しいマップが得られますC-PA。これは実質的にトライデータ構造です。

これは理にかなっていますか？

最初に構文解析コードを次のように書くことから始めると、役に立つかもしれません: 必要なルックアップを行う関数を他の誰かが書くと想像してみてください。構文解析コードを作成し、必要なこれらの任意の関数を使用して任意のインターフェイスを作成し、可能な限りシンプルかつクリーンにすることに集中します (ただし、単純化してすべてを 1 つの関数に置き換えることはありません!)。これで、最終的に得られたルックアップ関数を見ることができます。これにより、データ構造にアクセスする必要がある方法がわかります。これにより、必要なデータ構造のタイプが導き出されます。それを理解したら、それをロードする方法を考え出すことができます。

于 2009-05-24T05:40:37.683 に答える
1

さらに良いことに、ブースト ライブラリを使用する場合は、Boost トークナイザー ライブラリが常に存在します -> http://www.boost.org/doc/libs/1_39_0/libs/tokenizer/index.html

于 2009-05-24T05:55:45.410 に答える
1

  1. この方法は機能します。効率的かどうかはわかりませんが、機能するはずです。

  2. 独自のシステムではなく、標準の std::map を使用します。

  3. lexこれに使用できる(または)のようなツールがありますflex。問題は、XML 仕様が変更されたときに構築される語彙アナライザーを再生成できるかどうかです。lexXML 仕様が頻繁に変更されない場合は、スキャンやマッピングをより簡単に行うためのツールなどを使用できる場合があります。プログラムを使用している人の気まぐれで XML 仕様が変更される可能性がある場合は、lexおそらくあまり適切ではありません。

いくつかの注意点があります。特に、C++ ではなく と の両方が C コードlexを生成することです。flex

egrepまた、パターン マッチング テクノロジ(特に使用する種類のもの) を検討することも検討します。これには、実行時に処理できるというメリットがあります (egrep常に処理するため)。または、Perl、Python などのスクリプト言語を使用することもできます。または、PCRE (Perl 互換正規表現) ライブラリのようなものを検討することもできます。

于 2009-05-24T05:43:58.693 に答える
1

正規表現 (おそらく boost::regex ライブラリ) を使用できます。すべてのパターンが単なる文字列である場合、"(a|p|pp|u)" のような正規表現は貪欲な一致を見つけます。そう：

  1. 上記のパターンを使用して regex_search を実行し、次の一致を見つけます
  2. マッチ テキストを std::map にプラグインして、置換テキストを取得します。
  3. 一致しない消費された入力と置換テキストを出力に出力し、残りの入力で 1 を繰り返します。

そして完了。

于 2009-05-24T05:46:59.687 に答える
1

少し複雑に思えるかもしれませんが、これを行う最も効率的な方法は、グラフを使用してステート チャートを表すことです。最初は、boost.statechartが役立つと思っていましたが、あまり適切ではないと考えました。この方法は、単純な std::map を使用するよりも効率的です。多くのルールがあり、可能な文字数が制限されており、読み取るテキストの長さが非常に長い場合。

とにかく、単純なグラフを使用して：

0) 「開始」頂点でグラフを作成

1) xml 構成ファイルを読み取り、必要に応じて頂点を作成します (1 つの「文字セット」(「pp」など) から別の文字セット (「ppa」など) への移行)。各頂点内に、次の頂点への遷移テーブルを格納します。「キーテキスト」が完成したら、頂点を最終としてマークし、結果のテキストを保存します

2) テキストを読み、グラフを使用して解釈します。「開始」頂点から開始します。( * ) table を使用して、1 つの文字を解釈し、新しい頂点にジャンプします。新しい頂点が選択されていない場合、エラーが発生する可能性があります。それ以外の場合、新しい頂点が最終的​​な場合は、結果のテキストを出力し、最初の頂点に戻ります。解釈するテキストがなくなるまで (*) に戻ります。

boost.graphを使用してグラフを表すこともできますが、必要なものに対しては複雑すぎると思います。独自のカスタム表現を作成します。

于 2009-05-24T21:09:13.417 に答える