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