On the number of elements to reorder when updating a suffix array

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

zbMATH Keywords

complexityBurrows-Wheeler transformsuffix arraylongest common prefixdynamic data structureFM-indexself-index

Mathematics Subject Classification ID

Algorithms on strings (68W32)

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