On the number of elements to reorder when updating a suffix array
From MaRDI portal
Publication:414460
DOI10.1016/j.jda.2011.01.002zbMath1237.68268OpenAlexW2027441741WikidataQ125075052 ScholiaQ125075052MaRDI QIDQ414460
Laurent Mouchard, Mikaël Salson, Martine Léonard
Publication date: 11 May 2012
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2011.01.002
complexityBurrows-Wheeler transformsuffix arraylongest common prefixdynamic data structureFM-indexself-index
Related Items
Longest Common Prefix with Mismatches, Using static suffix array in dynamic application: case of text compression by longest first substitution, Lightweight BWT and LCP Merging via the Gap Algorithm, Burrows-Wheeler transform and LCP array construction in constant space, Lightweight merging of compressed indices based on BWT variants, Space-Efficient Parallel Construction of Succinct Representations of Suffix Tree Topologies
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A four-stage algorithm for updating a Burrows-Wheeler transform
- Dynamic extended suffix arrays
- Engineering a lightweight suffix array construction algorithm
- Compressed representations of sequences and full-text indexes
- Space Efficient Linear Time Construction of Suffix Arrays
- IN-PLACE UPDATE OF SUFFIX ARRAY WHILE RECODING WORDS
- Algorithm Theory - SWAT 2004