A link trie structure of storing multiple attribute relationships for natural language dictionaries

Abstract

Word relation is primitive knowledge and it is very useful for natural language processing systems. In the traditional systems, although each knowledge dictionary is constructed in separation, recent natural language applications become more complex by integrating the above multi-attribute relationships.

This paper presents an efficient data structure by introducing a trie that can define the linkage among their leaves. The linkage enables us to share the basic words required for multi-attribute relationships. Theoretical observations show that the worst-case time complexity of retrieving multi-attribute relationships is a constant. From the simulation results, it is shown that the presented method is 1/3 smaller than the competitive methods.

Keywords:

• Trie structures
• natural language dictionaries
• word relationships
• retrieval algorithms

Scope:

• Algorithims
• Information Storage and retrieval

C.R. Categories:

• E.1 Data Structures [Trees],
• E.2 Data Storage Representations [Linked Representations]
• H.3.3 Information Search and Retrieval [Retrieval Models]
• F.2.2 Nonnumerical Algorithms and problems

Computing Reviews (CR) Categories: General Terms:

• Algorithms
• Performance