Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
New Algorithms for Position Heaps
verfasst von : Travis Gagie, Wing-Kai Hon, Tsung-Han Ku
Erschienen in: Combinatorial Pattern Matching
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 easily 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.