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

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

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

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

Определение

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

Функция ограниченного расстояния определяется рекурсивно как: $$d_{a,b}(i,j)=\min {\begin{cases}0&{\text{if }}i=j=0,\\d_{a,b}(i-1,j)+1&{\text{if }}i>0,\\d_{a,b}(i,j-1)+1&{\text{if }}j>0,\\d_{a,b}(i-1,j-1)+1_{(a_{i}\neq b_{j})}&{\text{if }}i,j>0,\\d_{a,b}(i-2,j-2)+1_{(a_{i}\neq b_{j})}&{\text{if }}i,j>1{\text{ and }}a_{i}=b_{j-1}{\text{ and }}a_{i-1}=b_{j},\\\end{cases}}$$ где $1_{(a_{i}\neq b_{j})}$ индикаторная функция равна 0, когда $a_{i}=b_{j}$ и равен 1 в противном случае.

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

• $d_{a,b}(i-1,j)+1$ соответствует делеции (от a до b ),
• $d_{a,b}(i,j-1)+1$ соответствует вставке (от a до b ),
• $d_{a,b}(i-1,j-1)+1_{(a_{i}\neq b_{j})}$ соответствует совпадению или несовпадению, в зависимости от того, совпадают ли соответствующие символы,
• $d_{a,b}(i-2,j-2)+1_{(a_{i}\neq b_{j})}$ соответствует транспозиции между двумя последовательными символами.

Расстояние Дамерау – Левенштейна между a и b затем определяется значением функции для полных строк: $d_{a,b}{\big (}|a|,|b|{\big )}$, где $i=|a|$ обозначает длину строки a и $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 ), и поэтому это не истинная метрика.

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

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

algorithm OSA-distance is
    input: strings a[1..length(a)], b[1..length(b)]
    output: distance, integer
    
    let d[0..length(a), 0..length(b)] be a 2-d array of integers, dimensions length(a)+1, length(b)+1
    // note that d is zero-indexed, while a and b are one-indexed.
    
    for i := 0 to length(a) inclusive do
        d[i, 0] := i
    for j := 0 to length(b) inclusive do
        d[0, j] := j
    
    for i := 1 to length(a) inclusive do
        for j := 1 to length(b) inclusive do
            if a[i] = b[j] then
                cost := 0
            else
                cost := 1
            d[i, j] := minimum(d[i-1, j] + 1,     // deletion
                               d[i, j-1] + 1,     // insertion
                               d[i-1, j-1] + cost)  // substitution
            if i > 1 and j > 1 and a[i] = b[j-1] and a[i-1] = b[j] then
                d[i, j] := minimum(d[i, j],
                                   d[i-2, j-2] + 1)  // transposition
    return d[length(a), length(b)]

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

if i > 1 and j > 1 and a[i] = b[j-1] and a[i-1] = b[j] then
    d[i, j] := minimum(d[i, j],
                       d[i-2, j-2] + 1)  // transposition

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

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

algorithm DL-distance is
    input: strings a[1..length(a)], b[1..length(b)]
    output: distance, integer
    
    da := new array of |Σ| integers
    for i := 1 to |Σ| inclusive do
        da[i] := 0
    
    let d[−1..length(a), −1..length(b)] be a 2-d array of integers, dimensions length(a)+2, length(b)+2
    // note that d has indices starting at −1, while a, b and da are one-indexed.
    
    maxdist := length(a) + length(b)
    d[−1, −1] := maxdist
    for i := 0 to length(a) inclusive do
        d[i, −1] := maxdist
        d[i, 0] := i
    for j := 0 to length(b) inclusive do
        d[−1, j] := maxdist
        d[0, j] := j
    
    for i := 1 to length(a) inclusive do
        db := 0
        for j := 1 to length(b) inclusive do
            k := da[b[j]]
            ℓ := db
            if a[i] = b[j] then
                cost := 0
                db := j
            else
                cost := 1
            d[i, j] := minimum(d[i−1, j−1] + cost,  //substitution
                               d[i,   j−1] + 1,     //insertion
                               d[i−1, j  ] + 1,     //deletion
                               d[k−1, ℓ−1] + (i−k−1) + 1 + (j-ℓ−1)) //transposition
        da[a[i]] := i
    return d[length(a), length(b)]

Чтобы разработать правильный алгоритм для расчета неограниченного расстояния Дамерау – Левенштейна, обратите внимание, что всегда существует оптимальная последовательность операций редактирования, при которой однажды транспонированные буквы никогда впоследствии не изменяются. (Это справедливо до тех пор, пока стоимость транспозиции $W_{T}$, представляет собой, по крайней мере, среднее значение стоимости вставки и удаления, т. е. $2W_{T}\geq W_{I}+W_{D}$. ) Таким образом, нам нужно рассмотреть только два симметричных способа изменения подстроки более одного раза: (1) переставить буквы и вставить между ними произвольное количество символов или (2) удалить последовательность символов и переставить буквы, которые становятся соседними после удаление. Прямая реализация этой идеи дает алгоритм кубической сложности: $O{\big (}M\cdot N\cdot \max(M,N){\big )}$, где M и N — длины строк. Используя идеи Лоуренса и Вагнера, этот наивный алгоритм можно улучшить, чтобы он стал $O(M\cdot N)$ в худшем случае именно это и делает приведенный выше псевдокод.

Интересно, что алгоритм bitap можно модифицировать для обработки транспонирования. См. раздел «Поиск информации» ^[1] для примера такой адаптации.

Приложения

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

ДНК

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

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

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

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

Правительство США использует расстояние Дамерау-Левенштейна в своем API сводного списка проверки.

См. также

• Ispell – предлагает поправки, основанные на расстоянии Дамерау–Левенштейна, равном 1.
• Тайпсквоттинг - форма киберсквоттинга, основанная на ошибках при вводе адреса веб-сайта.

Дальнейшее чтение

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