Position heaps: a simple and dynamic text indexing data structure

DOI10.1016/J.JDA.2010.12.001MaRDI QIDQ533414zbMATH OpenOpenAlexFDO

Authors Andrzej Ehrenfeucht, R. M. McConnell, Nissa Osheim, Sung-Whan Woo

Publication date 3 May 2011

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2010.12.001

zbMATH Keywords

position heapstring searching

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Algorithms on strings (68W32)

Recommendations

• Contracted Suffix Trees: A Simple and Dynamic Text Indexing Data Structure
• Improved Dynamic Text Indexing
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
• scientific article; zbMATH DE number 1003303
• scientific article; zbMATH DE number 910911

Cites work

• Complete inverted files for efficient text retrieval and analysis
• Contracted Suffix Trees: A Simple and Dynamic Text Indexing Data Structure
• Dynamic extended suffix arrays
• File structures using hashing functions
• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 6876087 (Why is no real title available?)
• Introduction to algorithms
• On updating suffix tree labels
• Suffix Arrays: A New Method for On-Line String Searches

Cited in

(16)

• Time optimal left to right construction of position trees
• Permuted pattern matching algorithms on multi-track strings
• Position heaps for Cartesian-tree matching on strings and tries
• Dynamic index and LZ factorization in compressed space
• Constructing LZ78 tries and position heaps in linear time for large alphabets
• The parameterized suffix tray
• Linear-size suffix tries
• Contracted Suffix Trees: A Simple and Dynamic Text Indexing Data Structure
• On-line construction of position heaps
• Improved Dynamic Text Indexing
• New algorithms for position heaps
• Online algorithms for constructing linear-size suffix trie
• Position heaps for parameterized strings
• Inferring strings from position heaps in linear time
• Direct linear time construction of parameterized suffix and LCP arrays for constant alphabets
• Linear time online algorithms for constructing linear-size suffix trie

This page was built for publication: Position heaps: a simple and dynamic text indexing data structure

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