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

Question

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

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

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

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

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

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

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

Answer 1

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