Короче говоря, Java реализация суффиксного дерева и использования?

Question

Я ищу короткий, простой суффиксный алгоритм построения / использования дерева в Java. Лучшее из того, что я нашел, - это использование Semantic Discovery Toolkit, но его реализация занимает несколько тысяч строк и охватывает несколько классов. В идеале реализация должна быть как можно короче и занимать не более нескольких сотен строк.

У кого-нибудь есть такая реализация?

Answer 1

Я только что закончил реализацию суффиксного дерева на Java. В моей записи в блоге вы можете узнать больше о суффиксных деревьях, посмотреть, как использовать мою библиотеку, а также скачать и собрать библиотеку, используя Subversion и Maven. Да, он длиннее нескольких строк в одном файле класса, но он хорошо документирован и создан для практического использования в реальном мире. Кроме того, он использует подход Укконена для построения линейного времени. (Большинство реализаций, отмеченных здесь, имеют как минимум O (n ^ 2) время выполнения.)

Answer 2

Статья "Простое построение суффиксной линейной работы", написанная Карккайненом и Сандерсом, заканчивается 50 строками C ++. Возможно, вам также понадобится что-то для создания массива LCP. Поиск в Google: «Вычисление массива LCP за линейное время с учетом S и суффикса POS». должен найти вас, что.

Answer 3

Вы также можете взять мой , но это не алгоритм Укконена - как и все другие простые подходы, он работает в квадратичном времени. Я согласен с тем, что наивный алгоритм (который может работать нормально для более коротких последовательностей) легко написать максимум за полдня.