Алгоритм Укконена Обобщенные деревья суффикса

Question

Я понимаю ukkonen's algorithm. Мне просто любопытно, как расширить его, чтобы иметь в нем более одной строки (заканчивая специальным символом «$»).

Я читал где-то, что заданные строки s1 (скажем, «abcddefx $») и s2 (скажем, «abddefgh $»), я должен вставить s1 обычно по ukkonen's algo. Затем перейдите по дереву с помощью s2. То есть я должен искать s2 в дереве. Как только я доберусь до узла, где заканчивается поиск («ab», после «b»), я должен вернуться от алгоритма ukkonen.

Я понимаю основную логику этого. Но мне любопытно, что происходит со старыми ссылками суффикса. Они все еще действительны? Также я смущен о моей тройке (active_node, active_length, остаток), должен ли он (узел, представляющий «ab», 0,0), когда я начинаю новый проход ???

Answer 1

Для обработки специальных символов вы можете использовать Unicode Private Use Areas. Это несколько специальных диапазонов символов, зарезервированных для вашего собственного использования, однако диапазоны составляют всего около 4000 символов. В зависимости от поддержки юникода языка, который вы используете, это может быть очень просто или сложно.

Если это не сработает, вместо того, чтобы вставлять символы в ваше дерево, заверните их в какую-либо другую переменную (struct, object, dictionary), чтобы «расширить» их значение. Таким образом, вы можете предоставить дополнительную необходимую информацию (это конец строки, какая строка - это конец?). Затем вы можете предоставить пользовательские операторы для равенства в этой новой оболочке, а не напрямую использовать символы.