Расстояние Левенштейна — определяем «похожесть» строк

Интересный и очень полезный алгоритм «дистанция Левенштейна» (Levenshtein distance), так же известная как редакционное расстояние или дистанция редактирования. Эта «дистанция» — это минимальное количество правок одной строки (под правками подразумеваются три возможные операции: стирание символа, замена символа и вставка символа), чтобы превратить ее во вторую.

Несколько примеров намного лучше нудных формулировок:
levenshtein('ABC','ABC') = 0
levenshtein('ABC','ABCDEF') = 3
levenshtein('ABC','BCDE') = 3
levenshtein('BCDE','ABCDEF') = 2

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

Значение дистанции Левенштейна

Для того чтобы получить дистанцию Левенштейна между строк s и t (длиной m и n соответственно, индексация начинается с нуля) и редакционное предписание (какие именно правки нужно вносить), расчитывается матрица расстояний D (размерность m+1 * n+1), каждый элемент D[i, j] содержит дистанцию между между первыми i символами строки s и первыми j символами строки t. Например, матрица дистанций Левенштейна для строк s='ABC' и t='ABF' (добавлены последние символы подстрок, чтобы соответствие было явно видно):
\begin{bmatrix} & & A & B & F \\ & 0 & 1 & 2 & 3 \\A & 1 & 0 & 1 & 2 \\B & 2 & 1 & 0 & 1 \\C & 3 & 2 & 1 & 1\end{bmatrix} Столбцы соответствуют подстрокам строки t, а строки матрицы — подстрокам s. Строка и столбец с нулевым индексом соответствуют пустым подстрокам s и t. Каждый элемент этой матрицы содержит расстояние между подстроками соответствующих его индексам. Например, D[3,2] = 1 это расстояние между ABC и AB (всего одна правка — удалить C). Таким образом, D[3,3] = 1 это и есть искомая дистанция между ABС и ABF. (замена C на F). Кроме дистанции эта матрица содержит в себе информацию о тех правках, которые необходимо внести в строку s чтобы получить строку t — редакционное предписание. Но сначала о том, как эта матрица вычисляется.

Построение матрицы дистанций Левенштейна

Построение матрицы дистанций похоже на прокладывание маршрута через лабиринт: начинаем из левого верхнего угла матрицы-карты и должны попасть в правый нижний. Часть матрицы можно заполнить без вычислений: столбец и строка с нулевыми индексами заполняются числами по порядку, начиная с нуля. Это просто объяснить тем, что для того, чтобы из пустой строки получить некую строку T (длиной k), нужно ровно k вставок — по одной на каждый символ. Аналогично и в обратную сторону: для того, чтобы из строки S длиной l получить пустую строку, нужно ровно l удалений. Таким образом, числа в нулевой строке и колонке не зависят от содержимого сравниваемых строк. Далее немного теории о том, как считать остальные значения дистанций матрицы.

Правила заполнения матрицы дистанций Левенштейна (пример)

  1. Относительно ячейки D[i, j], ячейка, располагающаяся слева сверху от нее, D[i-1, j-1], представляет собой «пройденную дистанцию» — правки необходимые для того, чтобы первые i-1 символов строки s превратить в первые j-1 символов t, то есть подготовить s к операции замены s[i-1] на t[j-1] (индексация в строке начинается с 0, то есть s[i-1] это i-ый по счету символ). D[i, j-1] — ячейка слева — это правки, затраченные на подготовление строки s к вставке символа t[j-1]. Аналогично, ячейка сверху- D[i-1, j] — это дистанция, пройденная на превращение подстроки s[0..i-2] в t[0..j-2] (что позволяет удалить i-ый по счету символ, тем самым приведя s[0..i-1] к t[0..j-1]) Запутанно, но, думаю, дальше станет понятнее.
  2. Если s[i-1] == t[j-1], то значение можно скопировать из ячейки слева-сверху. Расстояние Левенштейна для подстрок s[0..i-1] и t[0..j-1] в данном случае будет равно расстоянию s[0..i-2] и t[0..j-2], так как на i-ый по счету символ строки s не требуется правки — он и так уже имеет нужное значение.  Подобный случай можно сравнивать с движением по карте по диагонали, без штрафа (без затраченных правок). D[i, j] = D[i-1, j-1]
  3. Если же символы s[i-1] != t[j-1], то возможны три варианта, из которых выбирается один с минимальной дистанцией:
    1. Операция замены: символ s[i-1] нужно заменить на t[j-1]. В таком случае дистанция равна дистанции слева-сверху + 1. Это похоже на движение так-же по диагонали, но со штрафом. D[i, j] = D[i-1, j-1] + 1
    2. Операция вставки: символ t[j-1] нужно вставить после на s[i-1] . Дистанция равна пройденной на образования t[0..j-2] из s[0..i-1] + одна операция вставки.  Это движение вправо по карте. D[i, j] = D[i, j-1] + 1
    3. Операция удаления: символ s[i-1] нужно удалить. Дистанция равна правкам, затраченным для образование t[0..j-1] из s[0..i-2] + 1 правка, отражающая удаление.  Это можно сравнить с движением вниз по карте. D[i, j] = D[i -1, j] + 1
  4. Если представлять правки в виде движений по карте, тогда построение матрицы — это поиск оптимального пути. Находясь в каждой ячейке, мы должны ответить на вопрос «Откуда дешевле всего сюда прийти?»
  5. Заполнять матрицу можно как угодно, но следует учесть, что для того чтобы сделать выбор минимальной дистанции, находясь в определенной ячейке, нужны три соседние ячейки: слева, сверху и слева-сверху. Поэтому начинать нужно из левого верхнего угла матрицы.

Пример расчета матрицы (теория)

Итак, у нас есть матрица, у которой нулевой столбец и строка уже заполнены, осталось найти 9 значений. Будем искать их построчно, слева направо, сверху вниз.

Строка 1

\begin{bmatrix} & & A & B & F \\ & 0 & 1 & 2 & 3 \\A & 1 & ? & ? & ? \\B & 2 & ? & ? & ? \\C & 3 & ? & ? & ?\end{bmatrix} \Rightarrow \begin{bmatrix} & & A & B & F \\ & 0 & 1 & 2 & 3 \\A & 1 & 0 & 1 & 2 \\B & 2 & ? & ? & ? \\C & 3 & ? & ? & ?\end{bmatrix}
  1. A-A: символы совпадают, значение берем слева-сверху = 0
  2. A-AB: символы различаются, слева 0, сверху-слева 1, сверху 2. берем минимальное значение + 1 = 1. Минимальное было слева, значит оптимальная операция- вставка. Все просто, чтобы A превратить в AB нужно вставить B.
  3. A-ABF: A и F различаются, выбираем минимальное из 1, 2 и 3 и прибавляем 1. ( = 2) Минимальное значение опять было слева, следовательно операция — снова вставка. Чтобы превратить A в ABF, нужно сначала получить AB (вставка) потом ABF (еще вставка)

Строка 2

\begin{bmatrix} & & A & B & F \\ & 0 & 1 & 2 & 3 \\A & 1 & 0 & 1 & 2 \\B & 2 & ? & ? & ? \\C & 3 & ? & ? & ?\end{bmatrix} \Rightarrow \begin{bmatrix} & & A & B & F \\ & 0 & 1 & 2 & 3 \\A & 1 & 0 & 1 & 2 \\B & 2 & 1 & 0 & 1 \\C & 3 & ? & ? & ?\end{bmatrix}
  1. AB-A: минимальное значение сверху (0), значит операция удаления (+1), итого правок 1. Чтобы из AB получить A нужно удалить B.
  2. AB-AB: B и B совпадают, копируем дистанцию слева-сверху (0). Чтобы из AB получить AB никаких правок не нужно
  3. AB-ABF: Вставка F + значение AB-AB = 0 + 1 = 1.

Строка 3

\begin{bmatrix} & & A & B & F \\ & 0 & 1 & 2 & 3 \\A & 1 & 0 & 1 & 2 \\B & 2 & 1 & 0 & 1 \\C & 3 & ? & ? & ?\end{bmatrix} \Rightarrow \begin{bmatrix} & & A & B & F \\ & 0 & 1 & 2 & 3 \\A & 1 & 0 & 1 & 2 \\B & 2 & 1 & 0 & 1 \\C & 3 & 2 & 1 & 1\end{bmatrix}
  1. ABC-A: минимальное значение сверху (1), добавляется операция удаления (+1), итого 2 удаления: из ABС нужно удалить BC и получится A.
  2. ABC-AB: снова минимальное значение сверху(0), так как, чтобы ABC превратить в AB, нужно стереть C. Итого 1 правка.
  3. ABС-ABF: слева-сверху 0 правок, слева 1, сверху тоже 1 правка. Выбирая наименьшее, мы выполняем замену C на F, что дает результирующее число правок равное 0+1 = 1

Искомая дистанция Левенштейна в этой матрице находится в правом нижнем углу, и вычисляется последней.

Редакционное предписание

Редакционное предписание — называется последовательность действий, необходимых для получения из первой строки второй кратчайшим образом. Обычно действия обозначаются так: D (англ. delete) — удалить, I (англ. insert) — вставить, R (replace) — заменить, M (match) — совпадение.
Для строк ABC и ABF редакционное предписание будет выглядеть так:
M M R
A B C
A B F

Чтобы построить редакционное предписание, проще всего запоминать выбранные операции во время построения матрицы. А так-же, можно проанализировать матрицу, двигаясь от правого нижнего угла в левому верхнему по минимальным весам и примечая ходы: ход влево — I(вставка), вверх — D(удаление), влево-вверх — R(замена), если символы различаются, иначе M(совпадение). Сложностей быть не должно. Теперь, как и обещал, реализация дистанции Левенштейна на Python.

Расчет дистанции Левенштейна на Python

def levenshtein(s, t):
    m, n = len(s), len(t)
    D = [range(n + 1)] + [[x + 1] + [None] * n for x in xrange(m)]
    for i in xrange(1, m + 1):
        for j in xrange(1, n + 1):
            if s[i - 1] == t[j - 1]:
                D[i][j] = D[i - 1][j - 1]
            else:
                before_insert = D[i][j - 1]
                before_delete = D[i - 1][j]
                before_change = D[i - 1][j - 1]
                D[i][j] = min(before_insert, before_delete, before_change) + 1
        # поиск предписания проходом от конца к началу    
    prescription = [] # собственно, предписание
    prescription_s = [] # соответствие предписания и символов строки s
    prescription_t = [] # соответствие предписания и символов строки t
    i, j = m, n
    while i and j:
        insert = D[i][j - 1]
        delete = D[i - 1][j]
        match_or_replace = D[i - 1][j - 1]
        best_choice = min(insert, delete, match_or_replace)
        if best_choice == match_or_replace:
            if s[i - 1] == t[j - 1]:  # match
                prescription.append('M')
            else: # replace
                prescription.append('R')
            prescription_s.append(s[i - 1])
            prescription_t.append(t[j - 1])
            i -= 1
            j -= 1
        elif best_choice == insert:
            prescription.append('I')
            prescription_s.append('-')
            prescription_t.append(t[j - 1])
            j -= 1
        elif best_choice == delete:
            prescription.append('D')
            prescription_s.append(s[i - 1])
            prescription_t.append('-')
            i -= 1
    # поиск шел в обратном направлении, reverse вернет прямой порядок
    prescription.reverse()
    prescription_s.reverse()
    prescription_t.reverse()
    print prescription
    print list(s)
    print prescription_s
    print list(t)
    print prescription_t

    for d in D:
        print d
    return D[m][n]

Возможности оптимизации и улучшения

  • Нет необходимости хранить всю матрицу в памяти, так как для расчета любого элемента нужны лишь значения на предыдущей строке и столбце. Можно хранить только две строки (или столбца — если m>n) — предыдущую и текущую. Выбирая операцию, можно на лету составлять редакционное предписание.
  • Часто бывает, что нет смысла строить всю матрицу — если символ совпадает, имеет смысл сразу же проверить следующую пару символов. Велика вероятность, что несколько символов совпадут подряд — что будет означать значительный рывок по диагонали. Если совпало подряд больше половины длины строки s, то имеет смысл дальше подгонять результат. Иногда это может сэкономить 80% вычислений.
  • Есть модификация алгоритма — алгоритм Дамерау-Левенштейна, особенный тем, что добавлена еще одна операция — транспозиция. Транспозиция — это операция по перестановке местами двух соседних символов. Дамерау доказал, что 80 % ошибок при наборе текста человеком являются транспозициями, что делает эту модификацию намного эффективнее в некоторых случаях.

На любые вопросы готов ответить в комментариях.

Спасибо, что читаете!

UPD 06.01.2014: Спасибо yarik за обнаружение и исправление ошибки в коде 🙂

Запись опубликована в рубрике Алгоритмы с метками , , . Добавьте в закладки постоянную ссылку.

18 комментариев: Расстояние Левенштейна — определяем «похожесть» строк

  1. zab говорит:

    «Чтобы построить редакционное предписание, проще всего запоминать выбранные операции во время построения матрицы. А так-же, можно проанализировать матрицу, двигаясь от правого нижнего угла в левому верхнему по минимальным весам и примечая ходы: ход влево — I(вставка), вверх — D(удаление), влево-вверх — R(замена), если символы различаются, иначе M(совпадение). »
    А можно реализацию дополнительно запостить?

  2. Dmitry говорит:

    def distance(a, b):
        n, m = len(a), len(b)
        if n > m:
            a, b = b, a
            n, m = m, n
         current_row = range(n+1) 
        for i in range(1, m+1):
            previous_row, current_row = current_row, [i]+[0]*n
            for j in range(1,n+1):
                add, delete, change = previous_row[j]+1, current_row[j-1]+1, previous_row[j-1]
                if a[j-1] != b[i-1]:
                    change += 1
                current_row[j] = min(add, delete, change)
     
        return current_row[n]
    

  3. Стас говорит:

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

  4. Sagynbek говорит:

    Спасибо большое, за то что так подробно написали, не жалея на это время.

  5. Sagynbek говорит:

    Кстати вот мой код на C++:

    using namespace std;
    int a[1005][1005]={0};
    int main(){
        string s,s1;
        int i,j;
        cin>>s>>s1;
        s=" "+s;
        s1=" "+s1;
        a[0][0]=0;
        for(i=1;i<max(s.size(),s1.size());i++)
            a[i][0]=i,a[0][i]=i;
        for(i=1;i<s.size();i++)
            for(j=1;j<s1.size();j++){
                if(s[i]==s1[j])a[i][j]=a[i-1][j-1];
                else
                a[i][j]=min(a[i-1][j-1],min(a[i-1][j],a[i][j-1]))+1;
            }
        cout<<a[s.size()-1][s1.size()-1]<<endl;
        system("pause");
        return 0;
    }

  6. Igrig говорит:

    в 18 строчке реализации — бага, имхо
    for x in xrange(max(m,n)):
    Разве не минимум должен быть?
    BTW, огромное спасибо!

    • muzhig говорит:

      Уважаемый Igrig, спасибо за комментарий. Насчет баги вы ошиблись: предположим, у нас есть слово длиной 0, и мы хотим найти необходимые правки, чтобы получить слово длиной 10. Сколько операций нам понадобится сделать? Разумеется, 10 вставок, что равно max(m, n). Аналогично решается обратный крайний случай, из слова длиной 10 получаем пустую строку за 10 удалений.

  7. yarik говорит:

    18 строка
    for x in xrange(max(m,n)) — не обработается первый символ
    for x in xrange(max(m,n)+1)

    • yarik говорит:

      Точнее while i>0 and j>0:

    • muzhig говорит:

      Уважаемый yarik, думается мне, вы ошибаетесь. max(m,n) = длина самого длинного слова = количество обрабатываемых символов.
      UPD: удалил ламерскую ерунду из комента

      • yarik говорит:

        a='ATGTTATA'
        b='ATCGTCC'
        ['M', 'I', 'M', 'M', 'D', 'D', 'R', 'R']
        ['T', '-', 'G', 'T', 'T', 'A', 'T', 'A']
        ['T', 'C', 'G', 'T', '-', '-', 'C', 'C']

        вместо
        AT-GTTATA
        ATCGT--CC

        • muzhig говорит:

          Спасибо большое за отличный пример! Ваша правда, я не учел, что в некоторых случаях оптимальнее- удалить и вставить, чем заменить, что удлиняет предписание. Код, конечно-же, поправлю на ваш вариант с while.

        • muzhig говорит:

          Кстати, судя по вашему примеру, мой код- не то, что вам нужно 🙂 Скорее всего, либо вам нужно просто значение дистанции, либо все предписания близкие к оптимальному. В любом случае, мой код- просто калька с текста, чтобы было понятно. Для практического применения, особенно в области генетики- либо его надо полностью переписывать, желательно на C (Cython в помощь), либо заюзать готовую реализацию (что, имхо, предпочтительней).

      • yarik говорит:

        В некоторых случаях последовательность получается длиннее, первоначальной

  8. The Unknown говорит:

    В пункте 1 ошибоки.
    чтобы первые i-1 символов строки s превратить в первые j-1 символов t
    i-2 и j-2. Это ж описание D[i-1, j-1]
    Аналогично, ячейка сверху- D[i-1, j] — это дистанция, пройденная на превращение подстроки s[0..i-2] в t[0..j-2]
    в t[0..j-1]

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *