A space efficient direct access data structure

DOI10.1016/J.JDA.2016.12.001MaRDI QIDQ2397148zbMATH OpenOpenAlexFDO

Authors Gilad Baruch, Shmuel T. Klein, Dana Shapira

Publication date 29 May 2017

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2016.12.001

zbMATH Keywords

direct accessrank/select data structuresskeleton Huffman treewavelet trees

Mathematics Subject Classification ID

Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Recommendations

• Random access to Fibonacci encoded files
• Accelerated partial decoding in wavelet trees
• A SIMPLE ALPHABET-INDEPENDENT FM-INDEX
• The myriad virtues of wavelet trees
• Online construction of wavelet trees

Cites work

• A simple storage scheme for strings achieving entropy bounds
• Adapting the Knuth-Morris-Pratt algorithm for pattern matching in Huffman encoded texts
• Alphabet partitioning for compressed rank/select and applications
• Evaluation of parallel text alignment systems -- the ARCADE project
• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• Jewels of Stringology
• Practical entropy-compressed rank/select dictionary
• Random access to Fibonacci encoded files
• Robust universal complete codes for transmission and compression
• Succinct Indexable Dictionaries with Applications to Encoding k-ary Trees, Prefix Sums and Multisets
• Universal codeword sets and representations of the integers

Cited in

(8)

• Optimal skeleton and reduced Huffman trees
• Accelerated partial decoding in wavelet trees
• Bidirectional adaptive compression
• Random access to Fibonacci encoded files
• Optimal Skeleton Huffman Trees Revisited
• Optimal skeleton Huffman trees
• Forward looking Huffman coding
• Minimizing access pointers into trees and arrays

This page was built for publication: A space efficient direct access data structure

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2397148)