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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Алгоритм)
м
Строка 19: Строка 19:
 
     '''declare''' '''int''' d[0..m, 0..n]
 
     '''declare''' '''int''' d[0..m, 0..n]
 
     '''declare''' '''int''' i, j, cost
 
     '''declare''' '''int''' i, j, cost
 +
     
 
     ''// База динамики''
 
     ''// База динамики''
 
     '''for''' i '''from''' 0 '''to''' m
 
     '''for''' i '''from''' 0 '''to''' m
Строка 24: Строка 25:
 
     '''for''' j '''from''' 1 '''to''' n
 
     '''for''' j '''from''' 1 '''to''' n
 
       d[0, j] = j
 
       d[0, j] = j
 +
   
 
     '''for''' i '''from''' 1 '''to''' m
 
     '''for''' i '''from''' 1 '''to''' m
 
       '''for''' j '''from''' 1 '''to''' n           
 
       '''for''' j '''from''' 1 '''to''' n           
Строка 29: Строка 31:
 
           '''if''' S[i] == T[j] '''then''' cost = 0
 
           '''if''' S[i] == T[j] '''then''' cost = 0
 
             '''else''' cost = 1
 
             '''else''' cost = 1
 +
         
 
           d[i, j] = minimum(
 
           d[i, j] = minimum(
 
                               d[i-1, j  ] + 1,                    ''// удаление''
 
                               d[i-1, j  ] + 1,                    ''// удаление''
Строка 41: Строка 44:
 
                                   d[i-2, j-2] + costTransposition ''// транспозиция''
 
                                   d[i-2, j-2] + costTransposition ''// транспозиция''
 
                               )
 
                               )
 +
   
 
     '''return''' d[m, n]
 
     '''return''' d[m, n]
  

Версия 02:39, 12 декабря 2011

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

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

Расстояние Дамерау — Левенштейна является метрикой.


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

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

Описание алгоритма

Метод динамического программирования позволяет найти расстояние Дамерау — Левенштейна между двумя строками [math]S[/math] и [math]T[/math], длины которых равны соответственно [math]m[/math] и [math]n[/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].

Наивный алгоритм

Простая модификация алгоритма поиска расстояния Левенштейна не приводит к цели. Рассмотрим псевдокод алгоритма, отличающегося от алгоритма поиска расстояния Левенштейна одной проверкой:

int DamerauLevenshteinDistance(char S[1..m], char T[1..n])
   declare int d[0..m, 0..n]
   declare int i, j, cost
     
   // База динамики
   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 cost = 0
            else cost = 1
          
         d[i, j] = minimum(
                              d[i-1, j  ] + 1,                    // удаление
                              d[i  , j-1] + 1,                    // вставка
                              d[i-1, j-1] + cost                  // замена
                          )
          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] + costTransposition // транспозиция
                              )
    
   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]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] соответственно.

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

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
   declare int D[0..m + 1, 0..n + 1]          // Динамика
   declare 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
    
   declare sd[0..количество различных символов в S и T] — отсортированный алфавит
   //для каждого элемента C алфавита задано значение sd[C] 
    
   foreach (char Letter in (S + T))
      if Letter не содержится в sd
         добавить Letter в sd
         sd[Letter] = 0
    
   for i from 1 to m
      declare int DB = 0
      for j from 1 to n
         declare int i1 = sd[target[j - 1]]
         declare int j1 = DB
         if source[i - 1] == target[j - 1] then
            D[i + 1, j + 1] = D[i, j]
            DB = 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[i1, j1] + (i - i1 - 1) + 1 + (j - j1 - 1))
      sd[S[i - 1]] = i
     
   return D[m + 1, n + 1]

См. также

Cсылки