Алгоритм Фараха — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(шаг 3: слияние четного и нечетного дерева)
(шаг 4: построение LCP-дерева)
Строка 140: Строка 140:
 
В результате описанных действий получится дерево <tex>M_x</tex>,в котором будут присутствовать поддеревья, которые прошли процедуру сличния, и которые ее избежали (т.е были перенесены в дерево <tex>M_x</tex> без изменений).
 
В результате описанных действий получится дерево <tex>M_x</tex>,в котором будут присутствовать поддеревья, которые прошли процедуру сличния, и которые ее избежали (т.е были перенесены в дерево <tex>M_x</tex> без изменений).
  
== шаг 4: построение LCP-дерева ==
+
== шаг 4:   ==
 +
 
 +
[[Файл:Tree101232merged.png|500px|thumb|right]]
 +
Разбираемся с двойными дугами (на этом примере из три). Для этого мы должны выяснить сколько начальных символов таких дуг совпадает. Совпадать может от одного до нескольких символов, или даже все. Проверять их все по очереди нельзя (это даст квадратичное время).
 +
Если дуги совпадают полностью, тогда ничего не делаем, удаляем одну из копий и всё. Если начало для двух дуг совпадает только частично, тогда нужно делать для них общее начало, а ветки которые на концах снова развести по разным деревъям (для этого можно во время снияния запомнить их начальный цвет или просто сохранить ссылки на исходные ветки).
 +
 
 +
 
 +
 
 +
 
 +
Для примера как это сделать возмём строку 10010010101000:
 +
 
 +
[[Файл:Treestep5_1.jpg|550px|thumb|left|]]
 +
 
 +
Для того чтобы узнать общее начало двойной дуги, мы должны взять одну чётную и одну нечётную на дереве, для которых родителем является конец нашей двойной дуги. Например на рисунке выше двойная дуга (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), так как от неё будет зависеть глубина расслояния.
 +
 
 +
Дерево после обработки:
 +
[[Файл:Treestep5_2.jpg|650px|thumb|left|]]
 +
 
 
== шаг 5: построение суффиксного дерева по LCP и слитому ==
 
== шаг 5: построение суффиксного дерева по LCP и слитому ==
  

Версия 17:05, 13 мая 2014

Эта статья находится в разработке!

Алгоритм Фарача — алгоритм построения суффиксного дерева для заданной строки [math]s[/math], который выполняется за время [math]O(N)[/math], при этом даже не требуется выполнения условия конечности алфавита. Такая эффективность достигается за счет того, что строковые последовательности определяются на индексированном алфавите или, что эквивалентно, на целочисленном алфавите [math]\Sigma = \{1, 2 {...}, a\}[/math], при этом накладывается дополнительное условие, что [math]a \in O(N)[/math]. Такие алфавиты часто встречаются на практике.


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

Основная идея алгоритма, заключается в том что мы уменьшаем размер исходной строки. Для этого мы разбиваем символы сходной строки на пару и пронумеровываем их, а из полученных номеров составляем новую строку, которая уже в 2 раза короче.

Мы опишем алгоритм Фарача в виде пяти выполняемых шагов. Используем в качестве примера строку [math]s = 121112212221[/math], определенную на алфавите [math]А = {1, 2} [/math] (в этом примере N = 12).

шаг 0: суффиксное дерево для сжатой строки

* Строка [math]s[/math] разбивается на пары: [math] 12 11 12 21 22 21 [/math]
* Пары сортирутся поразрядной сортировкой: [math]11 12 12 21 21 22 [/math].
* Удаляются копии: [math]11 12 21 22[/math].
* Парам даются номера (условно, в массиве они и так есть): [math]11-(0), 12-(1), 21-(2), 22-(3)[/math]
* Создаётся новая строка из номеров пар: 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

шаг 1: построение четного дерева

Определение:
Четное дерево [math]T^{even}_s[/math] является деревом суффиксов для строки [math]s[/math], узлы-листья которого ограничены нечетными позициями [math]2,4,6,{...} [/math] строки [math]s\$[/math].


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

Очевидно, что для этого достаточно умножить все расстояния в дереве на 2


Корректируются все развилки дерева (так как они могут совпадать в первых символах)
ID LCP STR
2 0 1112212221
0 1 121112212221
4 2 12212221
6 0 212221
10 2 21
8 1 2221

шаг 2: построение нечетного по четному

Определение:
Нечетное дерево [math]T^{odd}_s[/math] является деревом суффиксов для строки [math]s[/math], узлы-листья которого ограничены нечетными позициями [math]1,3,5,{...} [/math] строки [math]s\$[/math].


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

нечетное дерево
ID LCP STR
3 0 112212221
7 1 12221
11 1 1
1 0 21112212221
5 1 2212221
9 3 221

шаг 3: слияние четного и нечетного дерева

Далее необходимо найти эффективный способ слияния нечетного и четного деревьев в одно дерево [math]Т_s[/math]. Слияние будем производить начиная с корня. Предположим, что для каждого узла деревьев [math]Т_s^{odd}[/math] и [math]Т_s^{even}[/math] выходящие из них ребра занесены в специальные списки, где они упорядочены в возрастающем лексикографическом порядке подстрок, которые представляют эти ребра. Алгоритм слияния деревьев просматривает только первые буквы подстрок, представленных ребрами деревьев [math]Т_s^{odd}[/math] и [math]Т_s^{even}[/math], пусть это будут буквы [math]\lambda^{odd}[/math] и [math]\lambda^{even}[/math]. Тогда:

  • если [math]\lambda^{odd}[/math] [math]\ne[/math] [math]\lambda^{even}[/math], определяется поддерево, соответствующее меньшей из этих букв, и без изменений присоединяется к узлу-родителю;
  • если [math]\lambda^{odd}[/math] [math]=[/math] [math]\lambda^{even}[/math] и длины подстрок, представленных соответствующими ребрами, равны, в дерево слияния к текущему узлу добавляются два сына: один — из четного дерева, другой — из нечетного;
  • если [math]\lambda^{odd}[/math] [math]=[/math] [math]\lambda^{even}[/math] и длины подстрок, представленных соответствующими ребрами, различны, в дерево слияния к текущему узлу добавляются два узла, находящиеся на одном нисходящем пути, при этом ближайший узел будет соответствовать более короткой подстроке.

Если начать эту процедуру для корней нечетного и четного деревьев, далее она рекурсивно выполняется для корней всех поддеревьев, которые, возможно, уже содержат узлы из нечетного и четного деревьев, поскольку ранее мог быть реализован случай [math]\lambda^{odd}[/math] [math]=[/math] [math]\lambda^{even}[/math]. Так как время манипулирования с любым ребром этих деревьев фиксированно, то общее время слияния деревьев составит [math]O(N)[/math].

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

В результате описанных действий получится дерево [math]M_x[/math],в котором будут присутствовать поддеревья, которые прошли процедуру сличния, и которые ее избежали (т.е были перенесены в дерево [math]M_x[/math] без изменений).

шаг 4:

Tree101232merged.png

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



Для примера как это сделать возмём строку 10010010101000:

Treestep5 1.jpg

Для того чтобы узнать общее начало двойной дуги, мы должны взять одну чётную и одну нечётную на дереве, для которых родителем является конец нашей двойной дуги. Например на рисунке выше двойная дуга (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), так как от неё будет зависеть глубина расслояния.

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

Treestep5 2.jpg

шаг 5: построение суффиксного дерева по LCP и слитому

аспекты реализации

корректность и эффективность