Burrows-Wheeler transform and LCP array construction in constant space

详细信息    查看全文

• 作者：Felipe A. Louza^a ; ^{louza@ic.unicamp.br} ; Travis Gagie^b ; ^c ; ^{travis.gagie@mail.udp.cl} ; Guilherme P. Telles^a ; ^{gpt@ic.unicamp.br}
• 关键词：Burrows&ndash ; Wheeler transform ; LCP array ; In-place algorithms ; Compressed LCP array ; Elias coding
• 刊名：Journal of Discrete Algorithms
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：42
• 期：Complete
• 页码：14-22
• 全文大小：360 K
• 卷排序：42

文摘

In this article we extend the elegant in-place Burrows–Wheeler transform (BWT) algorithm proposed by Crochemore et al. [12]. 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.