Reducing space for index implementation.

DOI10.1016/S0304-3975(01)00222-5zbMath1063.68046WikidataQ61677954 ScholiaQ61677954MaRDI QIDQ1853739

Maxime Crochemore

Publication date: 22 January 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Index; DAWG; Pattern matching; Suffix tree; Suffix automaton; Text compression; Data retrieval; Suffix oracle

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68T10: Pattern recognition, speech recognition

68P05: Data structures

Related Items

Linear-size suffix tries, On the structure of compacted subword graphs of Thue-Morse words and their applications, Statistical properties of factor oracles, From Nerode's congruence to suffix automata with mismatches, On Sturmian graphs, Converting suffix trees into factor/suffix oracles, On-line construction of compact directed acyclic word graphs, The wide window string matching algorithm, On the Suffix Automaton with Mismatches, Statistical Properties of Factor Oracles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Automata and forbidden words
• The smallest automaton recognizing the subwords of a text
• Structures in logic and computer science. A selection of essays in honor of Andrzej Ehrenfeucht (65th birthday on August 8, 1997)
• Transducers and repetitions
• Average sizes of suffix trees and DAWGs
• On-line construction of suffix trees
• Suffix Arrays: A New Method for On-Line String Searches
• Efficient string matching
• A Space-Economical Suffix Tree Construction Algorithm
• A universal algorithm for sequential data compression
• Algorithms on Strings, Trees and Sequences
• Minimal forbidden words and symbolic dynamics