Wikipediaの英語版と日本語版のデータを解析して、単語Nグラムの生起確率のデータベースを作ってみた話。このデータは獲得年齢の推定にも使われるし、他にも様々な場合に単語やフレーズをポピュラーな順に並べるのに利用できる。誰かの役に立つかもしれないから、プログラムとデータを公開しておく。
今回は、Wikipediaを解析して、3グラムまでの単語の頻度を数えた。結果として、以下のデータベースが得られた。TkrzwのSkipDBMデータベースファイルである。
上記はBZIP2圧縮ファイルなので、ダウンロードしたらbunzip2コマンドで復元すること。中身を見るには以下のコマンドを実行する。
$ tkrzw_dbm_util get enwiki-stem-phrase-count.tks "" 94425391 $ tkrzw_dbm_util get enwiki-stem-phrase-count.tks "Tokyo " 64734 $ tkrzw_dbm_util get enwiki-stem-phrase-count.tks "Tokyo Disney Resort" 103 $ tkrzw_dbm_util list --jump "Mikio" --items 10 enwiki-stem-phrase-count.tks Mikio 260 Mikio Fujioka 3 Mikio Hirama 9 Mikio Ikemoto 5 Mikio Naruse 74 Mikio Naruse and 9 Mikio Oda 11 Mikio Sakai 3 Mikio Sato 13 Mikio be 3
キーが空白であるレコードは解析した文の数を示す。上記によると、9442万文を解析したようだ。それ以外のレコードは、キーのフレーズが出現した文の数を示す。一つの文に複数回出現しても1としか数えない。よって、その値を文の数で割れば、そのフレーズが文に出現する確率がわかる。例えば、「Tokyo」は 64734文に現れたので、出現率は0.068%だ。SkipDBMではキーが文字列の昇順で並んでいるので、前方一致検索ができる。listコマンドと--jumpオプションでそれを行う。上の例では、"Mikio" 以降のレコードを最大10件表示している。
単語の分割は、英語の場合には空白（というかラテン文字と半角数字とハイフン以外の全て）を区切りとして行い、日本語の場合にはMecabにかけて行なっている。よって、利用するアプリケーションも同じ方法で単語の分割を行なった上で、単語を空白で連結して検索キーを作る必要がある。ステミングなしの場合「走ったカメ」は "走っ た カメ" とし、「She loves him」は「She loves him」のままである。ステミングありの場合は各単語の基本形を並べて "走る た カメ" や "She love him" とする。また、屈折（もしくは活用・曲用）が起こる単語を基本形に直す処理をステミングとかレンマタイゼーションとかいうが、それを適用してから数え上げを行ったデータベースと、そうでないデータベースの二種類を用意した。基本形の取得は英語はNLTKで行い、日本語はMecabで行った。英和辞書を作るのに使うにはステミングがしてあった方が便利だが、その他の多くの用途では未加工の方が便利だろう。
そもそも何でN-gramのデータベースが必要になったかというと、Wiktionaryのレコードを全部辞書にしていては無駄が多すぎるからだ。マイナーすぎる固有名詞とか古語とかスペルミスとかは捨ててしまいたい。また、日本語の訳語に対応する英単語やフレーズが複数ある場合には出現数が多いものを優先して並べたい。辞書に含めるのは単語だけでなく複数語のフレーズもあるので、単語だけのデータベースでは不十分だ。英和辞書の構築に利用するくらいなら3グラムで十分だ。"come to an end" とか "come hell or high water" のような4グラム以上のフレーズも扱うけれども、3グラムのデータベースがあればそれらの出現率は推定できる。とはいえ、5語の熟語がWikipediaに出てくることなんてほぼないのだが。
実装の細かい話をメモがてらに書いておく。単語の共起確率を調べるためのデータベースを作る話を以前にしたが、今回は同一文内の「単語」の共起ではなく、同一分内の「単語列」の生起確率を調べる。つまり、特定の単語の組み合わせが連続して現れる確率である。連続したN個の単語を扱ったデータを単語Nグラムと言うが、今回は3個までを扱うので単語3グラムのデータベースを作るということになる。例によって英語版と日本語版のWikipediaを入力データとして使ったが、プログラム自体はどんなコーパスでも利用できる。
- parse_wikipedia.py : WikipediaのXMLからプレーンテキストを取り出す
- tokenize_text.py : プレーンテキストを単語列に分解し、ステミングを行う
- count_ngram_phrases.py : 単語列を頻度を数える
- divide_ngram_phrases.py : 単語列の頻度を文の数で割って確率を求める
「git clone https://github.com/estraier/tkrzw-dict.git」で一気にダウンロードした方が楽だろう。一連のコマンドは以下のように実行する。事前にPythonのregexモジュールとnltkモジュールとMeCabモジュールとtkrzwモジュールを入れておく必要がある。
$ bzcat enwiki-20200701-pages-articles-multistream.xml.bz2 > enwiki-raw.tsv $ cat enwiki-raw.tsv | ./tokenize_text.py --language en --stem --max_sentences 32 --readable > enwiki-tokenized-stem.tsv $ cat enwiki-tokenized-stem.tsv | ./count_ngram_phrases.py --data_prefix enwiki-stem
SkipDBMのファイルをスキャンしてレコードの値を確率に直し、かつ形式をHashDBMに変更するには、以下のコマンドを用いる。
$ ./divide_ngram_phrases.py --data_prefix enwiki-stem
一連のプログラムを、「生テキストの抽出」「トークナイジングおよびステミング」「数え上げ」「利用形式への変換」の4工程で分割したのは理由がある。第1工程でデータソースの形式への依存を終了させ、第2工程で自然言語処理への依存を終了させ、第3工程でスケーラビリティの問題を終了させ、第4工程でユースケースに合わせたデータを獲得する。それぞれのプログラムが入れ替え可能なのが重要だ。第4工程ではTkrzwのHashDBMに変換しているが、適当なプログラムを書いてtrie系のデータベースに変換する方が使い勝手が良いかもしれない。出現率が低すぎるレコードを消したり、ストップワードにペナルティをかけたりしてデータ量の削減に努めるのもよいだろう。
第3工程の数え上げのプログラムが今回の要点である。入力として、プレーンテキストかTSVテキストを受け取る。改行かタブを文区切りとして認識し、それ以外の空白文字を単語区切りとして認識し、それ以外の文字の連続を単語として認識する。大文字と小文字の正規化は行わない。例えば、「Japan」を「japan」に直したりはしない。ただし、文頭の単語だけは特別扱いする。文頭の単語が大文字で始まって小文字が続く場合には、先頭の大文字を小文字に正規化した単語も同時に出現したとみなす。例えば、「Leave me alone」という文があったなら、「Leave」「Leave me」「Leave me alone」「me」「me alone」「alone」を数え上げるとともに、「Leave」を小文字にした「leave」「leave me」「leave me alone」も数え上げる。文中の大文字の単語は正規化しない。文頭のみを二重に数えることで普通の語が文頭で大文字になった場合の救済をするとともに、固有名詞が文頭に来る可能性を考慮しても、その小文字の出現率が大文字のそれを上回ることがないようにできる。これに基づくと、「Japan」の出現率は0.29%で、「japan」の出現率は0.005%ということになる。
共起語の数え上げよりは少しは楽だが、N-gramの数え上げも組み合わせ問題になるので、レコード数が膨大になる。3グラムの場合、単語を一つ読む度に3つのフレーズの出現を記録せねばならない。今回は1億文くらい読んで、1文あたり平均20語くらいあるので、60億フレーズの出現を記録する。出現数は何らかの連想配列に記録せねばならないが、そのレコード数は異なりフレーズの数と同じになる。60億フレーズの全てが異なるということはありえないが、3グラムともなると、数10%くらいは異なることになる。仮に10%としても6億レコードの連想配列をメモリ上に保持することになり、1台で解析するのはなかなか大変だ。なので、例によってミニバッチ化して、途中結果を別個のSkipDBMに吐き出し、最後にマージする。ミニバッチ内で使う連想配列にはオンメモリB+木であるBabyDBMを使ってメモリ容量を削減するとともに、低頻度フレーズを足切りすることで、途中経過のSkipDBMの容量も抑える。スキップリストはソート済みのレコードを保持するので、最後のマージ処理は異なりフレーズ数Nとミニバッチ数Mに対してN*log(M)の計算量で済む。この方法だと、4グラムだろうが5グラムだろうが時間をかければ1台で解析できる。私のノートPCで動かして3グラムで5時間くらいで済むので、4グラムや5グラムでも10時間以内には終わりそうだ。
まとめ。1億文（20億語）の単語N-gramの数え上げくらいならPC1台でできるよ。DBMライブラリはすごく便利だよ。本当だよ。
