Суффиксное дерево - Алгоритм фарача

Алгортим общее описание

• Шаг 1
  Строка разбивается на пары: 12 11 12 21 22 21
  Пары сортирутся:11 12 12 21 21 22.
  Удаляются копии: 11 12 21 22.
  Парам даются номера (условно, в массиве они и так есть): 11 (0) 12 (1) 21 (2) 22 (3)
  Создаётся новая строка из номеров пар: 1 0 1 2 3 2
  Из полученной строки создаётся суффикcное дерево:
  
  Суффиксный массив новой строки:

  ID	LCP	str
  1	0	0 1 2 3 2
  0	0	1 0 1 2 3 2
  2	1	1 2 3 2
  3	0	2 3 2
  5	1	2
  4	0	3 2

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

• Шаг 2
  Из дерева сжатой строки получаем частичное (чётное) дерево исходной строки. Частичное потому в нём будут только половина суффиксов, т.е. тех которые стоят в чётных позициях. Очевидно что для этого достаточно умножить все расстояния в дереве на 2:
  

  Корректируются все развилки дерева (так как они могут совпадать в первых символах):
  
  Суффиксный массив чётного дерева исходной строки:

  ID	LCP	str
  2	0	1112212221
  0	1	121112212221
  4	2	12212221
  6	0	212221
  10	2	21
  8	1	2221

• Шаг 3
  Из чётного дерева, нужно получить нечётное дерево (дерево из суффиксов в нечётных позициях). Для этого можно взять суффиксный массив чётного дерева, отрезать первые символы, и выполнить стабильную сортировку по оставшимся первым символам:
  Суффиксный массив нечётного дерева исходной строки:

  ID	LCP	str
  3	0	112212221
  7	1	12221
  11	1	1
  1	0	21112212221
  5	1	2212221
  9	3	221

  
  
• Шаг 4
  Выполняется слияние. Для этого мы просто рекурсивно проходим дуги обоих деревьев, но сравниваем только первые символы дуг. Если в двух деревьях попадаются дуги разной длины, то длину эту грубо подгоняем, например лепим на более длинную ещё один узел (думаю так всё очевидно). Если попадаются две дуги с одинаковыми начальными символами, то обе заносятся в результат:

  Слитое дерево (условно):
  

  Слитое дерево (в упрощённом виде):
  

• Шаг 5
  Разбираемся с двойными дугами (на этом примере из три). Для этого мы должны выяснить сколько начальных символов таких дуг совпадает. Если дуги совпадают полностью, тогда ничего не делаем, удаляем одну из копий и всё. Если начало для двух дуг совпадает только частично, тогда нужно делать для них общее начало, а ветки которые на концах снова развести по разным деревъям (для этого можно во время снияния запомнить их начальный цвет или просто сохранить ссылки на исходные ветки).

  

Подробности

• Шаг 1: дерево сжатой строки
  Для построения дерева сжатой строки, алгоритм выполняется рекурсивно. Т.е. дерево для сжатой строки сроится с помощью повторного вызова того же алгоритма.
• Шаг 3: преобразование четного дерева в нечётное
  Для выяснения общего префикса строк, автор предлагает использовать находить общего предка вершин в суффиксном дереве. Считается что такой предок можно найти за константное время. Для примера в этом дереве, общее начало строк 5 и 9 (11011111000 1111011111000) записано в пути от корня до общего предка этих вершин:
  
  Поскольку структуры нечётного дерева у нас заранее нет и мы её только строим, то подходящих предков мы можем найти в исходном чётном дереве, для этого достаточно проверить вершины с номерами на еденицу меньше и отрезать первый символ.
• Шаг 5 удаление двойных дуг
  Практически самое сложное из того что надо сделать. Нам нужно пройти все двойные дуги и выяснить сколько начальных символов у них совпадает. Совпадать может от одного до нескольких символов, или даже все. Проверять их все по очереди нельзя (это даст квадратичное время). Для примера возмём строку 10010010101000

  
  Для того чтобы узнать общее начало двойной дуги, мы должны взять одну чётную и одну нечётную на дереве, для которых родителем является конец нашей двойной дуги. Например на рисунке выше двойная дуга (1), конец я пометил зелёным - является общим родителем для вершин 3 и 6. Чтобы узнать на каком расстоянии будет расслаиваться двойная дуга, надо увеличить номера вершин на еденицу и найти их родителя, он будет находится на еденицу ближе к корню (и путь у вершин будет одинаковой строкой, не считая размера). Родителя вершин 4, 7 я пометил жёлтым, он находится на расстоянии 1 от корня, следовательно дуга (1) должна расслаиваться в двух символах от корня, т.е. обе дуги совпадают и их просто надо слить.

  Разберём дуги по порядку:

  • (1) расслоение находится на расстоянии два от корня, т.е. дуга не расслаивается.
  • (2) конец является родителем вершин 2, 7. Родитель 3, 8 после слияния дуги (1), находится на глубине 2 символа. Значит дуга (2) расслаивается на глубине 3 символа, т.е. так же не расслаивается. Дугу (2) нужно вычислять после обработки дуги (1), потому что конец дуги (1) после обработки может оказаться на разной высоте, в зависимости от того на каком символе она расслоилась.
  • (3) конец является родителем 2, 9. Родитель 3, 10 находится на расстоянии 3, а наше расслоение на на расстоянии 4, т.е. сливается первый символ двойной дуги. Дугу (3) надо вычислять после дуги (2). Потому что если на дуге (2) появится разветвление, то компоненты дуги (3) придётся растащить по разным веткам дерева и сравнивать их будет не нужно.
  • (4) конец является родителем 1, 4. Расслаивается на втором символе.
  • (5) конец является родителем 0, 3. Дугу (5) можно обрабатывать только после дуги (4), так как от неё будет зависеть глубина расслояния.

  Дерево после обработки:
  

Замечания

На разных шагах приходится применять суфф. деревья или суфф. массивы. Преобразование дерева в массив и обратно делается за линейное время.

• Шаг 1:
  очень хорошее место для того чтобы ускорить процедуру.
  1. Когда вся строка состоит из одного символа, индекс так же получается ввиде одного числа. Эта ситуация будет замента при первой индексации (сжатия исходной строки).
  2. Когда все пары различны, т.е. количеством номеров в индексе совпало с количество пар исходной строки. Эта ситуация очень быстро возникает во время рекусии, притом на небольшой глубине.

  В этих случаях можно не продолжать рекурсивные вызовы, а делать специфичное постоение, это сильно ускоряет всю работу:

  1. Если все символы одинаковые - всё суффиксы просто будут идти в массиве по порядку.
  2. Если все пары уникальны - достаточно выполнить сортировку первых символов суффиксов и больше ничего не стоить.
  3. Если строка небольшая или глубина ветвлений небольшая (почти все пары уникальны) - то дерево можно построить в лоб, не прибегая к тяжёлым процедурам.

  Для справки покажу рекурсивную обработку файла rfc-index.xml

  глубина	размер строки	число уник. пар (новый алфавит)	уникальные пары %
  1	7661287	3193	> 1%
  2	3830643	61509	3%
  3	1915321	169206	17%
  4	957660	167675	35%
  5	478830	124981	52%
  6	239415	91360	76%
  7	119707	56328	94%
  8	59853	29900	99%
  9	29926	14963	100% (все пары уникальны)

• Шаг 3:
  не нужно находить общих предков вершин. Достаточно просто узнать его расстояние от корня. Т.е. просто находить минимумы lcp значений на отдельном отрезке в суффиксном массиве. По времени это таже константа, но всё таки немного проще и быстрее. Более того искать вообще ничего не надо, потому что lcp в суфф. массиве можно вычислить, за линейное время, т.е. совсем быстро и без всяких глупых построений.
• Шаг 5:
  очень проблемное место. Надо очень часто и много искать общих родителей двух вершин, хотя это и константная процедура, она отнимает время (благо что двойных дуг после слияния, остаётся очень мало). Кроме того на конце каждой дуги надо найти двух потомков, обязательно чётного и нечётного, для которых этот конец является родителем. Как не крути это процедура линейная по времени, но слишком простой её не назовёшь. Т.е. либо неудобства либо дополнительная память для хранения чисел в узлах. Так же получается что сами дуги зависят друг от друга, т.е. как показанно в примере, их надо обрабатывать в определённом порядке, иначе результат будет неверный. Тут я могу намекнуть на следущие мысли:
  1. можно обрабатывать двойные дуги в дереве по порядку, делая обход дерева в ширину. Но поскольку алфавит не имеет ограничений по размеру, ширина у дерева может оказаться заметной, а обход занять какую-то память.
  2. можно записать номера всех пар, для которых надо найти родителя и отсортировать их по убыванию радиальной сортировкой (время линейное).
  3. можно прошить все зависимости между вершинами с помощью ссылок. Получится что-то вроде суффиксных связей, которые по сути и станут суффиксными связями после полной обработки дерева.

  Если бы можно было каким-то образом узнавать совпадают ли двойные дуги полностью или нет, тогда можно было бы полностью избавиться от поиска общих предков. Потому что в случае полного совпадения дуг она полностью сливается. А в случае неполного, не обязательно знать на каком символе она будет расслаиваться. Достаточно узнать какая из двух дуг идёт раньше по алфавиту. Дерево в таком случае использовать будет не интересно, но при его обычном обходе можно получить правильный суффиксный массив, который удобно использовать на более высоком слое рекурсии или напрямую.

  офтоп

  Чтобы выяснить порядок в котором должны идти две дуги, достаточно посмотреть на любые суффиксы на конце каждой из дуг. Если у нас есть два суффикса i₁, i₂ и они начинаются на одинаковый символ, то достаточно посмотреть в каком порядке идут суффиксы i₁+1, i₂+1, порядок i₁, i₂ должен быть таким же. Покажу на примере. Есть суфф. массив:

  ID	str
  1	1112212221
  3	112212221
  4	12212221
  0	121112212221
  7	12221
  1	21112212221
  10	21
  6	212221
  9	221
  5	2212221
  8	2221

  мы ходим проверить суффиксы 4, 0, достаточно просто посмотреть на суффиксы 5, 1, они идут в массиве в другом порядке (1 раньше чем 5), поэтому 4, 0 надо просто поменять местами. Чтобы расставить весь массив в правильном порядке, достаточно таким образом проверить соседей для всех суффиксов в порядке убывания номеров. Это очень эффективная процедура, если порядок суффиксов был нарушен лишь частично.

Заключение

[тут реализация] - я выложил рассказ о практической реализации, и немного о суф. деревьях