497
правок
Изменения
Нет описания правки
{{В разработке}}
'''Алгоритм Фарача(Martin Farach,(1997))''' — алгоритм построения [[Сжатое суффиксное дерево|суффиксного дерева]] для заданной строки <tex>s</tex>, ( <tex>| s | = N) </tex> который выполняется за время <tex>O(N)</tex>, при этом даже не требуется выполнения условия конечности алфавита. Такая эффективность достигается за счет того, что строковые последовательности определяются на индексированном алфавите или, что эквивалентно, на целочисленном алфавите <tex>\Sigma = \{1, 2 \dots , k\}</tex>, при этом накладывается дополнительное условие, что <tex>k \in O(N)</tex>. Такие алфавиты часто встречаются на практике.
[[Файл:Treestep5_2.jpg|650px]]
= Оценки Замечания =
Как показывает автор с своей работе, чётное дерево <tex>T_s^{even}</tex> строится за линейное время. За линейное же время из него получается <tex>T_s^{odd}</tex>, и слияние <tex>T_s^{even}</tex> и <tex>T_s^{odd}</tex> занимает <tex>O(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]
