Compressed tries
Compressed tries
复制标题
压缩尝试
DOI：
10.1145/360248.360258
复制
发表时间：
1976
期刊：
影响因子：
--
通讯作者：
K. Maly
中科院分区：
文献类型：
--
作者：
K. Maly
本文提出了一种新的数据结构，称为压缩 trie 或 C-trie，用于信息检索系统。它具有与 trie 相同的底层 m 叉树结构，其中 m 是 trie 的参数，但是 trie 中节点的字段必须足够大才能容纳一个键或至少一个指针，而 C-trie 中的字段只有一位长。在本文的分析部分，将表明对于 n 个密钥的集合，以一个密钥的位检查来衡量的检索时间为 logmn 量级，并且存储要求为 n·(m + log2n) 位。这种存储要求和检索时间的改进是以降低结构灵活性为代价实现的，因此更新成本增加。首先将C-trie作为一种数据结构进行分析，然后讨论其在相对静态数据库中的几种使用方法。
This paper presents a new data structure, called a compressed trie or C-trie, to be used in information retrieval systems. It has the same underlying m-ary tree structure as a trie, where m is a parameter of the trie, but whereas the fields of the nodes in a trie have to be large enough to hold a key or at least a pointer, the fields in a C-trie are only one bit long. In the analysis part of the paper it will be shown that for a collection of n keys the retrieval time, measured in terms of bit inspections of one key, is of the order logmn and the storage requirement of the order n·(m + log2n) bits. This improvement in storage requirements and retrieval time is achieved at the cost of decreasing the flexibility of the structure, and therefore updating costs are increased. First the C-trie is analyzed as a data structure, and then several methods of its use for relatively static databases are discussed.