5

私はPythonでレンマタイザーを構築しています。リアルタイムで実行/かなり大量のデータを処理する必要があるため、処理速度が重要です。データ: 組み合わせることができるすべての単語タイプにリンクされているすべての可能な接尾辞があります。さらに、ワードタイプとレンマの両方にリンクされているレンマフォームがあります。プログラムは入力として単語を受け取り、その補題を出力します。単語 = 補題 + 接尾辞

例 (注: 例は英語で示されていますが、私は英語のレンマタイザーを作成していません):

言葉：禁止

見出し語: 禁止

接尾辞:ing

レンマ: 禁止する

私の解決策：

データを（ネストされた）辞書に変換しました：

suffixdict : {suffix1:[type1,type2, ... , type(n)], suffix2:[type1,type2, ... ,
type(n)]}    
lemmaformdict : {lemmaform:{type1:lemma}}

1) 可能なすべての接尾辞とそれらがリンクされている単語の種類を見つけます。可能な限り長い接尾辞が 3 文字の長さである場合、プログラムは 'ing'、'ng'、'n' を suffixdict のキーに一致させようとします。キーが存在する場合、値 (ワードタイプのセット) を返します。

2) 一致するサフィックスごとに、dict からレンマフォームを検索します。lemmaform が存在する場合、wordtypes を返します。

3) 最後に、プログラムはステップ 1) と 2) で生成された単語タイプの交差を試み、交差が成功した場合、単語のレンマを返します。

私の質問: 速度の観点から、私の問題に対するより良い解決策はありますか? (頻繁な単語と補題を辞書に保持するオプションを無視して) 大いに感謝します。

4

2 に答える 2

6

これは、有限状態トランスデューサの素晴らしいアプリケーションになります。なんで？文字列の書き換えを効率的に行うことができるためです (時間は入力のサイズに比例します)。次の単純な変換器を考えてみましょう:

ここに画像の説明を入力

入力として文字列を受け取り、入力文字のシーケンスが与えられたときに、初期状態 (ここでは 0) から最終状態 (それぞれ 10、12、17) へのパスが存在するかどうかをチェックします。最終状態に達すると、適切な出力が生成されます。たとえば、入力が「禁止」の場合は (禁止、ING) が生成されます。

ただし、有限状態オートマトンのバックグラウンドがあるかどうかはわかりません。そうでない場合は、試してみてください。努力する価値があります。:)トライは特別な種類の有限状態オートマトンです (上記のトランスデューサのサンプルはトライです)。

于 2012-03-23T17:49:00.633 に答える
2

認識された接尾辞の完全なセットをカバーする非決定論的 トライ オートマトンを使用することを検討しますが、単語を後方に分析します。非決定論的であることは、マシンが一度に複数の状態になる可能性があることを意味し、それらの状態のいずれかが受け入れている場合、マシン全体は受け入れ状態になります。

初期状態は受け入れ状態であるため、接尾辞を認識できません (英語のようにbe)。たとえば、初期状態から遷移()、('e', 'z', 'i')、('e', 'd', 'a')およびはすべて受理状態に到達し、NFA を使用する場合('e', 'v', 'o')は競合する を心配する必要はありません。'e'

初期状態から、各単語の「文字」は逆方向にフィードされます。マシンが受け入れ状態になるたびに、単語の残りの部分が検索され、lemmaformdictすべての結果が保持されます。次に、マシンの状態が null になるまで処理が続行されます (単に受け入れないだけではありません)。

その時点で、道に沿って示された補題の合計の選択は、文脈から取り除かれたその単語の可能な解釈につながります (そして、それは常に小さい数でなければなりません)。

NFA をどのように実装するかによって、パフォーマンスが決まります。NFA は一度構築されると DFA に変換できるため、マシンは常に 1 つの状態しか持たないため、マシンの構築を複雑にすることなくパフォーマンスを向上させることができます。欠点としては、個々の文字レベルで入力を処理する必要があるため、Python の場合はパフォーマンスが低下する可能性があります。(しかし、パフォーマンスが重要な場合は、 C++ に切り替える必要があります。)

于 2012-03-23T19:39:43.920 に答える