Реконструкция минимального редактирования расстояния
Я знаю, что есть аналогичные ответы на это в стеке, а также в Интернете, но я чувствую, что что-то упустил. Учитывая приведенный ниже код, нам нужно восстановить последовательность событий, которая привела к получению минимального расстояния редактирования. Для приведенного ниже кода нам нужно написать функцию, которая выводит:
Equal, L, L
Delete, E
Equal, A, A
Substitute, D, S
Insert, T
РЕДАКТИРОВАТЬ: КОД ОБНОВЛЕН С МОИМ (ЧАСТИЧНО ПРАВИЛЬНЫМ) РЕШЕНИЕМ
Вот код, с моим частичным решением. Это работает, например, мне дали ("lead" -> "last"), но не работает для примера ниже ("подсказка" -> "isnt"). Я подозреваю, что это потому, что первый символ равен, что выбрасывает мой код. Любые советы или указатели в правильном направлении будут великолепны!
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 ответа
По моему мнению, в этом случае важно более глубокое понимание алгоритма. Вместо того, чтобы дать вам некоторый псевдокод, я проведу вас по основным этапам алгоритма и покажу, как нужные данные "кодируются" в итоговой матрице, которая получается. Конечно, если вам не нужно накатывать свой собственный алгоритм, тогда вам, очевидно, следует просто использовать чей-то другой, как предлагает МэттХ!
Большая картина
Это выглядит для меня как реализация алгоритма Вагнера-Фишера. Основная идея состоит в том, чтобы вычислить расстояния между "соседними" префиксами, взять минимум и затем вычислить расстояние для текущей пары строк из этого. Так, например, скажем, у вас есть две строки '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)Имея в виду, что если текущее значение совпадает с минимальным, то мы должны перейти в верхнюю левую ячейку, поскольку это единственный вид движения, который не увеличивает расстояние редактирования.
Вот подробное описание шагов, которые вы можете предпринять, чтобы сделать это. Начиная с нижнего правого угла заполненной матрицы, повторяйте следующие действия, пока не дойдете до верхнего левого угла:
- Посмотрите на соседнюю ячейку слева вверху. Если он не существует, перейдите к шагу 3. Если ячейка существует, запишите сохраненное там значение.
- Значение в верхней левой ячейке равно значению в текущей ячейке? Если так, то сделайте следующее:
- Запишите пустую операцию (т.е.
Equal). В этом случае редактирование не требовалось, потому что символы в этом месте совпадают. - Обновите текущую ячейку, двигаясь вверх и влево.
- Вернитесь к шагу 1.
- Запишите пустую операцию (т.е.
- Здесь много филиалов:
- Если слева нет ячейки, а сверху нет ячейки, значит, вы находитесь в верхнем левом углу, и алгоритм завершен.
- Если слева нет ячейки, перейдите к шагу 4. (Это будет продолжаться в цикле, пока вы не достигнете верхнего левого угла.)
- Если выше ячейки нет, перейдите к шагу 5. (Это будет продолжаться в цикле, пока вы не достигнете верхнего левого угла.)
- В противном случае выполните трехстороннее сравнение между ячейкой слева, ячейкой слева вверху и ячейкой сверху. Выберите тот, который имеет наименьшее значение. Если есть несколько кандидатов, вы можете выбрать одного наугад; все они действительны на данном этапе. (Они соответствуют различным путям редактирования с одинаковым общим расстоянием редактирования.)
- Если вы выбрали ячейку выше, перейдите к шагу 4.
- Если вы выбрали ячейку слева, перейдите к шагу 5.
- Если вы выбрали ячейку слева вверху, перейдите к шагу 6.
- Вы движетесь вверх. Сделайте следующее:
- Запишите удаление введенного символа в текущей ячейке.
- Обновите текущую ячейку, двигаясь вверх.
- Вернитесь к шагу 1.
- Вы двигаетесь влево. Сделайте следующее:
- Запишите вставку выходного символа в текущую ячейку.
- Обновите текущую ячейку, двигаясь влево.
- Вернитесь к шагу 1.
- Вы двигаетесь по диагонали. Сделайте следующее:
- Запишите замену входного символа в текущей ячейке вместо выходного символа в текущей ячейке.
- Обновите текущую ячейку, двигаясь вверх и влево.
- Вернитесь к шагу 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')), Вы должны увеличить длину и добавить операцию, соответствующую движению из минимального предыдущего состояния. Это устраняет необходимость возврата к исходному состоянию и снижает сложность кода; но это занимает дополнительную память. Если вы сделаете это, окончательная последовательность редактирования появится вместе с конечным расстоянием редактирования в нижнем правом углу матрицы.
Я предлагаю вам взглянуть на модуль Питона-Левенштейна. Вероятно, вам удастся проделать долгий путь:
>>> import Levenshtein
>>> Levenshtein.editops('LEAD','LAST')
[('replace', 1, 1), ('replace', 2, 2), ('replace', 3, 3)]
Вы можете обработать вывод из редактирования операций, чтобы создать ваши подробные инструкции.
Я не знаю Python, но следующий код C# работает, если это поможет.
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
}