Fast Approximate Search in Large Dictionaries

DOI10.1162/0891201042544938zbMath1234.68424OpenAlexW2117084652MaRDI QIDQ3225420

Stoyan Mihov, Klaus U. Schulz

Publication date: 20 March 2012

Published in: Computational Linguistics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1162/0891201042544938

zbMATH Keywords

filteringdictionaryapproximate text searchcorrection timesgarbled stringsuniversal Levenshtein automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Natural language processing (68T50)

Related Items

Approximate string matching using a bidirectional index ⋮ Computing the Expected Edit Distance from a String to a Probabilistic Finite-State Automaton ⋮ Deciding word neighborhood with universal neighborhood automata ⋮ Computation of Similarity—Similarity Search as Computation ⋮ Computing the Expected Edit Distance from a String to a PFA ⋮ Unnamed Item

Cites Work

• Very fast and simple approximate string matching
• An approximate string-matching algorithm
• Approximate string-matching with \(q\)-grams and maximal matches
• Faster approximate string matching
• A sublinear algorithm for approximate keyword searching
• Fast string correction with Levenshtein automata
• A program for correcting spelling errors
• Finding approximate patterns in strings
• Algorithms for approximate string matching
• A binary n-gram technique for automatic correction of substitution, deletion, insertion and reversal errors in words
• The String-to-String Correction Problem
• Incremental Construction of Minimal Acyclic Finite-State Automata

This page was built for publication: Fast Approximate Search in Large Dictionaries