Вопрос по matrix, python – Реконструкция минимального редактирования расстояния

9

Я знаю, что есть аналогичные ответы на этот вопрос в стеке, а также в Интернете, но я чувствую, что что-то упустил. Учитывая приведенный ниже код, нам нужно восстановить последовательность событий, которая привела к полученному минимальному расстоянию редактирования. Для приведенного ниже кода нам нужно написать функцию, которая выводит:

Equal, L, L
Delete, E
Equal, A, A
Substitute, D, S
Insert, T

EDIT: CODE IS UPDATED WITH MY (PARTIALLY CORRECT) SOLUTION

Вот код с моим частичным решением. Это работает, например, мне дали («привести» - «последний»), но не работает в приведенном ниже примере («подсказка» - «нет»). Я подозреваю, что это потому, что первый символ равен, что выбрасывает мой код. Любые советы или указатели в правильном направлении будут великолепны!

def printMatrix(M):
        for row in M:
                print row
        print

def med(s, t):  
        k = len(s) + 1
        l = len(t) + 1

        M = [[0 for i in range(k)] for j in range(l)]
        MTrace = [["" for i in range(k)] for j in range(l)]

        M[0][0] = 0


        for i in xrange(0, k):
                M[i][0] = i
                MTrace[i][0] = s[i-1]

        for j in xrange(0, l):
                M[0][j] = j
                MTrace[0][j] = t[j-1]

        MTrace[0][0] = "DONE"

        for i in xrange(1, k):
                for j in xrange(1, l):

                        sub = 1
                        sub_op = "sub"
                        if s[i-1] == t[j-1]:
                                # equality
                                sub = 0
                                sub_op = "eq"


                        # deletion
                        min_value = M[i-1][j] + 1
                        op = "del"
                        if min_value > M[i][j-1] + 1:
                                # insertion
                                min_value = M[i][j-1] + 1
                                op = "ins"
                        if min_value > M[i-1][j-1] + sub:
                                # substitution
                                min_value = M[i-1][j-1] + sub
                                op = sub_op


                        M[i][j] = min_value
                        MTrace[i][j] = op                        

        print "final Matrix"
        printMatrix(M)
        printMatrix(MTrace)

############ MY PARTIAL SOLUTION

        def array_append(array,x,y):
            ops_string = MTrace[x][y]
            if ops_string == 'ins':
                array.append(("Insert",MTrace[0][y]))
            elif ops_string == 'sub':
                array.append(("Substitute",MTrace[x][0],MTrace[0][y]))
            elif ops_string == 'eq':
                array.append(("Equal",MTrace[x][0],MTrace[0][y]))
            elif ops_string == 'del':
                array.append(("Delete",MTrace[x][0]))


        i = len(s)
        j = len(t)

        ops_array = []
        base = M[i][j]
        array_append(ops_array,i,j)


        while MTrace[i][j] != "DONE":
            base = M[i][j]
            local_min = min(M[i][j-1],M[i-1][j],M[i-1][j-1])
            if base == local_min:
                i = i - 1
                j = j - 1
                array_append(ops_array,i,j)
            elif M[i][j-1] < M[i-1][j]:
                j = j -1
                array_append(ops_array,i,j)
            elif M[i-1][j] < M[i][j-1]:
                i = i - 1
                array_append(ops_array,i,j)
            else:
                i = i - 1
                j = j - 1
                array_append(ops_array,i,j)

        print ops_array
#########

        return M[k-1][l-1]      

print med('lead', 'last')

Ваш Ответ

3   ответа
9

питон-Левенштейна модуль. Вероятно, вам удастся пройти долгий путь:

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

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

2

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
    }
32

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

The Big Picture

Это выглядит для меня как реализацияАлгоритм Вагнера-Фишера, Основная идея состоит в том, чтобы вычислить расстояния между "близлежащими" префиксы, взять минимум, а затем рассчитать расстояние для текущей пары строк из этого. Так, например, скажем, у вас есть две строки'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, Это означает, что у нас есть возможность взять значение в верхней левой ячейкеwithout adding one, Руководящая интуиция здесь заключается в том, что нам не нужно увеличивать счет, потому что одна и та же буква добавляется в обе строки в этой позиции. И поскольку длины обеих струн увеличились на одну, мы движемся по диагонали.

  _ 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потому что последние две буквы этих двух строк одинаковы. Удобный!

Recreating the Sequence of Edits

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

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

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

Look at the neighboring cell to the upper left. If it doesn't exist, go to step 3. If the cell does exist, note the value stored there. 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. Update the current cell, moving up and left. Return to step 1. 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. If there is no cell to the left, go to step 4. (This will continue in a loop until you reach the upper-left corner.) If there is no cell above, go to step 5. (This will continue in a loop until you reach the upper-left corner.) 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. If you picked the cell to the left, go to step 5. If you picked the cell to the upper left, go to step 6. You are moving up. Do the following: Record a deletion of the input character at the current cell. Update the current cell, moving up. Return to step 1. You are moving left. Do the following: Record an insertion of the output character at the current cell. Update the current cell, moving left. Return to step 1. 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. Update the current cell, moving up and left. Return to step 1. Putting it Together

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

(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, и поэтому полностью взаимозаменяемы. В любой момент, когда вы работаете в обратном направлении через матрицу, если вы видите два разных возможных локальных минимума, вы можете взять любой из них, и конечный результат гарантированно будет правильным

Как только вы все это поймете, вам вообще будет трудно писать код. Ключ, в таких случаях, этоdeeply understand the algorithm первый. После того, как вы это сделали, его кодирование становится несложным делом.

Accumulation vs. Reconstruction

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

Error: User Rate Limit Exceeded Adam_G
Error: User Rate Limit ExceededminError: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded Adam_G
Error: User Rate Limit Exceeded Adam_G

Похожие вопросы