Как изменить Левенштейны Редактировать расстояние, чтобы считать «смежные обмены буквами» как 1 редактировать - PullRequest
Новая
       11

Как изменить Левенштейны Редактировать расстояние, чтобы считать «смежные обмены буквами» как 1 редактировать

11 голосов
/ 30 октября 2010

Я играю с Алгоритмом редактирования расстояния Левенштейна , и я хочу расширить его для подсчета транспозиций, то есть обмена смежными буквами, как 1 редактирования. Немодифицированный алгоритм подсчитывает количество вставок, удалений или замен, необходимых для получения определенной строки из другой. Например, расстояние редактирования от «КОТЕНОК» до «Сидеть» равно 3. Вот объяснение из Википедии:

  1. котенок → ситтен (замена 'k' на 's')
  2. ситтен → ситтин (замена 'e' на 'i')
  3. сижу → сидя (вставьте «g» в конце).

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

  1. CHIAR → CHAR (удалить «I»)
  2. CHAR → CHAIR (вставить «I»)

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

Ответы [ 3 ]

18 голосов
/ 30 октября 2010

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

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
             )
1 голос
/ 20 апреля 2013

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

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

1 голос
/ 30 октября 2010

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

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

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

Пусть слова будут 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))
                )

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

...