Category: Trie
Journal: ACM Transactions on Database Systems
Comment: トライのノードをビット列(e.g. 00011000)と思って、それを
        いかに最適に重ねあわせるかという話をしている。他の方式
        の可能性については議論していない。Greedyに順番に入れ
        ていくと最適にならない場合があるから最適のものをみつ
        けるには時間がかかる。(当然)
Number: 2
Bibtype: Article
Author: M. Al-Suwaiyel
        E. Horowitz
Pages: 243-263
Month: jun
Review: Algorithms for trie compaction.
        \\
        ACM Trans. Database Syst. 9, 2 (June 1984), 243 263.
        \\
        The trie is a data structure which permits very rapid
        access to records by key. Each successive digit of the
        key is used to access a node of a tree in order to
        obtain a pointer to a subtree containing all keys with
        the same prefix (up to the current symbol) as the
        desired key. The disadvantage of a trie is the large
        amount of space required for nondense key sets. One
        method of reducing space requirements, investigated by
        Comer in a number of papers (the most recent of which
        is [1]) involves reordering the sequence in which the
        digits of the key are used for searching. This method
        is only useful for static tries.
        \\
        The current paper presents another method for
        constructing static tries to preserve space by
        overlaying nodes of a trie so that empty pointers in
        one node occupy the same location as full pointers in
        another. The authors present an algorithm for
        achieving maximum compaction by this technique, first
        suggested by Knuth [2]. However, this algorithm is
        exponential and the authors proceed to present three
        algorithms for near-optimal compaction which are more
        efficient. These algorithms require O(mn2), O (mn
        log n), and O (mn) time, where n is the number of keys
        and m is the number of digits.
        \\
        It should be noted that an earlier paper by Tarjan and
        Yao [3], which is inexplicably missing from the
        current paper's references, presents a method for
        compacting a trie which is essentially an extension of
        one of the near-optimal methods presented here. The
        method is attributed to Aho and Ullman [4] and to an
        unpublished manuscript by Ziegler [5]. Also, the issue
        of whether minimal tree compaction is NP-complete,
        which is left as an open question in this paper, is
        claimed to have been answered affirmatively in an
        unpublished paper by Even, Lichtenstein, and Shiloach
        [6], according to the paper by Tarjan and Yao.
        \\
        A. M. Tenenbaum, Brooklyn, NY
        \\
        REFERENCES
        1] COMER, D. Analysis of a heuristic for full trie
        minimization, ACM Trans. Database Syst. 6, 3 (Sept. 
        1981), 513 537. See CR 22, 11 (Nov. 1981), Rev. 
        38,688.
        2] KNUTH, D. E. The art of computer programming. Vol. 
        3, Addison-Wesley Publ. Co., Reading, MA, 1975.
        3] TARJAN, R. E.; AND YAO, A. C. Storing a sparse
        table, Commun. ACM 22, 11 (Nov. 1979), 606 611.
        4] AHO, A. V.; AND ULLMAN, J. D. Principles of
        compiler design, Addison-Wesley Publ. Co., Reading,
        MA, 1977. See CR 19, 6 (June 1978), Rev. 33, 085.
        5] ZIEGLER, S. F. Smaller faster table driven parser,
        Unpublished manuscript, Academic Computing Center,
        Univ. of Wisconsin, Madison, 1977.
        6] EVEN, S.; LICHTENSTEIN, D. I.; AND SHILOACH, Y. 
        Remarks on Ziegler's method for matrix compression,
        Unpublished manuscript, 1977.
Title: Algorithm for Trie Compaction
Year: 1984
Volume: 9