A metric index for approximate string matching

DOI10.1016/j.tcs.2005.11.037zbMath1087.68027MaRDI QIDQ818138

Edgar Chávez, Gonzalo Navarro

Publication date: 24 March 2006

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.11.037

zbMATH Keywords

metric spaces; suffix trees; suffix arrays; indexed approximate string matching; metric indexes

Mathematics Subject Classification ID

68P10: Searching and sorting

Related Items

Fast index for approximate string matching, An artificial neural network based approach for online string matching/filtering of large databases

Uses Software

• PATRICIA
• GLIMPSE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new method for approximate indexing and dictionary lookup with one error
• A sublinear algorithm for approximate keyword searching
• Transducers and repetitions
• On-line construction of suffix trees
• Indexing text with approximate \(q\)-grams
• Suffix Arrays: A New Method for On-Line String Searches
• Linear-Time Construction of Suffix Arrays
• Space Efficient Linear Time Construction of Suffix Arrays
• Dictionary matching and indexing with errors and don't cares
• A Space-Economical Suffix Tree Construction Algorithm
• Algorithms on Strings, Trees and Sequences
• String Processing and Information Retrieval