Lower bounds for embedding edit distance into normed spaces
Alexandr Andoni, M. Deza, Anupam Gupta, Piotr Indyk, Sofya Raskhodnikova, Alexandr Andoni, Michel Marie Deza, Anupam Gupta, Piotr Indyk, Sofya Raskhodnikova · 2003
MIT S. Raskhodnikova MIT 1 Introduction The edit distance (also called Levenshtein metric) between two strings is the minimum number of operations (insertions, deletions and character substitutions) needed to transform one string into another. This distance is of key importance in computational biology, as well as text processing and other areas. Algorithms for problems involving this metric have been extensively investigated. In particular, the quadratic-time dynamic programming algorithm for computing the edit distance between two strings is one of the most investigated and used algorithms in computational biology. Recently, a new approach to problems involving edit distance has been proposed. Its basic component is construction of a mapping f (called an embedding), which maps any string s into a vector f (s) 2!