Loading article…
コンピュータサイエンスにおいて、文字列wと数値nに対するレーベンシュタインオートマトンとは、 wからのレーベンシュタイン距離が最大でnであるすべての文字列の集合を認識できる有限状態オートマトンである。つまり、文字列xがレーベンシュタインオートマトンによって認識される形式言語であるためには、最大でn 回の単一文字の挿入、削除、置換によってx をwに変換できる必要がある。 [1]
アプリケーション
レーベンシュタインオートマトンをスペル訂正に使用して、スペルミスのある単語に近い単語を特定の辞書から見つけることができる。このアプリケーションでは、単語がスペルミスであると識別されると、そのレーベンシュタインオートマトンが構築され、辞書内のすべての単語に適用されて、スペルミスのある単語に近い単語が判別される。辞書がトライ木として圧縮形式で保存されている場合、このアルゴリズムにかかる時間（オートマトンが構築された後）はトライ木内のノードの数に比例し、動的プログラミングを使用して辞書の各単語に対してレーベンシュタイン距離を個別に計算するよりも大幅に高速である。 [1]
有限辞書ではなく通常の言語で、与えられたターゲット単語に近い単語を見つけることも可能です。そのためには、単語のレーベンシュタインオートマトンを計算し、次に直積構成を使用してそれを通常の言語のオートマトンと組み合わせ、交差言語のオートマトンを作成します。あるいは、積構成を使用する代わりに、バックトラッキングアルゴリズムを使用して、レーベンシュタインオートマトンと指定された通常の言語のオートマトンの両方を同時に走査することもできます。[1]
レーベンシュタインオートマトンがLuceneで全文検索に使用され、クエリのスペルミスがあっても関連する文書を返すことができます。[2]
工事
任意の定数nに対して、 wとnに対するレーベンシュタインオートマトンをO(| w |)の時間で構築することができる。[1]
ミタンキンは、数値パラメータnのみで決定され、互いにレーベンシュタイン距離n以内にある単語のペア（ビットベクトルによって特定の方法でエンコードされたもの）を認識できる、この構造の変形であるユニバーサル・レーベンシュタイン・オートマトンを研究している。 [3]トゥゼはこのオートマトンを構築するための効果的なアルゴリズムを提案した。[4]
レーベンシュタイン（またはダメラウ・レーベンシュタイン）距離の3番目の有限オートマトン構成は、ハッサンらによるレーベンシュタイントランスデューサである。彼らは編集距離1を実装する有限状態トランスデューサを示し、次にこれらを組み合わせてある定数までの編集距離を実装する。[5]
参照
参考文献
- ^ abcd Schulz, Klaus U.; Mihov, Stoyan (2002). 「Levenshtein-Automataによる高速文字列修正」 . International Journal of Document Analysis and Recognition . 5 (1): 67–85. CiteSeerX 10.1.1.16.652 . doi :10.1007/s10032-002-0082-8. S2CID 207046453.
- ^ McCandless, Michael (2011 年 3 月 24 日). 「Lucene の FuzzyQuery は 4.0 で 100 倍高速化」. Changing Bits . 2021 年 6 月 7 日閲覧。
- ^ Mitankin, Petar N. (2005). ユニバーサル レーベンシュタイン オートマトン。構築とプロパティ(PDF) (論文). ソフィア大学 聖クリメント オフリドスキ。
- ^ Touzet H. (2016). 「レーベンシュタインオートマトンと単語の近傍のサイズについて」(PDF)。言語とオートマトン理論と応用。コンピュータサイエンスの講義ノート。第9618巻。コンピュータサイエンスの講義ノート。pp. 207–218。doi : 10.1007 / 978-3-319-30000-9_16。ISBN 978-3-319-29999-0.S2CID 34821290 。
- ^ Hassan, Ahmed; Noeman, Sara; Hassan, Hany (2008). 有限状態オートマトンを使用した言語に依存しないテキスト修正。IJCNLP。