𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A Comparison of Approximate String Matching Algorithms

✍ Scribed by PETTERI JOKINEN; JORMA TARHIO; ESKO UKKONEN

Publisher
John Wiley and Sons
Year
1996
Tongue
English
Weight
972 KB
Volume
26
Category
Article
ISSN
0038-0644

No coin nor oath required. For personal study only.

✦ Synopsis

Experimental comparisons of the running time of approximate string matching algorithms for the k differences problem are presented. Given a pattern string, a text string, and an integer k, the task is to find all approximate occurrences of the pattern in the text with at most k differences (insertions, deletions, changes). We consider seven algorithms based on different approaches including dynamic programming, Boyer-Moore string matching, sumx automata, and the distribution of characters. It turns out that none of the algorithms is the best for all values of the problem parameters, and the speed differences between the methods can be considerable. KEY WORDS: string matching; edit distance; k differences problem * The comparison was carried out in 1991. Some of the newer methods will probably be faster than the tested algorithms for certain values of problem parameters.

πŸ“œ SIMILAR VOLUMES

Word-oriented approximate string matchin
Word-oriented approximate string matching using occurrence heuristic tables: A heuristic for searching Arabic text
✍ Suleiman H. Mustafa πŸ“‚ Article πŸ“… 2005 πŸ› John Wiley and Sons 🌐 English βš– 143 KB πŸ‘ 2 views

## Abstract In this article, a word‐oriented approximate string matching approach for searching Arabic text is presented. The distance between a pair of words is determined on the basis of aligning the two words by using occurrence heuristic tables. Two words are considered related if they have the

A comparison of nine PLS1 algorithms
A comparison of nine PLS1 algorithms
✍ Martin Andersson πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 183 KB πŸ‘ 1 views

## Abstract Nine PLS1 algorithms were evaluated, primarily in terms of their numerical stability, and secondarily their speed. There were six existing algorithms: (a) NIPALS by Wold; (b) the non‐orthogonalized scores algorithm by Martens; (c) Bidiag2 by Golub and Kahan; (d) SIMPLS by de Jong; (e) i

A Fast Algorithm for the Optimal Alignme
A Fast Algorithm for the Optimal Alignment of Three Strings
✍ Lloyd Allison πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 272 KB

LLOYD ALLISON Department of Computer Science, Monash University, Australia 3168 (Received on 15 December 1992, Accepted in revised form on 10 March 1993) Ukkonen's (pair-wise) string alignment technique is extended to the problem of finding an optimal alignment for three strings. The resulting alg

A comparison of viscoplasticity formats
A comparison of viscoplasticity formats and algorithms
✍ Kenneth Runesson; Matti Ristinmaa; Lennart MΓ€hler πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 181 KB πŸ‘ 1 views

Algorithmic issues for the two thermodynamically consistent viscoplastic formulations of Perzyna and Duvaut-Lions are discussed. It is shown that it is simple to avoid the numerical problems associated with a small relaxation time without resorting to elaborate perturbation techniques, as suggested