Please use this identifier to cite or link to this item:
|Title:||Compressed dynamic tries with applications to LZ-compression in sublinear time and space|
|Citation:||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)|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Sep 22, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.