A Segmentation Matrix Method for Chinese Segmentation Ambiguity Analysis

Computational Linguistics and Chinese Language Processing Vol. 21, No. 1, June 2016, pp. 1-28 1  The Association for Computational Linguistics and Chinese Language Processing A Segmentation Matrix Method for Chinese Segmentation Ambiguity Analysis Yanping Chen,, Qinghua Zheng, Feng Tian, and Deli Zheng Abstract Chinese Segmentation Ambiguity (CSA) is a fundamental problem confronted when processing Chinese language, where a sentence can generate more than one segmentation paths. Two techniques are commonly used to identify CSA: Omni-segmentation and Bi-directional Maximum Matching (BiMM). Due to the high computational complexity, Omni-segmentation is difficult to be applied for big data. BiMM is easier to be implemented and has a higher speed. However, recall of BiMM is much lower. In this paper, a Segmentation Matrix (SM) method is presented, which encodes each sentence as a matrix, then maps string operation into set operations. To identify CSA, instead of scanning a whole sentence, only specific areas of the matrix are checked. SM has a computational complexity close to BiMM with recall the same as Omni-segmentation. In addition to CSA identification, SM also supports lexicon-based Chinese word segmentation. In our experiments, based on SM, several issues about CSA are explored. The result shows that SM is useful for CSA analysis. Keywords: Segmentation Matrix, Segmentation Ambiguity. 1. Introduction Chinese characters are originated from hieroglyphic and written next to each other without delimiter in between. The lack of orthographic words makes Chinese word segmentation difficult. It is often that a Chinese sentence can be parsed into several segmentation paths, which results in the Chinese Segmentation Ambiguity (CSA) problem. It can be roughly classified into two categories: Overlapping Ambiguity (OA) and Combinational Ambiguity (CA)1 (Liang, 1984; Sun, 2001). For the OA problem, a sentence contains at least two  Guizhou University  Xi'an Jiaotong University E-mail: ypench@gmail.com; qhzheng@mail.xjtu.edu.cn; ftian@sei.xjtu.edu.cn,; delizheng.2009@gmail.com 1 Formal definitions of CA and OA are given in Section 2. 2 Yanping Chen et al. overlapped words. For example, “温柔和” contains two overlapped words: “温柔” (Gentle) and “柔和” (Soft). The character “柔” can be assembled with either “温” and “和”. Only one is suitable in a given context. In Chinese, every character can be either a morpheme or a word (Li, 2011). Then, given a word containing more than one characters, whether it is appropriate to segment it will lead to the CA problem. For example, “温柔” (Gentle) can be further segmented into “温/柔” (Warm/ Soft). In Chinese, the OA is prevalent. For example, in the Penn Chinese Treebank corpus, there are 39% sentences are identified with this ambiguity. Therefore, the OA is widely studied in this field. When the CA is under consideration, the problem is more serious. For example, in the lexicon of our experiments, 75.25% words have the CA problem, even using a loose definition (See Definition 4 of Section 3). Furthermore, CA and OA are not independent. They often co-occur within a sentence, which worsens the performance of Chinese word segmentation (Chen et al., 2012). The problem is deteriorated by the fact that Chinese …

Content truncated to 500 words