Введение
В информационной теории и информатике расстояние Дамерау — Левенштейна (названное в честь Фредерика Д. Дамерау и Владимира И. Левенштейна) — это метрика для строк, используемая для измерения расстояния редактирования между двумя последовательностями. Неформально, расстояние Дамерау — Левенштейна между двумя словами — это минимальное количество операций (включающих вставку, удаление или замену одного символа, либо транспонирование двух соседних символов), необходимых для преобразования одного слова в другое. Расстояние Дамерау — Левенштейна отличается от классического расстояния Левенштейна тем, что, помимо трех классических операций редактирования одного символа (вставки, удаления и замены), допускает также транспозиции. Дамерау утверждал, что при исследовании опечаток для системы информационного поиска более 80% из них были вызваны одной ошибкой одного из четырех типов. В работе Дамерау рассматривались только опечатки, которые можно было исправить одной операцией редактирования. Изначально расстояние Дамерау — Левенштейна предназначалось для измерения расстояния между опечатками, допущенными человеком, с целью улучшения приложений, таких как средства проверки орфографии, однако оно также нашло применение в биологии для измерения вариаций между последовательностями белков.
In information theory and computer science, the Damerau–Levenshtein distance (named after Frederick J. Damerau and Vladimir I. Levenshtein) is a string metric for measuring the edit distance between two sequences. Informally, the Damerau–Levenshtein distance between two words is the minimum number of operations (consisting of insertions, deletions or substitutions of a single character, or transposition of two adjacent characters) required to change one word into the other. The Damerau–Levenshtein distance differs from the classical Levenshtein distance by including transpositions among its allowable operations in addition to the three classical single character edit operations (insertions, deletions and substitutions). Damerau stated that in an investigation of spelling errors for an information retrieval system, more than 80% were a result of a single error of one of the four types. Damerau's paper considered only misspellings that could be corrected with at most one edit operation. While the original motivation was to measure distance between human misspellings to improve applications such as spell checkers, Damerau–Levenshtein distance has also seen uses in biology to measure the variation between protein sequences.
Определение
Для выражения расстояния Дамерау — Левенштейна между двумя строками *s* и *t*, определяется функция *d*, значение которой является расстоянием между префиксом из *i* символов (начальной подстрокой) строки *s* и префиксом из *j* символов строки *t*. Функция ограниченного расстояния определяется рекурсивно как: более простая версия вычисляет так называемое оптимальное расстояние выравнивания строк или ограниченное расстояние редактирования, в то время как вторая вычисляет расстояние Дамерау — Левенштейна с соседними транспозициями. Добавление транспозиций значительно усложняет вычисления. Различие между двумя алгоритмами заключается в том, что алгоритм оптимального выравнивания строк вычисляет количество операций редактирования, необходимых для приведения строк к равенству при условии, что ни одна подстрока не редактируется более одного раза, в то время как второй алгоритм не имеет такого ограничения. Например, рассмотрим расстояние редактирования между CA и ABC. Расстояние Дамерау — Левенштейна LD(CA, ABC) = 2, поскольку CA → AC → ABC, но оптимальное расстояние выравнивания строк OSA(CA, ABC) = 3, потому что если использовать операцию CA → AC, то нельзя использовать AC → ABC, поскольку это потребовало бы редактирования подстроки более одного раза, что недопустимо в OSA, и поэтому кратчайшая последовательность операций — CA → A → AB → ABC. Следует отметить, что для оптимального расстояния выравнивания строк не выполняется неравенство треугольника: OSA(CA, AC) + OSA(AC, ABC) < OSA(CA, ABC), и, следовательно, это не является истинной метрикой.
The restricted distance function is defined recursively as: simpler one, computes what is known as the optimal string alignment distance or restricted edit distance, while the second one computes the Damerau–Levenshtein distance with adjacent transpositions. Adding transpositions adds significant complexity. The difference between the two algorithms consists in that the optimal string alignment algorithm computes the number of edit operations needed to make the strings equal under the condition that no substring is edited more than once, whereas the second one presents no such restriction. Take for example the edit distance between CA and ABC. The Damerau–Levenshtein distance LD(CA, ABC) = 2 because CA → AC → ABC, but the optimal string alignment distance OSA(CA, ABC) = 3 because if the operation CA → AC is used, it is not possible to use AC → ABC because that would require the substring to be edited more than once, which is not allowed in OSA, and therefore the shortest sequence of operations is CA → A → AB → ABC. Note that for the optimal string alignment distance, the triangle inequality does not hold: OSA(CA, AC) + OSA(AC, ABC) < OSA(CA, ABC), and so it is not a true metric.