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

Таблица 12.1. Матрица LCS для строк BEGIN и FINISH

_ _ F I N I S H

_ 0 0 0 0 0 0 0

B 0 0 0 0 0 0 0

E 0 0 0 0 0 0 0

G 0 0 0 0 0 0 0

I 0 0 1 1 1 1 1

N 0 0 1 2 2 2 2

Записать этот процесс выполнения действий вручную в виде кода не особенно трудно. Чтобы облегчить задачу начинающим программистам, я решил вначале создать класс матричного кеша. Внутри этого класса матрица хранится в объекте TList из TLists, причем ведущий объект TList представляет строки в матрице, а ведомый TLists - ячейки в столбцах отдельной строки. Кроме того, класс матрицы специфичен для решаемой задачи. Было бы излишним разрабатывать, кодировать и использовать общий класс матрицы. Код реализации класса матрицы показан в листинге 12.22.

Листинг 12.22. Класс матрицы для реализации алгоритма определения LCS

type

TtdLCSDir = (ldNorth, ldNorthWest, ldWest);

PtdLCSData = ^TtdLCSData;

TtdLCSData = packed record

ldLen : integer;

ldPrev : TtdLCSDir;

end;

type

TtdLCSMatrix = class private

FCols : integer;

FMatrix : TList;

FRows : integer;

protected

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

procedure mxSetItem(aRow, aCol : integer;

aValue : PtdLCSData);

public

constructor Create(aRowCount, aColCount : integer);

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