バイグラムとは、テキスト内またはテキストのコーパス内で隣接する2つの単語です。 たとえば、文で：
暑い夏でした。 1 2 3 4 5（夏の後のスペースはタイプミスでも間違いでもない）
そのようなバイグラムがあります：
- それは
- 暑かった
- 暑い夏に
- 夏に。
厳密に言えば、バイグラムは単語ではなくトークンで構成されています。 トークン、つまり タスクのフレームワークで分割できない単位は、単語または句読点のいずれかです。 トークン化は簡単なトピックではないので、私たちの体はすでにトークン化されて提案に分割されていると仮定します。提案をトークンのリストに変換するには、スペースで分割するだけで十分です。
私たちの仕事は、このリストを取得することです。
- それは190360でした
- 暑かった1017
- 暑い夏2621
- 夏に。 42146
数字は、ケース全体でバイグラムが見つかった回数を示します。
テキストでは、二重結合という用語をバイグラムという言葉の同義語として使用することを許可する場合があります。
この記事では、すべての実装の詳細を意図的に省略しました。 このアプローチ自体は興味深いものであり、お気に入りのプログラミング言語で実装することは難しくありません。 さらに、実装には、別の記事で説明するのに十分な興味深い詳細が含まれています。 説明文の最小数はJavaで示されます。
素朴なアプローチ
- 船体を駆け抜ける
- 各文からバイグラムを抽出する
- マルチセットデータ構造を使用してそれらを読み取ります（Javaでは、これはマルチスレッドバージョンではMultiset <String>またはConcurrentHashMultiset <String>です）
比較的小さくクリーンなケースでは機能するかもしれませんが、一般的なケースでは、単純なアプローチでは、テキストの配列全体を数える前にメモリが不足します。
中間クリッピングを追加
少し変更するだけで、単純なアプローチを実用的なアプローチに変えるのは非常に簡単です。
- 船体を駆け抜ける
- 各文からバイグラムを抽出する
- マルチセットを使用してそれらを数えます
- メモリが終了していることがわかるとすぐに、カウンターをクリアし、この時点で発生したバイグラムをしきい値の回数よりも削除します
この変更は完全に機能するアルゴリズムを提供しますが、カットオフは1つの問題をもたらします。不規則なタイプミスやエラーなどの不要なノイズとともに、まれな単語に関する多くの有用な情報を削除します。 たとえば、語彙素（単語形式のセット）がコーパスに1000回出現する場合、その個々の単語形式は、たとえばコーパスごとに200回未満しか出現せず、二重の組み合わせについて言えます。
私たちのタスクは、中間カットオフを使用せずに、可能な限り正直にバイグラムを数えることです。
一時メモリとしてディスクを使用します
RAMは現在比較的安価ですが、それでも価値があります。 さらに、16ギガバイトを超えるラップトップの多くのバージョンでは、プラットフォームの制限のため、思い通りにインストールすることはできません。 ディスク容量に問題はありません。コストが大幅に削減され、必要に応じて外付けドライブをいつでも使用できます。
セマンティックタグが言及されると、メモリ内の#hard_driveと#algorithmがマージソートとマージソートリストをポップアップ表示します。多くはPascalの学校で書きました。 これらのアルゴリズムの根底にあるアイデアは、問題の解決に非常に適しています。
問題の解決策の模式図
詳細に進む前に、問題の解決策の概略図を示します。
- ケースをほぼ等しいブロックに分割します。たとえば、それぞれ1ギガバイトです。
- ブロックごとにバイグラムを個別にカウントし、辞書式順序で並べ替えてディスクに書き込みます。
- 順序付きリストをマージするアルゴリズムを使用して、別々のファイルを2つの組み合わせで1つに結合し、一致するバイグラムの出現回数を合計します。
各ブロックのサイズは好みに合わせて選択できます（インストールされているRAMの数に応じて読みます）が、ほとんどのタスクではギガバイト単位のサイズが便利です。 また、プログラムで処理されたテキストのサイズに応じてカットオフを作成し、結果をディスクにドロップしてデータ構造をクリアする、モノリシックなケースで作業することもできます。
アルゴリズムを鳥瞰図で見ると、詳細に行くことができます。
各ブロックのバイグラムを数える
ダブルカウンターの最適なアーキテクチャを構築するには、2つの重要な要件を検討します。
- 複数のスレッドでカウントしたい。
- 出力では、辞書式順序でソートされたバイグラムのリストを取得する必要があります。
これらの2つのタスクを効果的に一緒に解決できることがわかりました。 シングルレベルカードを使用する代わりに提案されます（マルチセットは基本的にキーカウンターカードです）
ConcurrentHashMultiset<String>
バイグラムを計算するには、カードのマップを使用します。
ConcurrentMap<String, ConcurrentHashMultiset<String>>
この実験は、両方のデータ構造を使用した組み合わせのマルチスレッド計算がほぼ同時に実行されることを示していますが、2レベルマップを使用したソートははるかに高速です。 外部カードと内部カードのキーを個別にソートできます。
2レベルカードが提供するもう1つの主な利点は、バイグラムに従って追加のフィルタリングを非常に迅速に実行できることです。 たとえば、辞書のエントリを確認したり、正規化を実行したりすることもできます（高速ライド->高速ライド）。 同じ組み合わせをグループ化する前にこれらの操作を実行するのは非常に費用がかかります。 同じ操作が何度も実行されます。
すべてのブロックの結果を組み合わせる
したがって、前のアルゴリズムの出力には、次の形式のエントリを持つ多くのファイルがあります。
bigram1 count1 bigram2 count2 ... bigramN countN
キーは辞書式順序でソートされます。 私たちのタスクは、これらのファイルを1つに結合し、一致するキーの出現回数を合計することです。 2つのファイルを合計するタスクは簡単なものと見なされ、これ以上の説明は省略します。
すべてのファイルを結合する一般的なタスクは、バッテリーファイルを使用して解決でき、個々のブロックのファイルを順次追加します。
((((((N1 + N2) + N3) + N4) + N5) + N6) + N7)...
ただし、このキャンペーンは効果がありません。 一定回数の反復の後、個々のブロックの比較的小さなファイルを比較的大きなバッテリーに追加し、ほとんどの時間をディスクからのデータの読み取りとディスクへの書き込みに費やします。 一致するキーが1つのレコードに折りたたまれ、結果のファイルが2つの元のファイルの合計よりも小さくなるため、各反復でほぼ同じサイズのブロックが合計されるような戦略を構築する方がはるかに有益です。
再帰を使用するマージソートの実装フレームワークは、実装に最適です。 15個のファイルの概略図は次のようになります（マージ機能の場合、最初のインデックスがオンになり、2番目のインデックスは除外されます）。
| _ merge（0、15）= merge（0、7）+ merge（7、15）
| _ merge（0、7）= merge（0、3）+ merge（3、7）
| _ merge（0、3）= 0 + merge（1、3）
| _ merge（1、3）= 1 + 2
| _ merge（3、7）= merge（3、5）+ merge（5、7）
| _ merge（3、5）= 3 + 4
| _ merge（5、7）= 5 + 6
| _ merge（7、15）= merge（7、11）+ merge（11、15）
| _ merge（7、11）= merge（7、9）+ merge（9、11）
| _ merge（7、9）= 7 + 8
| _ merge（9、11）= 9 + 10
| _ merge（11、15）= merge（11、13）+ merge（13、15）
| _ merge（11、13）= 11 + 12
| _ merge（13、15）= 13 + 14
結果として、アルゴリズムは同じ14の合併を行いますが、バッテリーオプションを使用するとはるかに効率的に機能します。 マージアルゴリズムの理論的なメモリ要件はO（1）ですが、実際には、メモリは読み取りおよび書き込みバッファにのみ割り当てられます。
結論として
上記のアプローチを使用すると、ケースのバイグラムだけでなく、任意のnのn-gramも収集できます。 小さいブロックを使用する必要があり、多くの場合、中間結果をディスクにスローします。
冒頭で述べたように、実装の詳細については別の議論に値します。次の記事でそれらについて説明します。