- 著者
- M. Al-Suwaiyel, E. Horowitz
- タイトル
- Algorithm for Trie Compaction
- ページ
- 243-263
- 日時
- June 1984
- コメント
- トライのノードをビット列(e.g. 00011000)と思って、それを いかに最適に重ねあわせるかという話をしている。他の方式 の可能性については議論していない。Greedyに順番に入れ ていくと最適にならない場合があるから最適のものをみつ けるには時間がかかる。(当然)
- 感想
- 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.
- カテゴリ
- Trie

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