Расстояние Дамерау – Левенштейна

В теории информации и информатике, Дамерау– Расстояние Левенштейна (названо в честь Фредерика Дж. Дамерау и Владимира И. Левенштейна ) - это строковая метрика для измерения редактируемого расстояния между двумя последовательностями. Неформально расстояние Дамерау – Левенштейна между двумя словами - это минимальное количество операций (состоящих из вставки, удаления или замены одного символа или транспонирования двух соседних символов), необходимых для преобразования одного слова в другое..

Расстояние Дамерау – Левенштейна отличается от классического расстояния Левенштейна тем, что в число допустимых операций входят транспозиции в дополнение к трем классическим операциям редактирования одного символа (вставки, удаления и замены).

В своей основополагающей статье Дамерау заявил, что при исследовании орфографических ошибок для информационно-поисковой системы более 80% были результатом единственной ошибки одного из четырех типов. В статье Дамерау рассматривались только орфографические ошибки, которые можно исправить не более чем за одну операцию редактирования. В то время как исходной целью было измерить расстояние между человеческими орфографическими ошибками для улучшения таких приложений, как проверка орфографии, расстояние Дамерау-Левенштейна также использовалось в биологии для измерения вариации между последовательностями белков.

• 1 Определение
• 2 Алгоритм
  • 2.1 Оптимальное расстояние выравнивания строки
  • 2.2 Расстояние со смежными транспозициями
• 3 Приложения
  • 3.1 ДНК
  • 3.2 Обнаружение мошенничества
  • 3.3 Экспортный контроль
• 4 См. также
• 5 Ссылки
• 6 Дополнительная литература

Для выражения расстояния Дамерау – Левенштейна между двумя строками $a\; \{\backslash \; displaystyle\; a\}$и $b\; \{\backslash \; displaystyle\; b\}$функция $da,\; b\; (i,\; j)\; \{\backslash \; displaystyle\; d\_\; \{a,\; b\}\; (i,\; j)\}$определена, значение которого представляет собой расстояние между $i\; \{\backslash \; displaystyle\; i\}$- префиксом символа (начальной подстрокой) строки $a\; \{\backslash \; displaystyle\; a\}$и a $j\; \{\backslash \; displaystyle\; j\}$- символьный префикс $b\; \{\backslash \; displaystyle\; b\}$.

Ограничение Функция расстояния ted определяется рекурсивно как :,

$da,\; b\; (i,\; j)\; =\; min\; \{0,\; если\; i\; =\; j\; =\; 0\; da,\; b\; (i\; -\; 1,\; j)\; +\; 1,\; если\; i>0\; da,\; b\; (\; i,\; j\; -\; 1)\; +\; 1,\; если\; j>0\; da,\; b\; (i\; -\; 1,\; j\; -\; 1)\; +\; 1\; (ai\; \ne \; bj),\; если\; i,\; j>0\; da,\; b\; (i\; -\; 2,\; j\; -\; 2)\; +\; 1,\; если\; i,\; j>1\; и\; a\; [i]\; =\; b\; [j\; -\; 1]\; и\; a\; [i\; -\; 1]\; =\; b\; [j]\; \{\backslash \; displaystyle\; \backslash \; qquad\; d\_\; \{a,\; b\}\; (i,\; j)\; =\; \backslash \; min\; \{\backslash \; begin\; \{cases\}\; 0\; \{\backslash \; text\; \{if\}\}\; i\; =\; j\; =\; 0\; \backslash \backslash \; d\_\; \{a,\; b\}\; (i-1,\; j)\; +1\; \{\backslash \; text\; \{if\}\}\; i>0\; \backslash \backslash \; d\_\; \{\; a,\; b\}\; (i,\; j-1)\; +1\; \{\backslash \; text\; \{if\}\}\; j>0\; \backslash \backslash \; d\_\; \{a,\; b\}\; (i-1,\; j-1)\; +1\; \_\; \{(a\_\; \{i\}\; \backslash \; neq\; b\_\; \{j\})\}\; \{\backslash \; text\; \{if\}\}\; i,\; j>0\; \backslash \backslash \; d\_\; \{a,\; b\}\; (i-2,\; j-2)\; +1\; \{\backslash \; text\; \{if\}\}\; i,\; j>1\; \{\backslash \; text\; \{and\}\}\; a\; [i]\; =\; b\; [j-1]\; \{\backslash \; text\; \{and\}\}\; a\; [i-1]\; =\; b\; [j]\; \backslash \backslash \backslash \; end\; \{case\}\}\}$

где $1\; (ai\; \ne \; bj)\; \{\backslash \; displaystyle\; 1\; \_\; \{(a\_\; \{i\}\; \backslash \; neq\; b\_\; \{j\})\}\}$- индикаторная функция , равная 0, когда $ai\; =\; bj\; \{\backslash \; displaystyle\; a\_\; \{\; i\}\; =\; b\_\; \{j\}\}$и равно 1 в противном случае.

Каждый рекурсивный вызов соответствует одному из случаев, охватываемых расстоянием Дамерау – Левенштейна:

• $da,\; b\; (i\; -\; 1,\; j)\; +\; 1\; \{\backslash \; displaystyle\; d\_\; \{a,\; b\}\; (i-1,\; j)\; +1\}$соответствует удалению (от a до b).
• $da,\; b\; (i,\; j\; -\; 1)\; +\; 1\; \{\backslash \; displaystyle\; d\_\; \{a,\; b\}\; (i,\; j-1)\; +1\}$соответствует вставке (от a до b).
• $da,\; b\; (i\; -\; 1,\; j\; -\; 1)\; +\; 1\; (ai\; \ne \; bj)\; \{\backslash \; displaystyle\; d\_\; \{a,\; b\}\; (i-1,\; j-1)\; +1\; \_\; \{(a\_\; \{i\}\; \backslash \; neq\; b\_\; \{j\})\}\}$соответствует совпадению или несовпадению, в зависимости от того, соответствуют ли соответствующие символы одинаковы.
• $da,\; b\; (i\; -\; 2,\; j\; -\; 2)\; +\; 1\; \{\backslash \; displaystyle\; d\_\; \{a,\; b\}\; (i-2,\; j-2)\; +1\}$соответствует a перестановка между двумя последовательными символами.

Расстояние Дамерау – Левенштейна между a и b затем задается значением функции для полных строк: $da,\; b\; (|\; a\; |,\; |\; b\; |)\; \{\backslash \; displaystyle\; d\_\; \{a,\; b\}\; (|\; a\; |,\; |\; b\; |)\}$где $i\; =\; |\; а\; |\; \{\backslash \; displaystyle\; i\; =\; |\; a\; |\}$обозначает длину строки a и $j\; =\; |\; б\; |\; \{\backslash \; displaystyle\; j\; =\; |\; b\; |\}$- длина b.

Здесь представлены два алгоритма: первый, более простой, вычисляет так называемое оптимальное расстояние выравнивания строки или ограниченное расстояние редактирования, а второй вычисляет расстояние Дамерау – Левенштейна. со смежными транспозициями. Добавление транспозиций добавляет значительную сложность. Разница между двумя алгоритмами состоит в том, что алгоритм оптимального выравнивания строк вычисляет количество операций редактирования, необходимых для выравнивания строк при условии, что ни одна подстрока не редактируется более одного раза, тогда как второй алгоритм не представляет такое ограничение.

Возьмем для примера расстояние редактирования между 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 ), и поэтому оно не является истинная метрика.

Оптимальное расстояние выравнивания строки

Оптимальное расстояние выравнивания строки может быть вычислено с использованием прямого расширения Вагнера – Фишера алгоритма динамического программирования, который вычисляет Расстояние Левенштейна. В алгоритме псевдокода :

OSA-distance isinput : строки a [1..length (a)], b [1..length (b)] output : расстояние, целое число пусть d [0..length (a), 0..length (b)] будет 2-мерным массивом целых чисел, размеры length (a) +1, length ( b) +1 // обратите внимание, что d имеет нулевой индекс, а a и b - единичный. для i: = 0 от до длина (a) включительно dod [i, 0]: = i для j: = 0 до длина (b) включительно dod [0, j]: = j для i: = 1 до длина (a) включительно doдля j: = 1 до длина (b) включительно doifa [i] = b [j], затем стоимость: = 0 else cost: = 1 d [i, j]: = minimum (d [i-1, j] + 1, // удаление d [i, j-1] + 1, // вставка d [i-1, j-1] + cost) // замена если i>1 и j>1 и a [i] = b [j-1] и a [i-1] = b [j] затем d [i, j]: = minimum (d [i, j], d [i-2, j-2] + 1) // транспонирование return d [length (a), length (b)]

Отличие от алгоритма для расстояния Левенштейна заключается в добавлении одного повторения:

ifi>1 и j>1 и a [i] = b [j-1] и a [i-1] = b [j], тогда d [i, j]: = минимум (d [i, j], d [i-2, j- 2] + 1) // транспонирование

Расстояние со смежными транспозициями

Следующий алгоритм вычисляет истинное расстояние Дамерау – Левенштейна с соседними транспозициями; этот алгоритм требует в качестве дополнительного параметра размер алфавита Σ, чтобы все записи массивов находились в [0, | Σ |):

алгоритм DL-расстояние isвход : строки a [1..length (a)], b [1..length (b)] output : расстояние, целое число da: = новый массив | Σ | целые числа для i: = 1 - | Σ | включительно doda [i]: = 0 пусть d [−1..length (a), −1..length (b)] будет 2-мерным массивом целых чисел, размеры length (a) +2, length (b) +2 // обратите внимание, что d имеет индексы, начинающиеся с -1, в то время как a, b и da имеют единичный индекс. maxdist: = длина (a) + длина (b) d [-1, -1]: = maxdist для i: = от 0 до length (a) включительно dod [i, −1]: = maxdist d [i, 0]: = i для j: = от 0 до length (b) включительно dod [−1, j]: = maxdist d [0, j]: = j для i: = от 1 до length (a) включительно dodb: = 0 для j: = 1 до длина (b) включительно dok: = da [b [j]] ℓ: = db if a [i] = b [j] затем cost: = 0 db: = j else cost: = 1 d [i, j]: = minimum (d [i −1, j − 1] + cost, // подстановка d [i, j − 1] + 1, // вставка d [i − 1, j] + 1, // удаление d [k − 1, ℓ − 1 ] + (i − k − 1) + 1 + (j-ℓ − 1)) // транспонирование da [a [i]]: = i return d [length (a), length (b)]

Чтобы разработать правильный алгоритм для вычисления неограниченного расстояния Дамерау – Левенштейна, обратите внимание, что всегда существует оптимальная последовательность операций редактирования, при которой однажды транспонированные буквы никогда не изменяются впоследствии. (Это справедливо до тех пор, пока стоимость транспонирования, $WT\; \{\backslash \; displaystyle\; W\_\; \{T\}\}$, по крайней мере, равна средней стоимости вставки и удаления, т. Е. $2\; WT\; \ge \; WI\; +\; WD\; \{\backslash \; displaystyle\; 2W\_\; \{T\}\; \backslash \; geq\; W\_\; \{I\}\; +\; W\_\; \{D\}\}$.) Таким образом, нам нужно рассмотреть только два симметричных способа изменения подстроки более одного раза : (1) транспонировать буквы и вставлять между ними произвольное количество символов или (2) удалять последовательность символов и переносить буквы, которые становятся смежными после удаления. Прямая реализация этой идеи дает алгоритм кубической сложности: $O\; (M\; \cdot \; N\; \cdot \; max\; (M,\; N))\; \{\backslash \; displaystyle\; O\; \backslash \; left\; (M\; \backslash \; cdot\; N\; \backslash \; cdot\; \backslash \; max\; (M,\; N)\; \backslash \; right)\}$, где M и N - длины строки. Используя идеи Лоуренса и Вагнера, этот наивный алгоритм может быть улучшен до $O\; (M\; \cdot \; N)\; \{\backslash \; displaystyle\; O\; \backslash \; left\; (M\; \backslash \; cdot\; N\; \backslash \; right)\}$в худшем случае., что и делает указанный выше псевдокод.

Интересно, что битовый алгоритм может быть изменен для обработки транспонирования. См. Раздел поиска информации для примера такой адаптации.

Расстояние Дамерау – Левенштейна играет важную роль в обработке естественного языка. В естественных языках строки короткие, а количество ошибок (орфографических ошибок) редко превышает 2. В таких обстоятельствах ограниченное и реальное расстояние редактирования различаются очень редко. Оммен и Локи даже смягчили ограничение на ограниченное расстояние редактирования, введя обобщенные транспозиции. Тем не менее, необходимо помнить, что ограниченное расстояние редактирования обычно не удовлетворяет неравенству треугольника и, таким образом, не может использоваться с метрическими деревьями.

ДНК

Поскольку ДНК часто подвергается вставкам, делециям, заменам и транспозициям, и каждая из этих операций происходит примерно в одном и том же временном масштабе, расстояние Дамерау – Левенштейна является подходящей метрикой вариации между двумя цепями ДНК. Более распространенным в задачах выравнивания ДНК, белков и других биоинформатики является использование тесно связанных алгоритмов, таких как алгоритм Нидлмана – Вунша или алгоритм Смита – Уотермана.

Обнаружение мошенничества

Алгоритм можно использовать с любым набором слов, например с именами поставщиков. Поскольку ввод осуществляется вручную по своей природе, существует риск ввода ложного поставщика. Сотрудник-мошенник может указать одного реального поставщика, такого как "Rich Heir Estate Services", а не ложного поставщика "Rich Hier State Services". Затем мошенник создает фальшивый банковский счет, и компания направляет чеки к реальному поставщику и ложному поставщику. Алгоритм Дамерау – Левенштейна обнаружит переставленную и пропущенную букву и привлечет внимание проверяющего на предмет мошенничества.

Экспортный контроль

Правительство США использует расстояние Дамерау – Левенштейна в своем API Consolidated Screening List.

• Ispell предлагает исправления, основанные на на расстоянии Дамерау – Левенштейна 1
• Typosquatting

• Наварро, Гонсало (март 2001 г.), «Экскурсия по приблизительному сопоставлению строк», ACM Computing Surveys, 33 (1): 31–88, CiteSeerX 10.1.1.452.6317, doi : 10.1145 / 375360.375365, S2CID 207551224