A Parsing Method for Identifying Words in Mandarin Chinese Sentences

1 Introduction

In processing Chinese sentences, the first phase is to identify words in sentences before doing further process­ ing, such as syntactic and semantic analysis (Chen, 88]. Each Chinese sentence is composed of a sequence of Chi­ nese characters. The character sequence is to be parti­ tioned into segments with each segment corresponding to a Chinese word. Unfortunately, there is no boundary mark between any two consecutive words in a Chinese sentence. For many Chinese sentences, there are usu­ ally many ways to identify words in the sentences, i.e. the sentences are ambiguous in word composition. For an input sentence, the identification module first looks up possible words in the system dictionary. If there exists any ambiguity, the identification system should resolve it. The system is to identify the most favorable sequence of words for the input sentence. Most work done in resolving the ambiguity arising from identify­ ing words is as follows. The approach uses a statistic method to group Chinese characters into two-character words making use of a measure of character association based on mutual information (Sproat and Shih, 90]. A statistic approach using frequency count of words [ ;tll{ , 86](Liu et al., 75] is based on the statistical relaxation method widely used in image processing (Fan and Tsai, 87]. The structural method sets up heuristic rules for word-to-word relation to check the relationship among characters [Ho, 83][Liang, 87](Yeh and Lee, 88a][Zhang, 87] . In the unification-based approach [Yeh and Lee, 88b](Yeh and Lee, 90], the unification is a primitive op­ eration. The ambiguous word strings are resolved by

Abstract

This paper presents a parsing method for identifying words in mandarin Chinese sentences. The identifi­ cation system is composed of a Tomita's parser aug­ mented with tests originally a part of the English­ Chinese machine translation system CCL-ECMT to­ gether with the associated augmented context-free grammar for word composition. The simple aug­ mented grammar with the score function effectively captures the intuitive idea oflongest possible compo­ sition of Chinese words in sentences and, at the same time, take into consideration the frequency counts of words. The identification rate of this system for the corpora taken from books and a newspaper is 99.6%. This identification system is simple, but the identification rate is relatively high. The min­ imum element for word-composition parsing is down to characters as opposed to sentence parsing down to Chinese words. It has the potential of incorpo­ rating phrase structures and semantic checking into the system. In this way, word identification, syntac­ tic and even semantic analysis can be organized into a single phase. The results of testing the word iden­ tification on corpora taken from books and a Chinese newspaper are also presented.

ambiguity-resolution rules. Then the survived segmen­ tations are ranked by the Markov process. Finally, an HPSG-based chart parser prunes results of identification of illegal syntactic and semantic construction.

This paper presents a simple but effective method for identifying Chinese words in sentences. It is based on the intuition of longest matching of Chinese words. The identification rate of testing on corpora of more than 16000 characters taken from a newspaper and books is about 99.6%. The word identification system is com­ posed of a dictionary, a simple context-free grammar with augmented tests for word composition, a score function embedded in the tests of grammar to reflect longest matching of Chinese words, and a Tomita's parser (Tomita, 86] augmented with tests. The parser is originally a part of the English-Chinese machine transla­ tion system CCL-ECMT, formally ERSO-ECMT (Tang and Huang, 88]. Here, the minimum element for pars­ ing is down to characters. The system usually outputs more than one result of word identification for an input Chinese sentence. The first output is the most favorable one which has highest score. The form of the Chinese word-composition grammar is the same as the one used for English sentence syntax in CCL-ECMT.

The structure of the Chinese word identification sys­ tem is shown in Figure 1.

2 The Dictionary, the Grammar for Word Composition, and the Parser

The system Chinese dictionary contains a list of Chinese words sorted by character. Each word has at least one character. Each entry contains the word, its frequency count, and its part of speech. The total number of words is about 90000. The dictionary is taken from a source independent of the testing corpora.

The basic concept of constructing the context-free grammar for composition of Chinese words is as follows, but not necessarily appearing in this form.

s --> WL

WL --> W WL

WL --> w

w --> X

w --> XX

w --> XXX

w --> xxxx

w --> xxxxx

In above, S is a Chinese sentence, WL a list of words, W a Chinese word, and x a Chinese character. In gen­ eral, Chinese words of more than five characters are very rare. Therefore, in the grammar for Chinese word com­ position, a Chinese word can only comprise one to five characters.

Word-composition tests can be augmented to gram­ mar rules. The resulting grammar is called augmented context-free grammar. A rule is currently being used by the parser to construct parsing tree only under the condition that the tests should be met for the present parsing status. Mainly, the augmented tests include the following categories in the system. Some examples are shown in below.

• 1). Replication of text:
• . Numbers:
• 3). Prefix: the first characters in the examples are the

ABAB -- !!tliU!III. AABB -- &&.-Jill . ABAC -- I&ISI!illl!. AAB ~otli. A-A W-W. A'!' A !!'!'!!. AA II II .

prefL"'{eS.

• 4). Suffix: the last characters in the examples are the suffixes.

In general, unknown words not covered by the tests in above can not be identified.

This system has the capability of easily adding com­ position rules and any syntactic structures written in the same form of augmented context-free grammar, such as the determiner measure rules collected by the Chinese Lexicon Group, Academia Sinica, Taiwan. At present, the determiner measure has been added into the word­ identification system. Syntactic and semantic checking for the current sentence segment under processing can also be added as tests under a grammar rule. The long­ term goal would be developing syntactic and semantic analysis for complete sentences and the associated word identification module as one system. In fact, there is no clear boundary between word identification and further syntactic and semantic analysis of sentences. In gen­ eral, the word identification can not be separated from the high level analysis, if we wish to do word identifi­ cation well. In the identification system presented here, syntax of sentence segments may help identify words.

3 The Score Function

A score function is set up in the system. The formula for the score function is based on the intuition of longest Chinese words matching and taking into the consider~ tion the frequency counts of words. The score function is implemented in the augmented tests under grammar rules. The score for an identification is accumulated until the end of parsing the whole sentence. The final accumulated score is the score of the result of identifi­ cation. For a sentence, there are usually more than one parsing tree. Each tree has its own score. The pars­ ing tree with highest score identifies the most favorable word composition of the input sentence. The score func­ tion for a sentence is as follows:

where length(word i) is the length of the ith word, frequency-count( word i) the frequency count of the ith word in the sentence, and constant set to 10,000,000,000 in the identification system. In fact, the constant can be any big number that makes

Lwordi[frequency-count(word i)/constant] < 1.

Since the summation in above is less than 1, the score from

would dominate the total score. The frequency count dominates the score only when comparing words of the same length.

4 The Structure of the Deter­ miner Measure

The Chinese Lexicon group, Computer Center, Academia Sinica, Taiwan, has developed a context-free grammar for determiner measure which is in the same form as the Chinese word composition grammar used here. This part of syntactic analysis has been merged into the word identification system.

For example, an expression with numbers is as fol­ lows.

NO= -. =· ~. :.~.n. 1\,t,A. n. +. e.T. ···· ~. · · ·· a. ~·} * IH1 --> (NO) Description = { ~. ~ M = { II . ·. ~. OM --> ( IN1 ) (optional Description ) ( M )

In above, DM defines the determiner measure, IN1 specifies numbers, M is a collection of units, and De­ scription is optional.

The determiner measure provides additional restric­ tions on syntactic structure of sentences with measure. It helps in identifying words of determiner measure.

5 An Example

Chinese sentence: IIIISt~P·ItAS!~~.

(People's life in developing country.)

The system outputs five trees. They corresponds to five results of identification. The first tree is the one with highest score. It should correspond to correct in­ terpretation of human, if it is identified right . The trees are as follows.

In the trees of this example, it clearly indicates that grouping of characters into words depends further on grouping of segments of sentence. The information of the system dictionary is apparently not enough to iden­ tify words in all sentences. To the extreme, the word identification process depends on syntactic and even se­ mantic information of the sentence.

6 Experiment

The word identification system is implemented in LISP on TI microExplorer. The average speed of identifi­ cation is about 13 characters per second. The testing corpora are taken from an article on optical character recognition, the preface of a book on QuickC and MS­ DOS, and an article from a Chinese newspaper. There are more than 16,000 characters in the corpora. The identification rate is defined as the ratio of the number of characters correctly identified and the total number of characters in the testing corpus. The identification rate for our corpora as a whole is 99.6 %.

Without test functions under the grammar rules to prune unfavorable trees in advance, the parser usually generate so many parsing trees for some long Chinese sentences. That would take long parsing time. For some sentences, the parsing time may exceed 6 minutes, a time set for the word identification system. The parsing time would be considerably reduced if many trees can be pruned away in advance. But it is possible that, in some cases, favorable trees might be cut off. This is a tradeoff between identification rate and run time.

Since the system is based on longest matching, a shorter matching already covered by a longer matching may be ignored. This would considerably reduced run time for constructing parsing trees. In this way, for some long sentences, the number of trees which survives may be less than 10, compared with more than 1200 trees in the cases of some sentences without tests and actions added for eliminating shorter matching. This kind of tests and actions can be easily implemented under the grammar rules. At present, the grammar is small and there are not many tests in the system, so the system can be easily maintained.

There are still some infrequent unsolvable problems which reflect in the misidentified rate 0.4 % under this scheme. Most problems of this kind need syntactic and even semantic information to solve them.

A list of misidentified sentences taken from the cor­ pora is collected in Appendix A.

7 Discussion and Conclusions

In processing Chinese sentence, identification of words is usually not done alone. In general , there is no clear boundary between identifying word composition and identifying the syntactic structure of sentences. The cor­ rectness of identification of some words even depends on the higher level syntactic and semantic structure.

Depending on the source of area, the identification rate may be different. The frequency count of words is collected from a corpus of a specific domain. It may not be applied to other domains with the same result.

Here a simple parsing method for Chinese word iden­ tification is presented. It has high identification rate and is flexible . Syntatic information for sentence segments and even semantic checking can be easily incorporated into the system.

8 Acknowledgments

The determiner measure presented in this paper is the work of Chinese Lexicon Knowledge Base Group, Computer Center, Academia Sinica, Nankang, Taiwan. Many thanks are due to all of them. We wish to thank Ming-Song Wang for his comments and support for test­ ing the corpora. We also wish to thank United Informat­ ics, Inc. , for providing us with the database of Chinese text .

The paper is a partial result of the project No. 33H3100 conducted by ITRI under the sponsorship of the Ministry of Economic Affairs, R.O.C.

Appendix A

The following are typical misidentified Chinese sentences taken from the testing corpora. They can be roughly classified into two categories. In each example, the first one is the output of the word identification system, and the second one is what the sentence is supposed to be identified that way.

Category 1. In this category, longest matching is wrong. The long segments of Chinese characters should be further identified into shorter words to make sense. The syntactic word composition rules are apparently not enough for word identification. In general , seman­ tic information is needed for this category. Fortunately enough, the method of longest matching can still iden­ tify words with identification rate of more than 99%.

<f till~ ·a ¢1 1ft B9 ~- Mlli BtM 1111

Category 2. In this category, the score contributed from length is the same for both the first result with highest score and the correct one. Here, the frequency count dominates the difference. Unfortunately, the most frequently used words are not always the one to make sense. It still needs syntactic and semantic information to rank the outcomes of identification.