В 1973 году Вайнер дал первое линейное построение суффиксных деревьев. Алгоритм был упрощен в 1976 году МакКрейтом, а в 1995 году - Укконеном. Тем не менее, я нахожу алгоритм Укконена относительно концептуально задействованным.
Были ли упрощения алгоритма Укконена с 1995 года?
ds.algorithms
Randomblue
источник
источник
Ответы:
Я не уверен, были ли какие-либо новые результаты, непосредственно упрощающие построение деревьев суффиксов. Тем не менее, был по крайней мере один результат, дающий очень простой алгоритм для построения массивов суффиксов за линейное время.
Обратите внимание, что существует более чем концептуальная эквивалентность между этими двумя структурами данных, поскольку вы можете использовать массив суффиксов (со временем для запроса самого длинного общего префикса) для построения эквивалентного дерева суффиксов. Это должно быть относительно простое упражнение, но я могу дать более подробную информацию, если потребуется.O (1)
источник
В дополнение к тому, что было упомянуто ( Kärkkäinen & Sanders, 2003 ), я думаю, вы по достоинству оцените «более новую» версию Kärkkäinen, Sanders and Burkhard, 2006 . Алгоритм в основном соответствует структуре алгоритма Фараха. Возможно, это концептуально проще, но реальным преимуществом является то, что они предоставляют читателю реализацию алгоритма. Это всего около 50 строк C ++, так что в действительности нет никаких скрытых деталей.
источник