Задача о расстоянии Дамерау-Левенштейна — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
(Упрощённый алгоритм: Замена min на /min, перевод переменных в tex, визуальное форматирование псевдокода)
Строка 15: Строка 15:
 
Здесь и далее будем использовать следующие обозначения: <tex>S</tex> и <tex>T</tex> {{---}} строки, между которыми требуется найти расстояние Дамерау {{---}} Левенштейна; <tex>M</tex> и <tex>N</tex> {{---}} их длины соответственно.
 
Здесь и далее будем использовать следующие обозначения: <tex>S</tex> и <tex>T</tex> {{---}} строки, между которыми требуется найти расстояние Дамерау {{---}} Левенштейна; <tex>M</tex> и <tex>N</tex> {{---}} их длины соответственно.
  
Рассмотрим алгоритм, отличающийся от алгоритма поиска расстояния Левенштейна одной проверкой (храним матрицу <tex>D</tex>, где <tex>D(i, j)</tex> — расстояние между префиксами строк: первыми i символами строки <tex>S</tex> и первыми j символами строки <tex>T</tex>). Рекуррентное соотношение имеет вид:
+
Рассмотрим алгоритм, отличающийся от алгоритма поиска расстояния Левенштейна одной проверкой (храним матрицу <tex>D</tex>, где <tex>D(i, j)</tex> — расстояние между префиксами строк: первыми <tex>i</tex> символами строки <tex>S</tex> и первыми <tex>j</tex> символами строки <tex>T</tex>). Рекуррентное соотношение имеет вид:
  
 
Ответ на задачу {{---}} <tex>D(M,N)</tex> , где
 
Ответ на задачу {{---}} <tex>D(M,N)</tex> , где
  
 
<tex>D(i, j) = \left\{\begin{array}{lllc}
 
<tex>D(i, j) = \left\{\begin{array}{lllc}
min(A, D(i - 2, j - 2) + transposeCost)&&;i > 1,\ j > 1,\ S[i] = T[j-1],\ S[i-1] = T[j]\\
+
\min{(A, D(i - 2, j - 2) + transposeCost)}&&;i > 1,\ j > 1,\ S[i] = T[j-1],\ S[i-1] = T[j]\\
 
A&&;\text{otherwise}\\
 
A&&;\text{otherwise}\\
 
\end{array}\right.
 
\end{array}\right.
 
</tex>
 
</tex>
  
<tex>A = \left\{\begin{array}{llcl}
+
<tex>
 +
A = \left\{\begin{array}{llcl}
 
0&&;&i = 0,\ j = 0\\
 
0&&;&i = 0,\ j = 0\\
 
i&&;&j = 0,\ i > 0\\
 
i&&;&j = 0,\ i > 0\\
 
j&&;&i = 0,\ j > 0\\
 
j&&;&i = 0,\ j > 0\\
 
D(i - 1, j - 1)&&;&S[i] = T[j]\\
 
D(i - 1, j - 1)&&;&S[i] = T[j]\\
\rm{min}(\\
+
\min{(}\\
 
&D(i, j - 1) + insertCost\\
 
&D(i, j - 1) + insertCost\\
 
&D(i - 1, j) + deleteCost&;&j > 0,\ i > 0,\ S[i] \ne T[j]\\
 
&D(i - 1, j) + deleteCost&;&j > 0,\ i > 0,\ S[i] \ne T[j]\\
Строка 38: Строка 39:
 
</tex>
 
</tex>
  
Таким образом для получения ответа необходимо заполнить матрицу D, пользуясь рекуррентным соотношением.
+
Таким образом для получения ответа необходимо заполнить матрицу <tex>D</tex>, пользуясь рекуррентным соотношением.
 
Сложность алгоритма: <tex>O\left (M \cdot N \right )</tex>. Затраты памяти: <tex>O\left (M \cdot N \right)</tex>.
 
Сложность алгоритма: <tex>O\left (M \cdot N \right )</tex>. Затраты памяти: <tex>O\left (M \cdot N \right)</tex>.
  
Строка 45: Строка 46:
 
  '''int''' DamerauLevenshteinDistance('''char''' S[1..M], '''char''' T[1..N])
 
  '''int''' DamerauLevenshteinDistance('''char''' S[1..M], '''char''' T[1..N])
 
     '''int''' d[0..M, 0..N]
 
     '''int''' d[0..M, 0..N]
     '''int''' i, j, cost
+
     '''int''' i, j, cost, deleteCost = 1, insertCost = 1, replaceCost = 1, transposeCost = 1
 
        
 
        
     ''// База динамики''
+
     ''<font color=green>// База динамики</font>''
 
     '''for''' i '''from''' 0 '''to''' M
 
     '''for''' i '''from''' 0 '''to''' M
 
       d[i, 0] = i
 
       d[i, 0] = i
Строка 55: Строка 56:
 
     '''for''' i '''from''' 1 '''to''' M
 
     '''for''' i '''from''' 1 '''to''' M
 
       '''for''' j '''from''' 1 '''to''' N           
 
       '''for''' j '''from''' 1 '''to''' N           
           ''// Стоимость замены''
+
           ''<font color=green>// Стоимость замены</font>''
           '''if''' S[i] == T[j] '''then''' replaceCost = 0
+
           '''if''' S[i] == T[j] '''then'''
            '''else''' replaceCost = 1
+
                replaceCost = 0
 +
          '''else'''
 +
                replaceCost = 1
 
            
 
            
 
           d[i, j] = minimum(
 
           d[i, j] = minimum(
                               d[i-1, j  ] + deleteCost,          ''// удаление''
+
                               d[i-1, j  ] + deleteCost,          ''<font color=green>// удаление</font>''
                               d[i  , j-1] + insertCost,          ''// вставка''
+
                               d[i  , j-1] + insertCost,          ''<font color=green>// вставка</font>''
                               d[i-1, j-1] + replaceCost          ''// замена''
+
                               d[i-1, j-1] + replaceCost          ''<font color=green>// замена</font>''
 
                           )
 
                           )
 
           '''if'''(i > 1 '''and''' j > 1  
 
           '''if'''(i > 1 '''and''' j > 1  
Строка 69: Строка 72:
 
               d[i, j] = minimum(
 
               d[i, j] = minimum(
 
                                   d[i, j],
 
                                   d[i, j],
                                   d[i-2, j-2] + transposeCost ''// транспозиция''
+
                                   d[i-2, j-2] + transposeCost     ''<font color=green>// транспозиция</font>''
 
                               )
 
                               )
 
      
 
      

Версия 22:28, 8 декабря 2014

Определение:
Расстояние Дамерау — Левенштейна (Damerau — Levenshtein distance) между двумя строками, состоящими из конечного числа символов — это минимальное число операций вставки, удаления, замены одного символа и транспозиции двух соседних символов, необходимых для перевода одной строки в другую.

Является модификацией расстояния Левенштейна, отличается от него добавлением операции перестановки.

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


Практическое применение

Расстояние Дамерау — Левенштейна, как и метрика Левенштейна, является мерой "схожести" двух строк. Алгоритм его поиска находит применение в реализации нечёткого поиска, а также в биоинформатике (сравнение ДНК), несмотря на то, что изначально алгоритм разрабатывался для сравнения текстов, набранных человеком (Дамерау показал, что 80% человеческих ошибок при наборе текстов составляют перестановки соседних символов, пропуск символа, добавление нового символа, и ошибка в символе. Поэтому метрика Дамерау — Левенштейна часто используется в редакторских программах для проверки правописания).

Упрощённый алгоритм

Не решает задачу корректно, но бывает полезен на практике.

Здесь и далее будем использовать следующие обозначения: [math]S[/math] и [math]T[/math] — строки, между которыми требуется найти расстояние Дамерау — Левенштейна; [math]M[/math] и [math]N[/math] — их длины соответственно.

Рассмотрим алгоритм, отличающийся от алгоритма поиска расстояния Левенштейна одной проверкой (храним матрицу [math]D[/math], где [math]D(i, j)[/math] — расстояние между префиксами строк: первыми [math]i[/math] символами строки [math]S[/math] и первыми [math]j[/math] символами строки [math]T[/math]). Рекуррентное соотношение имеет вид:

Ответ на задачу — [math]D(M,N)[/math] , где

[math]D(i, j) = \left\{\begin{array}{lllc} \min{(A, D(i - 2, j - 2) + transposeCost)}&&;i \gt 1,\ j \gt 1,\ S[i] = T[j-1],\ S[i-1] = T[j]\\ A&&;\text{otherwise}\\ \end{array}\right. [/math]

[math] A = \left\{\begin{array}{llcl} 0&&;&i = 0,\ j = 0\\ i&&;&j = 0,\ i \gt 0\\ j&&;&i = 0,\ j \gt 0\\ D(i - 1, j - 1)&&;&S[i] = T[j]\\ \min{(}\\ &D(i, j - 1) + insertCost\\ &D(i - 1, j) + deleteCost&;&j \gt 0,\ i \gt 0,\ S[i] \ne T[j]\\ &D(i - 1, j - 1) + replaceCost\\ ) \end{array}\right. [/math]

Таким образом для получения ответа необходимо заполнить матрицу [math]D[/math], пользуясь рекуррентным соотношением. Сложность алгоритма: [math]O\left (M \cdot N \right )[/math]. Затраты памяти: [math]O\left (M \cdot N \right)[/math].

Псевдокод алгоритма:

int DamerauLevenshteinDistance(char S[1..M], char T[1..N])
   int d[0..M, 0..N]
   int i, j, cost, deleteCost = 1, insertCost = 1, replaceCost = 1, transposeCost = 1
     
   // База динамики
   for i from 0 to M
      d[i, 0] = i
   for j from 1 to N
      d[0, j] = j
    
   for i from 1 to M
      for j from 1 to N           
         // Стоимость замены
         if S[i] == T[j] then
               replaceCost = 0
         else
               replaceCost = 1
          
         d[i, j] = minimum(
                              d[i-1, j  ] + deleteCost,           // удаление
                              d[i  , j-1] + insertCost,           // вставка
                              d[i-1, j-1] + replaceCost           // замена
                          )
          if(i > 1 and j > 1 
                   and S[i] == T[j-1] 
                   and S[i-1] == T[j]) then
             d[i, j] = minimum(
                                  d[i, j],
                                  d[i-2, j-2] + transposeCost     // транспозиция
                              )
    
   return d[M, N]

Контрпример: [math]S =[/math] [math]'CA'[/math] и [math]T =[/math] [math]'ABC'[/math]. Расстояние Дамерау — Левенштейна между строками равно 2 ([math]CA \rightarrow AC \rightarrow ABC[/math]), однако функция приведённая выше возвратит 3. Дело в том, что использование этого упрощённого алгоритма накладывает ограничение: любая подстрока может быть редактирована не более одного раза. Поэтому переход [math]AC \rightarrow ABC[/math] невозможен, и последовательность действий такая: ([math]CA \rightarrow A \rightarrow AB \rightarrow ABC[/math]).

Условие многих практических задач не предполагает многократного редактирования подстрок, поэтому часто достаточно упрощённого алгоритма. Ниже представлен более сложный алгоритм, который корректно решает задачу поиска расстояния Дамерау — Левенштейна.

Корректный алгоритм

В интересах краткости положим [math]insertCost = deleteCost = replaceCost = transposeCost = 1[/math]. При иной формулировке задачи формулы легко обобщаются на любой случай.

Сложность алгоритма: [math]O\left (M \cdot N \cdot \max(M, N) \right )[/math]. Затраты памяти: [math]O\left (M \cdot N \right)[/math]. Однако скорость работы алгоритма может быть улучшена до [math]O\left (M \cdot N \right)[/math].

В основу алгоритма положена идея динамического программирования по префиксу. Будем хранить матрицу [math]D[0..M + 1][0..N + 1][/math], где [math]D[i + 1][j + 1][/math] — расстояние Дамерау — Левенштейна между префиксами строк [math]S[/math] и [math]T[/math], длины префиксов — [math]i[/math] и [math]j[/math] соответственно.

Будем заполнять матрицу следующим образом, используя рекуррентное соотношение, описанное ниже:

for i from 0 to M
   for j from 0 to N
      вычислить D(i + 1, j + 1);
return D(m + 1, n + 1);

Для учёта транспозиции потребуется хранение следующей информации. Инвариант:

[math]lastPosition[x][/math] — индекс последнего вхождения [math]x[/math] в [math]S[/math]

[math]last[/math] — на i-й итерации внешнего цикла индекс последнего символа [math]T: T[last] = S[i][/math]

Тогда если на очередной итерации внутреннего цикла положить: [math]i' = lastPosition[T[j]],\ j' = last[/math], то

[math]D(i, j) = min(A, D(i', j') + (i - i' - 1) + 1 + (j - j' - 1))[/math][math](*)[/math]

, где

[math]A = \left\{\begin{array}{llcl} 0&&;&i = 0,\ j = 0\\ i&&;&j = 0,\ i \gt 0\\ j&&;&i = 0,\ j \gt 0\\ D(i - 1, j - 1)&&;&S[i] = T[j]\\ \rm{min}(\\ &D(i, j - 1) + 1\\ &D(i - 1, j) + 1&;&j \gt 0,\ i \gt 0,\ S[i] \ne T[j]\\ &D(i - 1, j - 1) + 1\\ ) \end{array}\right. [/math]

Доказательства требует лишь формула [math](*)[/math], смысл которой — сравнение стоимости перехода без использования транспозиции ([math]A[/math]) со стоимостью перехода, включающего в число операций транспозицию; остальные формулы обосновываются так же, как и в доказательстве алгоритма Вагнера — Фишера. Но действительно, при редактировании подпоследовательности несколько раз всегда существует оптимальная последовательность операций одного из двух видов:

  • Переставить местами соседние символы, затем вставить некоторое количество символов между ними;
  • Удалить некоторое количество символов, а затем переставить местами символы, ставшие соседними.

Тогда если символ [math]S[i][/math] встречался в [math]T[1]..T[j][/math] на позиции [math]j'[/math], а символ [math]T[j][/math] встречался в [math]S[1]..S[i][/math] на позиции [math]i'[/math]; то [math]T[1]..T[j][/math] может быть получена из [math]S[1]..S[i][/math] удалением символов [math]S[i' + 1]..S[i - 1][/math], транспозицией ставших соседними [math]S[i'][/math] и [math]S[i][/math] и вставкой символов [math]T[j' + 1]..T[j - 1][/math]. Суммарно на это будет затрачено [math]D(i', j') + (i - i' - 1) + 1 + (j - j' - 1)[/math] операций, что описано в [math](*)[/math]. Поэтому мы выбирали оптимальную последовательность операций, рассматрев случай с транспозицией и без неё.

Псевдокод алгоритма:

int DamerauLevenshteinDistance(char S[1..M], char T[1..N])
   // Обработка крайних случаев
   if (S == "") then
      if (T == "") then
         return 0
      else
         return N
   else if (T == "") then
      return M
   int D[0..M + 1, 0..N + 1]          // Динамика
   int INF = M + N                    // Большая константа
    
   // База индукции
   D[0, 0] = INF;
   for i from 0 to M
      D[i + 1, 1] = i
      D[i + 1, 0] = INF
   for j from 0 to N
      D[1, j + 1] = j
      D[0, j + 1] = INF
    
   int lastPosition[0..количество различных символов в S и T]
   //для каждого элемента C алфавита задано значение lastPosition[C] 
    
   foreach (char Letter in (S + T))
      if Letter не содержится в lastPosition
         добавить Letter в lastPosition
         lastPosition[Letter] = 0
    
   for i from 1 to M
      int last = 0
      for j from 1 to N
         int i' = lastPosition[T[j]]
         int j' = last
         if S[i] == T[j] then
            D[i + 1, j + 1] = D[i, j]
            last = j
         else
            D[i + 1, j + 1] = minimum(D[i, j], D[i + 1, j], D[i, j + 1]) + 1
         D[i + 1, j + 1] = minimum(D[i + 1, j + 1], D[i' + 1, j' + 1] + (i - i' - 1) + 1 + (j - j' - 1))
      lastPosition[S[i]] = i
     
   return D[M + 1, N + 1]

См. также

Cсылки