A New Method of N-gram Statistics for Large Number of n and Automatic Extraction of Words and Phrases from Large Text Data of Japanese

Makoto Nagao, Shinske Mori
A New Method of N-gram Statistics for Large Number of n and Automatic Extraction of Words and Phrases from Large Text Data of Japanese
COLING '94 Proceedings of the 15th conference on Computational linguistics - Volume 1, Pages 611-615

大規模テキストから文字 n-gram 出現頻度を計算するアルゴリズム

2つのステージからなる

First stage
文字からなる入力文字列に対して,番目から末尾までの部分文字列を-th word と呼ぶ.
この words を辞書順でソートし(comb sortを使うと計算量は),隣接した words の共通する接頭辞の長さを数える.

Second stage
ソート後の最初の word のn文字を読む.
また,次の word との共通接頭辞の長さをみる.
n以上なら,次の word と2つ先の word の共通接頭辞の長さをみる... と繰り返す.
n より小さくなった時点で,チェックした words の数が最初の word の先頭 n文字の出現頻度となる.
これを最後まで続ければ,n-gramの出現頻度表を得られる.
Comments