Суфіксне дерево
Суфіксне дерево — основана на дереві структура даних. Знаходить застосування в алгоритмах на рядках.
прабаба. Кожен підрядок завершується спеціальним символом $. Сім шляхів від кореня до листів (показані квадратами) відповідають семи суфіксам.Визначення
Суфіксне дерево T для рядка S довжини m це орієнтоване дерево, що має m листів пронумерованих від 1 до m. Кожна вершина, окрім кореня, має щонайменше два відгалуження, кожне ребро марковане непорожнім підрядком з рядка S. Жодна вершина не може мати ребра, маркування яких починається з однакової літери.
Головною особливістю суфіксного дерева є те, що конкатенація маркувань ребер на шляху від кореня до листа i дає суфікс рядка S починаючи з i-ї літери.
Суфіксне дерево існує не для кожного рядка. Якщо суфікс рядка збігається з його префіксом (наприклад, рядок xabxa) то шлях для першого суфікса не зможе бути завершений в листі, в графі з'явиться цикл. Цієї проблеми можна уникнути, якщо до рядка додати літеру, яка в ньому не зустрічається. Зазвичай, цю літеру позначають $.
Історія
Перший алгоритм побудови суфіксного дерева за лінійний час був запропонований Вайнером в 1973 році[1]. Алгоритм був істотно спрощений МакКрейтом в 1976 році[2] та Укконеном в 1995 році[3][4]. Алгоритм Укконена може будувати дерево по одній літері з швидкодією на рівні найшвидших алгоритмів того часу. Ці алгоритми побудови суфіксних дерев мають лінійний час роботи для скінченного алфавіту, а найгірший час роботи складає в загальному випадку.
Фарах в 1997 році[5] запропонував оптимальний алгоритм побудови суфіксних дерев для всіх алфавітів. Зокрема, це перший алгоритм побудови суфіксного дерева для рядка з алфавітом з цілих чисел в поліноміальному діапазоні. Цей алгоритм служить основою для нових алгоритмів побудови як суфіксних дерев, так і суфіксних масивів.
Властивості
Оскільки всі внутрішні вершини суфіксного дерева крім кореня мають щонайменше два відгалуження, кількість таких вершин не може перевищувати n − 1; а загальна кількість вершин не перевищує n + (n − 1) + 1 = 2n, із них: n листів, n − 1 внутрішніх вершин окрім кореня, 1 корінь.
Застосування
Суфіксні дерева та суфіксні масиви знаходять широке застосування для розв'язання задач на рядках у прийнятний час. Наприклад, задача з'ясувати, чи входить взірець P до рядка S із побудованим суфіксним деревом може бути розв'язана за час O(|P|). Узагальненні суфіксні дерева знаходять застосування при пошуку найдовшого спільного підрядка.
Література
- Weiner, P. (1973). Linear pattern matching algorithm. 14th Annual IEEE Symposium on Switching and Automata Theory. с. 1–11. doi:10.1109/SWAT.1973.13.
- Gusfield, Dan (1999). Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press. ISBN 0-521-58519-8.
- Srinivas Aluru (2005). 29. Suffix Trees and Suffix Arrays. У Dinesh P. Mehta, Sartaj Sahni. Handbook of Data Structures and Applications. Chapman & Hall/CRC. ISBN 1-58488-435-5.