Алгоритм Ханта – Зиманского

С. Г. Кипров
Алгоритм Ханта – Зиманского
Метод выделения наибольшей общей последовательность LCS (longest common sequence,) для двух входных строк X и Y Ханта – Зиманского зависит от количества совпадений символов (элементов) и длины общей последовательности, а время затраченное на работу данного алго-ритма вычисляется O(C*LogN), где C – количество общих символов, N – длина одной из двух сравниваемых последовательностей.
Входные данные: Даны две строки X и Y, длин N и M.
Суть алгоритма: Сканируется одна из строк строка (лучше меньшей длины, для того, чтобы время LogN было меньше). Если символ (элемент) находиться в другой строке, то запо-минаем его индекс и позицию, которую он займет в максимальной общей последовательности. Затем из полученного набора выбираем максимальную общую последовательность. Ниже пред-ставлен набросок алгоритма.

// инициализация
kk0 = 0
for s = 1 to n
kks = n + 1
// вычисление |LCS(X, Y)|
for i = 1 to n
for j = n downto 1
if xi = yi
//найти s, для которого kks-1 < j < kks
kks = j
print max s такое, что kks =/=n + 1 (?????)

Теперь все более подробно:

Инициализация №1
Если последовательно будет производиться сравнение одной последовательности с не-сколькими, то имеет смысл произвести инициализацию №1 только один раз, а затем использо-вать полученный результат.
Для ответа на вопрос, о нахождении одного символа (элемента) последовательности в другой, можно использовать линейный поиск символа (подстроки) в последовательности (алго-ритмы Бойра-Мура, Рабина, Кнута-Морриса-Пратта в этом случае будут менее эффективны [1]), но это займет достаточно большое количество времени. Поэтому лучше ввести некоторую новую переменную множественного типа (set of Char) или массив бинарных элементов (array [Char] of Boolean).
Инициализация осуществляется проходом по строке и внесением текущего символа (эле-мента) в набор существующих (????)

Var
MaskSet1 : Set of Char;
MaskSet2 : array [Char] of Integer;

procedure SetInitialization;
begin
for i := 1 to Length(Mask) do begin
// внесение элемента во множество просмотренных
MaskSet := MaskSet1 + [Mask[i]];
MaskSet2[Mask[i]] := True;
end;
end;

Mask – одна из последовательностей
MaskSet1, MaskSet2 – две переменные отвечающие за нахождение символа в Mask
Далее данная процедура будет немного изменена, для хранения индекса символа Mask. Таким образом, при введении данной процедуры, сокращается время, потраченное на поиск символа в последовательности, в N раз (для худшего случая).

На Рис.1 представлен массив Boolean элементов, и результат после его заполнения.

Инициализация №2 (Массив указателей)
Для нахождения общей подпоследовательности символов максимальной длины (LCS), сначала необходимо найти все общие символы в последовательностях. Для этого просканиро-вать вторую последовательность и, при нахождении символа принадлежащего первой, записы-ваем его в массив указателей [2].
Необходимо отметить, что в данной инициализации все элементы записаны в обратном порядке. Это необходимо для того, чтобы найти все вхождения одинаковых символов и запи-сать их позиции в обратном порядке. Для того, чтобы не внести один элемент из одной после-довательности, встречающийся в другой дважды, в максимальную общую последовательность. Таким образом, при использовании других структур данных, необходимо записывать их в об-ратном поступлению элементов порядке, или идти с кона в начало в описанной ниже процеду-ре.
Ниже приведена процедура записи в массив

type
PElement = ^TElement;
TElement = packed record
SymbolIndex : Integer;
Next : PElement;
end;

TMaskSet = array [Char] of Integer;

var
PLetterArray : array [Char] of PElement;
MaskSet : TMaskSet;

procedure InitSymbolsIndexes;
var
i : Integer;
Index : Integer;
begin
FillChar(PLetterArray, SizeOf(PLetterArray), 0);
for i := 1 to Length(Buf) do begin
// берем общий элемент, получаем его индекс
Index := MaskSet[Buf[i]];
if Index > 0 then begin
// добавление элемента в стек
AddElement(PLetterArray[Buf[i]], i);
end;
end;
end;

Таким образом в PLetterArray хранятся индексы общих символов для сравниваемых по-следовательностей. Объем требуемый для PLetterArray зависит только от количества общих символов. Поэтому если не имеется ни одного общего символа все указатели будут равняться nil, следовательно PLetterArray будет занимать объем памяти только для собственного хране-ния.

Сборка общей подпоследовательности
Для сборки общей подпоследовательности символов будет использоваться ранее сформи-рованный PLetterArray. Проходя по элементам PLetterArray, выбираем не нулевые указатели, которые дают нам позицию символа (SymbolIndex). Далее мы будем ставить его на свое место в общей подпоследовательности (на самом деле мы только поставим его в очередь на вхождение в общую подпоследовательность). Поиск индекса символа в массиве можно осуществлять как прямым, так и бинарным поиском. Для хранения информации о найденном элементе опять ис-пользуем указатели [2].
После данной процедуры мы будем иметь связный список (нечто наподобие массива), в котором будут храниться индексы символа в исходных последовательностях и общей подпос-ледовательности.
Ниже приведены процедуры и структуры данных реализующие вышесказанное.

type
PByteArray = ^TByteArray;
TByteArray = array [0..MaxInt div 16] of Integer

PCoinsiding = ^TCoinsiding;
TCoinsiding = record
Step : Integer;
CodeLetter : Integer;
CodeLetterMask : Integer;
Next : PCoinsiding;
end;

var
CommonPath : PByteArray;
PLetterArray : array [Char] of PElement;
Temp : PElement;
Coinsidings : PCoinsiding;
// максимальная длина подпоследовательности
MaxLengthLCS : Integer;

// бинарный поиск элемента в массиве
procedure FindPosition(x, y, j : Integer; var s : Integer);
begin
while y > x do begin
if CommonPath^[(x + y) div 2] >= j then y := (x + y) div 2
else x := ((x + y) div 2) + 1;
end;
s := x;
end;

procedure Solve;
var
i, j, s : Integer;
begin
MaxLengthLCS := 1;
// проход по последовательности
for i := 1 to Length(Mask) do begin
Temp := PLetterArray[Mask[i]];
while Temp <> nil do begin
j := Temp^.SymbolIndex;
s := Length(Buf);
FindPosition(0, MaxLengthLCS, j, s);
if (j < CommonPath[s]) then begin
CommonPath[s] := j;
MaxLengthLCS := Max (MaxLengthLCS, S + 1);
// добавление элемента в стек AddConsiding(Coinsidings, i, j, s);
end;
Temp := Temp^.Next;
end;
end;
end;

На Рис.3 представлен связный список для двух последовательностей «zeitgeost» и «preterit», сформированный по вышеописанной процедуре



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

function GetSubSequence (MaxCommon: Integer): String;
var
SubString : String;

Begin
// инициализируем общую строку
SubString := ‘’;
// ищем в связном списке правый символ из LCS
while Coinsidings ^.Step <> MaxCommon do
Coinsidings := Coinsidings^.Next;
// продолжаем поиск элемента с текущим индексом LCS, пока не
// соберем всю LCS и не кончится связный список
while (MaxCommon > 0) and (Coinsidings <> nil) do begin
if Coinsidings^.Step = MaxCommon then begin
// если нашли символ с текущим индексом, то добавляем его в строку и
// уменьшаем текущий индекс
SubString := Mask[Coinsidings^. CodeLetterMask]
Dec(MaxCommon);
end;
Coinsidings := Coinsidings^.Next;
end;
Result := SubString;
end;

Описанная выше процедура GetSubSequence использует связный список и выдает общую последовательность символов Рис.4



Ниже приведен пример вычисления LCS(preterit, zeitgeist), для описанному выше алго-ритму, который выдает следующий список пар (i, j) для LCS (в обратном порядке):
(8, 9), (7, 7), (5, 6), (4, 4), (3, 2).
Это проиллюстрировано ниже, узлы указывают точки (i, j), такие что Xi = Yj. LCS форми-руется символами в соответствии с заполненными узлами, а именно eteit.
j 1 2 3 4 5 6 7 8 9
i z e i t g e i s t
1 p
2 r
3 e


4 t


5 e


6 r
7 i


8 t


Заключение
Проведем анализ алгоритма.
 объем: при своевременном освобождении указателей, объем памяти не превысит объем па-мяти необходимый для хранения всех общих символов, в противном случае понадобиться до трех подобных объемов.
 время: алгоритм приведенный ниже достаточно хорошо оптимизирован и требует время равное O(CLogN + Nk), где С – количество общих символов, N – длина одной из последова-тельности, k – некий постоянный коэффициент. Коэффициент k может быть еще немного уменьшен. Алгоритм Ханта – Зиманского быстро работает на последовательностях с широ-ким алфавитом, и на последовательностях с небольшим количеством одинаковых символов
 алгоритм Ханта – Зиманского может быть применен при неточном поиске файлов, текста, поиске ошибок, но в случае когда алфавит узок время работы алгоритма может превысить квадрат (например, на последовательностях X =’aaaaaaaa’ и Y =’ aaaaaaaa’ время работы бу-дет O(N2*LogN)).
Заметки
 заметим, что все процедуры были даны без освобождения указателей
 вышеописанные процедуры находят только одну LCS, но данный алгоритм легко изменить так, чтобы он находил все LCS (для этого необходимо изменить структуру PCoinsiding до дерева указателей, лист дерева должен обладать списком указателей на низлежащий уро-вень)
Список литературы:
1. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.:МЦНМО, 1999.
2. Окулов С.М. Основы программирования. – М: ЮНИМЕДИФСТАЙЛ, 2002.