Алгоритм Фараха — различия между версиями
Slavian (обсуждение | вклад) |
Slavian (обсуждение | вклад) (скелет статьи) |
||
| Строка 2: | Строка 2: | ||
'''Алгоритм Фарача''' — алгоритм построения [[Сжатое суффиксное дерево|суффиксного дерева]] для заданной строки <tex>s</tex>, который выполняется за время <tex>O(N)</tex>, при этом даже не требуется выполнения условия конечности алфавита. Такая эффективность достигается за счет того, что строковые последовательности определяются на индексированном алфавите или, что эквивалентно, на целочисленном алфавите <tex>\Sigma = \{1, 2 {...}, a\}</tex>, при этом накладывается дополнительное условие, что <tex>a \in O(N)</tex>. Такие алфавиты часто встречаются на практике. | '''Алгоритм Фарача''' — алгоритм построения [[Сжатое суффиксное дерево|суффиксного дерева]] для заданной строки <tex>s</tex>, который выполняется за время <tex>O(N)</tex>, при этом даже не требуется выполнения условия конечности алфавита. Такая эффективность достигается за счет того, что строковые последовательности определяются на индексированном алфавите или, что эквивалентно, на целочисленном алфавите <tex>\Sigma = \{1, 2 {...}, a\}</tex>, при этом накладывается дополнительное условие, что <tex>a \in O(N)</tex>. Такие алфавиты часто встречаются на практике. | ||
| + | |||
| + | = описание алгоритма = | ||
Основная идея алгоритма, заключается в том что мы уменьшаем размер исходной строки. Для этого мы разбиваем символы сходной строки на пару и пронумеровываем их, а из полученных номеров составляем новую строку, которая уже в 2 раза короче. | Основная идея алгоритма, заключается в том что мы уменьшаем размер исходной строки. Для этого мы разбиваем символы сходной строки на пару и пронумеровываем их, а из полученных номеров составляем новую строку, которая уже в 2 раза короче. | ||
| + | |||
| + | Мы опишем алгоритм Фарача в виде пяти выполняемых шагов. Используем в качестве примера строку <tex>s = 121112212221</tex>, определенную на алфавите <tex>А = {1, 2} </tex> (в этом примере N = 12). | ||
| + | == шаг 1: построение нечетного дерева == | ||
| + | == шаг 2: построение четного дерева по нечетному == | ||
| + | == шаг 3: слияние четного и нечетного дерева == | ||
| + | == шаг 4: построение LCP-дерева == | ||
| + | == шаг 5: построение суффиксного дерева по LCP и слитому == | ||
| + | |||
| + | |||
| + | = аспекты реализации = | ||
| + | |||
| + | |||
| + | = корректность и эффективность = | ||
Версия 12:58, 13 мая 2014
Алгоритм Фарача — алгоритм построения суффиксного дерева для заданной строки , который выполняется за время , при этом даже не требуется выполнения условия конечности алфавита. Такая эффективность достигается за счет того, что строковые последовательности определяются на индексированном алфавите или, что эквивалентно, на целочисленном алфавите , при этом накладывается дополнительное условие, что . Такие алфавиты часто встречаются на практике.
Содержание
описание алгоритма
Основная идея алгоритма, заключается в том что мы уменьшаем размер исходной строки. Для этого мы разбиваем символы сходной строки на пару и пронумеровываем их, а из полученных номеров составляем новую строку, которая уже в 2 раза короче.
Мы опишем алгоритм Фарача в виде пяти выполняемых шагов. Используем в качестве примера строку , определенную на алфавите (в этом примере N = 12).
