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

      0 references
      1983
      0 references
      edit distance
      0 references
      evolutionary distance
      0 references
      string-to-string correction
      0 references
      string matching
      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

      Identifiers