Расстояние Левенштейна: вывод операций редактирования из матрицы - PullRequest
Новая
       2

Расстояние Левенштейна: вывод операций редактирования из матрицы

7 голосов
/ 01 мая 2011

Я написал алгоритм Левенштейна в C ++

Если я введу:
строка s: демократ
Строка т: республиканская

Я получаю заполненную матрицу D, и число операций (расстояние Левенштейна) можно прочитать в D [10] [8] = 8
Помимо заполненной матрицы я хочу построить оптимальное решение. Как должно выглядеть это решение? У меня нет идеи.
Пожалуйста, только напишите мне, КАК ДОЛЖЕН СМОТРЕТЬ для этого примера.

Ответы [ 6 ]

36 голосов
/ 02 мая 2011

Вопрос
Учитывая матрицу, полученную по алгоритму Левенштейна, как можно найти " оптимальное решение "?
то есть, как мы можем найти точную последовательность строковых операций: вставки, удаления и подстановки [одной буквы], необходимые для преобразования строки s в строку t?

Во-первых, следует отметить, что во многих случаях существует НЕСКОЛЬКО оптимальных решений .
В то время как алгоритм Левенштейна обеспечивает минимальное количество операций (8 в демократ / республиканец пример) есть много последовательностей (из 8 операций), которые могут произвести это преобразование.

«Декодируя» матрицу Левенштейна, можно перечислить ВСЕ такие оптимальные последовательности.
Общая идея состоит в том, что все оптимальные решения следуют «пути», от верхнего левого угла до нижнего правого угла (или в другом направлении), в результате чего значения ячейки матрицы на этом пути либо остаются неизменными, либо увеличиваются на единицу (или уменьшаются на единицу в обратном направлении), начиная с 0 и заканчивая оптимальным количеством операций для рассматриваемых строк (от 0 до 8 демократов / республиканский случай). Число увеличивается, когда необходима операция, и остается тем же, когда буквы в соответствующих позициях в строках совпадают.

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

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

Иллюстрация с демократом - республиканский пример

Следует также отметить, что матрицу можно построить одним из двух способов: с «демократом» по горизонтали или по вертикали. Это не меняет вычисления расстояния Левенштейна и не меняет список необходимых операций; это только изменяет способ интерпретации матрицы, например, горизонтальное перемещение по «пути» означает либо вставку символа [из строки t], либо удаление символа [из строки s] в зависимости от того, является ли строка «s» «горизонтальной» или "вертикаль" в матрице.

Я буду использовать следующую матрицу. Следовательно, условные обозначения (только в направлениях слева направо и / или сверху вниз)

  • горизонтальное перемещение - это ВСТАВКА буквы из 't string'
  • вертикальное движение - это DELETION буквы из строки '
  • диагональный ход:
    • бездействие (обе буквы в соответствующих позициях одинаковы); номер не меняется
    • a ЗАМЕНА (буквы на соответствующих позициях различны); число увеличивается на единицу.

Матрица Левенштейна для s = "демократ", t = "республиканец" 

      r  e  p  u  b  l  i  c  a  n
   0  1  2  3  4  5  6  7  8  9  10
d  1  1  2  3  4  5  6  7  8  9  10
e  2  2  1  2  3  4  5  6  7  8  9
m  3  3  2  2  3  4  5  6  7  8  9
o  4  4  3  3  3  4  5  6  7  8  9
c  5  5  4  4  4  4  5  6  6  7  8
r  6  5  5  5  5  5  5  6  7  7  8
a  7  6  6  6  6  6  6  6  7  7  8
t  8  7  7  7  7  7  7  7  7  8  8

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

Starting at the bottom-rightmost cell, and working our way backward toward 
the top left.

For each "backward" step, consider the 3 cells directly adjacent to the current
cell   (in the left, top or left+top directions)

   if the value in the diagonal cell (going up+left) is smaller or equal to the
      values found in the other two cells
   AND 
      if this is same or 1 minus the value of the current cell 
   then  "take the diagonal cell"
         if the value of the diagonal cell is one less than the current cell:
            Add a SUBSTITUTION operation (from the letters corresponding to
            the _current_ cell)
         otherwise: do not add an operation this was a no-operation.

   elseif the value in the cell to the left is smaller of equal to the value of
       the of the cell above current cell
   AND 
       if this value is same or 1 minus the value of the current cell 
   then "take the cell to left", and
        add an INSERTION of the letter corresponding to the cell
   else
       take the cell above, add
       Add a DELETION operation of the letter in 's string'

Следуя этому неформальному псевдокоду, мы получаем следующее:

Начните с ячейки «n», «t» внизу справа.
Выберите ячейку [diagonal] «a», «a» в качестве следующего пункта назначения, поскольку она меньше двух других (и удовлетворяет тому же условию или условию -1).
Обратите внимание, что новая ячейка на единицу меньше текущей ячейки
, поэтому шаг 8 заменяет «t» на «n»: Democra N

Продолжить с «a», «a"cell,
Выберите ячейку [diagonal]" c "," r "в качестве следующего пункта назначения ...
Обратите внимание, что новая ячейка имеет то же значение, что и текущая ячейка ==> операция не требуется .

Продолжить с ячейки "c", "r",
Выбрать ячейку [diagonal] "i", "c" в качестве следующего пункта назначения ...
Обратите внимание, что новая ячейкана единицу меньше текущей ячейки
, поэтому шаг 7 заменяет «r» на «c»: democ C an

Продолжить с ячейки «i», «c»,
Выберите ячейку [diagonal] "l", "o" в качестве следующего пункта назначения ...
Обратите внимание, что новая ячейка на единицу меньше текущей ячейки
, поэтому шаг 6 заменяет "c" на "i": demo I can

Продолжить с ячейки "l", "o",
Выбрать ячейку [диагональ] "b", "m" в качестве следующего пункта назначения ...
Обратите внимание, что новая ячейка на 1 меньше текущей ячейки
, поэтому шаг5 заменяет "o" на "l": dem L ican

Продолжить с ячейки "b", "m",
Выбрать [диагональ] "u", "e "ячейка как следующий пункт назначения ...
Обратите внимание, что новая ячейка на единицу меньше текущей ячейки
, поэтому шаг 4 заменяет" m "на" b ": de B lican

Продолжите с ячейки «u», «e»,
Обратите внимание, что диагональная ячейка не подходит, потому что «левая» ячейка меньше ее.В качестве следующего пункта назначения выберите [слева] ячейку «p», «e» ...
, поэтому на шаге 3 после «e» вставляется «u»: de U blican

Продолжить с «p», «e»,
снова «диагональная» ячейка не подходит. Выберите [left] «e», «e» в качестве следующего пункта назначения ...
поэтому шаг2 - «p» после «e»: de P ublican

Продолжить с ячейки «e», «e»,
Выбрать [диагональ] «r», «d "ячейка как следующий пункт назначения ...
Обратите внимание, что новая ячейка имеет то же значение, что и текущая ячейка ==> операция не требуется .

Продолжите с" r "," d"cell,
Выберите ячейку [diagonal]" start "в качестве следующего пункта назначения ...
Обратите внимание, что новая ячейка на единицу меньше текущей ячейки
, поэтому шаг 1 заменяет" d "на" r ".": R epublican

Вы попали в ячейку со значением 0: ваша работа выполнена !

1 голос
/ 18 мая 2016

Вот алгоритм VBA, основанный на ответе mjv. (очень хорошо объяснено, но некоторые дела отсутствовали). 

    Sub TU_Levenshtein()

        Call Levenshtein("democrat", "republican")

        Call Levenshtein("ooo", "u") 

        Call Levenshtein("ceci est un test", "ceci n'est pas un test")

    End Sub

    Sub Levenshtein(ByVal string1 As String, ByVal string2 As String)

        ' Fill Matrix Levenshtein (-> array 'Distance')

        Dim i As Long, j As Long
        Dim string1_length As Long
        Dim string2_length As Long
        Dim distance() As Long

        string1_length = Len(string1)
        string2_length = Len(string2)
        ReDim distance(string1_length, string2_length)

        For i = 0 To string1_length
            distance(i, 0) = i
        Next

        For j = 0 To string2_length
            distance(0, j) = j
        Next

        For i = 1 To string1_length
            For j = 1 To string2_length
                If Asc(Mid$(string1, i, 1)) = Asc(Mid$(string2, j, 1)) Then
                    distance(i, j) = distance(i - 1, j - 1)
                Else
                    distance(i, j) = Application.WorksheetFunction.min _
                    (distance(i - 1, j) + 1, _
                     distance(i, j - 1) + 1, _
                     distance(i - 1, j - 1) + 1)
                End If
            Next
        Next

        LevenshteinDistance = distance(string1_length, string2_length) ' for information only

        ' Write Matrix on VBA sheets (only for visuation, not used in calculus)

        Cells.Clear

        For i = 1 To UBound(distance, 1)
            Cells(i + 2, 1).Value = Mid(string1, i, 1)
        Next i

        For i = 1 To UBound(distance, 2)
            Cells(1, i + 2).Value = Mid(string2, i, 1)
        Next i

        For i = 0 To UBound(distance, 1)

            For j = 0 To UBound(distance, 2)

                Cells(i + 2, j + 2) = distance(i, j)

            Next j

        Next i

        ' One solution

        current_posx = UBound(distance, 1)
        current_posy = UBound(distance, 2)

        Do

            cc = distance(current_posx, current_posy)

            Cells(current_posx + 1, current_posy + 1).Interior.Color = vbYellow ' visualisation again

            ' Manage border case

            If current_posy - 1 < 0 Then

                MsgBox ("deletion. " & Mid(string1, current_posx, 1))

                current_posx = current_posx - 1
                current_posy = current_posy

                GoTo suivant

            End If

            If current_posx - 1 < 0 Then

                MsgBox ("insertion. " & Mid(string2, current_posy, 1))

                current_posx = current_posx
                current_posy = current_posy - 1

                GoTo suivant

            End If

            ' Middle cases

            cc_L = distance(current_posx, current_posy - 1)
            cc_U = distance(current_posx - 1, current_posy)
            cc_D = distance(current_posx - 1, current_posy - 1)

            If (cc_D <= cc_L And cc_D <= cc_U) And (cc_D = cc - 1 Or cc_D = cc) Then

                If (cc_D = cc - 1) Then

                    MsgBox "substitution. " & Mid(string1, current_posx, 1) & " by " & Mid(string2, current_posy, 1)

                    current_posx = current_posx - 1
                    current_posy = current_posy - 1

                    GoTo suivant

                Else

                    MsgBox "no operation"

                    current_posx = current_posx - 1
                    current_posy = current_posy - 1

                    GoTo suivant

                End If

            ElseIf cc_L <= cc_D And cc_L = cc - 1 Then

                MsgBox ("insertion. " & Mid(string2, current_posy, 1))

                current_posx = current_posx
                current_posy = current_posy - 1

                GoTo suivant

            Else

                MsgBox ("deletion." & Mid(string1, current_posy, 1))

                current_posx = current_posx
                current_posy = current_posy - 1

                GoTo suivant

            End If

    suivant:

        Loop While Not (current_posx = 0 And current_posy = 0)

    End Sub
1 голос
/ 01 мая 2011

С тех пор, как я поиграл с ним, было несколько раз, но мне кажется, что матрица должна выглядеть примерно так: 

. . r e p u b l i c a n
. 0 1 2 3 4 5 6 7 8 9 10
d 1 1 2 3 4 5 6 7 8 9 10
e 2 2 1 2 3 4 5 6 7 8 9
m 3 3 2 2 3 4 5 6 7 8 9
o 4 4 3 3 3 4 5 6 7 8 9
c 5 5 4 4 4 4 5 6 7 8 9
r 6 5 5 5 5 5 5 6 7 8 9
a 7 6 6 6 6 6 6 6 7 7 8
t 8 7 7 7 7 7 7 7 7 7 8

Хотя не принимайте это как должное.

0 голосов
/ 14 июня 2018

C # реализация ответа JackIsJack с некоторыми изменениями:

  • Операции выводятся в «прямом» порядке (JackIsJack выводит в обратном порядке);
  • Последнее предложение «else» в оригиналеответ работал некорректно (похоже на ошибку копирования-вставки).

Код консольного приложения: 

class Program
{
    static void Main(string[] args)
    {
        Levenshtein("1", "1234567890");
        Levenshtein( "1234567890", "1");

        Levenshtein("kitten", "mittens");
        Levenshtein("mittens", "kitten");
        Levenshtein("kitten", "sitting");
        Levenshtein("sitting", "kitten");
        Levenshtein("1234567890", "12356790");
        Levenshtein("12356790", "1234567890");
        Levenshtein("ceci est un test", "ceci n'est pas un test");
        Levenshtein("ceci n'est pas un test", "ceci est un test");
    }

    static void Levenshtein(string string1, string string2)
    {
        Console.WriteLine("Levenstein '" + string1 + "' => '" + string2 + "'");

        var string1_length = string1.Length;
        var string2_length = string2.Length;

        int[,] distance = new int[string1_length + 1, string2_length + 1];

        for (int i = 0; i <= string1_length; i++)
        {
            distance[i, 0] = i;
        }


        for (int j = 0; j <= string2_length; j++)
        {
            distance[0, j] = j;
        }


        for (int i = 1; i <= string1_length; i++)
        {
            for (int j = 1; j <= string2_length; j++)
            {
                if (string1[i - 1] == string2[j - 1])
                {
                    distance[i, j] = distance[i - 1, j - 1];
                }
                else
                {
                    distance[i, j] = Math.Min(distance[i - 1, j] + 1, Math.Min(
                       distance[i, j - 1] + 1,
                       distance[i - 1, j - 1] + 1));
                }

            }
        }


        var LevenshteinDistance = distance[string1_length, string2_length];// for information only
        Console.WriteLine($"Levernstein distance: {LevenshteinDistance}");

        // List of operations
        var current_posx = string1_length;
        var current_posy = string2_length;

        var stack = new Stack<string>(); // for outputting messages in forward direction

        while (current_posx != 0 || current_posy != 0)
        {
            var cc = distance[current_posx, current_posy];
            // edge cases
            if (current_posy - 1 < 0)
            {
                stack.Push("Delete '" + string1[current_posx - 1] + "'");
                current_posx--;
                continue;
            }

            if (current_posx - 1 < 0)
            {
                stack.Push("Insert '" + string2[current_posy - 1] + "'");
                current_posy--;
                continue;
            }

            // Middle cases
            var cc_L = distance[current_posx, current_posy - 1];
            var cc_U = distance[current_posx - 1, current_posy];
            var cc_D = distance[current_posx - 1, current_posy - 1];

            if ((cc_D <= cc_L && cc_D <= cc_U) && (cc_D == cc - 1 || cc_D == cc))
            {
                if (cc_D == cc - 1)
                {
                    stack.Push("Substitute '" + string1[current_posx - 1] + "' by '" + string2[current_posy - 1] + "'");
                    current_posx--;
                    current_posy--;
                }
                else
                {
                    stack.Push("Keep '" + string1[current_posx - 1] + "'");
                    current_posx--;
                    current_posy--;
                }
            }
            else if (cc_L <= cc_D && cc_L == cc - 1)
            {
                stack.Push("Insert '" + string2[current_posy - 1] + "'");
                current_posy--;                   
            }
            else
            {
                stack.Push("Delete '" + string1[current_posx - 1]+"'");
                current_posx--;                   
            }
        }

        while(stack.Count > 0)
        {
            Console.WriteLine(stack.Pop());
        }
    }
}
0 голосов
/ 05 сентября 2017

Вот код Matlab, по вашему мнению, это правильно?Кажется, чтобы дать правильные результаты :) 

clear all

s = char('democrat');
t = char('republican');

% Edit Matrix
m=length(s);
n=length(t);
mat=zeros(m+1,n+1);
for i=1:1:m
    mat(i+1,1)=i;
end
for j=1:1:n
    mat(1,j+1)=j;
end
for i=1:m
    for j=1:n
        if (s(i) == t(j))
            mat(i+1,j+1)=mat(i,j);
        else
            mat(i+1,j+1)=1+min(min(mat(i+1,j),mat(i,j+1)),mat(i,j));
        end
    end
end

% Edit Sequence
s = char('democrat');
t = char('republican');
i = m+1;
j = n+1;
display([s ' --> ' t])
while(i ~= 1 && j ~= 1)
    temp = min(min(mat(i-1,j-1), mat(i,j-1)), mat(i-1,j));
    if(mat(i-1,j) == temp)
        i = i - 1;
        t = [t(1:j-1) s(i) t(j:end)];
        disp(strcat(['iinsertion: i=' int2str(i) ' , j=' int2str(j) ' ; ' s ' --> ' t]))
    elseif(mat(i-1,j-1) == temp)
        if(mat(i-1,j-1) == mat(i,j))
            i = i - 1;
            j = j - 1;
            disp(strcat(['uunchanged: i=' int2str(i) ' , j=' int2str(j) ' ; ' s ' --> ' t]))
        else
            i = i - 1;
            j = j - 1;
            t(j) = s(i);
            disp(strcat(['substition: i=' int2str(i) ' , j=' int2str(j) ' ; ' s ' --> ' t]))
        end
    elseif(mat(i,j-1) == temp)
        j = j - 1;
        t(j) = [];
        disp(strcat(['dddeletion: i=' int2str(i) ' , j=' int2str(j) ' ; ' s ' --> ' t]))
    end
end
0 голосов
/ 21 июня 2011

Недавно я поработал с матрицей алгоритма расстояния Левенштейна. Мне нужно было произвести операции, которые превратили бы один список в другой. (Это будет работать и для строк.)

Показывают ли следующие (обеты) тесты ту функциональность, которую вы ищете? 

  , "lev - complex 2"
  : { topic
    : lev.diff([13, 6, 5, 1, 8, 9, 2, 15, 12, 7, 11], [9, 13, 6, 5, 1, 8, 2, 15, 12, 11])
    , "check actions"
    : function(topic) { assert.deepEqual(topic, [{ op: 'delete', pos: 9, val: 7 },
                                                 { op: 'delete', pos: 5, val: 9 },
                                                 { op: 'insert', pos: 0, val: 9 },
                                                ]); }
    }
  , "lev - complex 3"
  : { topic
    : lev.diff([9, 13, 6, 5, 1, 8, 2, 15, 12, 11], [13, 6, 5, 1, 8, 9, 2, 15, 12, 7, 11])
    , "check actions"
    : function(topic) { assert.deepEqual(topic, [{ op: 'delete', pos: 0, val: 9 },
                                                 { op: 'insert', pos: 5, val: 9 },
                                                 { op: 'insert', pos: 9, val: 7 }
                                                ]); }
    }
  , "lev - complex 4"
  : { topic
    : lev.diff([9, 13, 6, 5, 1, 8, 2, 15, 12, 11, 16], [13, 6, 5, 1, 8, 9, 2, 15, 12, 7, 11, 17])
    , "check actions"
    : function(topic) { assert.deepEqual(topic, [{ op: 'delete', pos: 0, val: 9 },
                                                 { op: 'insert', pos: 5, val: 9 },
                                                 { op: 'insert', pos: 9, val: 7 },
                                                 { op: 'replace', pos: 11, val: 17 }
                                                ]); }
    }
...