Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi
Рисунок 12.1. LCS для слов "banana" и "abracadabra"
Итак, тем или иным способом мы определили LCS двух слов. Предположим, что длина этой подпоследовательности равна х. Взгляните на последние буквы обоих слов. Если ни одна из них не является частью соединительной линии, и при этом они являются одной и той же буквой, то эта буква должна быть последней буквой LCS и между ними должна была бы существовать соединительная линия. (Если эта буква не является последней буквой подпоследовательности, ее можно было бы добавить, удлинив LCS на одну букву, что противоречило бы сделанному предположению о том, что первая подпоследовательность является самой длинной.) Удалим эту последнюю букву из обоих слов и из подпоследовательности.
Полученная сокращенная подпоследовательность длиной x - 1 представляет собой LCS двух сокращенных слов. (Если бы это было не так, для двух сокращенных слов должна была бы существовать общая подпоследовательность длиной X или больше. Добавление заключительных букв привело бы к увеличению длины новой общей подпоследовательности на единицу, а, значит, для двух полных слов должна была бы существовать общая подпоследовательность, содержащая x+1 или более букв. Это противоречит предположению о том, что мы определили LCS.)
Теперь предположим, что последняя буква в LCS не совпадает с последней буквой первого слова. Это означало бы, что LCS двух полных слов была бы также LCS первого слова без последней буквы и второго слова (если бы это было не так, можно было бы снова добавить последнюю букву к первому слову и найти более длинную LCS двух слов). Эти же рассуждения применимы и к случаю, когда последняя буква второго слова не совпадает с последней буквой LCS.
Все это замечательно, но о чем же оно свидетельствует? LCS содержит в себе LCS усеченных частей обоих слов. Для отыскания LCS строк X и Y мы разбиваем задачу на более мелкие задачи. Если бы последние символы слов X и Y совпадали, нам пришлось бы найти LCS для строк X и Y без их последних букв, а затем добавить эту общую букву. Если нет, нужно было бы найти LCS для строки X без последней буквы и строки Y, а также LCS строки X и строки Y без ее последней буквы, а затем выбрать более длинную из них. Мы получаем простой рекурсивный алгоритм.
Однако во избежание проблемы, которая может быть порождена простым решением, вначале необходимо описать алгоритм несколько подробней.
Мы пытаемся вычислить LCS двух строк X и Y. Вначале мы определяем, что строка X содержит n символов, а строка Y - m. Обозначим строку, образованную первыми i символами строки X, как Х(_i_). i может принимать также нулевое значение, что означает пустую стоку (это соглашение упростит понимание алгоритма). В таком случае Х(_n_) соответствует всей строке. С применением этой формы записи алгоритм сводится к следующему; если последние два символа строк Х(_n_) и Y(_m_) совпадают, самая длинная общая последовательность равна LCS Х(_n-1_) и Y(_m-1_) с добавлением этого последнего символа. Если они не совпадают, LCS равна более длинной из LCS строк Х(_n-2_) и Y(_m_) и LCS строк Х(_n_) и Y(_m-1_). Для вычисления этих "меньших" LCS мы рекурсивно вызываем одну и ту же подпрограмму.
Тем не менее, обратите внимание, что для вычисления LCS строк Х(_n-1_) и Y(_m_) может потребоваться вычислить LCS строк Х(_n-2_) и Y(_m-1_), LCS строк Х(_n-1_) и Y(_m-1_) и LCS строк Х(_n-2_) и Y(_m_). Вторую из этих подпоследовательностей можно уже вычислить. При недостаточной внимательности можно было бы вычислять одни и те же LCS снова и снова. В идеале во избежание этих повторных вычислений нужно было бы кешировать ранее вычисленные результаты. Поскольку мы располагаем двумя индексами для строк X и Y, имеет смысл воспользоваться матрицей.
Что необходимо хранить в каждом из элементов этого матричного кеша? Очевидный ответ - саму строку 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;
{уничтожить производный объект}
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(
