Name
Abstract | ||
|---|---|---|
Given a file T, we suggest a data structure based on pruning a Huffman shaped Wavelet tree (WT) according to the underlying skeleton Huffman tree that enables direct access to the i-th element of T. This pruned WT is especially designed to support faster random access and save memory storage, at the price of less effective rank and select operations, as compared to the original Huffman shaped WT. The savings are significant only if the underlying alphabet is large enough. We give empirical evidence that when memory storage is of main concern, our suggested data structure generally outperforms other direct access techniques such as those due to Klekci, dacs and sampling, with a slowdown as compared to dacs and fixed length encoding. A Huffman shaped Wavelet tree is pruned by means of a Skeleton Huffman tree.The data structure supports faster random access and saves memory storage.It enables an enhanced rank and select operation rather than an exhaustive one. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.jda.2016.12.001 | J. Discrete Algorithms |
Keywords | DocType | Volume |
Wavelet trees,Direct access,Skeleton Huffman tree,Rank/select data structures | Journal | 43 |
ISSN | Citations | PageRank |
1570-8667 | 0 | 0.34 |
References | Authors | |
21 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gilad Baruch | 1 | 1 | 3.40 |
| Shmuel T. Klein | 2 | 434 | 77.80 |
| Dana Shapira | 3 | 144 | 32.15 |