Книга: Фундаментальные алгоритмы и структуры данных в Delphi
Вычисление LCS двух файлов
Вычисление 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;
ldWest : begin
slWriteChange(F, aFromInx, aToInx-1);
writeln(Ff FToFile[aToInx]);
end;
end;
end;
end;
procedure TtdFileLCS.WriteChanges(const aFileName : string);
var
F : System.Text;
begin
System.Assign(F, aFileName);
System.Rewrite(F);
try
slWriteChange (F, pred(FFromFile.Count), pred(FToFile.Count)) finally
System.Close(F);
end;
end;
- Резервное копирование многофайловых баз данных
- Восстановление из резервных копий многофайловых баз данных
- Forced writes - палка о двух концах
- Создание файлов с блокировкой
- Рекомендуемое расширение для файлов баз данных - *.ib
- Создание многофайловой базы данных
- Правила именования файлов
- Глава 6 Файловые системы
- 3.4 Сетевая файловая система
- Глава 2 Вычисление
- 6.4 Другие файловые системы
- 6.5 Файловая система NTFS