レベンシュテインオートマトン

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

コンピュータサイエンスでは、文字列wと数値nのレーベンシュタインオートマトンwからレーベンシュタイン距離が最大でnであるすべての文字列のセットを認識できる有限状態オートマトンです。つまり、文字列xは、最大n個の単一文字の挿入、削除、および置換によってxをwに変換できる場合にのみ、Levenshteinオートマトンによって認識される形式言語になります。[1]

アプリケーション

Levenshtein automataは、スペルミスのある単語に近い特定の辞書内の単語を見つけることにより、スペル修正に使用できます。このアプリケーションでは、単語のスペルが間違っていると識別されると、そのLevenshteinオートマトンが作成され、辞書内のすべての単語に適用されて、スペルが間違っている単語に近い単語が判別されます。辞書がトライとして圧縮された形式で保存されている場合、このアルゴリズムの時間(オートマトンが構築された後)はトライ内のノードの数に比例し、動的計画法を使用してそれぞれのレーベンシュタイン距離を個別に計算するよりも大幅に高速です辞書の単語。[1]

有限辞書ではなく、特定のターゲット単語に近い正規言語の単語を見つけることもできます。これは、その単語のLevenshteinオートマトンを計算し、 Cartesian製品構造を使用して、次のオートマトンと組み合わせることができます。正規言語、交差言語のオートマトンを提供します。あるいは、製品構成を使用するのではなく、バックトラッキングアルゴリズムを使用して、Levenshteinオートマトンと特定の正規言語のオートマトンの両方を同時にトラバースすることもできます。[1]

Levenshtein automataは、クエリのスペルが間違っている場合でも関連ドキュメントを返すことができる全文検索にLuceneで使用されます。[2]

建設

任意の固定定数nに対して、 wnのLevenshteinオートマトンは時間O(| w |)で構築できます。[1]

Mitankinは、数値パラメーターnによってのみ決定される、ユニバーサルレーベンシュタインオートマトンと呼ばれるこの構造の変形を研究します。これは、互いにレーベンシュタイン距離n内にある単語のペア(ビットベクトルによって特定の方法でエンコードされた)を認識できます。[3] Touzetは、このオートマトンを構築するための効果的なアルゴリズムを提案しました。[4]

しかし、レーベンシュタイン(またはダメラウ-レーベンシュタイン)距離の3番目の有限オートマトン構造は、 Hassanetal。のレーベンシュタイントランスデューサーです、編集距離1を実装する有限状態トランスデューサを示し、一定までの編集距離を実装するためにこれらを構成します。[5]

も参照してください

  • agrep、近似正規表現マッチング用のツール(数回実装)
  • TRE、レーベンシュタインスタイルの編集に耐性のある正規表現マッチング用のライブラリ

参照

  1. ^ a b c d Schulz、Klaus U .; ミホフ、ストヤン(2002)。「Levenshtein-Automataによる高速文字列修正」文書分析と認識の国際ジャーナル5(1):67–85。CiteSeerX10.1.1.16.652 _ 土井10.1007/s10032-002-0082-8S2CID207046453 _
  2. ^ McCandless、Michael(2011年3月24日)。「LuceneのFuzzyQueryは4.0で100倍高速です」ビットの変更2021-06-07を取得{{cite web}}:CS1 maint:url-status(link
  3. ^ Mitankin、Petar N.(2005)。ユニバーサルレベンシュテインオートマタ。建物とプロパティ(PDF)(論文)。ソフィア大学セントクリメントオリドスキー。
  4. ^ Touzet H.(2016)。「LevenshteinAutomatonと単語の近傍のサイズについて」(PDF)言語とオートマトンの理論と応用コンピュータサイエンスの講義ノート。9618.コンピュータサイエンスの講義ノート。pp。207–218。土井10.1007/978-3-319-30000-9_16ISBN  978-3-319-29999-0
  5. ^ ハッサン、アーメド; ノエマン、サラ; ハッサン、ハニー(2008)。有限状態オートマトンを使用した言語に依存しないテキスト修正IJCNLP。