Как работают деревья Суффикса?

Question

Я просматриваю раздел структур данных в The Algorithm Design Manual и наткнулся на деревья суффикса.

Примерные состояния:

Вход:

XYZXYZ$ 
YZXYZ$ 
    ZXYZ$ 
    XYZ$ 
    YZ$ 
    Z$ 
     $ 

Выход:

Я не могу понять, как это дерево получает формируется из заданного входной строки. Деревья суффикса используются для нахождения данной подстроки в данной строке, но как это дерево помогает в этом? Я понимаю другой приведенный ниже пример три, но ниже, если ниже trie уплотняется до дерева суффикса, то как бы это выглядело?

Answer 1

Стандартные эффективные алгоритмы для построения дерева суффиксов, безусловно, нетривиально. Основной алгоритм для этого называется алгоритмом Укконена и является модификацией наивного алгоритма с двумя дополнительными оптимизациями. Вы, вероятно, лучше всего читаете this earlier question, чтобы узнать, как его построить.

Вы можете построить суффикс дерева, используя стандартные алгоритмы вставки на radix tries, чтобы вставить каждый суффикс в дерево, но при этом wlil потребуется время O (п), который может быть дорогим для больших строк.

Что касается быстрого поиска подстроки, помните, что дерево суффиксов является сжатым trie всех суффиксов исходной строки (плюс некоторый специальный маркер конца строки). Если строка S является подстрокой исходной строки T и у вас есть три всех суффиксов T, вы можете просто выполнить поиск, чтобы увидеть, является ли T префиксом любой из строк в этом trie. Если это так, то T должна быть подстрокой S, так как все ее символы существуют в последовательности где-то в T. Алгоритм поиска подстроки дерева суффикса - именно этот поиск применяется к сжатому trie, где вы следуете за соответствующими ребрами на каждом шаге.

Надеюсь, это поможет!

Answer 2

Дерево суффикса в основном просто уплотняет пробелы букв вместе, когда нет выбора. Например, если вы посмотрите на правую сторону три в своем вопросе, после того, как вы увидели w, на самом деле есть только два варианта: was и when. В trie as в was и hen в when каждый по-прежнему имеет один узел для каждой буквы. В суффиксом дерева, вы бы поместить их вместе в двух узлов, имеющих as и hen, поэтому правая сторона вашего синтаксического дерева превратится в:

Answer 3

Я не могу понять, как это дерево генерируется из данной входной строки.

Вы по существу создаете патрицию со всеми суффиксами, которые вы указали. При вставке в patricia trie вы выполняете поиск корня для дочернего элемента, начинающегося с первого символа из входной строки, если он существует, вы продолжаете движение по дереву, но если это не так, вы создаете новый узел из корня.Корень будет иметь столько же детей, сколько уникальных символов во входной строке ($, a, e, h, i, n, r, s, t, w). Вы можете продолжить этот процесс для каждого символа во входной строке.

Деревни суффикса используются для нахождения данной подстроки в данной строке, но как данное дерево помогает в этом?

Если вы ищете подстроку «курица», затем начинайте поиск с корня для ребенка, который начинается с «h». Если длина строки в дочернем «h» затем продолжит обработку дочернего «h» до тех пор, пока вы не дойдете до конца строки или не получите несоответствие символов в строке ввода и дочерней строке «h». Если вы соответствуете всем дочерним «h», то есть вход «hen» соответствует «he» в дочернем «h», затем переходите к детям «h», пока не дойдете до «n», если он не сможет найти начало ребенка с "n", то подстрока не существует.

Compact Suffix Trie code:

└── (black) 
    ├── (white) as 
    ├── (white) e 
    │ ├── (white) eir 
    │ ├── (white) en 
    │ └── (white) ere 
    ├── (white) he 
    │ ├── (white) heir 
    │ ├── (white) hen 
    │ └── (white) here 
    ├── (white) ir 
    ├── (white) n 
    ├── (white) r 
    │ └── (white) re 
    ├── (white) s 
    ├── (white) the 
    │ ├── (white) their 
    │ └── (white) there 
    └── (black) w 
     ├── (white) was 
     └── (white) when 

Suffix Tree code:

String = the$their$there$was$when$ 
End of word character = $ 
└── (0) 
    ├── (22) $ 
    ├── (25) as$ 
    ├── (9) e 
    │ ├── (10) ir$ 
    │ ├── (32) n$ 
    │ └── (17) re$ 
    ├── (7) he 
    │ ├── (2) $ 
    │ ├── (8) ir$ 
    │ ├── (31) n$ 
    │ └── (16) re$ 
    ├── (11) ir$ 
    ├── (33) n$ 
    ├── (18) r 
    │ ├── (12) $ 
    │ └── (19) e$ 
    ├── (26) s$ 
    ├── (5) the 
    │ ├── (1) $ 
    │ ├── (6) ir$ 
    │ └── (15) re$ 
    └── (29) w 
     ├── (24) as$ 
     └── (30) hen$