Джулиан М. Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi

использовать стрелку, указывающую вправо (-> ), а для обозначения вставки - стрелку, указывающую влево (<-). Перенос символа не обозначается.

Листинг 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 для двух файлов --">