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

Что необходимо хранить в каждом из элементов этого матричного кеша? Очевидный ответ - саму строку LCS. Однако, это не слишком целесообразно - да, это упростит вычисление LCS, но не поможет определить, какие символы нужно удалить из строки X, а какие новые символы вставить с целью получения строки Y. Лучше в каждом элементе хранить достаточный объем информации, чтобы можно было генерировать LCS за счет применения алгоритма типа O(1), а также достаточный объем информации для определения команд редактирования, обеспечивающих переход от строки X к строке Y.

Один из информационных элементов, в котором мы действительно нуждаемся, -это длина LCS на каждом этапе. Используя упомянутое значение, с помощью рекурсивного алгоритма можно легко выяснить длину LCS для двух полных строк. Чтобы можно было сгенерировать саму строку LCS, необходимо знать путь, пройденный по матричному кешу. Для этого в каждом элементе потребуется сохранять указатель на предыдущий элемент, который был использован для построения LCS для данного элемента.

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

Давайте вручную вычислим LCS для случая строк BEGIN/FINISH. Мы получим матрицу 6x7 (мы будем учитывать пустые подстроки, поэтому индексация должна начинаться с 0). Вместо того, чтобы рекурсивно заполнять матрицу (все эти рекурсивные вызовы трудно поддерживать в упорядоченном виде), итеративно вычислим все ячейки слева направо и сверху вниз. Вычисление ячеек первой строки и первого столбца не представляет сложности: они все являются нулями. Почему? Да потому, что наиболее длинная общая последовательность пустой и любой другой строки равна нулевой строке. С этого момента можно начать определение LCS для ячейки (1,1) или двух строк B и F. Два последних символа этих односимвольных строк не совпадают. Следовательно, длина LCS равна максимальной из предшествующих ячеек, расположенных к северу и к западу от данной. Обе эти ячейки нулевые, поэтому их максимальное значение и, следовательно, значение этой ячейки равно нулю. Ячейка (1,2) соответствует строкам B и F1. Ее значение также рано нулю. Ячейка (2,1) соответствует строкам BE и F: длина LCS снова равна 0. Продолжая подобные вычисления, можно заполнить все 42 ячейки матрицы. Обратите внимание на ячейки, соответствующие совпадающим символам: именно в них длина LCS возрастает. Конечный результат показан в таблице 12.1.

Таблица 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;