Алгоритм Карккайнена-Сандерса

Суффиксный массив, за линейное время

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

Используется тоже самое сжатие и слияние, с той разницей что алфавит разбивается не на два, а на три символа. Две части отправляются на рекурсивное построение, одна используется для слияния.

Про это много написано, и написано про алгорим Фарача, поэтому сразу начну с примера.

mississippi

(I) перекодировка в новый алфавит

Мы используем алфавит по три символа. Если три способа порезать, наш образец по три символа, в зависимости от начального смещения:

0: mississippi.

1:  ississippi..

2:   ssissippi

мы используем нарезки, с позиций 1 и 2. Если пронумеровать тройки символов, получится следующее:

[0] iss
[1] ipp
[2] ssi
[3] pi.
[4] ppi

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

(II) проблемы преобразования

Отвлечемся на секунду и представим, что мы сроку взяли строку misisippi. составили дерево из пар (misisippi.), а не из троек - взяли строку из нового алфавита: 12230, и составили из неё суффиксный массив:
[4] 0 [0] 12230 [1] 2230 [2] 230 [3] 30
Чтобы вернуть строку в исходный алфавит, достаточно, не вникая в алфавит, умножить все позиции массива на два, и немного подправить начальные позиции:
[8] i. [0] misisippi. [2] sisippi. [4] sippi. [6] ppi.

(II)

С нашими тройками, придётся использовать более сложный подход. Мы не можем использовать для работы 2/3 массива. Так же, не можем поставить символы нового алфавита в ряд, покрытие исходной строки будем не равномерным, и сортировать его бесполезно, порядок строк не будет соотвествовать порядку в исходном алфавите. Мы просто не сможем восстановить порядок исходных строк.

Тут мы используем достаточно не очевидный подход - просто делаем конкатенацию строк для 2 и 3 позиции:

1: iss iss ipp → 001
2: ssi ssi pp. → 223

Из новой строки 001223 делаем суффиксный массив:

После этого нам надо вернуться с исходному алфавиту. Тут все упирается в простое математическое преобразование. Надо умножить всё смещения на три, учитывая то что вторая часть новой строки, отображается в тройки с позиции 2 (тут, не самый удобный пример):

[1] iss iss ipp
[4] iss ipp
[7] ipp
[2] ssi ssi pp.
[5] ssi pp.
[8] pp.

(III) массив для нулевых позиций

Теперь, надо составить суффиксный массив, для троек с позиции ноль. Здесь аналогично алгоритму Фарача. Берём строки для смещения 1, и сдвигаем для на один символ назад. Выполняем стабильную сортировку по первому символу.

[0] m iss iss ipp
[3] s iss ipp
[9] s ipp

(IV) слияние

Теперь на надо слить, массив для позиций 1,2 и для позиции 0, чтобы получить полный массив. В нашем примере мы сливаем для массива:

[offset mod 3 = 1,2]
[1] ississipp
[4] issipp
[7] ipp
[2] ssissipp
[5] ssipp
[8] pp

[offset mod 3 = 0]
[0] mississipp
[3] sissipp
[6] sipp
[9] p

Поскольку наши массивы частично перекрыты, слияние становится очень простым, не надо строить дерево и мержить дуги.

Мы знаем относительный порядок строк в массиве 1,2 и можем использовать его, как основной источник информации.

Если у нас есть две строки:

[1] ississipp
[4] issipp

есть два варианта:

первые символы не совпадают, тогда порядок строк очевиден.
первые символы одинаковые, тогда порядок строк [1] ississipp ↔ [4] issipp
будет таким же как относительный порядок строк [2] ssissipp ↔ [5] ssipp а порядок этих строк, можно поглядеть в массиве 1,2

И, ещё одно небольшой усложение, для каждых строк, в позиции 1, есть следующие за ними строки в позиции 2. Для строк в позиции 2, следом идущих строк нет, поэтому, для них нам приходится сравнивать два начальных символа, и смотреть строки идущие следом, через один символ (rank[i1+2]<rank[i2+2]).

Реализация

Есть исходник автора, я пробовал написать сам, но как его не упрощай, проще сделать нельзя. Можно только постараться и сделать, тоже самое, только ещё уродливее.

suff-arr.cpp

По пунктам:

(I) - Compress - создаём индекс для позиций 1,2. Сортируем сравнивая стройки в этих позициях. Как известно поразрядную сортировку можно, делать от старших разрядов к младшим не получая ничего хорошего. Можно от младших к старшим, получая стабильную и линейную по времени сортировку. После сравниваем идущие по алфавиту тройки и нумеруем.
(II) - Decompress - Сделав массив, для новой строки, возвращаемся в исходный алфавит.
(III) - MakeEvenArr - Берем суффиксы из позиций 1, и после сортировки получаем массив для позиций 0.
(IV) - Merge -Сливаем массивы

Техническая ерунда, которую не забыл показать:

Приходится добавлять три нуля в конец некоторых массивов, чтобы не усложнять сравнение троек
Приходится добавлять позицию за концом строки в массив 12, чтобы не пропустить последний символ в строкe 0.
Во время слияния приходится откидывать символы за концом строки, но это можно делать в другом месте.

Скорость

Ускорять током нечего.

В какой-то момент все символы алфавита, становятся уникальными, и массив можно получить простой сортировкой.
Где-то 20% процентов времени, отнимает сортировка, поэтому основное внимание надо уделять сортировкам.
Можно повторно использовать часть массивов, не выделяя их отдельно. Где-то это экономит память. Где-то даст неощутимый прирост скорости, за счёт экономии памяти.
Можно избавиться от деления на 3, умножения на 2/3, отстатка от деления на 3, но с этим отлично справляется любой компилятор.

Когда я думал про сортировку, то заметил два момента, про которые не подумал в алгоритме фарача.

Не надо создавать монотонный индекс, для сортировки массива уникальных символов. Достаточно просто инвертировать индексы (InvertArray), без сортировки.
Не надо использовать std::vector, потому что он лишний раз инициализирует значения, когда его про это не просят.

Поэтому, я сделал, версию без stl, и чуть поправил арифметику. Больше там ничего не придумаешь, по крайней мере за вечер:

suff-arr-arr.cpp

Как это вообще работает

Всё что нам нужно, всегда иметь возможность поглядеть относительный порядок строк в одном из массивов:

Разбиение 1,2 / 0 (mod 3)

Имеем два массива

offset mod 3 = 1,2
offset mod 3 = 0

Сравнивая строки с любым смещением, мы всегда сможем использовать первый массив, т.е. свести это к сравнению строк в позиции 1,2. просто сравнием первые символы и увеличиваем индекс:

0,1 +1 → 1,2 - пример: сливаем [4]issipp ↔ [6]sipp, узнаём порядок из строк в первом массиве [5]ssipp ↔ [7]ipp
0,2 +2 → 2,1 - пример: сливаем [2]ssissipp ↔ [3]sissipp, узнаём порядок из строк в первом массиве [4]issipp ↔ [5]ssipp
1,2 → 1,2 - эти строки сравнивать не приходится

Разбиение 1 / 0 (mod 2)

Разбиение на две равные части, как в алгоритме Фарача. У нас нет массива, в котором можно посмотреть односительный порядок строк. Так же, если строки попали в два разных массива, можно сколько угодно увеличивать их индекс, они всё равно остануться в разных массивах.

Разбиение 2,3 / 0,1 (mod 4)

Мы разбиваем массив на четвёрки символов. Из строк offset = 2,3 (mod 4) строим первый суффиксный массив. Далее уменьшаем позиции строк на два символа и сортируем по первым двум символам, чтобы получить второй массив. Получаем два массива

offset mod 4 = 2,3
offset mod 4 = 0,1

Для таких массивов, тоже нельзя выполнить корректное слияние. Мы можем использовать информацию в порядке строк, в первом или втором массиве. Но, если нам попадуться строки со смещениями 0 и 2, они будут в разным массивах, и сколько их не увеличивай, они останутся в разных массивах.

Вся суть в том, что имея две строки со смещением i,j mod n , мы всегда могли бы свести из к одному из массивов. Для простоты надо оценивать не сами индексы, а расстояния между ними, поскольку индексы i,j всегда можно свести к индексам 0,(j-i).

Пример разбиение 3,4,5,6 / 0,1,2 (mod 7)

Любые два индекса мы можем сместить так, чтобы они попали в первый массив. Нам надо взять строки, со смешениями 3,4,5,6 (mod 7) отсортировать семерки символов и построить из них суффиксный массив, уменьшить индексы на 3, отсортировать по трём символам, чтобы получить второй массив. Скорость алгоритма будет описываться уравнением T(n) = T(4/7 n) + O(N), это что-то близкое к 2+(1/3). Оценивать результат не берусь, потому что будет больше сравнений и большее сжатие строки.

Нам достаточно иметь массивы с расстояниями между индексами 0,1,2,3, для индексов с расстоянием 4, можно получить информацию в массиве с расстоянием 2. На практике, мы просто выкидываем индексы с позициями 4, оставляем 3,5,6. Мы по прежнему имеем информация с для индексов с любой разницей:

0: 3 - 3 mod 7
1: 6 - 5 mod 7
2: 5 - 3 mod 7
3: 6 - 3 mod 7
4: 3 - 6 mod 7
5: 3 - 5 mod 7
6: 6 - 5 mod 7

Но есть дополнительная трудность, мы не можем получить сразу все недостающие позиции, поэтому понадобиться дополнительная сортировка и слияние.

Можно строить более большие и сложные разбиения, и ещё больше экономить, выкидывая индексы. Но учитывая то, как расчтёт сложность алгоритма, в эту тему можно не углубляться.

Измерения

Я использовал файл rfc-index.xml размеров 12111693 байт.

Размеры строки и алфавита внутри рекусии, время работы не считая рекурсивного времени:

 size: 12111693 [alphabet:256]     t=1.626 сек
 size:  8074462 [alphabet:30834]   t=1.426 сек
 size:  5382975 [alphabet:767340]  t=0.998 сек
 size:  3588650 [alphabet:1467546] t=0.669 сек
 size:  2392434 [alphabet:1762113] t=0.426 сек
 size:  1594956 [alphabet:1580474] t=0.270 сек
 size:  1063304 [alphabet:1063278] t=0.147 сек
 size:   708870 [alphabet:708869]  t=0.079 сек

С разрядностью алфавита тут играться нельзя. Трюки на глубоких уровнях рекурсии - не помогут. Они занимают очень незначительную часть времени.

Сравниваем:

Алгоритм Укконена, без искуственного распределения памяти.
Алгоритм Фарача, одноядерный, без новых доработок.
Прямое создание суффикного массива, без расчёта lcp значений.

Как видите, все три алгоритма - применены не в самых идеальных условиях.

Visual Studio 2015, AMD-FX-8300

Алгоритм Фарача одноядерный - 16 сек
Алгоритм Укконена - 5.6 сек
Суффиксный массив std::vector - 6.6 сек
Суффиксный массив без stl - 5.8 сек

Ubuntu g++.5.4 -O4 и какой-то Intel i7

Алгоритм Фарача одноядерный - 13 сек
Алгоритм Укконена - 5.3 сек
Суффиксный массив std::vector - 4.4 сек
Суффиксный массив без stl - 4.0 сек
Суффиксный массив без stl с расчётом lcp значений - 4.4 сек

Вывод, алгоритм на массивах не лучше и не хуже, чем алгоритм Укконена. Сравнивать расход памяти, особого смысла не имеет. Из плюсов, проще работать с большим алфавитом, можно не строить lcp значения.

Параллельный режим

Можно встраивать многоядерный режим, в разные части алгоритма.

Сортировка, тут нет вопросов.
Слияние, тут тоже очень просто. Оба сливаемых массива, перед слиянием проходят радиальную сортировку. Поэтому мы имеем индексы первых символов, для каждого массива, слияние можно делать в параллельном цикле, и это будет красиво. Если бы эти индексы не надо было дополнительно копировать из сортировки, мы бы ускорили работу, даже в одноядерном режиме.
Создание нового алфавита, после сортировки, вот тут всё сложно. Можно распараллелить, подсчёт символов, если модифицировать многоядерную сортировку. Но алгоритм получается таким неудобным, что проще его не трогать.

Я не привожу примеры, потому что параллельные вычисления скользкая тема. Распараллеливать алгоритм можно там, где делаются вычисления и работает сам процессор. Если вся работа сводиться к перекладывают байтов, работа упрёться в пропускную способность память, независимо от числа потоков.