Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/40982
Title: Compressed dynamic tries with applications to LZ-compression in sublinear time and space
Authors: Jansson, J.
Sadakane, K.
Sung, W.-K. 
Issue Date: 2007
Source: Jansson, J.,Sadakane, K.,Sung, W.-K. (2007). Compressed dynamic tries with applications to LZ-compression in sublinear time and space. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 4855 LNCS : 424-435. ScholarBank@NUS Repository.
Abstract: The dynamic trie is a fundamental data structure which finds applications in many areas. This paper proposes a compressed version of the dynamic trie data structure. Our data-structure is not only space efficient, it also allows pattern searching in o(|P|) time and leaf insertion/deletion in o(log n) time, where |P| is the length of the pattern and n is the size of the trie. To demonstrate the usefulness of the new data structure, we apply it to the LZ-compression problem. For a string S of length s over an alphabet A of size σ, the previously best known algorithms for computing the Ziv-Lempel encoding (LZ78) of S either run in: (1) O(s) time and O(s log s) bits working space; or (2) O(sσ) time and O(sHk + s log σ/ log σ s) bits working space, where Hk is the k-order entropy of the text. No previous algorithm runs in sublinear time. Our new data structure implies a LZ-compression algorithm which runs in sublinear time and uses optimal working space. More precisely, the LZ-compression algorithm uses O(s(log σ + log logσ s)logσ s) bits working space and runs in O(s(log log s)2/(logσ s log log log s)) worst-case time, which is sublinear when σ = 2 o(log slog log log s/(log log s)2)). © Springer-Verlag Berlin Heidelberg 2007.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/40982
ISBN: 9783540770497
ISSN: 03029743
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

57
checked on Dec 9, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.