Являются ли ссылки суффиксов в дереве суффиксов такими же, как рёбра неудачи в ахо-коразическом автомате?

Question

Являются ли ссылки суффиксов в дереве суффиксов такими же, как рёбра неудачи в ахо-коразическом автомате?

Если да, может ли кто-нибудь объяснить назначение суффиксных ссылок в дереве суффиксов для точного сопоставления строк?

1

algorithm suffix-tree aho-corasick

Источник

user4806357 04 окт '16 в 15:52

1 ответ

Решение

Другие вопросы по тегам algorithm suffix-tree aho-corasick

user1794345 04 окт '16 в 16:07 2016-10-04 16:07 · Accepted Answer · 2016-10-04 16:07

Здесь ничего нет. Суффиксные ссылки - это конкретные переходы в дереве суффиксов. Учитывая состояние в дереве, представляющем подстроку (s_i), с 0 i + 1), с 0

Эти конкретные переходы используются во время построения дерева для быстрого обновления ветвей дерева при добавлении новых символов. Как следует из их названия, учитывая начальное состояние, представляющее строку S, если вы продолжаете следовать ссылкам суффикса, вы будете перечислять суффиксы S.

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

Как точное совпадение строк работает в дереве суффиксов? Вы идете по своему дереву. Если вы находитесь в узле, вы должны выбрать хороший переход, начиная с символа, соответствующего вашей строке. Если нет несоответствия, вы можете оказаться в явном состоянии (узел) или в неявном состоянии (в середине перехода): в этот момент вы знаете, что входная строка является подстрокой строки, представленной суффиксом дерево.