Суфіксне дерево — основана на дереві структура даних. Знаходить застосування в алгоритмах на рядках.

Визначення

Суфіксне дерево T для рядка S довжини m це орієнтоване дерево, що має m листів пронумерованих від 1 до m. Кожна вершина, окрім кореня, має щонайменше два відгалуження, кожне ребро марковане непорожнім підрядком з рядка S. Жодна вершина не може мати ребра, маркування яких починається з однакової літери.

Головною особливістю суфіксного дерева є те, що конкатенація маркувань ребер на шляху від кореня до листа i дає суфікс рядка S починаючи з i-ї літери.

Суфіксне дерево існує не для кожного рядка. Якщо суфікс рядка збігається з його префіксом (наприклад, рядок xabxa) то шлях для першого суфікса не зможе бути завершений в листі, в графі з'явиться цикл. Цієї проблеми можна уникнути, якщо до рядка додати літеру, яка в ньому не зустрічається. Зазвичай, цю літеру позначають $.

Історія

Перший алгоритм побудови суфіксного дерева за лінійний час був запропонований Вайнером в 1973 році. Алгоритм був істотно спрощений МакКрейтом в 1976 році та Укконеном в 1995 році. Алгоритм Укконена може будувати дерево по одній літері з швидкодією на рівні найшвидших алгоритмів того часу. Ці алгоритми побудови суфіксних дерев мають лінійний час роботи для скінченного алфавіту, а найгірший час роботи складає в загальному випадку.

Фарах в 1997 році запропонував оптимальний алгоритм побудови суфіксних дерев для всіх алфавітів. Зокрема, це перший алгоритм побудови суфіксного дерева для рядка з алфавітом з цілих чисел в поліноміальному діапазоні. Цей алгоритм служить основою для нових алгоритмів побудови як суфіксних дерев, так і суфіксних масивів.

Властивості

Оскільки всі внутрішні вершини суфіксного дерева крім кореня мають щонайменше два відгалуження, кількість таких вершин не може перевищувати n −  1; а загальна кількість вершин не перевищує n + (n − 1) + 1 = 2n, із них: n листів, n − 1 внутрішніх вершин окрім кореня, 1 корінь.

Застосування

Суфіксні дерева та суфіксні масиви знаходять широке застосування для розв'язання задач на рядках у прийнятний час. Наприклад, задача з'ясувати, чи входить взірець P до рядка S із побудованим суфіксним деревом може бути розв'язана за час O(|P|), найбільше загальне підстроювання двох рядків, лінеаризація циклічного рядка, завдання про підстроку для бази зразків. Узагальненні суфіксні дерева знаходять застосування при пошуку найдовшого спільного підрядка.

Див. також Суфіксний масив Префіксне дерево

Примітки

Література