Computing the longest common prefix array based on the Burrows-Wheeler transform

详细信息    查看全文

• 作者：Timo Beller ; ^{Timo.Beller@uni-ulm.de} ; Simon Gog ^{Simon.Gog@uni-ulm.de} ; Enno Ohlebusch ^{Enno.Ohlebusch@uni-ulm.de} ; Thomas Schnattinger ^{Thomas.Schnattinger@uni-ulm.de}
• 关键词：Longest common prefix array ; Burrows&ndash ; Wheeler transform ; Wavelet tree ; Shortest unique substrings ; Shortest absent words
• 刊名：Journal of Discrete Algorithms
• 出版年：2013
• 出版时间：January, 2013
• 年：2013
• 卷：18
• 期：Complete
• 页码：22-31
• 全文大小：301 K

文摘

Many sequence analysis tasks can be accomplished with a suffix array, and several of them additionally need the longest common prefix array. In large scale applications, suffix arrays are being replaced with full-text indexes that are based on the Burrows-Wheeler transform. In this paper, we present the first algorithm that computes the longest common prefix array directly on the wavelet tree of the Burrows-Wheeler transformed string. It runs in linear time and a practical implementation requires approximately 2.2 bytes per character.