N-gramモデルと二分探索で英文の入力補完をするコマンド #アルゴリズム

こういうことができました。

コマンドラインツールまでは作って公開したので，どなたかテキストエディタのプラグインを作っていただけませんか……？

N-gram モデル

N-gram モデルとは，任意の文章を単語単位に分割し，N 個の単語ごとのかたまりに切り出したデータのことです。

I am a university student. という文章をいろいろな N で切り分けてみましょう。

N = 1 のとき

1個の単語ごとのかたまりに切り出します。すると

I
am
a
university
student

となります。

N = 2 のとき

2個ごとの単語のかたまりに切り出すので，

I am
am a
a university
university student

となります。

N = 3 のとき

I am a
am a university
a university student

になります。

たくさんの英文から N-gram モデルを作る

大量に英文を集めて，どんな N-gram がどのくらい出現するかを調べてみます。

例として，

I am a university student.
I am not a boy.
I will be back.

という大量の英文を集めることができたことにします。

N-gram の個数をそれぞれ数えてみましょう。すると，

I am → 2
I will → １
a boy → １
a university → １
am a → 1
am not → １
be back → １
not a → 1
university student → １
will be → １

という N-gram モデルが手に入ります。

N-gram モデルを使って次に来る単語の予測をする

前節では３つの英文から N-gram モデルを手に入れました。これをつかって英文の入力補完ができそうです。

例えば I に続く単語について考えてみましょう。
モデルを見てみると，Iで始まるものは，I am が２個，I will が１個とわかりました。
このことは，「Iの次にamは頻出する，willも登場する」と解釈することができます。
同様にして，「am のあとには a か not が来る」とわかります。

もし本当に大量に英文が手に入って，巨大な N-gram モデルが手に入ったなら，精度の良い補完ができそうに思えてきました。

The Google Books Ngram Viewer

実は Google はThe Google Books Ngram Viewerという，とんでもなく巨大な N-gram のデータを公開しています。
このデータは，すごい量の文献をスキャンして N = 1〜５の N-gram について，登場年や登場頻度を数えたものだそうです。
データの各行は

N-gram TAB 登場年 TAB 登場回数 TAB 登場する文献の個数 NEWLINE

となっており，例えば

circumvallate   1978   335    91
circumvallate   1979   261    91

という行は，circumvallate は 1978 年に 91 冊で 335 回，1979 年に 91 冊で 261 回登場していることを表しています。

このデータセットをいい感じに整形することで英語の入力補完の辞書として使えそうです。

データの整形

先程得られた N-gram モデルの例

I am → 2
I will → １
a boy → １
a university → １
am a → 1
am not → １
be back → １
not a → 1
university student → １
will be → １

より，辞書データを作成します。
(N-1)-gram を用いて N 番目の単語を求めることができればよいので，以下のようなデータにすればよさそうです。

I          am will
a          boy university
am         a not
be         back
not        a
university student
will       be

この辞書を検索することで「be のあとには back が来る」とわかりますね。

二分探索

Google Ngram Viewer のおかげで巨大な辞書を入手することができました。
データの一部（約2TB）を使い，手元であれこれ整形した結果，合計で 42,619,909 行の辞書を手に入れることができました！
ファイルサイズにして 1.63GB！これはやばい！

ところで，入力補完として使うためには検索の速さが求められます。
タイピングの速さよりも検索の速さが十分速くないと，入力にストレスを感じそうです。
42,619,909 行の辞書を検索するには気の遠くなる時間がかかりそう〜〜〜

そこで二分探索を使います。

二分探索とは，あらかじめソートされているデータに対して高速に検索をかけられるアルゴリズムです。
データを大小の2等分にして，「欲しいデータが大きい方にあるか，小さい方にあるか」を繰り返して検索対象を絞り込んでいきます。
データの個数が $N$ 個あった場合，計算量は $O(\log(N))$ です。つまりとんでもなく速い！
今回 N = 42,619,909 ですが， $\log(42619909) = 25.3\cdots$ なので26回比較をするだけで目当てのデータを見つけることができます。

ということをやるコマンドラインツールを作った

↓コマンドラインツール Nextword
https://github.com/high-moctane/nextword

↓Nextword が使うデータ
https://github.com/high-moctane/nextword-data

標準入力で英文を受け取って，標準出力に英単語の候補を返すだけのプログラムです。
Go 言語で書きました。

使い方とかを Qiita に乗せるのはあんまり趣旨じゃないのかな？という気がしたので，
もし英語の README.md が嘘英語すぎて読めない場合は，以下のブログをご覧になってください。
https://highmoctane.hatenablog.com/entry/2020/01/19/095526

本当は nextword を使ったテキストエディタの英文入力補完プラグインを公開するところまでやりたかったですが，
就活が忙しくなってきたのでしばらくできなそうです……。

もし優しい方がいらっしゃったら，この nextword を使ってエディタのプラグインを作っていただけませんか……？
個人的には Vim と VSCode のプラグインを使ってみたいです。
お待ちしています……(｀･ω･´)！

裏話

Google の N-gram のデータ，実はちゃんとソートされていないんですよ〜〜。
しかもデータのサイズが1ファイルあたり何十GBもある……。
ソートするのにもデータがメモリに乗り切らないのです。

この問題を解決するためにマージソートを使いました。
マージソートならデータをすべてメモリに乗せなくても，中間結果をファイルに保存すれば良いです。
ソートのアルゴリズムの特徴は計算量だけではないんだなあということが勉強になりました。