Во-первых, существует множество способов построения дерева суффиксов.Существует оригинальный метод O (n) от Weiner (1973), улучшенный метод McCreight (1976), наиболее известный Ukkonen (1991/1992), и ряд дополнительных улучшений, в основном связанных с внедрением и хранением.соображения эффективности.Наиболее примечательным среди них является, пожалуй, Эффективная реализация ленивых суффиксных деревьев Гигериха и Курца.
Более того, поскольку прямое построение суффиксных массивов стало возможным в O(n) время в 2003 году (например, с использованием алгоритма Skew , но есть и другие), и поскольку существуют хорошо изученные методы для
суффиксные массивыобычно предпочтительнее суффиксных деревьев.Поэтому, если вы намерены создать высокооптимизированную реализацию для конкретной цели, вам может потребоваться изучить алгоритмы построения массивов суффиксов.
Однако, если вы заинтересованы в построении дерева суффиксов и, в частности,Алгоритм Ukkonen, я хотел бы предложить вам внимательно взглянуть на описание в этом SO посте , о котором вы уже упоминали, и мы попытаемся улучшить это описание вместе.Это, безусловно, далеко от совершенно интуитивного объяснения.
Чтобы ответить на вопрос о том, как сравнивать входную строку с метками ребер: По соображениям эффективности при построении и поиске начальная буква символ каждой метки ребра обычно хранится в узле.Но остальное нужно искать в основной текстовой строке, как вы сказали, и это действительно может вызвать проблемы, в частности, когда строка настолько велика, что не может быть легко сохранена в памяти.Это (плюс тот факт, что, как и любая прямая реализация дерева, дерево суффиксов - это структура данных, которая содержит много указателей, которые занимают много памяти и затрудняют поддержание ссылочной локальности и кэширование памяти ) - одна из главных причин того, что деревья суффиксов намного сложнее обрабатывать, чем, например, инвертированные индексы.