Text indexing with errors

DOI10.1016/J.JDA.2006.11.001MaRDI QIDQ925060zbMATH OpenOpenAlexFDO

Authors Moritz G. Maaß, Johannes Nowak

Publication date 29 May 2008

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

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

zbMATH Keywords

edit distancesuffix treetext indexingtriesuffix arrayaverage-caseLevenshtein distancePATRICIA tree

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Analysis of algorithms (68W40) Data structures (68P05) Nonnumerical algorithms (68W05)

Recommendations

• Combinatorial Pattern Matching
• Text Indexing and Dictionary Matching with One Error
• Dictionary matching and indexing with errors and don't cares
• A linear size index for approximate pattern matching
• scientific article; zbMATH DE number 2185612

Cites work

• scientific article; zbMATH DE number 1670652 (Why is no real title available?)
• scientific article; zbMATH DE number 2086228 (Why is no real title available?)
• scientific article; zbMATH DE number 2011852 (Why is no real title available?)
• scientific article; zbMATH DE number 2038766 (Why is no real title available?)
• scientific article; zbMATH DE number 2119724 (Why is no real title available?)
• scientific article; zbMATH DE number 3240929 (Why is no real title available?)
• A Space-Economical Suffix Tree Construction Algorithm
• A linear lower bound on index size for text retrieval
• A new method for approximate indexing and dictionary lookup with one error
• A sublinear algorithm for approximate keyword searching
• Algorithms for approximate string matching
• Algorithms on Strings, Trees and Sequences
• Asymptotic properties of data compression and suffix trees
• Asymptotical growth of a class of random trees
• Combinatorial Pattern Matching
• Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
• Dictionary Look-Up with One Error
• Dictionary matching and indexing with errors and don't cares
• Error detecting and error correcting codes
• Improved bounds for dictionary look-up with one error
• Linear-time construction of suffix arrays (extended abstract)
• Lower bounds for high dimensional nearest neighbor search and related problems
• On-line construction of suffix trees
• Self-alignments in words and their applications
• Space efficient linear time construction of suffix arrays
• Sublinear approximate string matching and biological applications
• Suffix Arrays: A New Method for On-Line String Searches
• Text Indexing and Dictionary Matching with One Error
• Tighter bounds for nearest neighbor search and related problems in the cell probe model
• Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems

Cited in

(6)

• Lossless seeds for searching short patterns with high error rates
• Approximate search of short patterns with high error rates using the \(01^\ast 0\) lossless seeds
• Combinatorial Pattern Matching
• Errata for ``Faster index for property matching
• Indexing factors with gaps
• A linear size index for approximate pattern matching

This page was built for publication: Text indexing with errors

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