Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi
Код реализации простой технологии обхода, которая может быть приведена в соответствие с нашими потребностями, показан в листинге 12.26. Подпрограмма содержит два метода: первый вызывается пользователем с указанием имени файла, а второй представляет собой рекурсивную подпрограмму, которая записывает данные в файл. Весь основной объем работы выполняется во второй подпрограмме. Поскольку в матрице путь LCS кодируется в обратном направлении (т.е. для определения пути необходимо начать с конца и продвигаться к началу матрицы), мы создаем метод, который вначале вызывает сам себя, а затем записывает данные, соответствующие текущей позиции. Необходимо обеспечить прерывание выполнения рекурсивной подпрограммы. Это соответствует случаю, когда подпрограмма вызывается для ячейки (0,0). В этом случае никакие данные не записываются в файл. Если индекс строки То равен нулю, мы выполняем рекурсивный вызов, перемещаясь вверх по матрице (индекс строки From уменьшается), и предпринимаемым действием должно быть удаление символа из строки From. Если индекс строки From равен нулю, мы выполняем рекурсивный вызов, перемещаясь по матрице влево, и тогда действием является ставка текущего символа в строку То. И, наконец, если оба индекса не равны нулю, мы находим соответствующую ячейку в матрице, выполняем рекурсивный вызов и записываем действие в файл. Перемещению вниз соответствует удаление, перемещению вправо - вставка, перемещению по диагонали - ни одно из упомянутых действий (символ "переносится" из одной строки в другую). Для обозначения удаления мы будем использовать стрелку, указывающую вправо (-> ), а для обозначения вставки - стрелку, указывающую влево (<-). Перенос символа не обозначается.
Листинг 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.
Листинг 12.27. Класс TtdFileLCS
type
TtdFileLCS = class private
FFromFile : TStringList;
FMatrix : TtdLCSMatrix;
FToFile : TStringList;
protected
function slGetCell(aFromInx, aToInx : integer): integer;
procedure slWriteChange(var F : System.Text;
aFromInx, aToInx : integer);
public
constructor Create(const aFromFile, aToFile : string);
destructor Destroy; override;
procedure WriteChanges(const aFileName : string);
end;
constructor TtdFileLCS.Create(const aFromFile, aToFile : string);
begin
{создать производный объект}
inherited Create;
{выполнить считывание файлов}
FFromFile := TStringList.Create;
FFromFile.LoadFromFile(aFromFile);
FToFile := TStringList.Create;
FToFile.LoadFromFile(aToFile);
{создать матрицу}
FMatrix := TtdLCSMatrix.Create(FFromFile.Count, FToFile.Count);
{заполнить матрицу}
slGetCell(pred(FFromFile.Count), pred(FToFile.Count));
end;
destructor TtdFileLCS.Destroy;
begin
{уничтожить матрицу}
FMatrix.Free;
{освободить списки строк}
FFromFile.Free;
FToFile.Free;
{уничтожить производный объект}
inherited Destroy;
end;
Однако нужно решить одну проблему: при работе со строками отсчет символов начинается с 1, а при работе со списком строк отсчет строк (строк в исходном файле) начинается с 0. Поэтому необходимо внести ряд изменений.
Первое изменение заключается в простом кодировании рекурсивного метода. Если помните, итеративный метод требовал предварительного выделения ячеек, расположенных вдоль верхней и левой сторон матрицы, и установки их значений равными 0, в то время как в рекурсивном методе для выполнения этой задачи использовался оператор If. Потенциально это позволяет сэкономить достаточно большой объем памяти (в общем случае текстовые файлы могут содержать несколько сотен или даже тысяч строк).
Второе изменение, как уже отмечалось, - отсчет строк с 0. Рекурсивная подпрограмма автоматически решает эту задачу.
Код реализации рекурсивного метода генерирования LCS для двух файлов приведен в листинге 12.28.
Листинг 12.28. Генерация LCS для пары файлов
function TtdFileLCS.slGetCell(aFromInx, aToInx : integer): integer;
var
LCSData : PtdLCSData;
NorthLen: integer;
WestLen : integer;
begin
if (aFromInx = -1) or (aToInx = -1) then
Result := 0
else begin
LCSData := FMatrix[aFromInx, aToInx];
if (LCSData <> nil) then
Result := LCSData^.ldLen
else begin
{создать новый элемент}
New(LCSData);
{если две текущие строки совпадают, необходимо увеличить значение счетчика относительно элемента, расположенное о к северо-западу от текущего, т.е. предшествующего элемента}
if (FFromFile[aFromInx] = FToFile [aToInx]) then begin
LCSData^.ldPrev := ldNorthWest;
LCSData^.ldLen := slGetCell(aFromInx-1, aToInx-1) + 1;
end
{в противном случае текущие строки различны: необходимо использовать максимальный из элементов, расположенных к северу или западу (использование элемента, расположенного к западу, предпочтительнее)} else begin
NorthLen := slGetCell(aFromInx-1, aToInx);
WestLen := slGetCell(aFromInx, aToInx-1);
if (NorthLen > WestLen) then begin
LCSData^.ldPrev := ldNorth;
LCSData^.ldLen := NorthLen;
end
else begin
LCSData^.ldPrev := ldWest;
LCSData^.ldLen := WestLen;
end;
end;
{установить элемент в матрице}
FMatrix [ aFromInx, aToInx ] := LCSData;
{вернуть длину данного LCS}
Result := LCSData^.ldLen;
end;
end;
end;
Метод записи последовательности редактирования, которая обеспечивает преобразование первого файла во второй, не особенно изменился по сравнению с рассмотренным ранее, за исключением того, что выполняется запись строк, а не символов. Эта подпрограмма приведена в листинге 12.29.
Листинг 12.29. Запись последовательности редактирования для пары файлов
procedure TtdFileLCS.slWriteChange(var F : System.Text;
aFromInx, aToInx : integer);
var
Cell : PtdLCSData;
begin
{если оба индекса меньше нуля, данная ячейка является первой ячейкой матрицы LCS, поэтому подпрограмма просто выполняет выход}
if (aFromInx = -1) and (aToInx = -1) then
Exit;
{если индекс строки From меньше нуля, ячейка расположена в левом столбце матрицы, поэтому необходимо переместиться вверх; этому будет соответствовать удаление}
if (aFromInx = -1) then begin
slWriteChange(F, aFromInx, aToInx-1);
writeln(F, '->', FToFile[aToInx]);
end
{если индекс строки To меньше нуля, ячейка расположена в верхней строке матрицы, поэтому необходимо переместиться влево; этому будет соответствовать вставка}
else
if (aToInx = -1) then begin
slWriteChange(F, aFromInx-1, aToInx);
writeln(F, '<-', FFromFile[aFromInx]);
end
{в противном случае необходимо выполнить действия, указанные ячейкой}
else begin
Cell := FMatrix[aFromInx, aToInx];
case Cell^.ldPrev of
ldNorth :
begin
slWriteChange(F, aFromInx-1, aToInx);
writeln(F, '<-', FFromFile [aFromInx]);
end;
ldNorthWest : begin
slWriteChange(F, aFromInx-1, aToInx-1);
writeln(F, 1 ', FFromFile[aFromInx]);
end;
