ロシアの形態のハイブリッド実装

検索ソリューションを作成するとき、開発者が最初に対処しなければならないことの1つは、予備のテキスト処理です。 用語に分類し、ストップワードをフィルタリングします。 この段階での検索の質に影響する重要な操作は、単語を通常の形式にすることです。 この問題に対する主なアプローチは次のとおりです。





最も単純なケースでは、トランケーション演算子（ステミング）を使用できます。これは、語尾を捨てて、単語のメイン形式を残します。 最も人気のある英語のソリューションはSnawball Stemmerです。 いくつかの簡単なルールに基づいています。 たとえば、sが単語の最後の文字である場合、破棄できます。 英語での彼の仕事の例を次に示します。



コメント->コメント

使用->使用

ステミング->ステム

受信->受信

開発->開発。



Snawballはロシア語をサポートしていますが、その使用は十分に高品質の結果を与えません。 切り捨てが異なる方法で行われる同じ単語の2つの単語形式の例を次に示します。



レビュー->レビュー

レビュー->レビュー



別のアプローチは、すべてのペア（単語、正規形）を保存することです。 これの欠点は明らかです。 なじみのない単語が見つかった場合、そのアルゴリズムは機能しません。 ロシア語の現代の辞書には150万以上の単語形式が含まれているという事実から、もう1つのマイナス点があります。 それらはすべて保存し、それらの中をすばやく検索する必要があります。 ステートマシンを構築して、必要なメモリの量を減らし、作業の速度を上げることができます。 このようなオートマトンを構築するためのアルゴリズムは、[1]に記載されています。 C ++での実装は、aot.ruサイトで入手できます。 このアルゴリズムの実装は非常に困難です。



ステミングとボキャブラリーアプローチのハイブリッドバージョンを使用できます。 ほとんどの場合、単語の最後の数文字を知っていれば、通常の形式を正しく判断できれば十分です。 したがって、ペア（単語、正規形）を（単語の終わり、正規形の終わり）に置き換えます。 単語の終わりとして、単語の最後の7文字を取り上げます。 したがって、辞書になじみのない単語がないという問題は解決されました。 この結果は辞書よりも悪いことは明らかですが、ステマーの結果よりははるかに良いでしょう。 7文字以内の単語の場合、アルゴリズムは正確な答えを出します。 また、aot.ruの形態の実装で、なじみのない単語のヒューリスティックとして使用されます。 実装の違いは、ステートマシンが辞書の単語と同じ方法で構築されることです。



その複雑さと必要なメモリ量の問題を検討してください。 ロシア語のアルファベットでは、単語にハイフンが発生する可能性があることを考慮して、33文字に加えて したがって、単語内の1文字は0〜33の数字でエンコードされ、64ビットのデータ型（たとえば、javaではlong）には7〜12本に関する情報を含めることができます。 私たちの目的にはこれで十分です。 実験のために、LGPL 2.0ライセンスで配布されているaot.ruプロジェクトサイトから辞書を取得します。 彼は私たちに75万のユニークなペア（単語の終わり、通常の形の終わり）をくれます。 いくつかのペアには、通常の形式を判別するのと同じ語尾があります。 1つだけ残します。これは、より一般的で、ロシア語のより一般的な単語に適しています。 したがって、この方法で約69万ペアになります。 特に、60万件を超えるケースについては、標準形が明確に決定します。



アルゴリズムが機能するために必要なデータが約10.6メガバイトを占めると計算するのは簡単です。 バイナリ検索を使用して、目的のエンディングを見つけることができます。 （約20の比較を見つける必要があります）。 aot.ruのアルゴリズムで比較すると、形態学的情報を含まないマシンのサイズは約5メガバイトです。 単語の最後にヒューリスティックを実装するには、もう1つのオートマトンが必要です。残念ながら、そのサイズは表示されません。 したがって、メモリサイズは同等であり、この実装は低コストでそれほど悪い結果を与えません。



このアプローチの実装はjavaで実装され、ロシア語のAnalayzerも作成されました

検索フレームワークluceneの場合 。 これは、apache 2.0ライセンスの下で配布されます。



[1] Jan Daciuk、Bruce Watson、Richard Watson、最小非循環有限状態オートマトンおよび変換器のインクリメンタル構築、自然言語処理における有限状態法の手順、pp。 48-56、ビルケント大学、アンカラ、トルコ、1998年6月29日-7月1日。



ロシアの形態のハイブリッド実装。