簡単な分詞器Tokenizer
一、概要
分詞器の役割は、文字列を「語」のリストに変えて、「大学生活」という入力を例に説明します。
「大学生活」という言葉に分詞をつけると、普通は一つの分詞器は三つのステップに分けて実現されます。
（1）「大学生活」という言葉の中のすべての言葉を見つけて一つの集合とします。すなわち、「大、大学、大学生、学、学生、生、生活、生」
（2）第一歩で得られた集合の中から、「大学生活」という言葉に結合できるすべてのサブセットを見つけました。
[大、学、生、活]
[大、学、生活]
[大、学生、活]
【大学、学生、生活】
【大学、生活】
【大学生、生活】
（3）第二のステップで生成されたすべてのサブ集中は、最終的な分詞結果として最も可能なものを選ぶ。
第1ステップの集合を得るためには、通常辞書が必要です。ほとんどの分詞器は辞書に基づいて分詞を作っています。「大学、大学生、勉強、学習機、学生、怒り、生活、生きている」という小さな辞書があります。まず「大学生活」という言葉の中にこの辞書の中のすべての言葉を合わせると、一部の学生の頭の中にこのような過程が現れるかもしれません。
大学
大学生
学生
生活
ここまで来たようです。辞書の中で単語を見つけたら完璧に完成しました。しかし、本当の分詞器の辞書には、何十万、あるいは何百万という語彙があります。このようなアルゴリズムを使うと、性能が低すぎます。このようなマッチングを効率的に実現するためのアルゴリズムは多くあります。
二、AC自動機（Aho-Coorasick atomaton）
AC自動機は、一般的なマルチモード整合アルゴリズムであり、辞書ツリー（trieツリー）のデータ構造とKMPアルゴリズムの失敗ポインタの思想に基づいて実現され、良い性能を持ち、非常に簡単に実現される。
2.1、辞書ツリー（trieツリー）
Baidu百科のtrieツリーについての説明：Trieツリーは、ツリー構造であり、一種のハッシュツリーの変種である。典型的なアプリケーションは、統計、並べ替え、大量の文字列を保存するために使用されます。文字列に限らず、検索エンジンシステムによってしばしばテキストの語彙統計に使用されます。その利点は、文字列の共通プレフィックスを利用してクエリ時間を低減し、無駄な文字列比較を最大限に低減し、ハッシュツリーよりもクエリ効率が高いことである。
次の「大学、大学生、勉強、学習機、学生、怒り、生活、生きている」という辞書が保管されているtrieツリー：
これは、各語のn番目の単語でn番目からn番目のノード間のパス・ハッシュ値を作成するハッシュツリーと見なすことができ、各ノードは実際に格納される単語である。
今はこの木で「大学生活」のマッチングをしています。「大」の字からマッチし始めました。下の図のように、ルートノードから一番左の経路で大字にマッチしました。「大」のノードに沿って「大学」にマッチングできます。続けてマッチングすれば「大学生」にマッチングできます。その後、辞書の中で「大」の字で始まる単語がなくなりました。これで「大学、大学生」の第一ラウンドマッチが終わりました。
「学」の頭の単語に引き続きマッチします。方法は同じです。「学生」にマッチします。
「生」と「生」の頭に続く言葉が、このように「大学生活」という辞書の中の言葉から全部検出されました。
「大」の文字にマッチする最初の単語を例にとって、「大」、「大学」、「大学」、「大学生活」を含むかどうかを辞書で調べる必要がありますが、「大学生」という単語を見つけたら、マッチングの回数を減らします。このような性能の優位性はもっと明らかです。
2.2、失敗の指針
上記のマッチング過程を見てみます。「大学生」という単語にマッチした後、辞書には他の「大」という字で始まる単語が存在しないため、本輪が終わって、「学」という字で始まる単語に引き続きマッチします。この時、「大学生」ノードの指針があれば、「学生」のノードにまっすぐに向けられます。同じように、「学生」にマッチした後、「学生」ノードに「生活」ノードがあると、もう一回クエリを減らすことができます。この次の層のノードがマッチングできないため、ジャンプする必要があるポインタが失敗のポインタです。失敗のポインタを作成したツリーは次のように見えます。
図上の赤い線は失敗ポインタです。下のノードが一致しない場合、どのノードにジャンプしてマッチングを続けるべきかを指します。
失敗したポインタの作成プロセスは、通常は以下の通りです。
1.trieツリーを作成します。
2.BFSの各ノード（DFSは使用できない。なぜなら、各階層のノードの失敗ポインタは、作成時に、前の階層のノードの失敗ポインタが全部作成されたことを保証するためである。）
3.ルートノードのサブノードの失敗ポインタは、ルートノードを指す。
4.他のノードは、親ノードの失敗ポインタが指すノードのサブノードがノードワードと同じノードを持っているかどうかを調べ、失敗ポインタがノードに向けられている場合、ない場合は、同じノードまたはルートノードが見つかるまで、先ほどのプロセスを繰り返す。
照会のプロセスは以下の通りです。
このコードを実行すると出力されます。
大学
大学生
学生
生活
辞書に出てくるすべての語にマッチした後、次のステップを続けます。得られた集合の中で、「大学生活」という文章に結合できるすべてのサブセットを見つけます。しかし、このところで一つの小さな問題がありました。上で調べた4つの単語の中には「大学」と「生活」という言葉だけが「大学生活」という文章を作ることができます。辞書がすべての単語を網羅するのは難しいという現実があります。ここでは、一致する単語の集合に単一の単語を追加的に配置することができ、これは新しいセットを得る。
[大学、大学生、学生、生活]U[大、学、生、活]=[大学、大学生、学生、生活、大、学、生、活]
この集合の分詞の組み合わせは、スタートノードから終了ノードまでの全経路がすべての分詞方式であることを図に示すことができる。
三、最終的な分詞の結果
これらの可能な分詞の組み合わせの中で、最終的な分詞の結果としてどれを選ぶべきですか？大部分の分詞器の主な違いはここにも現れています。いくつかの分詞器は使用者の選択のためにさまざまな分詞戦略があるかもしれません。例えば、最小ワードポリシーは、エンドノードに到達することができるすべての経路の中で最も短い（最小ノードを通過する）1つを図中に選択することである。上のこの方向図に対して、最短経路は2つあります。それぞれ「大学、生活」と「大学生、生活」の最終的な分詞はこの2つの経路の中で一つを選びます。この選択法は最も簡単で性能も高いが，精度が劣る。実際によく考えてみると、どの分詞戦略を使っても、一番正しい確率の高いものを選ぶのが目的です。大学生活は、「大、学、生」の確率がP（大）P（学𞓜大）P（生124;大、学）P（活𞓜大、学、生）です。つまり、その確率を計算するには、「大」の出現確率を知る必要があります。「生」が同時に現れた時に「生」が現れる確率。これらの出現確率は、大量の文章からなるテキストライブラリで集計できますが、問題は、辞書が任意のN個の単語を記録する場合、単語Wが出現する確率、M個の単語を格納する辞書はM^N級の関係データを保存する必要があります。この辞書は大きすぎるので、Nの大きさは制限されます。一般的にNは2または3です。条件確率を計算する時は、前の2つから3つの単語だけを考慮します。これはマルコフチェーンに基づいて行う簡略化です。Nを2と呼ぶ場合は二元モデル、Nを3と呼ぶ場合は三元モデルと呼ぶ。50万語の辞書がある二元モデルは50万円から50万円の関係が必要です。これもかなり大きいサイズです。圧縮したり、他の近似形式に変えたりできます。この部分は比較的複雑です。ここでは説明しないで、もっと簡単な形を使います。各単語の出現は独立した事件であると仮定して、P（大、学、生、生、生、生）＝P（大）P（学）P（生P）P（生P）（生P）（生P）（生P））（生P）））（生P）（生P））（生P））この確率を計算するには、単語の出現確率、単語の出現確率=単語の出現回数/テキストライブラリの単語の総量を知る必要があります。前に使っていた辞書を「大学5、大学生4、勉強6、学習機3、学生5、怒っている8、生活7、生きている2」に更新した後の数字はこれらの単語がテキストバンクに出現する回数で、テキストバンクの単語の問題はこれらの単語の出現回数の合計=5+4+5+8+7+2=40です。
P（大学、生活）＝P（大学）P（生活）＝5/40*7/40
P（大学生、活）=P（大学生）P（活）＝4/40*0/40ここで問題が発生しました。辞書にない単語については、その確率は0です。これは乗積全体が0になるという不合理なことです。この場合は平滑処理ができます。簡単に言えば、辞書にない単語の出現回数を1に設定できます。活)=P（大学生）P（活）=4/40*1/40
最終的には最も可能な単語の組み合わせを選ぶことができます。これで3歩目が終わります。
以上が簡単な分詞器Tokenizerの詳細です。分詞器Tokenizerに関する資料は他の関連記事に注目してください。
分詞器の役割は、文字列を「語」のリストに変えて、「大学生活」という入力を例に説明します。
「大学生活」という言葉に分詞をつけると、普通は一つの分詞器は三つのステップに分けて実現されます。
（1）「大学生活」という言葉の中のすべての言葉を見つけて一つの集合とします。すなわち、「大、大学、大学生、学、学生、生、生活、生」
（2）第一歩で得られた集合の中から、「大学生活」という言葉に結合できるすべてのサブセットを見つけました。
[大、学、生、活]
[大、学、生活]
[大、学生、活]
【大学、学生、生活】
【大学、生活】
【大学生、生活】
（3）第二のステップで生成されたすべてのサブ集中は、最終的な分詞結果として最も可能なものを選ぶ。
第1ステップの集合を得るためには、通常辞書が必要です。ほとんどの分詞器は辞書に基づいて分詞を作っています。「大学、大学生、勉強、学習機、学生、怒り、生活、生きている」という小さな辞書があります。まず「大学生活」という言葉の中にこの辞書の中のすべての言葉を合わせると、一部の学生の頭の中にこのような過程が現れるかもしれません。
public class Demo1{
//
static Set<String> dic = new HashSet(){{
add(" ");
add(" ");
add(" ");
add(" ");
add(" ");
add(" ");
add(" ");
add(" ");
}};
//
static List<String> getAllWordsMatched(String sentence){
List<String> wordList = new ArrayList<>();
for(int index = 0;index < sentence.length();index++){
for(int offset = index+1; offset <= sentence.length();offset++){
String sub = sentence.substring(index,offset);
if(dic.contains(sub)){
wordList.add(sub);
}
}
}
return wordList;
}
public static void main(String[] args){
String sentence = " ";
getAllWordsMatched(sentence).forEach(System.out::println);
}
}大学
大学生
学生
生活
ここまで来たようです。辞書の中で単語を見つけたら完璧に完成しました。しかし、本当の分詞器の辞書には、何十万、あるいは何百万という語彙があります。このようなアルゴリズムを使うと、性能が低すぎます。このようなマッチングを効率的に実現するためのアルゴリズムは多くあります。
二、AC自動機（Aho-Coorasick atomaton）
AC自動機は、一般的なマルチモード整合アルゴリズムであり、辞書ツリー（trieツリー）のデータ構造とKMPアルゴリズムの失敗ポインタの思想に基づいて実現され、良い性能を持ち、非常に簡単に実現される。
2.1、辞書ツリー（trieツリー）
Baidu百科のtrieツリーについての説明：Trieツリーは、ツリー構造であり、一種のハッシュツリーの変種である。典型的なアプリケーションは、統計、並べ替え、大量の文字列を保存するために使用されます。文字列に限らず、検索エンジンシステムによってしばしばテキストの語彙統計に使用されます。その利点は、文字列の共通プレフィックスを利用してクエリ時間を低減し、無駄な文字列比較を最大限に低減し、ハッシュツリーよりもクエリ効率が高いことである。
次の「大学、大学生、勉強、学習機、学生、怒り、生活、生きている」という辞書が保管されているtrieツリー：
これは、各語のn番目の単語でn番目からn番目のノード間のパス・ハッシュ値を作成するハッシュツリーと見なすことができ、各ノードは実際に格納される単語である。
今はこの木で「大学生活」のマッチングをしています。「大」の字からマッチし始めました。下の図のように、ルートノードから一番左の経路で大字にマッチしました。「大」のノードに沿って「大学」にマッチングできます。続けてマッチングすれば「大学生」にマッチングできます。その後、辞書の中で「大」の字で始まる単語がなくなりました。これで「大学、大学生」の第一ラウンドマッチが終わりました。
「学」の頭の単語に引き続きマッチします。方法は同じです。「学生」にマッチします。
「生」と「生」の頭に続く言葉が、このように「大学生活」という辞書の中の言葉から全部検出されました。
「大」の文字にマッチする最初の単語を例にとって、「大」、「大学」、「大学」、「大学生活」を含むかどうかを辞書で調べる必要がありますが、「大学生」という単語を見つけたら、マッチングの回数を減らします。このような性能の優位性はもっと明らかです。
2.2、失敗の指針
上記のマッチング過程を見てみます。「大学生」という単語にマッチした後、辞書には他の「大」という字で始まる単語が存在しないため、本輪が終わって、「学」という字で始まる単語に引き続きマッチします。この時、「大学生」ノードの指針があれば、「学生」のノードにまっすぐに向けられます。同じように、「学生」にマッチした後、「学生」ノードに「生活」ノードがあると、もう一回クエリを減らすことができます。この次の層のノードがマッチングできないため、ジャンプする必要があるポインタが失敗のポインタです。失敗のポインタを作成したツリーは次のように見えます。
図上の赤い線は失敗ポインタです。下のノードが一致しない場合、どのノードにジャンプしてマッチングを続けるべきかを指します。
失敗したポインタの作成プロセスは、通常は以下の通りです。
1.trieツリーを作成します。
2.BFSの各ノード（DFSは使用できない。なぜなら、各階層のノードの失敗ポインタは、作成時に、前の階層のノードの失敗ポインタが全部作成されたことを保証するためである。）
3.ルートノードのサブノードの失敗ポインタは、ルートノードを指す。
4.他のノードは、親ノードの失敗ポインタが指すノードのサブノードがノードワードと同じノードを持っているかどうかを調べ、失敗ポインタがノードに向けられている場合、ない場合は、同じノードまたはルートノードが見つかるまで、先ほどのプロセスを繰り返す。
照会のプロセスは以下の通りです。
このコードを実行すると出力されます。
大学
大学生
学生
生活
辞書に出てくるすべての語にマッチした後、次のステップを続けます。得られた集合の中で、「大学生活」という文章に結合できるすべてのサブセットを見つけます。しかし、このところで一つの小さな問題がありました。上で調べた4つの単語の中には「大学」と「生活」という言葉だけが「大学生活」という文章を作ることができます。辞書がすべての単語を網羅するのは難しいという現実があります。ここでは、一致する単語の集合に単一の単語を追加的に配置することができ、これは新しいセットを得る。
[大学、大学生、学生、生活]U[大、学、生、活]=[大学、大学生、学生、生活、大、学、生、活]
この集合の分詞の組み合わせは、スタートノードから終了ノードまでの全経路がすべての分詞方式であることを図に示すことができる。
三、最終的な分詞の結果
これらの可能な分詞の組み合わせの中で、最終的な分詞の結果としてどれを選ぶべきですか？大部分の分詞器の主な違いはここにも現れています。いくつかの分詞器は使用者の選択のためにさまざまな分詞戦略があるかもしれません。例えば、最小ワードポリシーは、エンドノードに到達することができるすべての経路の中で最も短い（最小ノードを通過する）1つを図中に選択することである。上のこの方向図に対して、最短経路は2つあります。それぞれ「大学、生活」と「大学生、生活」の最終的な分詞はこの2つの経路の中で一つを選びます。この選択法は最も簡単で性能も高いが，精度が劣る。実際によく考えてみると、どの分詞戦略を使っても、一番正しい確率の高いものを選ぶのが目的です。大学生活は、「大、学、生」の確率がP（大）P（学𞓜大）P（生124;大、学）P（活𞓜大、学、生）です。つまり、その確率を計算するには、「大」の出現確率を知る必要があります。「生」が同時に現れた時に「生」が現れる確率。これらの出現確率は、大量の文章からなるテキストライブラリで集計できますが、問題は、辞書が任意のN個の単語を記録する場合、単語Wが出現する確率、M個の単語を格納する辞書はM^N級の関係データを保存する必要があります。この辞書は大きすぎるので、Nの大きさは制限されます。一般的にNは2または3です。条件確率を計算する時は、前の2つから3つの単語だけを考慮します。これはマルコフチェーンに基づいて行う簡略化です。Nを2と呼ぶ場合は二元モデル、Nを3と呼ぶ場合は三元モデルと呼ぶ。50万語の辞書がある二元モデルは50万円から50万円の関係が必要です。これもかなり大きいサイズです。圧縮したり、他の近似形式に変えたりできます。この部分は比較的複雑です。ここでは説明しないで、もっと簡単な形を使います。各単語の出現は独立した事件であると仮定して、P（大、学、生、生、生、生）＝P（大）P（学）P（生P）P（生P）（生P）（生P）（生P））（生P）））（生P）（生P））（生P））この確率を計算するには、単語の出現確率、単語の出現確率=単語の出現回数/テキストライブラリの単語の総量を知る必要があります。前に使っていた辞書を「大学5、大学生4、勉強6、学習機3、学生5、怒っている8、生活7、生きている2」に更新した後の数字はこれらの単語がテキストバンクに出現する回数で、テキストバンクの単語の問題はこれらの単語の出現回数の合計=5+4+5+8+7+2=40です。
P（大学、生活）＝P（大学）P（生活）＝5/40*7/40
P（大学生、活）=P（大学生）P（活）＝4/40*0/40ここで問題が発生しました。辞書にない単語については、その確率は0です。これは乗積全体が0になるという不合理なことです。この場合は平滑処理ができます。簡単に言えば、辞書にない単語の出現回数を1に設定できます。活)=P（大学生）P（活）=4/40*1/40
最終的には最も可能な単語の組み合わせを選ぶことができます。これで3歩目が終わります。
以上が簡単な分詞器Tokenizerの詳細です。分詞器Tokenizerに関する資料は他の関連記事に注目してください。