2012/12/19 by Travis Gagie, Gagie, Travis, Wing-Kai Hon +3
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genomics and Phylogenetic Studies #cs.DS
paper · pdf · doi:10.48550/arxiv.1212.4613
openalex publication_date 2012/12/19 · arxiv created 2013/01/13 · arxiv updated 2013/01/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present several results about position heaps, a relatively new alternative to suffix trees and suffix arrays. First, we show that, if we limit the maximum length of patterns to be sought, then we can also limit the height of the heap and reduce the worst-case cost of insertions and deletions. Second, we show how to build a position heap in linear time independent of the size of the alphabet. Third, we show how to augment a position heap such that it supports access to the corresponding suffix array, and vice versa. Fourth, we introduce a variant of a position heap that can be simulated efficiently by a compressed suffix array with a linear number of extra bits.