An experimental study of compression methods for dynamic tries
2002 (English)In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 33, no 1, 19-33 p.Article in journal (Refereed) Published
We study an order-preserving general purpose data structure for binary data, the LPC-trie. The structure is a compressed trie, using both level and path compression. The memory usage is similar to that of a balanced binary search tree, but the expected average depth is smaller. The LPC-trie is well suited to modem language environments with efficient memory allocation and garbage collection. We present an implementation in the Java programming language and show that the structure compares favorably with a balanced binary search tree.
Place, publisher, year, edition, pages
2002. Vol. 33, no 1, 19-33 p.
data structures, trie, LPC-trie, level compression, relaxed level compression, memory management, binary search tree, Java, efficient implementation, search-trees
IdentifiersURN: urn:nbn:se:kth:diva-21367DOI: 10.1007/s00453-001-0102-yISI: 000174307400003OAI: oai:DiVA.org:kth-21367DiVA: diva2:340065
QC 201005252010-08-102010-08-10Bibliographically approved