単語一致（先を見越して）アルゴリズムのパフォーマンスを改善する

Question

テキストアノテーションの機能をhttp://mandarinspot.com/annotateに再現しようとしていますが、私は解決策がありますが、スピードの点では私の努力はあまりありません。私は文字列検索アルゴリズムを見て、テクニックはアプリケーションごとに異なるので、私はここでいくつかのポインタを探しています。

このページは、中国語の塊を取り、上にピンインの発音を追加し、定義のツールチップを追加します。このページを再現する理由は次のとおりです。1. Gwoyeu Romatzyhと呼ばれる別の発音システムを使用するのが好きです。2.プログラミングを再学習するために。

私は何をしているのかを説明し、基礎となる中国語を英語で置き換えようとします。 「ゲイリーがブドウとグレープフルーツを食べた」という文字列の場合、「正しい名前」[食物を摂取する] [果物はクラスターで成長する] [大きな柑橘類の果実]のように、各単語の定義を出力する必要があるとしましょう。今では、「ブドウ」と「グレープフルーツ」が同じように始まるので、プログラムはそれらを区別する必要があります（中国語では、文字列の分割はオプションではないので、実際には "Garyateagrapeandagrapefruit" 「グレープフルーツ」の解析時に「先読みする」）。

私のデータ構造は、各ノードが単一の中国語と親のIDを保持するツリー構造です。その文字がフレーズの一部である場合、parentはそのフレーズの前の文字が何であるかを教えてくれます。

例：「ABC」が中国語の場合、AはIDが1で、親IDはなくB：ID = 2および親= 1、C：ID = 3、親= 2です。 "ABD"の場合、DはID = 4、親は2（B）です。各ノードには、その文字または単語の英語定義を保持する別の配列を指す「定義」配列もあります。ノードが単語の最後のものでない場合、「定義」は空白になります。文字列を解析するために

、

1. は、2つの変数に、現在の文字（curChar）、およびそれに続く文字（nextChar）を持ちます。
2. nextCharがノードの文字と一致し、このノードにcurCharが親としてあるノードを検索します。これが本当であれば、私は2文字以上の長い言葉を持っていることがわかります。それが偽であれば、私はcurCharとnextCharの間に関係がないと結論し、私がcurCharまで持っていたものを出力します。

ありがとうございました！

Answer 1

Aho-Corasick in Wikipediaは、ストリームに表示されている辞書のすべての単語を見つける高速なアルゴリズムを提供します。あなたがやっているように、最長の選択肢を選ぶこともできますし、ダイナミックプログラミングを使って、ストリーム内のすべての文字を考慮した単語を見つけることもできます。

Answer 2

ちょっとした提案 - ツリーの代わりにハッシュテーブルを使用するのはどうですか？ローリングハッシュ（Rabin-Karp文字列seachアルゴリズムで使用されているようなもの）と組み合わせて使用​​すると、検索効率が向上し、ハッシュ計算にサブ文字列あたりO（1）がかかり、ルックアップが平均しますケースO（1）。