Суфіксне дерево

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Визначення[ред.ред. код]

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

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

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

Історія[ред.ред. код]

Перший алгоритм побудови суфіксного дерева за лінійний час був запропонований Вайнером в 1973 році[1]. Алгоритм був істотно спрощений МакКрейтом в 1976 році[2] та Укконеном в 1995 році[3][4]. Алгоритм Укконена може будувати дерево по одній літері з швидкодією на рівні найшвидших алгоритмів того часу. Ці алгоритми побудови суфіксних дерев мають лінійний час роботи для скінченного алфавіту, а найгірший час роботи складає O(n\log n) в загальному випадку.

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

Властивості[ред.ред. код]

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

Застосування[ред.ред. код]

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

Примітки[ред.ред. код]

Література[ред.ред. код]

Див. також[ред.ред. код]