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

A New Mel;hod of' N-gram S(;al:istics for Lmge Nulril.)er of' n all(] Autorna, tJc ]:.xl;ra, ct on of Words ml(] Phra,ses from Large icxl; Data o[' ,Ja,pa,nes(; M,~d,:otc, Nagao, Shilisul(e Mori l)(;pa, rl;illolit 0[" l!,]o,('.trl(:al ]!AIII~II]C(H'IIIg Kyo(,o University Abstract In the process of establish in g the it, form ation the- ory, C. F,. Shannon prol)ose.d the Markov I)ro(:ess as a good model to characterize ~t natural la.nguage. The core or this ide.a is t;o cah:ula.te the ['re(lU('Ii- des of strings compose(l of 'n characters ('n-grams), but this statistical analysis of large text. (lata a.,id for a large n lilts llever be(HI carried ()tit })eca./ise of the memory limitation of (:omputer and the short- age of text data. Taking advantage of the recent powerful computers we developed a. new aJgorithm of n-grams of large text data for arbitr~try hu'ge 'n a,nd (:alculated successl'ully, within ,'ela, tiv(.ly short thlle~ n-grams of some Japa,nese text (la, t~t con- taining between two an(l thirty million chara,(:ters. From this exl)eriment it 1)ecame (:loa,r t]l&t the au- tomatic extraction or detern,i,tation of words, (:om- l)ound words and (;ol]ocations is possible by mutu- ally comparing n-gram statistics for dill'etch t values of lt. category: topical pa,per~ quantitative linguisth:s, large text corpora, text t)rocesshlg 1 Introduction Claude E. Shannon estal)lished tile in foH.atio, the- ory in 19d8 [1]. Iris theory included the co,lcept tlutt ~ hmgnage could be a,pproximated by an n- th order Markov model by n to l)e extended t(~ infinity. Since his proposal there were ma.ny tri- ~tls to ea.h:ulate n-grams (statistics of 'n c},ara.(:ter strings of a language) lbr a big text data, of a, la.- guage, l[owever computers u 1) to tim present to.hi not ca.h:ulate them for a large n 1)e(:ause the cah:u- |ation require(1 hug(; amount of memory space au([ time. For example the I'r(,quen('y ea, h;ulati(m of 10- grams of English requires a,t least 2(;win l0 s ~ I() (~ giga word memory space. Therefore tile ca,lcuh~tiou was done at most for n :: d ,.o 5 wil;h modest text qua, n tit;,, We developed a new method of calcula, ting w gra.ms For large 'n's. We (1o not In'el)are a table for an 'n. gra.m. Our methods consists of two stages. The first stage perh)rms I;he sorting of sul)strings of a text, aim fin(Is out tile lenlKth of t:he prefix parts which axe the same for th(; a, dja(:ent sul)stritGs iN the st)rted ta,ble. The second sta,ge is the (:a,lcuh~,tion of an 'n-gram when it is aal(ed for a sl)ecific n. Only the existing 'n, chara,cter combinations require the ta, hle entrie,g t'm' (,lie l'requen(:y count, so that we .eed not r(,serve a, big si)ace for 'n-gram table. The progranl we ha,ve develol)e(1 requires 71 bytes for an l cha, ra,cter text of two byte (:ode such as Japa, llcse and Chinese texts and 6! bytes for an l character text o1' English and other F',uropean la,nguages. By the present program '., ca, n be extended up to …

Content truncated to 500 words