New algorithms for position heaps

DOI10.1007/978-3-642-38905-4_11MaRDI QIDQ4928564zbMATH OpenOpenAlexFDO

Authors Travis Gagie, Wing-Kai Hon, Tsung-Han Ku

Publication date 14 June 2013

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1212.4613

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Abstract: 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.

Recommendations

• On-line construction of position heaps
• Position heaps: a simple and dynamic text indexing data structure
• Time optimal left to right construction of position trees
• Position heaps for parameterized strings
• Sparse text indexing in small space

Cited in

(3)

• Linear-size suffix tries
• On-line construction of position heaps
• Constructing LZ78 tries and position heaps in linear time for large alphabets

This page was built for publication: New algorithms for position heaps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4928564)