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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показаны 32 промежуточные версии 5 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Расстояние Дамерау {{---}} Левенштейна''' (Damerau {{---}} Levenshtein distance) между двумя строками, состоящими из конечного числа символов {{---}} это минимальное число операций вставки, удаления, замены одного символа и транспозиции двух соседних символов, необходимых для перевода одной строки в другую.}}
+
'''Расстояние Дамерау-Левенштейна''' (англ. ''Damerau-Levenshtein distance'') между двумя строками, состоящими из конечного числа символов {{---}} это минимальное число операций вставки, удаления, замены одного символа и транспозиции двух соседних символов, необходимых для перевода одной строки в другую.}}
 
Является модификацией [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера|расстояния Левенштейна]], отличается от него добавлением операции перестановки.
 
Является модификацией [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера|расстояния Левенштейна]], отличается от него добавлением операции перестановки.
 
Расстояние Дамерау {{---}} Левенштейна является метрикой. (Предполагаем, что цены операций таковы, что выполнено правило треугольника: если две последовательные операции можно заменить одной, то это не ухудшает общую цену.)
 
 
  
 
==Практическое применение==
 
==Практическое применение==
Расстояние Дамерау {{---}} Левенштейна, как и метрика [http://ru.wikipedia.org/wiki/Левенштейн,_Владимир_Иосифович Левенштейна], является мерой "схожести" двух строк. Алгоритм его поиска находит применение в реализации нечёткого поиска, а также в биоинформатике (сравнение ДНК), несмотря на то, что изначально алгоритм разрабатывался для сравнения текстов, набранных человеком ([http://en.wikipedia.org/wiki/Frederick_J._Damerau Дамерау] показал, что 80% человеческих ошибок при наборе текстов составляют перестановки соседних символов, пропуск символа, добавление нового символа, и ошибка в символе. Поэтому метрика Дамерау {{---}} Левенштейна часто используется в редакторских программах для проверки правописания).   
+
Расстояние Дамерау-Левенштейна, как и метрика Левенштейна, является мерой "схожести" двух строк. Алгоритм его поиска находит применение в реализации нечёткого поиска, а также в биоинформатике (сравнение ДНК), несмотря на то, что изначально алгоритм разрабатывался для сравнения текстов, набранных человеком (Дамерау показал, что 80% человеческих ошибок при наборе текстов составляют перестановки соседних символов, пропуск символа, добавление нового символа, и ошибка в символе. Поэтому метрика Дамерау-Левенштейна часто используется в редакторских программах для проверки правописания).   
  
 
==Упрощённый алгоритм==
 
==Упрощённый алгоритм==
 
Не решает задачу корректно, но бывает полезен на практике.
 
Не решает задачу корректно, но бывает полезен на практике.
  
Здесь и далее будем использовать следующие обозначения: <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>
0&&;&i = 0,\ j = 0\\
+
A = \left\{\begin{array}{llcl}
i&&;&j = 0,\ i > 0\\
+
0&;\ i = 0,\ j = 0\\
j&&;&i = 0,\ j > 0\\
+
i * deleteCost&;\ j = 0,\ i > 0\\
D(i - 1, j - 1)&&;&S[i] = T[j]\\
+
j * insertCost&;\ i = 0,\ j > 0\\
\rm{min}(\\
+
D(i - 1, j - 1)&;\ S[i] = T[j]\\
 +
\min{(}\\
 +
\begin{array}{llcl}
 
&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&&\\
 
&D(i - 1, j - 1) + replaceCost\\
 
&D(i - 1, j - 1) + replaceCost\\
 +
\end{array}&;\ j > 0,\ i > 0,\ S[i] \ne T[j]\\
 
)
 
)
 
\end{array}\right.
 
\end{array}\right.
 
</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>.
  
 
Псевдокод алгоритма:
 
Псевдокод алгоритма:
  
  '''int''' DamerauLevenshteinDistance('''char''' S[1..M], '''char''' T[1..N])
+
  '''int''' DamerauLevenshteinDistance(S: '''char[1..M]''', T: '''char[1..N]'''; deleteCost, insertCost, replaceCost, transposeCost: '''int'''):
    '''int''' d[0..M, 0..N]
+
    d: '''int[0..M][0..N]'''
    '''int''' i, j, cost
+
     
     
+
    ''<font color=green>// База динамики</font>''
    ''// База динамики''
+
    d[0][0] = 0
    '''for''' i '''from''' 0 '''to''' M
+
    '''for''' i = 1 '''to''' M
      d[i, 0] = i
+
        d[i][0] = d[i - 1][0] + deleteCost
    '''for''' j '''from''' 1 '''to''' N
+
    '''for''' j = 1 '''to''' N
      d[0, j] = j
+
        d[0][j] = d[0][j - 1] + insertCost
 
      
 
      
    '''for''' i '''from''' 1 '''to''' M
+
    '''for''' i = 1 '''to''' M
      '''for''' j '''from''' 1 '''to''' N           
+
        '''for''' j = 1 '''to''' N           
          ''// Стоимость замены''
+
            ''<font color=green>// Стоимость замены</font>''
          '''if''' S[i] == T[j] '''then''' replaceCost = 0
+
            '''if''' S[i] == T[j]
             '''else''' replaceCost = 1
+
                d[i][j] = d[i - 1][j - 1]
         
+
             '''else'''
          d[i, j] = minimum(
+
                d[i][j] = d[i - 1][j - 1] + replaceCost                 
                              d[i-1, j ] + deleteCost,           ''// удаление''
+
            d[i][j] = min(
                              d[i , j-1] + insertCost,           ''// вставка''
+
                              d[i][j],                                     ''<font color=green>// замена</font>''
                              d[i-1, j-1] + replaceCost          ''// замена''
+
                              d[i - 1][j    ] + deleteCost,               ''<font color=green>// удаление</font>''
                          )
+
                              d[i   ][j - 1] + insertCost                ''<font color=green>// вставка</font>''              
          '''if'''(i > 1 '''and''' j > 1  
+
                          )
                    '''and''' S[i] == T[j-1]  
+
            '''if'''(i > 1 '''and''' j > 1 '''and''' S[i] == T[j - 1] '''and''' S[i - 1] == T[j])
                    '''and''' S[i-1] == T[j]) '''then'''
+
                d[i][j] = min(
              d[i, j] = minimum(
+
                                   d[i][j],
                                   d[i, j],
+
                                   d[i - 2][j - 2] + transposeCost         ''<font color=green>// транспозиция</font>''
                                   d[i-2, j-2] + transposeCost ''// транспозиция''
+
                              )
                              )
+
     '''return''' d[M][N]
      
+
 
    '''return''' d[M, N]
+
Контрпример: <tex>S =</tex> <tex>'CA'</tex> и <tex>T =</tex> <tex>'ABC'</tex>. Расстояние Дамерау-Левенштейна между строками равно <tex>2\ (CA \rightarrow AC \rightarrow ABC)</tex>, однако функция приведённая выше возвратит <tex>3</tex>. Дело в том, что использование этого упрощённого алгоритма накладывает ограничение: любая подстрока может быть редактирована не более одного раза. Поэтому переход <tex>AC \rightarrow ABC</tex> невозможен, и последовательность действий такая: <tex>(CA \rightarrow A \rightarrow AB \rightarrow ABC)</tex>.
  
Контрпример: <tex>S =</tex> <tex>'CA'</tex> и <tex>T =</tex> <tex>'ABC'</tex>. Расстояние Дамерау  {{---}} Левенштейна между строками равно 2 (<tex>CA \rightarrow AC \rightarrow ABC</tex>), однако функция приведённая выше возвратит 3. Дело в том, что использование этого упрощённого алгоритма накладывает ограничение: любая подстрока может быть редактирована не более одного раза. Поэтому переход <tex>AC \rightarrow ABC</tex> невозможен, и последовательность действий такая: (<tex>CA \rightarrow A \rightarrow AB \rightarrow ABC</tex>).
+
Упрощенный алгоритм Дамерау-Левенштейна не является метрикой, так как не выполняется правило треугольника: <tex>\mathtt{DLD}('CA',\ 'AC') + \mathtt{DLD}('AC',\ 'ABC') \ngeqslant \mathtt{DLD}('CA',\ 'ABC')</tex>.
  
Условие многих практических задач не предполагает многократного редактирования подстрок, поэтому часто достаточно упрощённого алгоритма. Ниже представлен более сложный алгоритм, который корректно решает задачу поиска расстояния Дамерау {{---}} Левенштейна.
+
Условие многих практических задач не предполагает многократного редактирования подстрок, поэтому часто достаточно упрощённого алгоритма. Ниже представлен более сложный алгоритм, который корректно решает задачу поиска расстояния Дамерау-Левенштейна.
  
 
==Корректный алгоритм==
 
==Корректный алгоритм==
В интересах краткости положим <tex>insertCost = deleteCost = replaceCost = transposeCost = 1</tex>. При иной формулировке задачи формулы легко обобщаются на любой случай.
+
В основу алгоритма положена идея [[Динамическое программирование#.D0.9F.D1.80.D0.B8.D0.BD.D1.86.D0.B8.D0.BF_.D0.BE.D0.BF.D1.82.D0.B8.D0.BC.D0.B0.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8_.D0.BD.D0.B0_.D0.BF.D1.80.D0.B5.D1.84.D0.B8.D0.BA.D1.81.D0.B5|динамического программирования по префиксу]]. Будем хранить матрицу <tex>D[0..M + 1][0..N + 1]</tex>, где <tex>D[i + 1][j + 1]</tex> {{---}} расстояние Дамерау-Левенштейна между префиксами строк <tex>S</tex> и <tex>T</tex>, длины префиксов {{---}} <tex>i</tex> и <tex>j</tex> соответственно.
 
 
Сложность алгоритма: <tex>O\left (M \cdot N \cdot \max(M, N) \right )</tex>. Затраты памяти: <tex>O\left (M \cdot N \right)</tex>. Однако скорость работы алгоритма может быть улучшена до <tex>O\left (M \cdot N \right)</tex>.
 
 
 
В основу алгоритма положена идея динамического программирования по префиксу. Будем хранить матрицу <tex>D[0..M + 1][0..N + 1]</tex>, где <tex>D[i + 1][j + 1]</tex> {{---}} расстояние Дамерау {{---}} Левенштейна между префиксами строк <tex>S</tex> и <tex>T</tex>, длины префиксов {{---}} <tex>i</tex> и <tex>j</tex> соответственно.
 
 
 
Будем заполнять матрицу следующим образом, используя рекуррентное соотношение, описанное ниже:
 
 
 
'''for''' i '''from''' 0 '''to''' M
 
    '''for''' j '''from''' 0 '''to''' N
 
      вычислить D(i + 1, j + 1);
 
'''return''' D(m + 1, n + 1);
 
  
 
Для учёта транспозиции потребуется хранение следующей информации. Инвариант:
 
Для учёта транспозиции потребуется хранение следующей информации. Инвариант:
  
<tex>lastPosition[x]</tex> {{---}} индекс последнего вхождения <tex>x</tex> в <tex>S</tex>
+
<tex>\mathtt{lastPosition}[x]</tex> {{---}} индекс последнего вхождения <tex>x</tex> в <tex>S</tex>
  
<tex>last</tex> {{---}} на i-й итерации внешнего цикла индекс последнего символа <tex>T: T[last] = S[i]</tex>
+
<tex>\mathtt{last}</tex> {{---}} на <tex>i</tex>-й итерации внешнего цикла индекс последнего символа <tex>T: T[\mathtt{last}] = S[i]</tex>
  
Тогда если на очередной итерации внутреннего цикла положить: <tex>i' = lastPosition[T[j]],\ j' = last</tex>, то
+
Тогда если на очередной итерации внутреннего цикла положить: <tex>i' = \mathtt{lastPosition}[T[j]],\ j' = \mathtt{last}</tex>, то
  
<tex>D(i, j) = min(A, D(i', j') + (i - i' - 1) + 1 + (j - j' - 1))</tex><tex>(*)</tex>
+
<tex>D(i, j) = \min{(A, D(i', j') + (i - i' - 1) \cdot deleteCost + transposeCost + (j - j' - 1) \cdot insertCost)}</tex> <tex>(*)</tex>
  
 
, где
 
, где
  
<tex>A = \left\{\begin{array}{llcl}
+
<tex>
0&&;&i = 0,\ j = 0\\
+
A = \left\{\begin{array}{llcl}
i&&;&j = 0,\ i > 0\\
+
0&;\ i = 0,\ j = 0\\
j&&;&i = 0,\ j > 0\\
+
i * deleteCost&;\ j = 0,\ i > 0\\
D(i - 1, j - 1)&&;&S[i] = T[j]\\
+
j * insertCost&;\ i = 0,\ j > 0\\
\rm{min}(\\
+
D(i - 1, j - 1)&;\ S[i] = T[j]\\
&D(i, j - 1) + 1\\
+
\min{(}\\
&D(i - 1, j) + 1&;&j > 0,\ i > 0,\ S[i] \ne T[j]\\
+
\begin{array}{llcl}
&D(i - 1, j - 1) + 1\\
+
&D(i, j - 1) + insertCost\\
 +
&D(i - 1, j) + deleteCost&&\\
 +
&D(i - 1, j - 1) + replaceCost\\
 +
\end{array}&;\ j > 0,\ i > 0,\ S[i] \ne T[j]\\
 
)
 
)
 
\end{array}\right.
 
\end{array}\right.
 
</tex>
 
</tex>
  
Доказательства требует лишь формула <tex>(*)</tex>, смысл которой {{---}} сравнение стоимости перехода без использования транспозиции (<tex>A</tex>) со стоимостью перехода, включающего в число операций транспозицию; остальные формулы обосновываются так же, как и в доказательстве [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера|алгоритма Вагнера {{---}} Фишера]]. Но действительно, при редактировании подпоследовательности несколько раз всегда существует оптимальная последовательность операций одного из двух видов:
+
Доказательства требует лишь формула <tex>(*)</tex>, смысл которой {{---}} сравнение стоимости перехода без использования транспозиции <tex>(A)</tex> со стоимостью перехода, включающего в число операций транспозицию; остальные формулы обосновываются так же, как и в доказательстве [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера|алгоритма Вагнера-Фишера]]. Но действительно, при редактировании подпоследовательности несколько раз всегда существует оптимальная последовательность операций одного из двух видов:
 
*Переставить местами соседние символы, затем вставить некоторое количество символов между ними;
 
*Переставить местами соседние символы, затем вставить некоторое количество символов между ними;
 
*Удалить некоторое количество символов, а затем переставить местами символы, ставшие соседними.
 
*Удалить некоторое количество символов, а затем переставить местами символы, ставшие соседними.
  
Тогда если символ <tex>S[i]</tex> встречался в <tex>T[1]..T[j]</tex> на позиции <tex>j'</tex>, а символ <tex>T[j]</tex> встречался в <tex>S[1]..S[i]</tex> на позиции <tex>i'</tex>; то <tex>T[1]..T[j]</tex> может быть получена из <tex>S[1]..S[i]</tex> удалением символов <tex>S[i' + 1]..S[i - 1]</tex>, транспозицией ставших соседними <tex>S[i']</tex> и <tex>S[i]</tex> и вставкой символов <tex>T[j' + 1]..T[j - 1]</tex>. Суммарно на это будет затрачено <tex>D(i', j') + (i - i' - 1) + 1 + (j - j' - 1)</tex> операций, что описано в <tex>(*)</tex>. Поэтому мы выбирали оптимальную последовательность операций, рассматрев случай с транспозицией и без неё.
+
Тогда если символ <tex>S[i]</tex> встречался в <tex>T[1]..T[j]</tex> на позиции <tex>j'</tex>, а символ <tex>T[j]</tex> встречался в <tex>S[1]..S[i]</tex> на позиции <tex>i'</tex>; то <tex>T[1]..T[j]</tex> может быть получена из <tex>S[1]..S[i]</tex> удалением символов <tex>S[i' + 1]..S[i - 1]</tex>, транспозицией ставших соседними <tex>S[i']</tex> и <tex>S[i]</tex> и вставкой символов <tex>T[j' + 1]..T[j - 1]</tex>. Суммарно на это будет затрачено <tex>D(i', j') + (i - i' - 1) \cdot deleteCost + transposeCost + (j - j' - 1) \cdot insertCost</tex> операций, что описано в <tex>(*)</tex>. Поэтому мы выбирали оптимальную последовательность операций, рассмотрев случай с транспозицией и без неё.
 +
 
 +
Сложность алгоритма: <tex>O\left (M \cdot N \cdot \max{(M, N)} \right )</tex>. Затраты памяти: <tex>O\left (M \cdot N \right)</tex>. Однако скорость работы алгоритма может быть улучшена до <tex>O\left (M \cdot N \right)</tex>.
 
   
 
   
 
Псевдокод алгоритма:
 
Псевдокод алгоритма:
  
  '''int''' DamerauLevenshteinDistance('''char''' S[1..M], '''char''' T[1..N])'''
+
  '''int''' DamerauLevenshteinDistance(S: '''char[1..M]''', T: '''char[1..N]'''; deleteCost, insertCost, replaceCost, transposeCost: '''int'''):
    ''// Обработка крайних случаев''
+
    ''<font color=green>// Обработка крайних случаев</font>''
    '''if''' (S == "") '''then'''
+
    '''if''' (S == "")
      '''if''' (T == "") '''then'''
+
        '''if''' (T == "")
          '''return''' 0
+
            '''return''' 0
      '''else'''
+
        '''else'''
          '''return''' N
+
            '''return''' N
    '''else''' '''if''' (T == "") '''then'''
+
    '''else''' '''if''' (T == "")
      '''return''' M
+
        '''return''' M
    '''int''' D[0..M + 1, 0..N + 1]         ''// Динамика''
+
    D: '''int[0..M + 1][0..N + 1]'''  ''<font color=green>// Динамика</font>''
    '''int''' INF = M + N                   ''// Большая константа''
+
    INF = (M + N) * max(deleteCost, insertCost, replaceCost, transposeCost)  ''<font color=green>// Большая константа</font>''
 
      
 
      
    ''// База индукции''
+
    ''<font color=green>// База индукции</font>''
    D[0, 0] = INF;
+
    D[0][0] = INF
    '''for''' i '''from''' 0 '''to''' M
+
    '''for''' i = 0 '''to''' M
      D[i + 1, 1] = i
+
        D[i + 1][1] = i * deleteCost
      D[i + 1, 0] = INF
+
        D[i + 1][0] = INF
    '''for''' j '''from''' 0 '''to''' N
+
    '''for''' j = 0 '''to''' N
      D[1, j + 1] = j
+
        D[1][j + 1] = j * insertCost
      D[0, j + 1] = INF
+
        D[0][j + 1] = INF
 
      
 
      
    '''int''' lastPosition[0..количество различных символов в S и T]
+
    lastPosition: '''int[0..количество различных символов в S и T]'''
    ''//для каждого элемента C алфавита задано значение lastPosition[C]''  
+
    ''<font color=green>//для каждого элемента C алфавита задано значение lastPosition[C]</font>''  
 
      
 
      
    '''foreach''' ('''char''' Letter '''in''' (S + T))
+
    '''foreach''' ('''char''' Letter '''in''' (S + T))
      '''if''' Letter не содержится в lastPosition
+
        lastPosition[Letter] = 0
          добавить Letter в lastPosition
 
          lastPosition[Letter] = 0
 
 
      
 
      
    '''for''' i '''from''' 1 '''to''' M
+
    '''for''' i = 1 '''to''' M
      '''int''' last = 0
+
        last = 0
      '''for''' j '''from''' 1 '''to''' N
+
        '''for''' j = 1 '''to''' N
          '''int''' i' = lastPosition[T[j]]
+
            i' = lastPosition[T[j]]
          '''int''' j' = last
+
            j' = last
          '''if''' S[i] == T[j] '''then'''
+
            '''if''' S[i] == T[j]
            D[i + 1, j + 1] = D[i, j]
+
                D[i + 1][j + 1] = D[i][j]
            last = j
+
                last = j
          '''else'''
+
            '''else'''
            D[i + 1, j + 1] = minimum(D[i, j], D[i + 1, j], D[i, j + 1]) + 1
+
                D[i + 1][j + 1] = min(D[i][j] + replaceCost, D[i + 1][j] + insertCost, D[i][j + 1] + deleteCost)
          D[i + 1, j + 1] = minimum(D[i + 1, j + 1], D[i' + 1, j' + 1] + (i - i' - 1) + 1 + (j - j' - 1))
+
            D[i + 1][j + 1] = min(D[i + 1][j + 1], D[i'][j'] + (i - i' - 1) <tex>\cdot</tex> deleteCost + transposeCost + (j - j' - 1) <tex>\cdot</tex> insertCost)
      lastPosition[S[i]] = i
+
        lastPosition[S[i]] = i
 
        
 
        
    '''return''' D[M + 1, N + 1]
+
    '''return''' D[M][N]
  
 
==См. также==
 
==См. также==
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
+
*[[Задача о наибольшей общей подпоследовательности]]
 +
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
 +
*[[Динамическое программирование по профилю]]
  
==Cсылки==
+
==Источники информации==
*[http://en.wikipedia.org/wiki/Damerau–Levenshtein_distance Статья на английской Википедии]
+
*[http://en.wikipedia.org/wiki/Damerau–Levenshtein_distance Wikipedia {{---}} Damerau-Levenshtein distance]
*[http://habrahabr.ru/blogs/algorithm/114997/ Нечёткий поиск в тексте и словаре (Хабрахабр)]
+
*[http://ru.wikipedia.org/wiki/Расстояние_Дамерау_—_Левенштейна Википедия {{---}} Расстояние Дамерау-Левенштейна]  
 +
*[http://habrahabr.ru/blogs/algorithm/114997/ Хабрахабр {{---}} Нечёткий поиск в тексте и словаре]
 +
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 3-е изд. — М.: «Вильямс», 2013. — с. 440. — ISBN 978-5-8459-1794-2
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Динамическое программирование]]
 
[[Категория: Динамическое программирование]]

Текущая версия на 19:33, 4 сентября 2022

Определение:
Расстояние Дамерау-Левенштейна (англ. 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 * deleteCost&;\ j = 0,\ i \gt 0\\ j * insertCost&;\ i = 0,\ j \gt 0\\ D(i - 1, j - 1)&;\ S[i] = T[j]\\ \min{(}\\ \begin{array}{llcl} &D(i, j - 1) + insertCost\\ &D(i - 1, j) + deleteCost&&\\ &D(i - 1, j - 1) + replaceCost\\ \end{array}&;\ j \gt 0,\ i \gt 0,\ S[i] \ne T[j]\\ ) \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(S: char[1..M], T: char[1..N]; deleteCost, insertCost, replaceCost, transposeCost: int):
    d: int[0..M][0..N]
      
    // База динамики
    d[0][0] = 0
    for i = 1 to M
        d[i][0] = d[i - 1][0] + deleteCost
    for j = 1 to N
        d[0][j] = d[0][j - 1] + insertCost
    
    for i = 1 to M
        for j = 1 to N           
            // Стоимость замены
            if S[i] == T[j]
               d[i][j] = d[i - 1][j - 1]
            else
               d[i][j] = d[i - 1][j - 1] + replaceCost                   
            d[i][j] = min(
                             d[i][j],                                     // замена
                             d[i - 1][j    ] + deleteCost,                // удаление
                             d[i    ][j - 1] + insertCost                 // вставка               
                         )
            if(i > 1 and j > 1 and S[i] == T[j - 1] and S[i - 1] == T[j])
                d[i][j] = min(
                                  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]. Расстояние Дамерау-Левенштейна между строками равно [math]2\ (CA \rightarrow AC \rightarrow ABC)[/math], однако функция приведённая выше возвратит [math]3[/math]. Дело в том, что использование этого упрощённого алгоритма накладывает ограничение: любая подстрока может быть редактирована не более одного раза. Поэтому переход [math]AC \rightarrow ABC[/math] невозможен, и последовательность действий такая: [math](CA \rightarrow A \rightarrow AB \rightarrow ABC)[/math].

Упрощенный алгоритм Дамерау-Левенштейна не является метрикой, так как не выполняется правило треугольника: [math]\mathtt{DLD}('CA',\ 'AC') + \mathtt{DLD}('AC',\ 'ABC') \ngeqslant \mathtt{DLD}('CA',\ '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] соответственно.

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

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

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

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

[math]D(i, j) = \min{(A, D(i', j') + (i - i' - 1) \cdot deleteCost + transposeCost + (j - j' - 1) \cdot insertCost)}[/math] [math](*)[/math]

, где

[math] A = \left\{\begin{array}{llcl} 0&;\ i = 0,\ j = 0\\ i * deleteCost&;\ j = 0,\ i \gt 0\\ j * insertCost&;\ i = 0,\ j \gt 0\\ D(i - 1, j - 1)&;\ S[i] = T[j]\\ \min{(}\\ \begin{array}{llcl} &D(i, j - 1) + insertCost\\ &D(i - 1, j) + deleteCost&&\\ &D(i - 1, j - 1) + replaceCost\\ \end{array}&;\ j \gt 0,\ i \gt 0,\ S[i] \ne T[j]\\ ) \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) \cdot deleteCost + transposeCost + (j - j' - 1) \cdot insertCost[/math] операций, что описано в [math](*)[/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(S: char[1..M], T: char[1..N]; deleteCost, insertCost, replaceCost, transposeCost: int):
    // Обработка крайних случаев
    if (S == "")
        if (T == "")
            return 0
        else
            return N
    else if (T == "")
        return M
    D: int[0..M + 1][0..N + 1]   // Динамика
    INF = (M + N) * max(deleteCost, insertCost, replaceCost, transposeCost)  // Большая константа
    
    // База индукции
    D[0][0] = INF
    for i = 0 to M
        D[i + 1][1] = i * deleteCost
        D[i + 1][0] = INF
    for j = 0 to N
        D[1][j + 1] = j * insertCost
        D[0][j + 1] = INF
    
    lastPosition: int[0..количество различных символов в S и T]
    //для каждого элемента C алфавита задано значение lastPosition[C] 
    
    foreach (char Letter in (S + T))
        lastPosition[Letter] = 0
    
    for i = 1 to M
        last = 0
        for j = 1 to N
            i' = lastPosition[T[j]]
            j' = last
            if S[i] == T[j]
                D[i + 1][j + 1] = D[i][j]
                last = j
            else
                D[i + 1][j + 1] = min(D[i][j] + replaceCost, D[i + 1][j] + insertCost, D[i][j + 1] + deleteCost)
            D[i + 1][j + 1] = min(D[i + 1][j + 1], D[i'][j'] + (i - i' - 1) [math]\cdot[/math] deleteCost + transposeCost + (j - j' - 1) [math]\cdot[/math] insertCost)
        lastPosition[S[i]] = i
     
    return D[M][N]

См. также

Источники информации