Compression Methods by Code Mapping and Code Dividing for Chinese Dictionary Stored in a Double-Array Trie

Proceedings of the 5th International Joint Conference on Natural Language Processing, pages 1189–1197, Chiang Mai, Thailand, November 8 – 13, 2011. c⃝2011 AFNLP Compression Methods by Code Mapping and Code Dividing for Chinese Dictionary Stored in a Double-Array Trie Huidan Liu Institute of Software, Chinese Academy of Sciences; Graduate University of the Chinese Academy of Sciences huidan@iscas.ac.cn Minghua Nuo Institute of Software, Chinese Academy of Sciences; Graduate University of the Chinese Academy of Sciences minghua@iscas.ac.cn Longlong Ma Institute of Software, Chinese Academy of Sciences longlong@iscas.ac.cn Jian Wu Institute of Software, Chinese Academy of Sciences wujian@iscas.ac.cn Yeping He Institute of Software, Chinese Academy of Sciences yeping@iscas.ac.cn Abstract There is serious data sparseness problem in Chinese dictionary stored in a double- array trie. This paper proposes six com- pression methods by code mapping and code dividing to make it more compact, and a metric called Resource Consump- tion Ratio is proposed to evaluate these methods. Under the proposed criteria, five of the six methods are better than the base- line. The best method maps the character code into its frequency order, and then di- vides it into two jump codes. It achieves a space usage reduction of 39.88% and takes only 0.20% time of the baseline on the construction while it takes 13.21% more time on the retrieval. As preprocessing methods, these methods can be used to re- duce more space by combining to other compression method which improves the double-array structure itself. 1 Introduction In many applications of processing strings, a trie search is very useful because it enables fast re- trieval and longest prefix matching with a smal- l dictionary (Fredkin, 1960). Tries are used in a broad range of applications to represent a set of strings in fields such as information retrieval sys- tems (Brain and Tharp, 1994; Nelson, 1997; Oka- da et al., 2001), lexical analyses (Aho et al., 2007; Lesk, 1975), morphological analyses (Aoe et al., 1996), natural language processing (Baeza-Yates and Gonnet, 1996; Peterson, 1980), bibliographic search (Aho et al., 1975), pattern matching (Flajo- let and Puech, 1986), for IP address routing tables (Fu et al., 2007; Nilsson and Karlsson, 1999; Pao and Li, 2003), and text indexing (Navarro, 2004). Double-array is a trie implementation which is proposed by (Aoe, 1989), and it is widely used in many applications at present because it combines the fast access of a matrix form with the compact- ness of a list form. However, there is a serious data sparseness problem when the double-array is used to store Chinese dictionary (Chinese double-array, hereafter, and similarly, English double-array for English dictionary). For a typical English dic- tionary with 45,373 words, the compression ra- tio of the double-array reaches 94.48%, but for a Chinese dictionary with 343,103 words, it’s on- ly 43.95%. In this paper, we analyze the reason- s which lead to the data sparseness, and propose several methods to reduce the space usage of the Chinese double-array. This paper is organized as follows: Section 2 introduces related work. Section 3 …

Content truncated to 500 words