Data Management

New Algorithms for Position Heaps

Date Added: Dec 2012
Format: PDF

Position heaps are data structures for indexed pattern matching in a string, recently introduced as an alternative to suffix trees and suffix arrays. In this paper, the authors show how to modify an algorithm by Bannai, Inenaga and Takeda for computing LZ78 parses, such that it builds position heaps in linear time independent of the alphabet size; this answers a question posed by Kucherov. They also show how to augment a position heap such that it supports access to the corresponding suffix array, and vice versa. Finally, they introduce a variant of a position heap, which they call a suffix heap that can be simulated efficiently by a compressed suffix array with a linear number of extra bits.