A Fast Retrieval Algorithm of Trie Structures for a Large Set of Keys

在自然语言处理中，需要建立一个庞大的字典。因此，开发实用的自然语言处理系统需要一个快速而紧凑的数据结构：自动句子或文档、生成系统、自动校对阅读系统、机器翻译系统、字处理系统等等。特里结构是一种很好的技术，它可以搜索给定字符串的最长可应用键和所有前缀键，本文提出了一种Trie树结构的压缩算法和一种即使在密钥集很大的情况下也能快速检索的算法。本研究提出的方法在理论上得到了评价，并得到了EDR日语词典、英语词典和复合词等多种检索键的支持，该方法适用于多种自然语言处理系统的词典，因此在今后的研究中还需要进行更实际的评价。

In natural language processing, it needs to build a huge size dictionary. Thus, a fast and compact date stracture is required to develope practical natural language processing syatems : a automatic sentence, or document, a generation system, an automatic proof reading system, a machine translation system, a word processing system, and so on. A trie structure is a good technique that can search the longest applicable key and all prefix keys for a given string, but it takes a huge space for a large set of keys.This project porposed a compaction algorithm of trie structures and a fast retrieval algorithm even if a large set of keys. The approach proposed in this project is analyzed by theoretical evaluation and the evaluation is supported by a variety of sets of keys : EDR Japanese dictionaries, English dictionaries and compound words.The idea presented can apply to dictionaries of many natural language processing systems, so a more practical evaluation should be done in the future research.