No label defined (Q3315039)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3845091
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3845091 |
Statements
1983
0 references
edit distance
0 references
evolutionary distance
0 references
string-to-string correction
0 references
string matching
0 references
0.8586300611495972
0 references
0.8558386564254761
0 references
[This article was published in this book announced in this Zbl 0513.00010.] The edit distance between two strings is usually measured as the minimum number of deletions, insertions and changes of symbols needed to transform one string into the other. Also the transposition of two ajacent symbols can be included in the editing operations. This paper gives an improved algorithm for computing the edit distance. For two strings \(a_ 1a_ 2...a_ m\) and \(b_ 1b_ 2...b_ n\) the algorithm computes the edit distance s as well as the corresponding sequence of editing steps (insertions, deletions, changes, transpositions) in time 0(\(s\cdot \min(m,n))\) and in space \(0(s^ 2)\). If the editing sequence is not needed, the space requirement reduces to 0(s). Given a threshold value t, the algorithm can also be modified to test in time 0(\(t\cdot \min(m,n))\) and space 0(t) whether the edit distance of the two strings is at most t. For small s, this algorithm significantly improves the well-known dynamic programming method for this problem [see e.g. the paper by \textit{R. A. Wagner} ad \textit{M. J. Fischer}, J. Assoc. Comput. Mach. 21, 168-173 (1974; Zbl 0278.68032)], whose time requirement is 0(mn) and space requirement is 0(mn) or 0(min(m,n)) depending on whether or not the editing sequence is needed. Also note that instead of 'edit distance' the terms 'evolutionary distance' and 'string-to-string correction' are sometimes used in the literature.
0 references