Burrows-Wheeler transform and LCP array construction in constant space

DOI10.1016/J.JDA.2016.11.003zbMATH Open1359.68340arXiv1611.08198OpenAlexW3105423208MaRDI QIDQ511147FDOQ511147

Travis Gagie, Felipe A. Louza, Guilherme P. Telles

Publication date: 14 February 2017

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

Abstract: In this article we extend the elegant in-place Burrows-Wheeler transform (BWT) algorithm proposed by Crochemore et al. (Crochemore et al., 2015). Our extension is twofold: we first show how to compute simultaneously the longest common prefix (LCP) array as well as the BWT, using constant additional space; we then show how to build the LCP array directly in compressed representation using Elias coding, still using constant additional space and with no asymptotic slowdown. Furthermore, we provide a time/space tradeoff for our algorithm when additional memory is allowed. Our algorithm runs in quadratic time, as does Crochemore et al.'s, and is supported by interesting properties of the BWT and of the LCP array, contributing to our understanding of the time/space tradeoff curve for building indexing structures.

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

zbMATH Keywords

LCP arrayBurrows-Wheeler transformin-place algorithmscompressed LCP arrayElias coding

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Optimal Dynamic Sequence Representations
• Compressed suffix trees with full functionality
• Suffix Arrays: A New Method for On-Line String Searches
• Universal codeword sets and representations of the integers
• Optimal suffix sorting and LCP array construction for constant alphabets
• Permuted Longest-Common-Prefix Array
• Inducing the LCP-Array
• Fast and Lightweight LCP-Array Construction Algorithms
• Combined data structure for previous- and next-smaller-values
• Lightweight algorithms for constructing and inverting the BWT of string collections
• Replacing suffix trees with enhanced suffix arrays
• Lightweight data indexing and compression in external memory
• On the number of elements to reorder when updating a suffix array
• Algorithm Theory - SWAT 2004
• Wee LCP
• Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time
• Practical compressed suffix trees
• Low space external memory construction of the succinct permuted longest common prefix array
• LCP array construction using \(O(\operatorname{sort}(n))\) (or less) I/Os
• Computing the Burrows-Wheeler transform in place and in small space
• Computing the longest common prefix array based on the Burrows-Wheeler transform
• Lightweight LCP construction for very large collections of strings
• Computing the BWT and the LCP Array in Constant Space
• Average Linear Time and Compressed Space Construction of the Burrows-Wheeler Transform
• Faster External Memory LCP Array Construction
• Lightweight LCP Construction for Next-Generation Sequencing Datasets
• Compressed suffix trees
• Linear time construction of compressed text indices in compact space
• Inducing Suffix and LCP Arrays in External Memory
• LCP Array Construction in External Memory
• In-Place Suffix Sorting

Cited In (1)

• When a dollar makes a BWT

This page was built for publication: Burrows-Wheeler transform and LCP array construction in constant space

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