275
правок
Изменения
м
→Минусы алгоритма Укконена
# Существенно использует константность размера алфавита. Например, [[Алгоритм_Фарача | алгоритм Фарах-Колтона]] строит суффиксное дерево за линейное время независимо от размера алфавита.
# На сегодняшний день существуют кэш-эффективные алгоритмы, которые превосходят алгоритм Укконена на современных процессорах<ref>[https://www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=6&ved=0CFMQFjAF&url=http%3A%2F%2Fwww.researchgate.net%2Fprofile%2FYuanyuan_Tian%2Fpublication%2F30848628_Practical_methods_for_constructing_suffix_trees%2Flinks%2F0046352b38e5dc849e000000.pdf&ei=Bh4sVZL8EIausAHujoDoBg&usg=AFQjCNEAr63t7zZnWZPKYIZLjQQInbelSg&sig2=jAPs1IULJvJZt8xwx5PYtA&bvm=bv.90491159,d.bGg&cad=rja Yuanyuan Tian, Sandeep Tata, Richard A. Hankins, Jignesh M. Patel {{---}} Practical methods for constructing suffix trees.]</ref>.
# Размер суффиксного дерева превосходит входные данные в 10-60 раз, поэтому при очень больших размерах входных данных алгоритм Укконена сталкивается с проблемой ''memory bottleneck problem''(другое ее название ''thrashing'')<ref>[http://dspace.library.uvic.ca:8080/bitstream/handle/1828/2901/ThesisBarsky16july.pdf?sequence=1 Marina Barsky {{---}} Suffix trees for very large inputs.]</ref>.# Так же алгоритм предполагает, что дерево полностью должно быть загружено в память, а при больших размерах входных данных это опять же может быть затруднительно<ref>[http://arxiv.org/pdf/1012.4074.pdf Woong-Kee Loh, Yang-Sae Moon, Wookey Lee {{---}} A fast divide-and-conquer algorithm for indexing human genome sequences.]</ref>.
== Реализация ==
