Sliding suffix tree

DOI10.3390/A11080118MaRDI QIDQ2331636zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Andrej Brodnik, Matevž Jekovec

Publication date 30 October 2019

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/a11080118

zbMATH Keywords

online pattern matchingsliding windowsuffix tree

Mathematics Subject Classification ID

Data structures (68P05) Online algorithms; streaming algorithms (68W27) Algorithms on strings (68W32)

Review text

Summary: We consider a sliding window \(W\) over a stream of characters from some alphabet of constant size. We want to look up a pattern in the current sliding window content and obtain all positions of the matches. We present an indexed version of the sliding window, based on a suffix tree. The data structure of size \(\Theta(|W|)\) has optimal time queries \(\Theta(m+\mathrm{occ})\) and amortized constant time updates, where \(m\) is the length of the query string and occ is its number of occurrences.

Recommendations

• Most Recent Match Queries in On-Line Suffix Trees
• Compact directed acyclic word graphs for a sliding window
• Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
• Space efficient suffix trees
• Truncated suffix trees and their application to data compression.

Cites work

• A fast string searching algorithm
• A four-stage algorithm for updating a Burrows-Wheeler transform
• A simple parallel Cartesian tree algorithm and its application to suffix tree construction
• A Space-Economical Suffix Tree Construction Algorithm
• Cache-oblivious string dictionaries
• Compact directed acyclic word graphs for a sliding window
• Compressed representations of sequences and full-text indexes
• Compressed suffix trees with full functionality
• Efficient randomized pattern-matching algorithms
• Fast Pattern Matching in Strings
• scientific article; zbMATH DE number 3883638 (Why is no real title available?)
• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• On the sorting-complexity of suffix tree construction
• On-line construction of compact directed acyclic word graphs
• On-line construction of suffix trees
• Parallel lookups in string indexes
• Periodicity in streams
• Real-time streaming string-matching
• Replacing suffix trees with enhanced suffix arrays
• Sliding suffix tree

Cited in

(8)

• Palindromic trees for a sliding window and its applications
• Sliding suffix tree
• Querying regular languages over sliding windows
• Minimizers in semi-dynamic strings
• Pattern mining under Simon's congruence
• Faster sliding window string indexing in streams
• Maintaining the size of LZ77 on semi-dynamic strings
• Compact directed acyclic word graphs for a sliding window

This page was built for publication: Sliding suffix tree

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