Реконструкция минимального расстояния редактирования

Я считаю, что в этом случае важно более глубокое понимание алгоритма. Вместо того, чтобы давать вам какой-то псевдокод, я проведу вас через основные этапы алгоритма и покажу, как нужные вам данные «кодируются» в итоговой матрице, которая получается. Конечно, если вам не нужно сворачивать свой собственный алгоритм, вам, очевидно, следует просто использовать чужой, как предлагает MattH!

Большая картинка

Мне это кажется реализацией алгоритма Вагнера-Фишера. Основная идея состоит в том, чтобы вычислить расстояния между «ближайшими» префиксами, взять минимум, а затем вычислить расстояние для текущей пары строк из него. Так, например, скажем, у вас есть две строки 'i' и 'h'. Разложим их по вертикальной и горизонтальной осям матрицы, вот так:

  _ h
_ 0 1
i 1 1

Здесь '_' обозначает пустую строку, и каждая ячейка в матрице соответствует последовательности редактирования, которая переводит входные данные ('' или 'i') в выходные данные ('' или 'h').

Расстояние от пустой строки до любой строки длины L равно L (требуется L вставок). Расстояние от любой строки длины L до пустой строки также равно L (требуется удаление L). Это охватывает значения в первой строке и столбце, которые просто увеличиваются.

Отсюда вы можете вычислить значение любого местоположения, взяв минимальное значение из верхнего, левого и верхнего левого значений и добавив единицу, или, если буква в этой точке строки одинакова, взяв верхнее значение. -левое значение без изменений. Для значения (1, 1) в таблице выше минимальное значение равно 0 для (0, 0), поэтому значение для (1, 1) равно 1, и это минимальное расстояние редактирования от 'i' до 'h' (одна замена). В общем, минимальное расстояние редактирования всегда находится в правом нижнем углу матрицы.

Теперь давайте сделаем еще один, сравнив is с hi. Здесь снова каждая ячейка в матрице соответствует последовательности редактирования, которая преобразует входные данные ('', 'i' или 'is') в выходные данные ('', 'h' или 'hi').

  _ h i
_ 0 1 2
i 1 1 #
s 2 # #

Мы начинаем с увеличения матрицы, используя # в качестве заполнителя для значений, которые мы еще не знаем, и расширяем первую строку и столбец путем увеличения. Сделав это, мы можем начать вычисление результатов для позиций, отмеченных # выше. Начнем с (2, 1) (в (строке, столбце), т.е. в построчной нотации). Среди верхних, верхних и левых значений минимальное значение равно 1. Соответствующие буквы в таблице разные — s и h — поэтому мы добавляем единицу к этому минимальному значению, чтобы получить 2, и продолжаем.

  _ h i
_ 0 1 2
i 1 1 #
s 2 2 #

Давайте перейдем к значению (1, 2). Теперь все обстоит немного по-другому, потому что соответствующие буквы в таблице те же — они обе i. Это означает, что у нас есть возможность взять значение из верхней левой ячейки без добавления его. Руководящая интуиция здесь заключается в том, что нам не нужно увеличивать счет, потому что одна и та же буква добавляется к обеим строкам в этой позиции. А так как длины обеих струн увеличились на единицу, то двигаемся по диагонали.

  _ h i
_ 0 1 2
i 1 1 1
s 2 2 #

С последней пустой ячейкой все возвращается на круги своя. Соответствующие буквы s и i, поэтому мы снова берем минимальное значение и добавляем единицу, чтобы получить 2:

  _ h i
_ 0 1 2
i 1 1 1
s 2 2 2

Вот таблица, которую мы получим, если продолжим этот процесс для двух более длинных слов, начинающихся с is и hi -- isnt (без учета пунктуации) и hint:

  _ h i n t
_ 0 1 2 3 4
i 1 1 1 2 3
s 2 2 2 2 3
n 3 3 3 2 3
t 4 4 4 3 2

Эта матрица немного сложнее, но окончательное минимальное расстояние редактирования здесь по-прежнему составляет всего 2, потому что последние две буквы этих двух строк одинаковы. Удобный!

Воссоздание последовательности правок

Итак, как мы можем извлечь типы правок из этой таблицы? Ключ в том, чтобы понять, что движение по таблице соответствует определенным типам правок. Так, например, движение вправо от (0, 0) к (0, 1) ведет нас от _ -> _, не требующего редактирования, к _ -> h, требующему одного редактирования, вставки. Точно так же движение вниз от (0, 0) к (1, 0) ведет нас от _ -> _, не требующего редактирования, к i -> _, требующему одного редактирования, удаления. И, наконец, диагональное движение от (0, 0) к (1, 1) ведет нас от _ -> _, не требующего правок, к i -> h, требующему одной правки, замены.

Итак, теперь все, что нам нужно сделать, это обратить наши шаги вспять, проследив локальные минимумы между верхней, левой и верхней левой ячейками обратно к началу координат, (0, 0), имея в виду, что если текущее значение совпадает с минимумом, то мы должны перейти к верхней левой ячейке, так как это единственный вид движения, который не увеличивает расстояние редактирования.

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

1. Посмотрите на соседнюю ячейку слева вверху. Если ячейка не существует, перейдите к шагу 3. Если ячейка существует, обратите внимание на хранящееся там значение.
2. Is the value in the upper-left cell equal to the value in the current cell? If so, then do the following:
   • Record an empty operation (i.e. Equal). No edit was required in this case because the characters at this location are the same.
   • Обновите текущую ячейку, двигаясь вверх и влево.
   • Вернитесь к шагу 1.
3. There are many branches here:
   • If there is no cell to the left and no cell above, then you are in the upper-left corner, and the algorithm has completed.
   • Если слева нет ячейки, перейдите к шагу 4. (Это будет продолжаться в цикле, пока вы не дойдете до верхнего левого угла.)
   • Если выше нет ячейки, перейдите к шагу 5. (Это будет продолжаться в цикле, пока вы не дойдете до верхнего левого угла.)
   • Otherwise, do a three-way comparison between the cell to the left, the cell to the upper left, and the cell above. Pick the one with the smallest value. If there are multiple candidates, you can pick one at random; they are all valid at this stage. (They correspond to different edit paths with the same total edit distance.)
     • If you picked the cell above, go to step 4.
     • Если вы выбрали ячейку слева, перейдите к шагу 5.
     • Если вы выбрали ячейку в левом верхнем углу, перейдите к шагу 6.
4. You are moving up. Do the following:
   • Record a deletion of the input character at the current cell.
   • Обновите текущую ячейку, двигаясь вверх.
   • Вернитесь к шагу 1.
5. You are moving left. Do the following:
   • Record an insertion of the output character at the current cell.
   • Обновите текущую ячейку, двигаясь влево.
   • Вернитесь к шагу 1.
6. You are moving diagonally. Do the following:
   • Record a substitution of the input character at the current cell in place of the output character at the current cell.
   • Обновите текущую ячейку, двигаясь вверх и влево.
   • Вернитесь к шагу 1.

Собираем вместе

В приведенном выше примере есть два возможных пути:

(4, 4) -> (3, 3) -> (2, 2) -> (1, 2) -> (0, 1) -> (0, 0)

и

(4, 4) -> (3, 3) -> (2, 2) -> (1, 1) -> (0, 0)

Перевернув их, получим

(0, 0) -> (0, 1) -> (1, 2) -> (2, 2) -> (3, 3) -> (4, 4)

и

(0, 0) -> (1, 1) -> (2, 2) -> (3, 3) -> (4, 4)

Итак, для первого варианта наша первая операция — это движение вправо, т.е. вставка. Вставлена ​​буква h, так как мы переходим от isnt к hint. (Это соответствует Insert, h в вашем подробном выводе.) Наша следующая операция — движение по диагонали, то есть либо подстановка, либо отсутствие операции. В этом случае это недопустимо, потому что расстояние редактирования одинаково в обоих местах (т. е. одна и та же буква). Итак, Equal, i, i. Затем движение вниз, соответствующее удалению. Удалена буква s, так как снова мы переходим от isnt к hint. (Как правило, вставляемая буква берется из выходной строки, а удаляемая — из входной.) Итак, это Delete, s. Затем два диагональных движения без изменения стоимости: Equal, n, n и Equal, t, t.

Результат:

Insert, h
Equal, i, i
Delete, s
Equal, n, n
Equal, t, t

Выполнение этих инструкций на isnt:

isnt   (No change)
hisnt  (Insertion)
hisnt  (No change)
hint   (Deletion)
hint   (No change)
hint   (No change)

Для общего расстояния редактирования 2.

Я оставлю второй минимальный путь в качестве упражнения. Имейте в виду, что оба пути полностью эквивалентны; они могут быть разными, но они приведут к одному и тому же минимальному расстоянию редактирования, равному 2, и поэтому полностью взаимозаменяемы. В любой момент, когда вы работаете с матрицей в обратном направлении, если вы видите два разных возможных локальных минимума, вы можете выбрать любой из них, и окончательный результат гарантированно будет правильным.

Как только вы все это поймете, вам не составит труда написать код. Ключевым моментом в подобных случаях является глубокое понимание алгоритма. Как только вы это сделаете, закодировать это не составит труда.

Накопление против реконструкции

И последнее замечание: вы можете выбрать накапливать изменения по мере заполнения матрицы. В этом случае каждая ячейка вашей матрицы может быть кортежем: (2, ('ins', 'eq', 'del', 'eq', 'eq')). Вы должны увеличить длину, и добавить операцию, соответствующую перемещению из минимального предыдущего состояния. Это избавляет от поиска с возвратом и, таким образом, снижает сложность кода; но занимает дополнительную память. Если вы сделаете это, окончательная последовательность редактирования появится вместе с окончательным расстоянием редактирования в правом нижнем углу матрицы.

Я предлагаю вам взглянуть на модуль python-Levenshtein. Вероятно, вы проделаете долгий путь:

>>> import Levenshtein
>>> Levenshtein.editops('LEAD','LAST')
[('replace', 1, 1), ('replace', 2, 2), ('replace', 3, 3)]

Вы можете обрабатывать выходные данные операций редактирования для создания подробных инструкций.

Я не знаю python, но следующий код С# работает, если это поможет.

public class EditDistanceCalculator
{
    public double SubstitutionCost { get; private set; }
    public double DeletionCost { get; private set; }
    public double InsertionCost { get; private set; }

    public EditDistanceCalculator() : this(1,1, 1)
    {
    }

    public EditDistanceCalculator(double substitutionCost, double insertionCost, double deletionCost)
    {
        InsertionCost = insertionCost;
        DeletionCost = deletionCost;
        SubstitutionCost = substitutionCost;
    }

    public Move[] CalcEditDistance(string s, string t)
    {
        if (s == null) throw new ArgumentNullException("s");
        if (t == null) throw new ArgumentNullException("t");

        var distances = new Cell[s.Length + 1, t.Length + 1];
        for (int i = 0; i <= s.Length; i++)
            distances[i, 0] = new Cell(i, Move.Delete);
        for (int j = 0; j <= t.Length; j++)
            distances[0, j] = new Cell(j, Move.Insert);

        for (int i = 1; i <= s.Length; i++)
            for (int j = 1; j <= t.Length; j++)
                distances[i, j] = CalcEditDistance(distances, s, t, i, j);

        return GetEdit(distances, s.Length, t.Length);
    }

    private Cell CalcEditDistance(Cell[,] distances, string s, string t, int i, int j)
    {
        var cell = s[i - 1] == t[j - 1]
                            ? new Cell(distances[i - 1, j - 1].Cost, Move.Match)
                            : new Cell(SubstitutionCost + distances[i - 1, j - 1].Cost, Move.Substitute);
        double deletionCost = DeletionCost + distances[i - 1, j].Cost;
        if (deletionCost < cell.Cost)
            cell = new Cell(deletionCost, Move.Delete);

        double insertionCost = InsertionCost + distances[i, j - 1].Cost;
        if (insertionCost < cell.Cost)
            cell = new Cell(insertionCost, Move.Insert);

        return cell;
    }

    private static Move[] GetEdit(Cell[,] distances, int i, int j)
    {
        var moves = new Stack<Move>();
        while (i > 0 && j > 0)
        {
            var move = distances[i, j].Move;
            moves.Push(move);
            switch (move)
            {
                case Move.Match:
                case Move.Substitute:
                    i--;
                    j--;
                    break;
                case Move.Insert:
                    j--;
                    break;
                case Move.Delete:
                    i--;
                    break;
                default:
                    throw new ArgumentOutOfRangeException();
            }
        }
        for (int k = 0; k < i; k++)
            moves.Push(Move.Delete);
        for (int k = 0; k < j; k++)
            moves.Push(Move.Insert);

        return moves.ToArray();
    }

    class Cell
    {
        public double Cost { get; private set; }
        public Move Move { get; private set; }

        public Cell(double cost, Move move)
        {
            Cost = cost;
            Move = move;
        }
    }
}

public enum Move
{
    Match,
    Substitute,
    Insert,
    Delete
}

Некоторые тесты:

    [TestMethod]
    public void TestEditDistance()
    {
        var expected = new[]
            {
                Move.Delete, 
                Move.Substitute, 
                Move.Match, 
                Move.Match, 
                Move.Match, 
                Move.Match, 
                Move.Match, 
                Move.Insert,
                Move.Substitute, 
                Move.Match, 
                Move.Substitute, 
                Move.Match, 
                Move.Match, 
                Move.Match, 
                Move.Match
            };
        Assert.IsTrue(expected.SequenceEqual(new EditDistanceCalculator().CalcEditDistance("thou-shalt-not", "you-should-not")));

        var calc = new EditDistanceCalculator(3, 1, 1);
        var edit = calc.CalcEditDistance("democrat", "republican");
        Console.WriteLine(string.Join(",", edit));
        Assert.AreEqual(3, edit.Count(m => m == Move.Match)); //eca
    }