テキストの自動分析は、ほとんどの場合、辞書を使用した作業に関連付けられています。 これらは、形態学的分析、個人の割り当て（個人名と姓の辞書が必要）、組織、およびその他のオブジェクトに使用されます。

一般に、ディクショナリは{string、この文字列に関連付けられたデータ}という形式のレコードのセットです。

たとえば、形態素解析の場合、ディクショナリはトリプル{単語形式、標準形、形態学的特徴}で構成されます。 「mother soap frame」という文から「soap」という単語を分析する場合、次の分析オプションを取得できる必要があります。

標準形	特徴
SOAP	S（名詞）、性別（属格）、ED（単数形）、MEDIUM（中性）、NEOD （無生物）
SOAP	S（名詞）、MI（主格）、MN（複数）、MEDIUM（中性）、NEOD（無生物）
SOAP	S（名詞）、VIN（対格）、MN（複数）、MEDIUM（中性）、NEOD（無生物）
ウォッシュ	V（動詞）、PASS（過去時制）、ED（単数形）、FLASH（指示）、WIFE（女性）、NESOV（不完全形）

ハッシュテーブル

一見、すべてがシンプルです。 ハッシュテーブルを使用して、最後に対処する必要があります。 辞書が小さい場合、このソリューションは非常にシンプルで効果的です。

ただし、たとえば、ロシア語の形態学的辞書には、約500万の単語形式が含まれています。 それは次のことがわかります：

• これらの500万語のフォームを保存する必要があります
• 単語の形式ごとに、多くの形態的特徴のセットへのリンクが必要です
• 各単語形式について、その初期形式を保存します

このデータの整理方法は不経済です。なぜなら、第一に、単語は規則的に傾く傾向があるためです。 。

たとえば、「壁」という言葉：

• 単位 h：「walls a 」[them]、「walls s 」[genus]、「walls e 」[dates]、「walls u 」[wines]、「walls oi 」[creat]、「walls oi 」[creat]、 "Walls e " [predl];
• 多くの h：「walls s 」[im]、「walls」[genus]、「walls am 」[dates]、「walls s 」[wines]、「walls ami 」[creat]、「walls ah 」[文章]。

末尾のみが変化することがわかりますが、単語全体をハッシュテーブルに格納する必要があります。

基本（変更されない部分）とエンディングを別々に保存できますが、この場合、単語の検証は複雑です。

プレフィックスツリーからステートマシンまで

例を明確にするために、より単純な問題を検討します。分析の各単語形式について、その形態学的特徴のみを取得する必要がある場合です。 通常のフォームを保持する方法については、最後に説明します。

ハッシュテーブルと比較して、よりコンパクトな表現はプレフィックスツリー（トライ）です。



重要な注意-ツリーの各リーフノード（またはステートマシンの状態）に関連付けられた機能のセットは、図には表示されません。 たとえば、図「ノード6」では、「壁」の線に沿って、実際には3つの解析があります。

• 単数形、属格;
• 複数形、主格。;
• 複数形の対格。

プレフィックスツリーは、有限状態マシンと見なすことができます。

マシンには3つのタイプの状態があります。

• 初期-作業は機械から始まります。 決定性オートマトンでは、そのような状態は1ですが、非決定性オートマトンではいくつかあります。 図では、これは番号0の左端の状態です。
• 最終-そのような状態、その達成はそのような単語が辞書にあることを意味します。 それらは二重丸で示されます。
• 初期でも最終でもない単純な状態

将来的には、次の表記が使用されます。

• 文字列はwで示されます
• w [i]は、この単語のi番目の文字です（0から始まります）。
• s [i]はツリーのi番目のノード（またはオートマトンの状態）です。状態は非負の整数で番号付けされ、s [0]が初期状態であると仮定します。
• s [i] [j]-シンボルjによる状態s [i]からの遷移。 遷移がある場合、そのような式は状態番号を返し、そうでない場合は-1を返します。

プレフィックスツリー/ステートマシンの基本的なアルゴリズムを示します。

//      //    ()  int[] prefix(w) { int[] stateList; //         stateList[0] = 0; int current = 0; for(int i = 0; i < length(w); i++) { int next = s[current][w[i]] //   ,   if(next == -1) break; stateList[i+1] = next; } return stateList; } //      //      stateList void addSuffix(w, int[] stateList) { //        int current = stateList[length(stateList) - 1]; for(int i = length(stateList) - 1; i < length(w); i++) { //      int newState = addState(); //    s[current][w[i]] = newState; current = newState; //      stateList[i + 1] = current; } //     s[current] setFinal(current); } //     trie void add(w) { //     int[] prefixStates = prefix(w); //      addSuffix(w, prefixStates) } 

プレフィックスツリーを有限状態マシンとして表現することには、重要な特性があります。

• そのようなオートマトンが決定されます-各状態から、特定のシンボルによる遷移は1つだけです
• サイクルはありません。オートマトンをバイパスする方法では、状態が複数回アクセスされることはありません。

このような特別なオートマトンは、DAFSA（決定論的非循環有限状態オートマトン）と呼ばれます。

ひとつの重要なポイント。 表示の便宜上および実際の使用のために、状態は遷移表だけでなく、最終状態のデータによっても記述されると想定しています。 そして、そのようなデータが含まれている場合は状態が最終的であり、存在しない場合はそうではないと考えます。

最小状態マシン

プレフィックスツリーを使用すると、プレフィックスの冗長性がなくなります。 実際、これは、単語の変更されていない部分の記憶領域が削減されることを意味します。 ただし、たとえばロシア語では、語尾はほとんど定期的に変化します。

たとえば、「矢印」と「壁」という言葉は同じように変化します。

壁：単位 h：「wall」[them]、「walls」[genus]、「wall」[dates]、「wall」[wines]、「wall」[creat]、「wall」[creat]、「wall」[proposal] ; 多くの h：「壁」[それら]、「壁」[属]、「壁」[日付]、「壁」[勝]、「壁」[創造]、「壁」[提案]。

矢印：単位 h：「arrow」[them]、「arrows」[genus]、「arrow」[dates]、「arrow」[wines]、「arrow」[creat]、「arrow」[creat]、「arrow」[offer] ; 多くの h：「arrows」[them]、「arrows」[genus]、「arrows」[dates]、「arrows」[wines]、「arrows」[creat]、「arrows」[predl]。



語尾が始まる状態4と17は、両方の単語で同等であることがわかります。 明らかに、辞書には同じ変曲ルールを持つ多くの単語があります。 したがって、状態の数を大幅に減らすことができます。

実際、オートマトンの理論には、最小限のオートマトンの概念があります。最小限の状態を含むが、これと同等のオートマトンです。

たとえば、上記のマシンの場合、最小値は次のようになります。


有限状態マシンを最小化するアルゴリズムがありますが、それらにはすべて重大な欠点があります-その作業のために、最初に非最小化オートマトンを構築する必要があります。

もう1つの明らかな欠点は、構築された最小のオートマトンがそれほど簡単に変更できないことです。 プレフィックスツリーに使用される新しい単語を追加する簡単な手順には適合しません。

たとえば、「fox」と「box」という単語のオートマトンを作成し、それを最小化しました。



完全に再構築せずにこのマシンに「キツネ」という単語を追加すると、次の図が表示されます。



「キツネ」が追加された場所と「ボックス」が追加されなかったことが判明しました。

その結果、従来の最小化アルゴリズムを使用するためのスキームは次のとおりです。辞書の変更には、必要です。

• プレフィックスツリーを構築する（またはオプションで保存する）
• 機械を最小化

辞書が大きい場合、これらの手順にはかなりの時間とメモリがかかります。

決定論的非周期的有限状態機械の増分最小化

オートマトンを最小化することの難しさの解決策は、次の作業に示されています。JanDaciuk。 ブルース・W・ワトソン; ストヤン・ミホフ; リチャードE.ワトソン。 「最小非循環有限状態オートマトンのインクリメンタル構築 。 」 決定論的な非周期的有限状態マシンのための増分最小化アルゴリズムを提示します。 すでに構築されている最小のオートマトンを変更できます。 その結果、完全なオートマトンを作成して最小化する必要はありません。

繰り返しますが、私たちのマシンの壁+矢印を考えてみましょう


アルゴリズムの重要な概念は「文字列の状態」です。これは、マシンが指定された文字列を回るときに取得される一連の状態です。

たとえば、線を矢印でトラバースすると、次の状態シーケンスが得られます[0、1、2、14、15、15、4、9、10]。

このアルゴリズムのもう1つの重要な概念は、特定の状態への遷移の数（コンフルエンス）です。 遷移の数が複数ある場合、この状態の変更は安全ではありません。 図では、この状態は4です。2つの矢印が入っています。

さらに、アルゴリズムでは、これと同等の状態をすばやく取得できる状態レジスタがあると想定しています。

その結果、単語wを追加するアルゴリズムは次のようになります。

 void addMinWord(w) { //    w     int[] stateList = commonPrefix(w); //         int confIdx = findConfluence(stateList); //       if(confIdx > -1) { int idx = confIdx; while(idx < length(stateList)) { int prev = stateList[idx - 1]; int cloned = cloneState(stateList[idx]); stateList[idx] = cloned; //     //        s[prev][w[idx - 1]] = cloned; idx++; confIdx++; } } //   addSuffix(w, stateList); //    ,    . //  ,     replaceOrRegister(w, nodeList); } void replaceOrRegister(w, int[] stateList) { int stateIdx = length(stateList) - 1; int wordIdx = length(w) - 1; //      while(stateIdx > 0) { int state = stateList[stateIdx]; //    ,  state int regState = registerGet(state); if(regState == state) { //    state  ,     continue; } else if(regState == -1) { //     ,      registerAdd(state); } else { //  ,     ,  state int in = w[wordIdx]; //   s[stateList[stateIdx - 1]][in] = regState; //      stateList[stateIdx] = regState; //      removeState(state); } wordIdx--; stateIdx--; } } 

アルゴリズム操作図

最終状態がバイナリ記号である単純なケースを考えてください。 条件は最終的なものかそうでないかです。

文字列「fox」の自動。

オートマトンは最小限であり、すべての状態がレジストリ[0,1,2,3]にあることがわかります。

単語「ボックス」を追加します。 共通の接頭辞がないため、行全体を接尾辞として追加します。 その結果、以下が得られます。


状態3と6が等しいことがわかります。 6を3に置き換えます。


これで、2と5に等しいことがわかります。5を2に置き換えます。


そして今、それらは1と4に等しいことがわかります。4を1に置き換えます。


行「foxes」を追加します。 プレフィックスを計算すると、状態[0、1、2、3]がプレフィックスのパスであることがわかりました。
さらに、状態1には複数の遷移が含まれていることがわかりました。 その結果、「fox」という単語をバイパスするパスに沿って状態1、2、および3を複製する必要があります。前のマシンに単に「foxes」を追加すると、「boxes」という文字列が認識されるためです。



「ボックス」を追加します。



「ボックス」を追加することで、マシンは小さくなりました。 これは一見すると、新しい行が追加されたときにマシンが実際に減少したときの予期しない動作です。 逆の動作もあります-行が削除されたときにマシンが増加するとき。

アルゴリズムが正しく機能するためには、レジストリを正しく操作することが重要です。 状態は、状態遷移テーブルと最終サインの変更時にレジストリから削除されます。

また、通常のセットまたはテーブルとは異なり、レジストリへの追加/削除はこの状態で正確に動作し、要求は同じ立場で行われます。

実用化

提示されたアルゴリズムは、 AOTプロジェクトおよびETAP-3システムで使用され、迅速な形態素解析を編成します。 有限状態マシンを使用すると、1秒あたり約100〜150万ワードの分析速度が達成されます。 同時に、特別なトリックのないマシンのサイズは8 MBに収まります。

行データの保存は、以前は最終性の兆候として説明されていました。 このアプローチをより詳細に検討してください。

マシンの状態でのデータストレージ

このアプローチは、これらの文字列が何らかのアトミックオブジェクトと見なされることを前提としています。 これにより、オートマトンを最小化する効率が制限されます。

たとえば、最小のオートマトンを構築する手順は、一意の番号が文字列に関連付けられている場合、完全なハッシュ化には意味がありません。 この場合、各サフィックスは一意であるため、各最終状態は一意であるため、最小化は行われないためです。

形態学的分析の場合、形態学的特性のセットを関連データとして使用できます。 これは、単語形式の総数に対してこのようなセットが少ないため、うまく機能します。 たとえば、ロシア語では、採用モデルに応じて、そのようなセットの数は500〜900です。 単語形式は400〜500万です。

ただし、特性に加えて完全な正規形が維持される場合、最小化の有効性は無効になります。 これは、{標準形、形態的特徴}のペアがほとんど一意であるためです。

ETAP-3システムは、このようなアプローチを使用して形態学的情報を保存します。 形態素のセットのみがマシン自体に保存されます。 そして、通常のフォームを保存するために、次のトリックが使用されます。 オートマトンを作成する段階では、1文字ではなく2文字が入力シンボルとして使用されます。 たとえば、単語形式に「壁」（楽器の場合は「WALL」）を追加すると、次の一連の文字ペアが追加されます：「c：C」、「t：T」、「e：E」、「n：N」、「o：A」 、「Th：_」。

このようなマシンの「壁」と「矢印」という単語のすべての単語形式は、次のようになります。



通常の形式を記録するこのアプローチには、重要な利点があります。 これにより、2つの方向で形態を操作できます。 あなたはその分析を単語形式で得ることができます-分析。 そして、すべての単語形式を通常の形式、つまり合成で取得できます。

このアプローチの欠点は、オートマトンが一対の記号に対して決定論的であるという事実にもかかわらず、入力オートマトンのオートマトンではなくなり、この状態からのすべての遷移を整理する必要があることです。 たとえば、上の図の状態mです。 単語形式「a」の記号に従って、いくつかの遷移があります。

移行中のデータストレージ。 注釈を使用する

追加のデータを保存する別の方法は、元の研究で説明されています。 マシンに保存されている行自体を変更する必要があります。

設計スキームが提案されています。 ターゲット行の代わりに、ターゲット行、データ開始文字（注釈文字）、およびデータ自体で構成される拡張行がマシンに書き込まれます。

たとえば、この場合、形態的特徴は次のように書くことができます： "wall | + noun + women + im、..."、where '|' -注釈文字、および「+既存」、「+女性」、「+それら」-特別なデータ文字。

このアプローチは、AOTシステムで使用されます。 実際には、2つの参照がデータとして保存されます。形態学的特性と変曲規則番号です。 その結果、分析する際に、その形態学的特徴と単語形式を使用した初期形式の両方を取得することが可能です。

このアプローチの特徴は、オートマトンのモデルがやや複雑であることです。 遷移シンボルの解釈は、注釈シンボルの前か後かによって異なります。

もう1つの機能は、行ごとの走査がもう少し複雑であることです。 第1に、機械を通過した後、注釈記号による遷移がある状態にある場合、機械に線が存在します。 第二に、注釈記号の後のすべての注釈を収集する手順が必要です。 第三に、注釈のデコード手順が必要です。

メモリ最適化

メモリの量を最適化するために、有限オートマトンの2つの表現が使用されます。1つは最小オートマトンの構築用で、もう1つは分析用です。 2つの違いは、分析マシンは変更を意味しないため、より効率的にメモリに配置できることです。

分析マシンは、次の3つの構造で構成されています。

1. 変換テーブル-整数ペア{遷移シンボル、ターゲット状態}
2. 状態遷移の範囲の開始と終了のインデックス
3. 最終状態データ表

オートマトンは十分にコンパクトです。 たとえば、特別なトリックのないAOT辞書には約8Mbかかります。 形態素解析システムの完全なデータ。辞書分析だけでなく、予測単語分析も含まれ、16Mbに適合します。

最小化アルゴリズム自体は、Githubの私のプロジェクトで実装されています： github.com/kzn/fsa