равен нулю, мы выполняем рекурсивный вызов, перемещаясь по матрице влево, и тогда действием является ставка текущего символа в строку То. И, наконец, если оба индекса не равны нулю, мы находим соответствующую ячейку в матрице, выполняем рекурсивный вызов и записываем действие в файл. Перемещению вниз соответствует удаление, перемещению вправо - вставка, перемещению по диагонали - ни одно из упомянутых действий (символ 'переносится' из одной строки в другую). Для обозначения удаления мы будем использовать стрелку, указывающую вправо (-> ), а для обозначения вставки - стрелку, указывающую влево (<-). Перенос символа не обозначается.
Листинг 12.26. Вывод последовательности редактирования
procedure TtdStringLCS.slWriteChange(var F : System.Text;
aFromInx, aToInx : integer);
var
Cell : PtdLCSData;
begin
{если оба индекса равны нулю, данная ячейка является первой ячейкой матрицы LCS, поэтому подпрограмма просто выполняет выход}
if (aFromInx = 0) and (aToInx = 0) then
Exit;
{если индекс строки From равен нулю, ячейка расположена в левом столбце матрицы, поэтому необходимо переместиться вверх; этому будет соответствовать удаление}
if (aFromInx = 0) then begin
slWriteChange(F, aFromInx, aToInx-1);
writeln(F, '->', FToStr[aToInx]);
end
{если индекс строки To равен нулю, ячейка расположена в верхней строке матрицы, поэтому необходимо переместиться влево; этому будет соответствовать вставка}
else
if (aToInx = 0) then begin
slWriteChange(F, aFromInx-1, aToInx);
writeln(F, '< - FFromStr[aFromInx]);
end
{в противном случае необходимо выполнить действия, указанные ячейкой}
else begin
Cell := FMatrix[aFromInx, aToInx];
case Cell^.ldPrev of
ldNorth : begin
slWriteChange(F, aFromInx-1, aToInx);
writeln(F, ' <- ', FFromStr[aFromInx]);
end;
ldNorthWest : begin
slWriteChange(F, aFromInx-1, aToInx-1);
writeln(F, ' ', FFromStr[aFromInx]);
end;
ldWest : begin
slWriteChange(F, aFromInx, aToInx-1);
writeln(F, '-> FToStr[aToInx]);
end;
end;
end;
end;
procedure TtdStringLCS.WriteChanges(const aFileName : string);
var
F : System.Text;
begin
System.Assign(F, aFileName);
System.Rewrite(F);
try
slWriteChange(F, length(FFromStr), length(FToStr));
finally
System.Close(F);
end;
end;
Ниже показан текстовый файл, который был сгенерирован для преобразования слова 'illiteracy' в слово 'innumeracy'.
< - i
<- l
<- l
i
<- t
-> n
-> n
-> u
-> m
e
r
a
с
y
Это представление действий по редактированию легко доступно для понимания, но при необходимости его можно развернуть. Как видите, наиболее длинная общая подпоследовательностью является (i, e, r, a, c, y), а определение удалений и вставок не представляет сложности.
Памятуя о том, что примененный метод является рекурсивным, следует подумать о требуемой для его реализации глубине стека. Если бы строки вообще не имели общих символов, последовательность редактирования сводилась бы к удалению всех символов первой строки и вставке всех символов второй строки. Если первая строка содержит n символов, а вторая m, глубина стека должна быть пропорциональной сумме n + m.
Вычисление LCS двух файлов
После того, как мы ознакомились с решением для двух строк, его можно модифицировать для вычисления LCS и генерации команд редактирования для двух текстовых файлов. Дабы упростить себе задачу, выполним считывание обоих файлов в объект TStringsLists. Понятно, что теперь одновременно выполняется сравнение целых текстовых строк, а не символов, тем не менее, в основном, реализация остается практически той же самой. Код интерфейса и вспомогательных методов приведен в листинге 12.27.
