New algorithms for position heaps

DOI10.1007/978-3-642-38905-4_11zbMATH Open1381.68069arXiv1212.4613OpenAlexW1549546434MaRDI QIDQ4928564FDOQ4928564

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

Publication date: 14 June 2013

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

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.

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

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

Mathematics Subject Classification ID

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

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)