Суффиксный алгоритм массива

/*
Suffix array O(n lg^2 n)
LCP table O(n)
*/
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

#define REP(i, n) for (int i = 0; i < (int)(n); ++i)

namespace SuffixArray
{
const int MAXN = 1 << 21;
char * S;
int N, gap;
int sa[MAXN], pos[MAXN], tmp[MAXN], lcp[MAXN];

bool sufCmp(int i, int j)
{
if (pos[i] != pos[j])
return pos[i] < pos[j];
i += gap;
j += gap;
return (i < N && j < N) ? pos[i] < pos[j] : i > j;
}

void buildSA()
{
N = strlen(S);
REP(i, N) sa[i] = i, pos[i] = S[i];
for (gap = 1;; gap *= 2)
{
sort(sa, sa + N, sufCmp);
REP(i, N - 1) tmp[i + 1] = tmp[i] + sufCmp(sa[i], sa[i + 1]);
REP(i, N) pos[sa[i]] = tmp[i];
if (tmp[N - 1] == N - 1) break;
}
}

void buildLCP()
{
for (int i = 0, k = 0; i < N; ++i) if (pos[i] != N - 1)
{
for (int j = sa[pos[i] + 1]; S[i + k] == S[j + k];)
++k;
lcp[pos[i]] = k;
if (k)--k;
}
}
} // end namespace SuffixArray

Это алгоритм O (n log n) для построения массива суффиксов (или, скорее, он был бы, если бы вместо ::sort использовалась двухпроходная сортировка ковшей).

Работает, сначала отсортировав 2 грамма^(*), затем 4 грамма, затем 8 граммов и т. д. исходной строки SТаким образом, в i-й итерации мы сортируем 2^я-грамм. Там может быть не больше, чем журнал₂(n) такие итерации, и хитрость в том, что сортировка 2^я-грамм на i-м шаге облегчается тем, что каждое сравнение двух^я-грамм делается за O (1) время (а не O (2)^явремя).

Как оно работает? Что ж, в первой итерации он сортирует 2 грамма (он же биграммы), а затем выполняет то, что называется лексикографическое переименование. Это означает, что он создает новый массив (длиной n), который хранит, для каждого биграма, его ранг в биграмной сортировке.

Пример лексикографического переименования: Скажем, у нас есть отсортированный список некоторых биграмм {'ab','ab','ca','cd','cd','ea'}, Затем мы назначаем ряды (то есть лексикографические названия), переходя слева направо, начиная с ранга 0 и увеличивая ранг всякий раз, когда мы сталкиваемся с новый биграмм меняется. Итак, мы присваиваем ранги следующим образом:

ab : 0
ab : 0   [no change to previous]
ca : 1   [increment because different from previous]
cd : 2   [increment because different from previous]
cd : 2   [no change to previous]
ea : 3   [increment because different from previous]

Эти ранги известны как лексикографические названия.

Сейчас, в следующей итерации, мы сортируем 4 грамма. Это включает в себя много сравнений между различными 4 граммами. Как мы сравним два 4 грамма? Ну, мы могли бы сравнить их символ за символом. Это будет до 4 операций на сравнение. Но вместо этого мы сравниваем их глядя вверх ранги двух биграмм, содержащихся в них, с использованием таблицы рангов, сгенерированной на предыдущих шагах. Этот ранг представляет собой лексикографический ранг из предыдущей 2-граммовой сортировки, поэтому, если для любого данного 4-грамма его первые 2-граммы имеют более высокий ранг, чем первые 2-граммы другого 4-грамма, то он должен быть лексикографически большим где-то в первых двух символах. Следовательно, если для двух 4-граммов ранг первых 2-граммов идентичен, они должны быть идентичны в первые два символа. Другими словами, два поиска в таблице рангов достаточно сравнить все 4 символа из двух 4-граммовых.

После сортировки мы снова создаем новые лексикографические названия, на этот раз для 4 граммов.

На третьей итерации нам нужно отсортировать по 8 граммов. Опять же, двух просмотров в таблице лексикографических рангов из предыдущего шага достаточно, чтобы сравнить все 8 символов двух данных 8 граммов.

И так далее. Каждая итерация i имеет два шага:

1. Сортировка по 2^я-граммы с использованием лексикографических названий из предыдущей итерации для сравнения в 2 этапа (т. е. по времени (1)) каждый

2. Создание новых лексикографических названий

Повторяем пока все 2^я-граммы разные. Если это произойдет, мы сделали. Как мы узнаем, что все они разные? Ну, лексикографические имена представляют собой возрастающую последовательность целых чисел, начиная с 0. Так что, если наибольшее лексикографическое имя, генерируемое в итерации, совпадает с n-1затем каждый 2^я-грамм должен был иметь свое собственное, отличное лексикографическое название.

---

Теперь давайте посмотрим на код, чтобы подтвердить все это. Используются следующие переменные: sa[] это суффиксный массив, который мы создаем. pos[] таблица соответствия рангов (т.е. она содержит лексикографические названия), в частности, pos[k] содержит лексикографическое название kм-м предыдущего шага tmp[] вспомогательный массив, используемый для создания pos[],

Я дам дальнейшие объяснения между строками кода:

void buildSA()
{
N = strlen(S);

/* This is a loop that initializes sa[] and pos[].
For sa[] we assume the order the suffixes have
in the given string. For pos[] we set the lexicographic
rank of each 1-gram using the characters themselves.
That makes sense, right? */
REP(i, N) sa[i] = i, pos[i] = S[i];

/* Gap is the length of the m-gram in each step, divided by 2.
We start with 2-grams, so gap is 1 initially. It then increases
to 2, 4, 8 and so on. */
for (gap = 1;; gap *= 2)
{
/* We sort by (gap*2)-grams: */
sort(sa, sa + N, sufCmp);

/* We compute the lexicographic rank of each m-gram
that we have sorted above. Notice how the rank is computed
by comparing each n-gram at position i with its
neighbor at i+1. If they are identical, the comparison
yields 0, so the rank does not increase. Otherwise the
comparison yields 1, so the rank increases by 1. */
REP(i, N - 1) tmp[i + 1] = tmp[i] + sufCmp(sa[i], sa[i + 1]);

/* tmp contains the rank by position. Now we map this
into pos, so that in the next step we can look it
up per m-gram, rather than by position. */
REP(i, N) pos[sa[i]] = tmp[i];

/* If the largest lexicographic name generated is
n-1, we are finished, because this means all
m-grams must have been different. */
if (tmp[N - 1] == N - 1) break;
}
}

О функции сравнения

Функция sufCmp используется для сравнения двух (2 * пробел) -грамм лексикографически. Таким образом, в первой итерации сравниваются биграммы, во второй итерации 4 грамма, затем 8 граммов и так далее. Это контролируется gap, которая является глобальной переменной.

Наивная реализация sufCmp будет это:

bool sufCmp(int i, int j)
{
int pos_i = sa[i];
int pos_j = sa[j];

int end_i = pos_i + 2*gap;
int end_j = pos_j + 2*gap;
if (end_i > N)
end_i = N;
if (end_j > N)
end_j = N;

while (i < end_i && j < end_j)
{
if (S[pos_i] != S[pos_j])
return S[pos_i] < S[pos_j];
pos_i += 1;
pos_j += 1;
}
return (pos_i < N && pos_j < N) ? S[pos_i] < S[pos_j] : pos_i > pos_j;
}

Это позволит сравнить (2 * пробел) -граммы в начале i-го суффикса pos_i:=sa[i] с найденным в начале j-го суффикса pos_j:=sa[j], И он будет сравнивать их символ за символом, то есть сравнивать S[pos_i] с S[pos_j], затем S[pos_i+1] с S[pos_j+1] и так далее. Это продолжается, пока символы идентичны. Как только они различаются, возвращается 1, если символ в i-м суффиксе меньше, чем символ в j-м суффиксе, 0 в противном случае. (Обратите внимание, что return a<b в функции, возвращающей int означает, что вы возвращаете 1, если условие истинно, и 0, если оно ложно.)

Сложно выглядящее условие в операторе возврата касается случая, когда одна из (2 * пробела) -грамм находится в конце строки. В этом случае либо pos_i или же pos_j достигнет N перед сравнением всех (2 * пробела) символов, даже если все символы до этой точки идентичны. Затем он вернет 1, если i-й суффикс находится в конце, и 0, если j-й суффикс находится в конце. Это правильно, потому что если все символы идентичны, короче один лексикографически меньше. Если pos_i достигнут конец, i-й суффикс должен быть короче, чем j-й суффикс.

Ясно, что эта наивная реализация является O (разрывом), то есть ее сложность линейна по длине (2 * разрыв) -грамм. Однако функция, используемая в вашем коде, использует лексикографические имена, чтобы свести это значение к O (1) (в частности, максимально к двум сравнениям):

bool sufCmp(int i, int j)
{
if (pos[i] != pos[j])
return pos[i] < pos[j];
i += gap;
j += gap;
return (i < N && j < N) ? pos[i] < pos[j] : i > j;
}

Как видите, вместо поиска отдельных персонажей S[i] а также S[j], мы проверяем лексикографический ранг i-го и j-го суффикса. Лексикографические ранги были вычислены в предыдущей итерации для гэмп-грамм. Так что если pos[i] < pos[j]тогда i-й суффикс sa[i] должен начинаться с граммы разрыва, которая лексикографически меньше, чем грамма разрыва в начале sa[j], Другими словами, просто глядя вверх pos[i] а также pos[j] и сравнивая их, мы сравнили первое разрыв символы двух суффиксов.

Если ранги идентичны, мы продолжаем сравнивать pos[i+gap] с pos[j+gap], Это то же самое, что сравнение следующего разрыв символы (2 * пробел) -грамм, т.е. Вторая половина. Если ранги снова идентичны, две (2 * пробела) -граммы идентичны, поэтому мы возвращаем 0. В противном случае мы возвращаем 1, если i-й суффикс меньше, чем j-й суффикс, 0 в противном случае.

---

В следующем примере показано, как работает алгоритм, и, в частности, показана роль лексикографических имен в алгоритме сортировки.

Строка, которую мы хотим отсортировать abcxabcd, Требуется три итерации, чтобы сгенерировать массив суффиксов для этого. В каждой итерации я покажу S (строка), sa (текущее состояние массива суффиксов) и tmp а также pos, которые представляют собой лексикографические названия.

Сначала мы инициализируем:

S   abcxabcd
sa  01234567
pos abcxabcd

Обратите внимание, что лексикографические названия, которые первоначально представляют лексикографический ранг униграмм, просто идентичны самим символам (то есть униграммам).

Первая итерация:

Сортировка sa, используя биграммы в качестве критерия сортировки:

sa  04156273

Первые два суффикса — 0 и 4, потому что это позиции биграма ‘ab’. Затем 1 и 5 (позиции биграма «bc»), затем 6 (биграмма «cd»), затем 2 (биграмма «cx»). затем 7 (неполная биграмма «d»), затем 3 (биграмма «xa»). Очевидно, что позиции соответствуют порядку, основанному исключительно на биграммах персонажей.

Генерация лексикографических названий:

tmp 00112345

Как описано, лексикографические имена присваиваются в виде целых чисел. Первые два суффикса (оба начинаются с биграма ‘ab’) получают 0, следующие два (оба начинаются с биграма ‘bc’) получают 1, затем 2, 3, 4, 5 (каждый другой биграмма).

Наконец, мы отображаем это в соответствии с позициями в sa, получить pos:

sa  04156273
tmp 00112345
pos 01350124

(Путь pos генерируется это: пройти через sa слева направо и используйте запись для определения индекса в pos, Используйте соответствующую запись в tmp определить значение для этого индекса. Так pos[0]:=0, pos[4]:=0, pos[1]:=1, pos[5]:=1, pos[6]:=2, и так далее. Индекс прибывает из sa, значение от tmp.)

Вторая итерация:

Мы сортируем sa снова и снова мы смотрим на биграммы из pos (каждый из которых представляет собой последовательность два биграммы оригинальной струны).

sa  04516273

Обратите внимание, как изменилось положение 1 5 по сравнению с предыдущей версией sa, Раньше было 15, теперь это 51. Это потому, что биграмм в pos[1] и биграмма в pos[5] Раньше были идентичны (оба bc) во время предыдущей итерации, но теперь биграмма в pos[5] является 12в то время как биграмм в pos[1] является 13, Итак, положение 5 выходит до позиция 1, Это связано с тем, что каждое из лексикографических названий теперь представляет биграммы исходной строки: pos[5] представляет собой bc а также pos[6] представляет «CD». Итак, вместе они представляют bcd, в то время как pos[1] представляет собой bc а также pos[2] представляет собой cxтак вместе они представляют bcxчто на самом деле лексикографически больше, чем bcd,

Опять же, мы генерируем лексикографические названия, просматривая текущую версию sa слева направо и сравнивая соответствующие биграммы в pos:

tmp 00123456

Первые две записи все еще идентичны (оба 0), потому что соответствующие биграммы в pos оба 01, Остальное — строго возрастающая последовательность целых чисел, потому что все остальные биграммы в pos каждый уникален.

Мы выполняем сопоставление с новым pos как и прежде (принимая индексы из sa и значения из tmp):

sa  04516273
tmp 00123456
pos 02460135

Третья итерация:

Мы сортируем sa опять же, принимая биграммы pos (как всегда), каждый из которых теперь представляет собой последовательность из 4 биграмм оригинальной строки.

sa  40516273

Вы заметите, что теперь первые две записи поменялись местами: 04 стал 40, Это потому, что биграмм в pos[0] является 02 в то время как один в pos[4] является 01последний явно лексикографически меньше. Глубокая причина в том, что эти два представляют abcx а также abcdсоответственно.

Генерация лексикографических названий дает:

tmp 01234567

Все они разные, то есть самый высокий 7, который n-1, Итак, мы закончили, потому что сортировка теперь основана на м-граммах, которые все разные. Даже если мы продолжим, порядок сортировки не изменится.

---

Алгоритм, используемый для сортировки 2^я-граммы в каждой итерации, кажется, является встроенным sort (или же std::sort). Это означает, что это сортировка сравнения, которая в худшем случае занимает O (n log n), в каждой итерации. Поскольку в худшем случае есть log n итераций, это делает его O (n (log n)²) алгоритм времени Однако сортировка может быть выполнена с использованием двух проходов сортировки сегментов, поскольку ключи, которые мы используем для сравнения сортировки (то есть лексикографические имена предыдущего шага), образуют возрастающую целочисленную последовательность. Так что это может быть улучшено до фактического алгоритма O (n log n) времени для сортировки суффиксов.

---

Я полагаю, что это оригинальный алгоритм построения массива суффиксов, который был предложен в статье 1992 года Manber and Myers (ссылка на Google Scholar; это должно быть первое попадание, и там может быть ссылка на PDF). Это (в то же время, но независимо от статьи Гонне и Баеза-Йейтса) было то, что ввело суффиксные массивы (также известные как паттерны в то время) в качестве структуры данных, интересной для дальнейшего изучения.

Современные алгоритмы построения массива суффиксов — это O (n), поэтому вышеприведенный алгоритм больше не является лучшим доступным алгоритмом (по крайней мере, не с точки зрения теоретической сложности наихудшего случая).

---

Сноски

^(*) От 2-граммовый Я имею в виду последовательность из двух последовательный символы исходной строки. Например, когда S=abcde это строка, то ab, bc, cd, de 2 грамма S, Так же, abcd а также bcde 4 грамма Как правило, m-грамм (для положительного целого числа m) представляет собой последовательность m последовательные персонажи. 1-граммы также называют униграммами, 2-граммы — биграммами, 3-граммы — триграммами. Некоторые люди продолжают тетраграммы, пентаграммы и так далее.

Обратите внимание, что суффикс S что начинается и положение iэто (n-i) -грамма S, Кроме того, каждая m-грамм (для любого m) является префиксом одного из суффиксов S, Поэтому сортировка m-грамм (для m как можно большего размера) может быть первым шагом к сортировке суффиксов.