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

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

Суфіксне дерево для слова прабаба. Кожен підрядок завершується спеціальним символом $. Сім шляхів від кореня до листів (показані квадратами) відповідають семи суфіксам.

Визначення

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

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

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

Історія

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

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

Властивості

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

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

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

Примітки

1. Weiner, (1973)
2. McCreight, (1976)
3. Ukkonen, (1995)
4. Giegerich та Kurtz, (1997)
5. Farach, (1997)
6. Gusfield, (1999)

Література

• Weiner, P. (1973), Linear pattern matching algorithm, , с. 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 
• Srinivas Aluru (2005 }). 29. Suffix Trees and Suffix Arrays. У Dinesh P. Mehta, Sartaj Sahni (ред.). Handbook of Data Structures and Applications. Chapman & Hall/CRC. ISBN .

Див. також

• Префіксне дерево