о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999 36 9 Vol.36 No.9 1999



߽Զֵģ㷨
ꡡ
ժҪκͺֽϵȸϣзֱһִĴģͺһڴڲⲿֽ϶ȵĺֽϵģͣԲֵģںһк߽绮.ڷзֺѡռĻϣлӦŻ㷨.һͳƷȣзģͲֱӴδӹеõнǿӦ.÷ЧͿɿ.
ؼʡִʣΣֽϵ
ͼšTP391TP301.6
MODELS AND ALGORITHM FOR ASSIGNING WORD BREAKS TO CHINESE TEXT
FU Guo-Hong and
(Department of Computer Science and Engineering, Harbin Institute of Technology, Harbin 150001)
WANG Xiao-Long
(Department of Computer Science, Hong Kong Polytechnic University Hong Kong)
AbstractIn this paper, the word form model (WFM) based on word formation power of Chinese character string and the character juncture model (CJM) based on the affinity of the Chinese character pairs inside or outside words are described respectively. Then a linear interpolation method is applied to combine these two models together to assign word breaks to Chinese text. The relative searching algorithm is also given after the searching space is analyzed. Compared with general statistic models, the parameters of the models proposed can be directly trained from raw corpus, which results in a strong adaptability. The approach has proven both reliable and efficient by experiments. 
Key wordsChinese word segmentation, character juncture, word form
1
ȻġԶõСλ.ȻԴϵͳ롢ʶȶΪĴλ.Ǻıǻֵģ֮˱ûޱ־.ڴﴦҪǺִ.
ĿǰִҪ෽ڴʵķ13ݡͳƵķ45ݺͻϷ6.Ȼִʵоȡþ޴ɾͣںʶģԼͺʵ串ƣûбȽʵõķִϵͳ.
ķִʵһ߽绮ֹ.дڵз⣬뺺ֽϵʹεȸڷ˺ִĹڲּڴʵı߽Ӱϣֱ˴ģͺͺֽϵģͣԲֵģںһк߽绮.ͬʱԺִʵзֺѡռ˷ӦŻ㷨.봫ͳͳƷȣķֱͨδӹĴѵнǿӦ.ƵͳʵķЧͿɿ.
2ͳƵĺ߽绮ģ
2.1߽绮ֵĸʿ
1. һnִзֵS=Cn1=c1c2cnÿһںֶcici+1(1in)Ϊֽϵ(character juncture).ϵ߽ͣϵͷǴ߽ϵ㣬ֱtb=/tf=.
2.躺ִʴʵΪDںִCjiDƸִΪ(word form)f.fSfʾʵǾSеһзֺѡ.
ĳһw=Cji(1ijn)SڲֽϵΪtf߽ϵcjcj+1Ϊtb.ǣִʿΪһ߽绮ֹ̣úֽϵtbtfSзֳһϵִCji=cicj(1ijn)ʹִɵĴγɵĴʴW=Wm1=w1w2wm㺺ѧҪ.F=Fm1=f1f1fmΪWӦĴδTΪӦĺֽϵǴзִʴWɱʾΪԪ顴F,T.W^ΪSзֺѡ
=argwmaxWPr(WC)=argwmaxWPr(F,TC)
=argwmaxWPr(FC)Pr(TF,C)
=argwmaxWPr(FC)Pr(TF)
(1)
ʽPr(.)ʾ,arg max(.)ʾ(.).ʽеһƵ˸ʳ˷ʽڶƵϵֻڴһ.汾ĽֱӺִģͣͺֽϵӰ죨ϵģͣʽ(1)иʺ͵ļ㹫ʽ߽ϵļģ.
2.2ִĹģ(WFM)
ڸִPr(FC)=Pr(F)=Pr(W)ʵһڴƵķִģͣ7.ģ͵ĹؼǴƵƣһִͨϵеʦѧϰĿǰģĺִϻѻ.ף4ôƵķƵعƴƵȻַʵ޵ʦѧϰַĳ̶ֳһ̴ֶȵķײ̴ʽ϶ķִʽ.ף7ƥ䴮ƵĸĽȻִܱʽж̴ʵĴ֣÷ײϡ裺w1Ǵw2һӴѵw1Ϊw2Ӵ֣ôw1ĴƵPr(w1)=04.⣬ǲúִķƹƴƵ.
ͳƽǶȣf=CjiĹ(word formation powerWFP)СεʵʹƵйأôεĴʹó̶й.Pf(f)ʾfĹfʾfĴΣf(fD),N(\5)ʾִƵȣֱӴδӹıѧϰõ

(2)
F=f1f2fmΪSĳһδڴε໥Ӱ죬
Pr(FC)=Pr(f1f2fmCn1)=Pr(fkCn1)Pf(fk)
(3)
ʽ(3)ģͣӺִǶSзֳɴδFӦĴʴWĿ.
2.3 ֽϵģ(CJM)
t(cici+1)ʾֽϵͣĳһѡΪf=CjiS(1ijn)Ϊʣilj,t(clcl+1)=tft(cjcj+1)=tb.Pj(f)ΪfӦֽϵǴĸʣ
Pj(f)=Pr(t(cjcj+1))=tbcjcj+1)Pr(t(clcl+1)=tfclcl+1)
(4)
ȻPj(f)Խ󣬴fԽпܱзΪ.ڴε໥Ӱֻڴα߽ϵ㣬
Pr(TF)=Pj(fk)
(5)
ʽ(5)ֽϵģ.ӳںֽϳ̶Ⱥʹʱ߽໥Ӱ죬ģʵһ޴ʵִģ.ʽвͨѷʵϽѵģϺѵõ.Ϊ˱뺺ֻϢ򻯺ֽϵģ.
ֽϵcici+1MI(cici+1)ΪӦĻϢ

(6)
һأcici+1,Pr(t(cici+1)=tf)MI(cici+1).ζţڲĸֶԵĻϢϴ󣬶ڴʼֶԵĻϢԽС.ǣʽ(4)ɼΪ
Pj(f)=MI(clcl+1)-MI(cjcj+1)
(7)
2.4 ģںϵļģ
ϷԿģPfִֻĹĵӰ죻߽ģPbֻǿڴα߽ʹڲּ໥Ӱ죬Ӵε幹.ˣбҪģں.ʵߵӰ̶ȲͬͬʱΪ˱֤ǵĵһ£˱Ľʽ(3)ȡ֮󣬲Բֵķģͺʹ߽ģںһ𣬽Ƶرƽʽ(1)
=argwminW-logPf(fk)-(1-)Pj(fk)
(8)
ʽ(8)ĵĺ߽绮ּģ.У(1ܦˡ1)Ϊֵϵͨʵȷ2ʾȡ=0.9arg min(.)ʾ(.)С.
ʽ(8)дθʲ˶ʽĸ-logPf(f)ֽϵȡ˸ڸִִʵĿľǴпܵзѰһзִʴʹʽ(8)ļֵС.
ʽ(8)ʹüģиֱδӹĺԭʼıͳƵõѵռҲ󽵵ͣģ͵Ӧ.VcVwֱʾֿͺʵĴСģ͵Ĳѵռ(ƵȡֶֹԡƵ)ܹΪV2c+2Vw+Vcͬڴʵbi-gramģ͵ѵռV2wΪһVcVw.
3зֺѡռ㷨
3.1зֺѡռ
3.ڸS=Cn1УβĴɵĴδF=Fm1=f1f2fmΪþӵзֺѡʴ.
 4.ںnֵSзֺѡʴһжǰѾSпܵзֺѡʴɵļϣFΪӵзֺѡռ䣬n.зֺѡռĴСԦnʾn=n.
ڸS=Cn1=c1c2cnУlmaxʾʳԺciΪֵĴμϿɱʾΪ{fk}={Cji|Cji=cicjD,1ijn,1j-i+1lmaxӦĸγȣΪlk(1kni)niΪôμĴС.覵(i)ΪִCniкѡʴ

(9)
ʽ(9)ͨݹ鲢SӶзֺѡռ䦣nӦĴСn=(1).ɴ˿ԼӡйˮƽСзֺѡռСΪ168þ168з1ʾniͨʵƥõ.
1зֺѡռСnļ
i123456789101112
SйˮƽС
ni322222222121
(i)1688452322012844221
3.2 㷨
Sзֹʵзֺѡռ䦣nѰһѵзֺѡʴW^ʹʽ(8).ȽЧķʽʾеĺѡ֣ö̬滮㷨㷨񣬴һ·.ȫз˼Ļϣ÷̬滮㷨ͬջ㷨ϵĶɨ㷨㷨Ҫ󲽣(1)ôʵƥͶ3ɴ񣬲ͳݿ͹ʽ(2)(7)֣(2)÷̬滮㷨ͬջ㷨ϵĶɨ㷨񣬴һʽ(8)·.йشĶ㷨ף8ﲻ׸.
4ʵ
˼룬ʵһʵıĺ߽绮ϵͳ.ϵͳֿΪGB2312-80ֿ(6763֣.ϵͳʵ57400ʣҪɵӰıѧִ﷨Ϣʵ䡷9ɣڴ˻ϲ˿ȱGB2312-80 ֺͳõ57ִʣʹʵ걸.Ĳ1993Ӱ桶ձ1874֣ϵͳʵиִĹϵͳֶֿԵ׺϶Ƚѵ.ͬʱף10ɷִʵϣ346427ʣ585936֣ΪҪϣóõĺִִָ׼ȷʦʦΪϵͳָ꣬

(10)

(11)
Ҫ棺ִ׼ȷʵӰغģ͵.ڸϵͳָĻϣֱóʵԽ˷.
4.1з׼ȷʦӰ
Ӱз׼ȷʦкܶ࣬ĵʵҪֵϵģͺδ¼ʣ´ʣȷ棬ʵ2ͱ3ʾ.
2˴ʵ串ǲдʱзȷʦֵϵ˵ı仯.ӱݿԿ=0.9ʱڲδ¼ʵзȷʦﵽֵ99.75%ֱںֽϵģͣ=0.098.39%ʹģͣ=1.099.62%.
2׼ȷʦֵϵ˵Ĺϵ

0.00.10.20.30.40.50.60.70.80.91.0
(%)98.3998.4498.4998.5698.6998.8098.9899.1699.4499.7599.62

3˴ʵδ¼ʺͷִģͶ׼ȷʦӰʵ.ӱݿԿ(1) ģͺ޴ʵĽϵģ;ȡ˽Ϻõʵ˵ģЧģ(2)ģϵģ͵Ľзܣģ͵зȷʸ߳ͬµƥִ0.44ٷֵ㣻(3)δ¼ʶ׼ȷӰϴ.
3δ¼ʡģͶ׼ȷʦ(%)Ӱ

ģƥϵģʹģͻģ
ʵ串δ¼99.3298.3999.6299.75
ʵ䲻δ¼97.5196.9897.8097.95

4.2߽绮ģ͵
ķֱѵϺͲϳȡABģ͵˲ԣֱ296708ͬ.Խ4ʾ.
 4ģ͵Խ

 
 ģͺֽϵģͻģ
()()()
A29621973.9924683.1125686.49
B70848269.0858282.2859684.18

ӱݿɿ(1)ģ͵ۺ()ߣABʷֱΪ86.49%84.18%(2)AʵBĽܺڿţڱģͿֱӴδӹѵÿηǰʵֶԴзϽѧϰֲ죻(3)ݻʾֽϵģ͵ȴģǿ.ݷԭֽϵģͲ˺ֶԵĽڴʵı߽Ӱ. 
5չ
һ߽ԶֵͳģͣڷйغִʵռϣӦŻ㷨.ķصǽִĹʹڲּԼⲿڴʱֵ߽ӰϢһ壬ЩͳϢֱӴδӹĴеõҲѵռ䲻нǿӦӦǰ.
зʹʵδ¼Ǻִʵ⣬Ҫз.3ʵδ¼ʵӰ첻ɺ.δ¼ʵԶʶ߽Ļ֣ɿչķǺֵĹθfS,fD.ƪޣйδ¼⽫.
еʵûпϵͳʵ϶岻һµӰ.
עõҡĿĿ 863-3060-3-02-1.
߼飺, У19683ʿоҪ¼ѧо.
У19553ڣʿʦҪ˹ܺȻо.
ߵλꡡҵѧѧ빤ϵ150001
ѧϵ
ο
1Wang Xiaolong et al. The problem of separating characters into fewest words and its algorithms. Chinese Science Bulletin, 1989, 34(22):19241928
2Ԫ, ֣ӱ. һԶִģCWSMԶִϵͳPC-CWSS. Communications of COLIPS, 1991, 1(1): 5155
(Liang Nanyuan, Zheng Yanbin. A Chinese word segmentation model CWSM and segmentation system PC-CWSS. Communications of COLIPS(in Chinese), 1991, 1(1): 5155)
3ʤԶ. һִֺʷ. о뷢չ, 1997,33 (4):306311
(Wu Shengyuan. A Chinese word segmentation method. Computer Research and Development(in Chinese), 1997,33 (4):306311)
4Sproat R, Shih C, Gale W, Chang N. A stochastic finite-state word segmentation algorithm for Chinese. Computational Linguistics, 1996, 22(3): 377404
5ï, Ʋ, ޼.úԪ﷨ϵԶִеĽ. о뷢չ, 1997,34 (5): 332339
(Sun Maosong, Huang Changning, Zhou Jiayan et al. Using character bi-gram for ambiguity resolution in Chinese word segmentation. Computer Research and Development(in Chinese), 1997,34 (5): 332339)
6Wong P K, Chan C K. Chinese word segmentation based on maximum matching and word binding force. In: Proc of COLING '96, 16th Int Conference on Computational Linguistics, Copenhagen, Denmark, 1996. 200203
7Nasaaki Nagata. A self-organizing Japanese word segmenter using heuristic word identification and re-estimation. In: Proc of the 5th Workshop on Very Large Corpora, Beijing, 1997. 203215
8,,. ڴεĺıзַ. : ȫ˻ͨѶѧļ(NCMMSC-98),,1998. 328332
(Fu Guohong, Wang Xiaolong, Gong Yonghong. Word-form based Chinese word segmentation(in Chinese). In: Proc of the 5th National Conference on Man-Machine Speech Communication, Harbin, 1998.328332)
9ʿ. ִ﷨Ϣʵ. : 廪ѧ, 1998
(Yu Shiwen et al. The Grammatical Knowledge-Base of Contemporary ChineseA Complete Specification(in Chinese). Beijing: Tsinghua University Publishing House, 1998)
10 Hasan M M. Multilayer feedforward neural networks in part-of-speech tagging and word sense disambiguationMaster D dissertation]. National University of Singapore, Singapore, 1997
11 Taylor P, Black A W. Assigning phrase breaks from part-of-speech sequences. Computer Speech and Language, 1998,12(1): 99117
ԭյڣ1999-01-05޸ĸյڣ1999-06-03.
