Может кто-нибудь объяснить, когда и как расширить дерево суффиксов?

Question

Я работаю над PHP-скриптом, который должен найти самую длинную повторяемую подстроку. Я нашел эту вещь Суффикс-Три. Я пытаюсь реализовать алгоритм Укконнена, но не могу понять, когда и как расширить дерево.

Это нормально, если у меня есть новый символ, которого нет в дереве, но я должен создать новый узел и egde из корня для него. Но как я должен знать, должен ли я разделить край?

Я нашел его реализацию на C++ ( ссылка) и попытался перевести его на php, но я думаю, что в нем есть typeo, потому что он дает почти хороший результат, проблема в том, что я не могу это исправить, пока не сделаю это. понять это полностью...

Я прочитал дюжину описаний Суффикс-деревьев, но некоторые из них не слишком углубляются в это, другие вызывают у меня головную боль после второго предложения.

Вот код, который у меня есть сейчас: Suffix-tree.php (Извините, но этот редактор не смог его принять) Я использовал этот сайт, чтобы проверить результат.

Так что любой совет будет оценен...

РЕДАКТИРОВАТЬ: Я переписал его с JavaScript-материалов, найденных на упомянутом сайте. Вот ссылка на источник: Suffix-Tree v0.1

Answer 1

Хорошее объяснение дает Мэтт Махони, эксперт по сжатию данных. Но я тоже не понял реализацию, это довольно сложно. К вашему сведению, мне удалось запустить расширение php суффикс-дерева. Вы можете найти мой код в sourceforge, если это поможет. Я хотел бы увидеть ваш окончательный код, хотя!