A Trainable Rule-Based Algorithm for Word Segmentation

A Trainable Rule-based Algorithm for Word Segmentation David D. Palmer The MITRE Corporation 202 Burlington Rd. Bedford, MA 01730, USA palmer@mitre, org Abstract This paper presents a trainable rule-based algorithm for performing word segmen- tation. The algorithm provides a sim- ple, language-independent alternative to large-scale lexicai-based segmenters requir- ing large amounts of knowledge engineer- ing. As a stand-alone segmenter, we show our algorithm to produce high performance Chinese segmentation. In addition, we show the transformation-based algorithm to be effective in improving the output of several existing word segmentation algo- rithms in three different languages. 1 Introduction This paper presents a trainable rule-based algorithm for performing word segmentation. Our algorithm is effective both as a high-accuracy stand-alone seg- menter and as a postprocessor that improves the output of existing word segmentation algorithms. In the writing systems of many languages, includ- ing Chinese, Japanese, and Thai, words are not de- limited by spaces. Determining the word bound- aries, thus tokenizing the text, is usually one of the first necessary processing steps, making tasks such as part-of-speech tagging and parsing possible. A vari- ety of methods have recently been developed to per- form word segmentation and the results have been published widely. 1 A major difficulty in evaluating segmentation al- gorithms is that there are no widely-accepted guide- lines as to what constitutes a word, and there is therefore no agreement on how to "correctly" seg- ment a text in an unsegmented language. It is 1Most published segmentation work has been done for Chinese. For a discussion of recent Chinese segmentation work, see Sproat et al. (1996). frequently mentioned in segmentation papers that native speakers of a language do not always agree about the "correct" segmentation and that the same text could be segmented into several very different (and equally correct) sets of words by different na- tive speakers. Sproat et a1.(1996) and Wu and Fung (1994) give empirical results showing that an agree- ment rate between native speakers as low as 75% is common. Consequently, an algorithm which scores extremely well compared to one native segmentation may score dismally compared to other, equally "cor- rect" segmentations. We will discuss some other is- sues in evaluating word segmentation in Section 3.1. One solution to the problem of multiple correct segmentations might be to establish specific guide- lines for what is and is not a word in unsegmented languages. Given these guidelines, all corpora could theoretically be uniformly segmented according to the same conventions, and we could directly compare existing methods on the same corpora. While this approach has been successful in driving progress in NLP tasks such as part-of-speech tagging and pars- ing, there are valid arguments against adopting it for word segmentation. For example, since word seg- mentation is merely a preprocessing task for a wide variety of further tasks such as parsing, information extraction, and information retrieval, different seg- mentations can be useful or even essential for the different tasks. In this sense, word segmentation is similar to speech recognition, in …

Content truncated to 500 words