Матрица населенных действий в реализации алгоритма расстояния Левенштейна - PullRequest
Новая
       13

Матрица населенных действий в реализации алгоритма расстояния Левенштейна

2 голосов
/ 01 марта 2012

Я пытаюсь улучшить существующий исходный код для расчета расстояния Левенштейна в javascript, чтобы сгенерировать мартикс не только со значением текущих установок, но и с предпринятыми действиями (вставить, заменить, удалить или сопоставить)

Я получаю неправильные результаты в матрице "действий":

levenstein actions

в алгоритме мы видим, что (не JS, из Википедии): 

 d[i, j] := minimum
                    (
                      d[i-1, j] + 1,  // a deletion
                      d[i, j-1] + 1,  // an insertion
                      d[i-1, j-1] + 1 // a substitution
                    )

Итак, в моем коде JS я делаю следующее: 

// Step 6
d[i][j] = Minimum(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + cost);

// a deletion
if(d[i][j] == d[i - 1][j] + 1) {
    actions[i][j] = 'D';
}

// a insertion
if(d[i][j] == d[i][j - 1] + 1) {
    actions[i][j] = 'I';
}

// a substitution
if(d[i][j] == d[i - 1][j - 1] + cost) {
    actions[i][j] = 'R';
}

Матрица d (двумерный массив) предназначена для значений, и она заполняется правильными значениями. Но почему соответствующая матрица actions отображает не то, что логически сделал бы алгоритм?

Что я делаю неправильно в отношении присвоения им «I», «R», «D»? Или это правильно и просто не кажется мне логичным, так как я думал, что в вышеупомянутом сценарии вставка будет происходить на втором этапе.

Кстати, действительно ли целесообразно генерировать такую ​​матрицу "действий" в случае алгоритма Левенштейна?

1 Ответ

1 голос
/ 02 марта 2012

Обычно существует множество способов генерировать набор «действий» для любой заданной матрицы Левенштейна. В вашем примере вы можете проследить полученную матрицу затрат всегда до минимума, и вы найдете довольно много путей.

Вот несколько примеров: 

(0,0)(0,1)(1,2)(1,3)(2,4)(3,5)

(0,0)(1,1)(1,2)(1,3)(2,4)(3,5)

(0,0)(0,1)(0,2)(1,3)(2,4)(3,5)

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

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

Предлагаемое решение, когда мы предпочитаем замены, состоит в том, чтобы вставить A и N перед чем-либо еще, затем заменить M на N, A на A и X на S. Если вы проверите, то увидите, что это будет стоить четыре (две вставки и две «настоящие» замены), что в точности соответствует матрице (это последний путь в путях, которые я проследил).

Теперь снова проверяем вашу матрицу действий, что мы находим, если проследим обратно из последнего угла: R, R и R в местах (3,5), (2,4) и (1,3). Это соответствует окончательному замещению от MAX до NAS. Чего здесь не хватает, так это вставки ведущего AN, который я проследил выше. Глядя на матрицу, можно увидеть, что в первом ряду и столбце есть числа, а не действия. Однако это должны быть соответственно удаления и замены, и в этом случае вы можете создать окончательную последовательность SSRRR, стоимость которой для преобразования MAX в ANNAS.

равна четырем.

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

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

EDIT

Вот полная матрица действий для путей, включающая двусмысленности: 

*   D     D     D 
I   R    R/D    D
I  R/I   R/I    R
I  R/I   R/I   R/I
I  R/I    R   R/I/D
I  R/I    I     R
...