正規表現と有限状態法

正規言語に基づいた実用的な技術 — 正規表現によるパターンマッチングと有限状態トランスデューサーによる文字列から文字列へのマッピング — は、トークン化、正規化、形態素解析を効率的に処理します。

Definition

有限状態法とは、パターンとマッピングが正規表現または有限状態オートマトンおよびトランスデューサーとして表現され、効率的な線形時間認識を保証する言語処理技術です。

Scope

文字列に対するパターン言語としての正規表現、その計算上の実現としての有限状態オートマトンとトランスデューサー、およびそれらのテキスト正規化、トークン化、スペル、計算形態論への応用を扱います。音声処理や浅い処理で使用される重み付き有限状態法も含まれます。完全な音韻論的理論と深い構文解析は範囲外です。

Core questions

• 正規表現はどのようにしてテキストパターンを正確に指定し、抽出できるのでしょうか？
• 有限状態トランスデューサーは、形態論のように、表層形を語彙分析にどのようにマッピングするのでしょうか？
• トークン化と正規化において、有限状態法が好まれるのはなぜでしょうか？

Key concepts

• 正規表現
• 有限状態トランスデューサー
• トークン化
• テキスト正規化
• 形態素解析
• 二段階形態論
• 重み付きオートマトン
• 編集距離

Key theories

形態論と音韻論の正規モデル

音韻書き換え規則と形態論的交替が有限状態トランスデューサーにコンパイルできるという結果は、分析と生成を単一の効率的なフレームワークに統合します。

正規表現と有限オートマトンの等価性

正規表現、正規文法、有限状態オートマトンはすべて正確に正規言語を記述するため、宣言的なパターンを効率的な認識器にコンパイルできます。

History

正規表現はクリーネの研究から計算機科学に導入され、テキストツールで広く普及しました。1980年代には、コスケンニエミの二段階形態論とカプランおよびケイによる音韻規則のトランスデューサーへのコンパイルにより、有限状態技術が形態素処理の主力となり、ビーズリーとカートゥネンのハンドブックでこのアプローチが確立されました。

Debates

有限状態法はどこまでスケールできるのか？

有限状態技術は非常に効率的ですが、正規現象に限定されます。この議論は、よりリッチな統計モデルやニューラルモデルと比較して、どの言語処理タスクが有限状態法によって最もよく処理され続けるかに関係しています。

Key figures

• Martin Kay
• Ronald Kaplan
• Kimmo Koskenniemi
• Lauri Karttunen

Seminal works

• kaplan1994
• beesley2003

Frequently asked questions

形態論において、単なるルックアップテーブルではなく有限状態トランスデューサーを使用する理由は何ですか？

トランスデューサーは体系的な交替をコンパクトに符号化し、これまで見たことのない語形を分析または生成できますが、テーブルは明示的にリストされた語形のみを保存します。