A compact representation of hierarchical relations using decimal notations

Abstract

A decimal notation satisfies many simple mathematical properties. and it is a useful tool in the analysis of trees. A practical method is presented, that compresses the decimal codes while maintaining the fast determination of relations (e.g., ancestor, descendant, brother, etc.). A special node. called a kernel node,including many common subcodes of the other codes, is defined, and a compact data structure is presented using the kerne! nodes. Let n(m) be the number of the total (kernel) nodes. It is theoretically proved that encoding a decimal code is a constant time, that the worst-case time complexity of compressing the decimal codes is O(n+m ²), and that the size of the data structure is proportional to m. From the experimental results of some hierarchical semantic primitives for natural language processing, it is shown that the ratio m/n becomes an extremely small value, ranging from 0.047 to 0.13.

Keywords:

• Compression algorithm
• data structure
• decimal codes
• semantic primitives
• tree structures