Classes of cost functions for string edit distance

Autor:	Thomas A. Nartker, Horst Bunke, Stephen V. Rice
Rok vydání:	1997
Předmět:	Longest common subsequence problem Combinatorics Sequence String-to-string correction problem General Computer Science Damerau–Levenshtein distance Applied Mathematics String (computer science) Word processing Edit distance Jaro–Winkler distance Computer Science Applications Mathematics
Zdroj:	Algorithmica. 18:271-280
ISSN:	1432-0541 0178-4617
DOI:	10.1007/bf02526038
Popis:	Finding a sequence of edit operations that transforms one string of symbols into another with the minimum cost is a well-known problem. The minimum cost, or edit distance, is a widely used measure of the similarity of two strings. An important parameter of this problem is the cost function, which specifies the cost of each insertion, deletion, and substitution. We show that cost functions having the same ratio of the sum of the insertion and deletion costs divided by the substitution cost yield the same minimum cost sequences of edit operations. This leads to a partitioning of the universe of cost functions into equivalence classes. Also, we show the relationship between a particular set of cost functions and the longest common subsequence of the input strings.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::2ff1ec45d5a6f33c6b983014c132450e https://doi.org/10.1007/bf02526038 Zobrazit plný text záznamu Full text from SpringerLink