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

ColList := TList(FMatrix.List^[Row]);

if (ColList <> nil) then

for Col := 0 to pred(FCols) do

begin

if (ColList.List^[Col] <> nil) then

Dispose(PtdLCSData(ColList.List^[Col]));

ColList.List^[Col] :=nil;

end;

end;

end;

function TtdLCSMatrix.mxGetItem(aRow, aCol : integer): PtdLCSData;

begin

if not ((0 <= aRow) and (aRow < RowCount) and (0 <= aCol) and (aCol < ColCount)) then

raise Exception.Create(

'TtdLCSMatrix.mxGetItem: Row or column index out of bounds');

Result := PtdLCSData(TList(FMatrix.List^[aRow]).List^[aCol]);

end;

procedure TtdLCSMatrix.mxSetItem(aRow, aCol : integer;

aValue : PtdLCSData);

begin

if not ((0 <= aRow) and (aRow < RowCount) and (0 <= aCol) and (aCol < ColCount)) then

raise Exception.Create(

'TtdLCSMatrix.mxSetItem: Row or column index out of bounds');

TList(Matrix.List^[aRow]).List^[aCol] := aValue;

end;

Следующий шаг заключается в создании класса, который реализует алгоритм вычисления LCS для строк. Код интерфейса и выполнения служебных функций класса TtdStringLCS приведен в листинге 12.23.

Листинг 12.23. Класс TtdStringLCS

type

TtdStringLCS = class private

FFromStr : string;

FMatrix : TtdLCSMatrix;

FToStr : string;

protected

procedure slFillMatrix;

function slGetCell(aFromInx, aToInx : integer): integer;

procedure slWriteChange(var F : System.Text;

aFromInx, aToInx : integer);

public

constructor Create(const aFromStr, aToStr : string);

destructor Destroy; override;

procedure WriteChanges(const aFileName : string;

end;

constructor TtdStringLCS.Create(const aFromStr, aToStr : string);

begin

{создать производный объект}

inherited Create;

{сохранить строки}

FFromStr := aFromStr;

FToStr :=aToStr;

{создать матрицу}

FMatrix := TtdLCSMatrix.Create(succ(length(aFromStr)), succ(length(aToStr)));

{заполнить матрицу}

slFillMatrix;

end;

destructor TtdStringLCS.Destroy;

begin

{уничтожить матрицу}

FMatrix.Free;

{уничтожить производный объект}

inherited Destroy;

end;

При первой реализации алгоритма вычисления LCS я столкнулся с дилеммой: придерживаться ли ранее описанного рекурсивного алгоритма или же только что описанного процесса вычисления LCS вручную? Чтобы получить ответ на ряд вопросов (какой из методов проще, какой требует использования меньшего объема памяти, какой работает быстрее), я реализовал оба подхода, причем начал с реализации итеративного метода. Это итеративное решение приведено в листинге 12.24.

Листинг 12.24. Итеративное вычисление LCS

procedure TtdStringLCS.slFillMatrix;

var

FromInx : integer;

ToInx : integer;

NorthLen: integer;

WestLen : integer;

LCSData : PtdLCSData;

begin

{создать пустые элементы, располагающиеся вдоль верхней и левой сторон матрицы}

for ToInx := 0 to length (FToStr) do

begin

New(LCSData);

LCSData^.ldLen := 0;

LCSData^.ldPrev := ldWest;

FMatrix[0, ToInx] := LCSData;

end;

for FromInx := 1 to length (FFromStr) do

begin

New(LCSData);

LCSData^.ldLen := 0;

LCSData^.ldPrev := ldNorth;

FMatrix [FromInx, 0] := LCSData;

end;

{построчное, слева направо, заполнение матрицы}

for FromInx := 1 to length (FFromStr) do

begin

for ToInx := 1 to length (FToStr) do

begin {создать новый элемент}

New(LCSData);

{если два текущих символа совпадают, необходимо увеличить значение счетчика элемента, расположенного к северо-западу, т.е. предыдущего элемента}

if (FFromStr[FromInx] = FToStr[ToInx]) then begin

LCSData^.ldPrev := ldNorthWest;

LCSData^.ldLen := succ(FMatrix[FromInx-1, ToInx-1]^.ldLen);

end

{в противном случае текущие символы различны: необходимо использовать максимальный из элементов, расположенных к северу или к западу от текущего (к западу предпочтительнее)}

else begin

NorthLen := FMatrix[FromInx-1, ToInx]^.ldLen;

WestLen := FMatrix[FromInx, ToInx-1]^.ldLen;

if (NorthLen > WestLen) then begin

LCSData^.ldPrev := ldNorth;

LCSData^.ldLen := NorthLen;

end

else begin

LCSData^.ldPrev :=ldWest;

LCSData^.ldLen := WestLen;

end;

end;

{установить элемент в матрице}

FMatrix[FromInx, ToInx] := LCSData;

end;

end;

{на этом этапе длина элемента, расположенного в нижнем правом углу, равна LCS, и вычисление завершено}

end;

Мы начинаем с заполнения верхней строки и левого столбца матрицы нулевыми ячейками. Длина LCS в этих ячейках равна нулю (вспомните, что они описывают LCS пустой и какой-либо другой строки), и мы всего лишь устанавливаем флаг направления, дабы он указывал на предшествующую ячейку, ближайшую к ячейке (0,0). Затем следует вложенный цикл (цикл по столбцам внутри цикла по строкам). Для каждой строки мы вычисляем LCS для каждой из ячеек,.просматривая их слева направо. Эти вычисления выполняются для всех строк сверху вниз. Вначале мы проверяем, совпадают ли два символа, на которые ссылается ячейка. (Ячейка матрицы представляет собой переход от символа строки From (Из) к символу строки То (В).) Если они совпадают, длина LCS в этой ячейке равна длине LCS ячейки, расположенной к северо-западу от данной, плюс единица. Обратите внимание, что способ вычисления ячеек предполагает, что ячейка, на которую осуществляется ссылка, уже вычислена (именно поэтому мы заранее вычислили значения ячеек, расположенных вдоль верхней и левой сторон матрицы). Если два символа не совпадают, необходимо просмотреть ячейки, расположенные к северу и к западу от текущей. Мы выбираем ту, которая содержит наиболее длинную LCS, и используем это значение в качестве значения данной ячейки. Если две длины равны, можно выбрать любую из них. Однако мы будем придерживаться правила, что предпочтительнее выбирать LCS, соответствующую ячейке, которая расположена слева. Этот выбор обусловлен тем, что как только путь через матрицу, обеспечивающий определение LCS обеих строк, вычислен, удаления из первой строки выполняются раньше вставок во вторую строку.

Обратите внимание, что приведенный в листинге 12.24 метод требует постоянного времени для обработки двух строк, независимо от степени их совпадения или несовпадения. Если длина строк равна, соответственно, n и т, то время, требуемое для выполнения основного цикла, будет пропорционально произведению n * m, поскольку таковым является количество ячеек, значения которых нужно вычислить. (помните, что ячейка, для которой действительно нужно получить ответ - последняя, значение которой должно вычисляться;

она расположена в нижнем правом углу матрицы).

Алгоритм, реализованный с применением рекурсивного метода, приведен в листинге 12.25. Рекурсивная подпрограмма кодируется в виде функции, которая возвращает длину LCS для конкретной ячейки, заданной индексом строки и столбца (которые, в конечном счете, представляют собой индексы, указывающие на строки From и То).

Листинг 12.25. Рекурсивное вычисление LCS

function TtdStringLCS.slGetCell(aFromInx, aToInx : integer): integer;

var

LCSData : PtdLCSData;

NorthLen: integer;

WestLen : integer;

begin

if (aFromInx = 0) or (aToInx = 0) then

Result := 0

else begin

LCSData := FMatrix[ aFromInx, aToInx];

if (LCSData <> nil) then

Result := LCSData^.ldLen else begin

{создать новый элемент}

New(LCSData);

{если два символа совпадают, необходимо увеличить значение счетчика относительно элемента, расположенного к северо-западу от данного, т.е. предшествующего элемента}

if (FFromStr[aFromInx] = FToStr [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;

Первое существенное различие состоит в том, что не нужно генерировать нулевые значения для ячеек, расположенных вдоль верхней и правой сторон матрицы. Теперь эту задачу выполняет простой оператор If. (Честно говоря, в итеративном варианте вычисления LCS можно было бы обойтись без вычисления этих значений, но в этом случае внутренний код цикла оказался бы значительно сложнее для понимания и поддержки. Поэтому для простоты мы заранее вычисляем значения этих ячеек.) Если значение ячейки уже вычислено, мы просто возвращаем ее длину LCS. Если нет, необходимо выполнить ту же проверку, что и в предыдущем случае: совпадают ли два символа? Если да, то необходимо добавить единицу к значению LCS ячейки, расположенной к северо-западу от данной. Если нет, необходимо использовать большее из значений длины LCS ячеек, расположенных к северу и к западу от текущей. Естественно, эти значения LCS вычисляются в результате рекурсивных вызовов этой подпрограммы.

Применив обе версии (итеративную и рекурсивную), я сгенерировал матрицу для вычисления LCS слов "illiteracy" и "innumeracy". (Длина LCS этих слов равна 6 и выглядит как "ieracy".) Результаты этих немалых трудов приведены в таблицах 12.2 и 12.3. При использовании рекурсивной версии многие ячейки вообще не вычисляются (они помечены знаком вопроса). Эти ячейки образуют часть заключительной LCS.

Таблица 12.2. Итеративная матрица LCS слов "illiteracy" и "innumeracy".

Таблица 12.3. Рекурсивная матрица LCS слов "illiteracy" и "innumeracy".

Итак, мы получили матрицу, которая определяет наиболее длинную общую подпоследовательность. Как ее можно использовать? Одна возможность связана с реализацией подпрограммы, которая создает текстовый файл, описывающий изменения, называемые последовательностью редактирования (edit sequence). Это может упростить создание аналогичной подпрограммы для текстового файла - что, собственно, является конечной целью данного раздела.