Как изменить Levenshteins Редактировать Расстояние для подсчета "смежных обменов букв" как 1 править

Я играю с Levenshteins Edit Distance algorithm, и я хочу расширить это, чтобы пересчитать транспозиции, то есть обмен смежными буквами, как 1 редактировать. Немодифицированный алгоритм учитывает вставки, удаления или замены, необходимые для достижения определенной строки из другой. Например, расстояние редактирования от "KITTEN" до "SITTING" равно 3. Здесь объяснение из Википедии:

kitten → sitten (подстановка 'k' 's')
sitten → sittin (подстановка 'e' на 'i')
sittin → sit (вставить 'g' в конец).

Следуя тому же методу, расстояние редактирования от "CHIAR" до "CHAIR" равно 2:

CHIAR → CHAR (удалить 'I')
CHAR → ПРЕДСЕДАТЕЛЬ (вставить 'I')

Я хотел бы считать это как "1 edit", так как я обмениваю только две соседние буквы. Как я собираюсь это сделать?

Ответ 1

Вам понадобится еще один случай в алгоритме из Википедии:

if s[i] = t[j] then 
  d[i, j] := d[i-1, j-1]
else if i > 0 and j > 0 and s[i] = t[j - 1] and s[i - 1] = t[j] then
  d[i, j] := minimum
             (
               d[i-2, j-2] + 1 // transpose
               d[i-1, j] + 1,  // deletion
               d[i, j-1] + 1,  // insertion
               d[i-1, j-1] + 1 // substitution
             )
else
  d[i, j] := minimum
             (
               d[i-1, j] + 1,  // deletion
               d[i, j-1] + 1,  // insertion
               d[i-1, j-1] + 1 // substitution
             )

Ответ 2

Вам нужно изменить способ обновления таблицы динамического программирования. В исходном алгоритме рассматриваются хвосты (или главы) двух слов, которые отличаются не более чем длиной одной. Обновление - это минимум всех таких возможностей.

Если вы хотите изменить алгоритм таким образом, что изменения в двух соседних местоположениях считаются единичными, минимальный выше должен быть вычислен по хвостам (или головам), которые отличаются не более чем двумя. Вы можете расширить его до более крупных районов, но сложность будет экспоненциально увеличиваться по размеру этой окрестности.

Далее вы можете обобщить и назначить затраты, зависящие от символа (ов), удаленных, вставленных или замененных, но вы должны убедиться, что затраты, которые вы назначаете на парное редактирование, ниже двух отдельных изменений, в противном случае два одиночные изменения всегда будут побеждать.

Пусть слова будут w1 и w2

dist(i,j) = min(
                dist(i-2,j-2) && w1(i-1,i) == w2(j-1,j) else
                dist(i-1,j-1) && w1(i) == w2(j) else
                dist(i,j-1)   + cost(w2(j)),
                dist(i-1,j)   + cost(w1(i)),
                dist(i-1,j-1) + cost(w1(i), w2(j)),
                dist(i, j-2)  + cost(w2(j-1,j)),
                dist(i-2, j)  + cost(w1(i-1,i)),
                dist(i-2,j-2) + cost(w1(i-1,i), w2(j-1,j))
                )

То, что я подразумеваю под &&, состоит в том, что эти строки следует рассматривать только при выполнении условий.

Ответ 3

В других ответах используется алгоритм оптимальной строковой выстраивания, а не Damerau Levenshtein, который, как я думаю, является тем, что вы описываете.

У меня есть Java-реализация OSA с некоторыми оптимизациями здесь: https://gist.github.com/steveash/5426191