destructor Destroy; override;
procedure Clear;
property Items [aRow, aCol : integer] : PtdLCSData
read mxGetItem write mxSetItem;
default;
property RowCount : integer read FRows;
property ColCount : integer read FCols;
end;
constructor TtdLCSMatrix.Create(aRowCount, aColCount : integer);
var
Row : integer;
ColList : TList;
begin
{создать производный объект}
inherited Create;
{выполнить простую проверку}
Assert ((aRowCount > 0) and (aColCount > 0),
' TtdLCSMatrix.Create: Invalid Row or column count');
FRows := aRowCount;
FCols := aColCount;
{создать матрицу: она будет матрицей TList матриц TLists, упорядоченных по строкам}
FMatrix := TList.Create;
FMatrix.Count := aRowCount;
for Row := 0 to pred(aRowCount) do
begin
ColList := TList.Create;
ColList.Count := aColCount;
TList(FMatrix.List^[Row]) := ColList;
end;
end;
destructor TtdLCSMatrix.Destroy;
var
Row : integer;
begin
{уничтожить матрицу}
if (matrix <> nil) then begin
Clear;
for Row := 0 to pred(FRows) do
TList(FMatrix.List^[Row]).Free;
FMatrix.Free;
end;
{уничтожить производный объект}
inherited Destroy;
end;
procedure TtdLCSMatrix.Clear;
var
Row, Col : integer;
ColList : TList;
begin
for Row := 0 to pred(FRows) do
begin
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 обеих строк, вычислен, удаления из первой строки выполняются раньше вставок во вторую строку.