22
правки
Изменения
Нет описания правки
'''Алгоритм Фарача Фараха''', разработанный в 1997 году американским ученым Мартином Фарах-Колтоном (Martin Farach,(1997)-Colton)''' {{---}} алгоритм построения [[Сжатое суффиксное дерево|суффиксного дерева]] для заданной строки <tex>s</tex> длины <tex>N</tex>. Сам алгоритм выполняется за время <tex>O(N)</tex>, причём даже не требуется выполнение условия конечности алфавита. Такая эффективность достигается за счет того, что строковые последовательности определяются на индексированном алфавите или, что эквивалентно, на целочисленном алфавите <tex>\Sigma = \{1, 2 \dots , k\}</tex>. При этом накладывается дополнительное условие, что <tex>k = O(N)</tex>. Такие алфавиты часто встречаются на практике. Важно помнить, что алгоритм скорее теоретический, чем нежели практический, а основная его ценность его заключается в том, что размер алфавита может быть произвольным.
== Описание алгоритма ==
Идея алгоритма заключается в том, что мы уменьшаем размер исходной строки, строим суффиксное дерево для неё рекурсивно, а потом получаем из построенного дерево для текущей строки. Для этого мы разбиваем символы исходной строки на пары и нумеруем их, а из полученных номеров составляем новую строку, которая уже в <tex>2</tex> раза короче.
Алгоритм Фарача Фараха будет описан в виде пяти выполняемых шагов. Используем в качестве примера строку <tex>s = 121112212221</tex>, определенную на алфавите <tex>\Sigma = \{1, 2\} </tex> (в этом примере <tex>N = 12</tex>).
=== Шаг 1: суффиксное дерево для сжатой строки===
[[Файл:tree101232.png|thumb|300px|суффиксное дерево для сжатой строки]]
* Строка <tex>s</tex> разбивается на пары подряд идущих символов: <tex> \langle 12\rangle \langle 11\rangle \langle 12\rangle \langle 21\rangle \langle 22\rangle \langle 21\rangle </tex>
*: (если символов нечетное число {{---}} последняя пара дополняется специальным символом <tex>\$</tex>).* Пары сортируются устойчивой сотрировкой сортировкой (удобно сортировать [[Цифровая_сортировка | поразрядной]], так как число разрядов мало, размер алфавита — <tex>O(n)</tex>, то время работы сортировки — линейное): <tex> \langle 11 \rangle \langle 12\rangle \langle 12\rangle \langle 21\rangle \langle 21\rangle \langle22\rangle </tex>.
* Удаляются копии: <tex> \langle 11\rangle \langle 12\rangle \langle 21\rangle \langle 22\rangle </tex>.
* Парам даются номера (условно, в массиве они и так есть): <tex>\langle 11 \rangle -(0), \langle 12\rangle -(1), \langle 21\rangle - (2), \langle 22\rangle-(3)</tex>.* В исходной строке пары заменяются на номера: <tex>1 0 1 2 3 2</tex>.* Из полученной строки вдвое меньшего размера рекурсивно создаётся [[Сжатое суффиксное дерево | суффикcное дерево]] тем же алгоритмом:.* рекурсия Рекурсия не продолжается, если строка имеет длину <tex>1</tex>: суффиксное дерево строится тривиально.
=== Шаг 2: построение чётного дерева ===
В итоге получается <tex> T(n) = T(n / 2) + \Theta (n) = \Theta (n) </tex>.
==Минусы алгоритма ФарачаФараха==
Данный алгоритм является больше теоретическим, нежели практическим. Как можно было заметить, основная идея
== Источники информации ==
*[http://www.cs.rutgers.edu/~farach/pubs/Suffix.pdf Optimal suffix tree construction with large alphabets ]
*[http://www.proteus2001.narod.ru/gen/txt/11/farach.html Суффиксное дерево {{---}} Алгоритм фарачаФараха]
*[http://books.google.ru/books/about/Computing_Patterns_in_Strings.html?id=iKR0EewiCu4C&redir_esc=y Computing Patterns in Strings]
*[https://github.com/krzysztofp/Text-Algorithms/tree/master/Farach%20suffix%20tree Chris Parjaszewski's implementation]
