Chinese Word Segmentation based on Maximum Matching and Word Binding Force

Chinese Word Segmentation based on Maximum Matching and Word Binding Force Pak-kwong Wong and Chorkin Chan DeI)artment of Computer Scien(;(~ The Univ(;rsil;y of Itong Kong l)okfulam ih)a,d thmg Kong pkwong((~cs.hku.hk and (:chan¢~cs.hku.hk Abstract A Chinese word Seglnentation algorithm based on forward icnaxinnlln matching and word binding force is t)roposed in this pai)er. This algorithm Iilays a key role in post-processing the outtmt of a character or st/eech recognizer in deter- mining the proper word sequence c(/rre- st)onding to an input line of cha.raeter images or a speech wav(~,fol'tn. ~FO sup- port this algorithm, a text; (:orims of over 63 millions characters is employed to en- rich an 80,O00-words lexi(:on in terlns of its word entries and word binding forces. As it stands now, given an input line of text, the word segmentor can proce, ss on the average 210,000 characters per se(:- ond when running on an IBM RISC Sys- tem/6000 3BT workstation with a col rect word identitication rate of 99.74%. 1 Introduction A language model as a t)ost-processor is esse, ntial to a recognizer of speech or characters in order to determine the approi)riate word se, que, n(:e and henc.e the semantics of an inI)ut line of text or ut- terance. It is well known that an N-gram statistics language model is just as effective as, t)ut nmch more eificient than, a syntactk:/semantic analyser in determining the correct word sequence. A nec- essary condition to successflfl collection of N-gram statistics is the existence of a coInprehensive le, x- icon and a large text corpus. The latter must tie lexically analysed in order to identify all the words, from which, N-gram statistics can be de- rived. About 5,000 characters are being used in mod- ern Chinese and they are the building blocks of all wor(ls. Ahnost every character is a word and inost words are of one or two characters long but there are also abundant wor(ls longer than two charac- ters. Before it; is seginented into words, a line of text is just a sequence of characters and there are numerous word segmentation alternatives. Usu- ally, all but one of these alternatives arc syntac- tically and/or semantically incorrect. This is l;he case because unlike texts in English, Chinese texl;s have no word nlarkers. A tirst step towmds buiht- ing a language model based on N-gram statistics is to de, vek)p an etIMent lexical analyser to id(!ntify all the words in the, corpus. Word segmentation algorithlns behmg to one of two types ill general, viz., the structural (Wang et al., 1991) and the statistical type (Lua, 1990)(Lua and Gan, 1994)(Sproat and Shih, 1990) rt;spec- tively. A structural algorithm resolves segmenta- tion mnbiguities by examining the structural rcla- tionships between words, while a statistical algo-- rithm compares the usage flequencies of the words and their ordered combinations inste, ad. Both ap- proaches ln~ve serious liinitat;ions. 2 Maximum Matching Method for Segmentation Maximum matching (l,iu et al., /994) is one of the most I)opular structural segmentation algorithms for Chinese texts. This …

Content truncated to 500 words