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

Материал из Викиконспекты
Перейти к: навигация, поиск
(шаг 1: построение нечетного дерева)
(описание алгоритма)
Строка 8: Строка 8:
  
 
Мы опишем алгоритм Фарача в виде пяти выполняемых шагов. Используем в качестве примера строку <tex>s = 121112212221</tex>, определенную на алфавите <tex>А = {1, 2} </tex> (в этом примере N = 12).
 
Мы опишем алгоритм Фарача в виде пяти выполняемых шагов. Используем в качестве примера строку <tex>s = 121112212221</tex>, определенную на алфавите <tex>А = {1, 2} </tex> (в этом примере N = 12).
 +
== шаг 0: суффиксное дерево для сжатой строки==
 
== шаг 1: построение нечетного дерева ==
 
== шаг 1: построение нечетного дерева ==
  
Строка 18: Строка 19:
 
== шаг 4: построение LCP-дерева  ==
 
== шаг 4: построение LCP-дерева  ==
 
== шаг 5: построение суффиксного дерева по LCP и слитому ==
 
== шаг 5: построение суффиксного дерева по LCP и слитому ==
 
  
 
= аспекты реализации =
 
= аспекты реализации =

Версия 13:43, 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: суффиксное дерево для сжатой строки

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

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


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

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

шаг 4: построение LCP-дерева

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

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

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