Local decodability of the Burrows-Wheeler transform

DOI10.1145/3313276.3316317zbMath1433.68134arXiv1808.03978OpenAlexW2885864204MaRDI QIDQ5212815

Sandip Sinha, Omri Weinstein

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1808.03978

zbMATH Keywords

pattern matchingBurrows-Wheeler transformtext compressionsuccinct data structurescell-probe modellocal decoding

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05) Algorithms on strings (68W32)