Концептуально простые конструкции дерева суффиксов с линейным временем

Question

В 1973 году Вейнер дал первое линейное построение суффиксных деревьев.Алгоритм был упрощен в 1976 году МакКрейтом, а в 1995 году - Укконеном.Тем не менее, я считаю, что алгоритм Укконена относительно концептуально задействован.

Были ли упрощения алгоритма Укконена с 1995 года?

Answer 1

Более прямым ответом на исходный вопрос является построение нисходящего (и ленивого) суффиксного дерева от Giegerich, Kurtz, Stoye: https://pub.uni -bielefeld.de / luur / download? Func = downloadFile & recordOId = 1610397 & fileOId = 2311132

Кроме того, массивы суффиксов (как упомянуто в предыдущем ответе) не только легче построить, но и улучшить, чтобы имитировать все, что вы ожидаете от дерева суффиксов: http://www.daimi.au.dk/~cstorm/courses/StrAlg_e04/papers/KurtzOthers2004_EnhancedSuffixArrays.pdf

Поскольку структуры данных, включенные в расширенный массив суффиксов, могут быть сжаты, становятся возможными сжатые (эмулированные) деревья суффиксов: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.79.8644&rep=rep1&type=pdf

Answer 2

Это не прямой ответ, однако он может помочь вам.

В прошлом году, работая над этой темой, я прекратил использовать суффикс-массивы вместо суффикс-деревьев, а в IIRC я ​​использовал статью "Некомплексный алгоритм построения массива быстрых суффиксов »К.Б. Шюрманн (2007) [1] в качестве ссылки.IIRC, это двухпроходный линейный алгоритм для построения суффикс-массивов.

[1] http://scholar.google.com/scholar?q=An+incomplex+algorithm+for+fast+suffix+array+construction+&hl=en&btnG=Search&as_sdt=1%2C5&as_sdtp=on