Design of a Compact Deta Structure for the Patricia Trie

• SHISHIBORI Masami

  the Department of Information Science & Intelligent Systems, University of Tokushima

• OKADA Makoto

  the Department of Information Science & Intelligent Systems, University of Tokushima

• SUMITOMO Tooru

  the Department of Information Science & Intelligent Systems, University of Tokushima

• AOE Jun-ichi

  the Department of Information Science & Intelligent Systems, University of Tokushima

抄録

In many applications, information retrieval is a very important research field. In several key strategies, the binary trie is famous as a fast access method able to retrieve keys in order. Especially, a Patricia trie gives the shallowest trie by eliminating all nodes which have only one arc, and it requires the smallest storage among the other trie structures. If trie structures are implemented, however, the greater the number of the registered keys, the larger storage is required. In order to solve this problem, Jonge et al. proposed a mothod to change the normal binary trie into a compact bit stream. This paper proposes the improved trie representation for the Patricia trie, as well as the methods for searching and inserting the key on it. The theoretical and experimental results, using 50, 000 Japanese nouns and 50, 000 English words, show that this method generates 25-39 percent shorter bit streams than the traditional method. This method, thus, enables us to provide more compact storage and faster access than the traditional method.

収録刊行物

• IEICE transactions on information and systems

  IEICE transactions on information and systems 81 (4), 364-371, 1998-04-25

  一般社団法人電子情報通信学会

キーワード

• information retrieval
• trie method
• patricia trie
• data structures
• pre-order bit stream

詳細情報

• CRID: 1572543027240900608
• NII論文ID: 110003209975
• NII書誌ID: AA10826272
• ISSN: 09168532
• 本文言語コード: en
• データソース種別:
  • CiNii Articles