Может ли кто-нибудь дать мне пример о том, как и когда создавать ссылку суффикса в дереве суффиксов?
Если моя строка ABABABC, но используйте другой пример, если это лучше.
Надеемся дать некоторые иллюстрации, чтобы проиллюстрировать каждый шаг.
очень ценю.
Чтобы понять это, сначала напомните, что существует три типа узлов в дереве суффиксов:
На графике ниже, который является деревом суффиксов для ABABABC, желтый
кружок корень, серый, синий и зеленый внутренний
узлы, а маленькие черные - .
Можно заметить две важные вещи:
Внутренние узлы всегда имеют более 1 исходящего края. То есть, внутренние узлы отмечают те части дерева, где происходит ветвление.
Ветвление происходит везде, где задействована повторяющаяся строка, и только там. Для любого внутреннего node X строка, ведущая из корень в X должен происходить во входной строке как минимум столько раз так как из X есть исходящие ребра.
Пример: Строка, ведущая к синему node, равна ABAB. В самом деле, эта строка появляется дважды во входной строке: в позиции 0 и at 2. И поэтому синий node существует.
Теперь о ссылках суффикса:
Если строка s, ведущая к некоторому внутреннему node X, длиннее чем 1 символ, та же строка минус первый символ (назовите это s -1) тоже должно быть в дереве (это суффикс-дерево, в конце концов, поэтому суффикс любой из его строк должен быть в дереве тоже).
Пример:. Пусть s = ABAB, строка, ведущая к синему node. затем
после удаления первого символа s -1 есть BAB. А также
действительно, эта строка найдена и в дереве. Это приводит к зеленому
node.
Если какая-то строка s приводит к внутреннему node, ее сокращенная версия s -1 должна привести к внутреннему node (вызов это X -1). Зачем? Поскольку s должен появляться как минимум дважды в строка s -1 должна появляться как минимум столько раз (потому что он является частью s: везде, где появляется s s -1 тоже должен появиться). Но если s -1 появляется несколько раз во входной строке, тогда должно быть внутренний node для него.
В любой такой ситуации специальная ссылка, связывающая X с X -1, является суффикс.
Примечание: Из-за (1) и (2) выше каждого внутреннего node X, что имеет метку от корня до X более 1 символа должна иметь суффиксную ссылку на один и тот же внутренний node.
Пример:
Это то же дерево суффикса, что и раньше; пунктирные линии указывают на суффиксные ссылки. Если вы начинаете с синего node и следуете суффиксу ссылки оттуда (от синего, зеленого, до первого серого, второго серого), и посмотрите на строки, ведущие от корня к каждому node, вы будете см. это:
ABAB -> BAB -> AB -> B
(blue) (green) (gray1) (gray2)
Вот почему они называются суффиксными ссылками (вся последовательность называется цепочкой суффикса ).
Для чего они хороши?
Они хороши для удивительно многих вещей. Однако они играют особая роль в алгоритме Укконена для дерева суффиксов строительства, в частности в Правило 3, описанное там: После вставки конечного символа некоторого суффикса s в некоторой точке X, алгоритм должен вставить последний символ суффикса s -1 в O (1) раз. В Чтобы сделать это, он использует суффиксную ссылку для перехода прямо к месту X -1 и делает вставку.
Но заметьте, что нет необходимости помещать суффиксные ссылки в дерево суффиксов. Они не являются частью определения дерева суффикса — это просто специальные ссылки, используемые некоторыми алгоритмами, которые строят или используют деревья суффикса.
Что касается односимвольных узлов:Что делать, если есть внутренний node X, строка которого (т.е. Строка на пути от корня до X) состоит только из одного символа? По определению выше, X тогда не имеет суффикса. Однако вы можете предположить, что если бы у него была суффиксная ссылка, она указывала бы на корень node. Кроме того: если по определению выше внутренний node не имеет суффиксной ссылки, он должен быть односимвольным node, поэтому вы всегда можете предположить, что если суффиксная ссылка не присутствует во внутреннем node он должен быть односимвольным node, и поэтому node, который представляет суффикс s -1, является корнем node. (Некоторые алгоритмы могут фактически добавить явную ссылку суффикса, указывающую на корень node в этом случае.) Спасибо j_random_hacker за комментарий об этом.