オートマトン形態分析装置
形態を分析するためのプログラムを作成する方法に関する記事は、ときどき大騒ぎをスキップします。 ほとんどの場合、作成者はデータベース、または辞書などの標準構造を使用します。 しかし、これは必ずしも便利ではありません。 まず、速度が低下します。 第二に、なじみのない単語の形態を予測するなどの一部のアルゴリズムは、自明ではありません。
ここでは、これらの問題を回避しようとする状態マシンに基づいたバージョンを提供します。 どのように機能するかはここで見ることができます 。
形態学から何が欲しいのでしょうか。 通常、形態分析モジュールが必要です。
これらすべてを、形態学的辞書とオートマトンのライブラリという2つの要素から準備します。 LGPLのおかげで、 aot.ruプロジェクトから（既に受け入れられているように）最初に取得したもの。 また、オートマトンライブラリはこちらから： openfst.org 。 コードは最小化されます。必要な操作はすべてライブラリに既に実装されています。
形態学的辞書には、次の形式の行が含まれています。
「ヘイズ」という言葉の例を次に示します。 MGLという文字は、単語のルートです。 残りはエンディング（語形変化）です。 ルートと最初の変曲（この場合はMGLA）を追加することで、補題または正規化された単語を取得できます。 小さな2文字の組み合わせはアノードです。 つまり これは、単語形式の形態を一意に定義するコードです。 たとえば、「ga」の場合、「名詞、女性、単数、主格」です。
アクションに移りましょう。 辞書の各行に対して、この構造を構築します。
これが最終的なコンバーターです。 次のように機能します。 各遷移は2文字でマークされ、最初の記号は入力記号、2番目の記号は出力記号です。 初期状態から最終状態までのいずれかのパスに沿って着信シンボルと発信シンボルを「収集」すると、2つの単語が得られます。 魔法は、ここで入力語がその語の形態学的形式の1つになり、出力が補題+陽極になることです。 たとえば、このマシンに「GLOGO」という単語を「フィード」することで、「MGLAMg」を取得できます。 「-」は空の文字を示しているため、グラフを読み終えると無視できます。
一般に、標準の構成操作を使用して、入力によって出力ワードを取得できます。
Dが上の図のように辞書である場合、
Wは単語で、W = <（M、M）（G、D）（L、L）（O、O）（Y、Y）、（I、I）>
その場合、M-合成の結果-は等しくなります（空文字を除く）
M = W o D = <（M、M）（G、D）（A、A）（A、A）（a、a）（m、m）
上の図の構造には問題があります。 彼女は最適ではありません。 1つ目は、コンバータを無用に「膨張」させる余分な空文字です。 第二に、このコンバーター自体は最適ではありません。 完全な辞書のためにこのような構造を構築すると、後者は非常に大きくなります。
そのため、最初に発信シンボルを初期状態にシフトします。 これにより、空の文字の数が減ります。 openfstライブラリは、このような操作を実装しています。 fstpushと呼ばれます。
図からわかるように、マーク「-：-」の付いた円弧が表示されました。 パッケージングプロセス中に削除されます。
次に、コンバーターをパックします。 ここには微妙さがあります。 一般的に、最終ドライブは通常のステートマシンのようにパッケージ化することはできません。 事実、コンバーターとオートマトンを最小化するためには、コンバーターを決定する必要があります（各入力ワードには固有の出力があります）。 しかし、このコンバーターはそうではありません。
この問題を解決するには、次のことができます
これらの操作はすべて標準であり、コードを記述する必要はありません。 下の画像の「ヘイズ」という単語の結果。
図からわかるように、状態と遷移の数は著しく減少しました。 そして、これが私たちの目標です。
ここではすべてが簡単です。 必要なのは、着信ワードWが2つのコンバーターを備えた構成を構築し、最終状態への最短パスを見つけることだけです。
P =最短（W o T o D）
ここで、Dは辞書です
Tは、単語のプレフィックスを吸収し、各「食べた」文字にペナルティを与える重みを持つ特別なコンバーターです。
この例では、予測をまだ実装していません。 たぶん後で。
私の意見では、これは形態学を扱うかなり興味深い方法です。 2つの重要な利点を強調できます。
この例の速度に関しては、急降下から良い結果を得ることができませんでした。 2000ワード/秒のような結果になりました。 しかし、私は標準ライブラリを使用し、最適化についてはあまり気にしませんでした。 おそらく、他のタイプのトランスデューサーを使用すると、速度が上がる可能性があります。 辞書の重量は約35Mでした（ただし、コンパクトな表現を使用すると、3回圧縮されます）。
単純さを犠牲にして、ここでは多くのコードは不要です。 標準操作を使用するだけで十分です：合成、連結、結合、最短パスの検索。 辞書の作成には約50行のコードが必要でした。 ソースコードとPythonバインディングを含むTarballの例は、 ここからダウンロードできます 。
さらに、このアプローチには非常に興味深い機能があります。 トランスデューサをより複雑なスキームに組み合わせることにより、複雑な変換を構築できます。 たとえば、スペルカーに関する前回の記事の予測子にオートマトンを追加すると、「この単語は本当に不明なのか、エラーが含まれているのか」という質問に答える論理デバイスが得られます。
おそらくそれだけです。 面白かったと思います。
ここでは、これらの問題を回避しようとする状態マシンに基づいたバージョンを提供します。 どのように機能するかはここで見ることができます 。
形態学から何が欲しいのでしょうか。 通常、形態分析モジュールが必要です。
- 特定の単語の補題を取得する
- 特定の単語の形態情報を取得する
- 形態予測
これらすべてを、形態学的辞書とオートマトンのライブラリという2つの要素から準備します。 LGPLのおかげで、 aot.ruプロジェクトから（既に受け入れられているように）最初に取得したもの。 また、オートマトンライブラリはこちらから： openfst.org 。 コードは最小化されます。必要な操作はすべてライブラリに既に実装されています。
最初のステップ。 Parsimの形態学的辞書。
形態学的辞書には、次の形式の行が含まれています。
「ヘイズ」という言葉の例を次に示します。 MGLという文字は、単語のルートです。 残りはエンディング（語形変化）です。 ルートと最初の変曲（この場合はMGLA）を追加することで、補題または正規化された単語を取得できます。 小さな2文字の組み合わせはアノードです。 つまり これは、単語形式の形態を一意に定義するコードです。 たとえば、「ga」の場合、「名詞、女性、単数、主格」です。
アクションに移りましょう。 辞書の各行に対して、この構造を構築します。
これが最終的なコンバーターです。 次のように機能します。 各遷移は2文字でマークされ、最初の記号は入力記号、2番目の記号は出力記号です。 初期状態から最終状態までのいずれかのパスに沿って着信シンボルと発信シンボルを「収集」すると、2つの単語が得られます。 魔法は、ここで入力語がその語の形態学的形式の1つになり、出力が補題+陽極になることです。 たとえば、このマシンに「GLOGO」という単語を「フィード」することで、「MGLAMg」を取得できます。 「-」は空の文字を示しているため、グラフを読み終えると無視できます。
一般に、標準の構成操作を使用して、入力によって出力ワードを取得できます。
Dが上の図のように辞書である場合、
Wは単語で、W = <（M、M）（G、D）（L、L）（O、O）（Y、Y）、（I、I）>
その場合、M-合成の結果-は等しくなります（空文字を除く）
M = W o D = <（M、M）（G、D）（A、A）（A、A）（a、a）（m、m）
ステップ2 最適化。
上の図の構造には問題があります。 彼女は最適ではありません。 1つ目は、コンバータを無用に「膨張」させる余分な空文字です。 第二に、このコンバーター自体は最適ではありません。 完全な辞書のためにこのような構造を構築すると、後者は非常に大きくなります。
そのため、最初に発信シンボルを初期状態にシフトします。 これにより、空の文字の数が減ります。 openfstライブラリは、このような操作を実装しています。 fstpushと呼ばれます。
図からわかるように、マーク「-：-」の付いた円弧が表示されました。 パッケージングプロセス中に削除されます。
次に、コンバーターをパックします。 ここには微妙さがあります。 一般的に、最終ドライブは通常のステートマシンのようにパッケージ化することはできません。 事実、コンバーターとオートマトンを最小化するためには、コンバーターを決定する必要があります（各入力ワードには固有の出力があります）。 しかし、このコンバーターはそうではありません。
この問題を解決するには、次のことができます
- コンバーターをステートマシンに持ち込む
- マシンをパックします（標準アルゴリズムに従って）
- 結果のマシンをコンバーターに持ち込みます
これらの操作はすべて標準であり、コードを記述する必要はありません。 下の画像の「ヘイズ」という単語の結果。
図からわかるように、状態と遷移の数は著しく減少しました。 そして、これが私たちの目標です。
ステップ3 未知の単語の形態の予測。
ここではすべてが簡単です。 必要なのは、着信ワードWが2つのコンバーターを備えた構成を構築し、最終状態への最短パスを見つけることだけです。
P =最短（W o T o D）
ここで、Dは辞書です
Tは、単語のプレフィックスを吸収し、各「食べた」文字にペナルティを与える重みを持つ特別なコンバーターです。
この例では、予測をまだ実装していません。 たぶん後で。
結論
私の意見では、これは形態学を扱うかなり興味深い方法です。 2つの重要な利点を強調できます。
- 速度とリソース
- 開発のしやすさ
- アルゴリズムの普遍性
この例の速度に関しては、急降下から良い結果を得ることができませんでした。 2000ワード/秒のような結果になりました。 しかし、私は標準ライブラリを使用し、最適化についてはあまり気にしませんでした。 おそらく、他のタイプのトランスデューサーを使用すると、速度が上がる可能性があります。 辞書の重量は約35Mでした（ただし、コンパクトな表現を使用すると、3回圧縮されます）。
単純さを犠牲にして、ここでは多くのコードは不要です。 標準操作を使用するだけで十分です：合成、連結、結合、最短パスの検索。 辞書の作成には約50行のコードが必要でした。 ソースコードとPythonバインディングを含むTarballの例は、 ここからダウンロードできます 。
さらに、このアプローチには非常に興味深い機能があります。 トランスデューサをより複雑なスキームに組み合わせることにより、複雑な変換を構築できます。 たとえば、スペルカーに関する前回の記事の予測子にオートマトンを追加すると、「この単語は本当に不明なのか、エラーが含まれているのか」という質問に答える論理デバイスが得られます。
おそらくそれだけです。 面白かったと思います。
All Articles