Fast approximate search in large dictionaries

DOI10.1162/0891201042544938MaRDI QIDQ3225420zbMATH OpenOpenAlexFDO

Authors Stoyan Mihov, K. U. Schulz

Publication date 20 March 2012

Published in Computational Linguistics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

approximate text searchcorrection timesdictionaryfilteringgarbled stringsuniversal Levenshtein automaton

Mathematics Subject Classification ID

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

Recommendations

• Fast string correction with Levenshtein automata
• Fast approximate matching of words against a dictionary
• scientific article; zbMATH DE number 7360012
• scientific article; zbMATH DE number 975393
• Simple, compact and robust approximate string dictionary

Cites work

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

Cited in

(14)

• Fast string correction with Levenshtein automata
• Fast approximate matching of words against a dictionary
• Breadth-first search strategies for trie-based syntactic pattern recognition
• On the Levenshtein automaton and the size of the neighbourhood of a word
• Computing the expected edit distance from a string to a PFA
• Approximate string matching using a bidirectional index
• Computation of similarity -- similarity search as computation
• Constructing Efficient Dictionaries in Close to Sorting Time
• scientific article; zbMATH DE number 1949661 (Why is no real title available?)
• Computing the expected edit distance from a string to a probabilistic finite-state automaton
• Efficient graph-based dictionary search and its application to text-image searching
• A succinct four Russians speedup for edit distance computation and one-against-many banded alignment
• Deciding word neighborhood with universal neighborhood automata
• A model and a fast algorithm for multiple errors spelling correction

This page was built for publication: Fast approximate search in large dictionaries

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