English»Algorithms»Similarity Searching»Strings & Binary Codes»On-line methods | searchivarius.org
log in | about 

A Partial Deterministic Automaton for Approximate String Matching  Gonzalo Navarro - An approach based on a deterministic finite state automaton can achieve O(N)running time. However, the exponential dependence of the number of states on the pattern size and the maximal allowed edit distance limits its practicality. The author studies the idea of "lazy" automaton creation: states of the automaton are created "on the fly" while scanning a text.
AGREP-a fast approximate pattern-matching tool  S Wu, U Manber - Authors introduce a fast on-line approximate matching tool agrep. Agrep is the first util exploiting (among other techniques) bit-parallel matching algorithms, namely Shift-And.
Direct Pattern Matching on Compressed Text  Edleno Silva de Moura, Gonzalo Navarro, Nivio Ziviani, Ricardo Baeza Yates
Fast String Correction with Levenshtein Automata  K. Schulz, S. Mihov - A description of Universal Levenshtein Automaton.
Indexing Text with Approximate q-grams  Gonzalo Navarro, Erkki Sutinen, Jorma Tarhio - Authors present a new index for approximate string matching. The index collects textq-samples, that is, disjoint text substrings of length q, at fixed intervals and storestheir positions.
NR-grep: A Fast and Flexible Pattern Matching Tool  G. Navarro - NR-grep exploits efficient bit-parallel simulation of non-deterministic suffix automaton for efficient pattern matching.
Theoretical and Empirical Comparisons of Approximate String Matching Algorithms  W. I. Chang, J. Lampe