Перегляд вихідного коду сторінки Суфіксне дерево

[[Image:suffix_tree_prababa.png|thumb|250px|right|Суфіксне дерево для слова <code>прабаба</code>. Кожен підрядок завершується спеціальним символом <code>$</code>. Сім шляхів від кореня до листів (показані квадратами) відповідають семи суфіксам.]]
'''Суфіксне дерево'''&nbsp;— основана на [[Дерево (структура даних)|дереві]] [[структура даних]]. Знаходить застосування в алгоритмах на рядках.

== Визначення ==

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

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

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

== Історія ==

Перший алгоритм побудови суфіксного дерева за лінійний час був запропонований Вайнером в 1973 році<ref>{{harvtxt|Weiner|1973}}</ref>. Алгоритм був істотно спрощений МакКрейтом в 1976 році<ref>{{harvtxt|McCreight|1976}}</ref> та Укконеном в 1995 році<ref>{{harvtxt|Ukkonen|1995}}</ref><ref>{{harvtxt|Giegerich|Kurtz|1997}}</ref>. [[Алгоритм Укконена]] може будувати дерево по одній літері з швидкодією на рівні найшвидших алгоритмів того часу. Ці алгоритми побудови суфіксних дерев мають лінійний час роботи для [[Скінченна множина|скінченного алфавіту]], а найгірший час роботи складає <math>O(n\log n)</math> в загальному випадку.

Фарах в 1997 році<ref>{{harvtxt|Farach|1997}}</ref> запропонував оптимальний алгоритм побудови суфіксних дерев для всіх алфавітів. Зокрема, це перший алгоритм побудови суфіксного дерева для рядка з алфавітом з цілих чисел в поліноміальному діапазоні. Цей алгоритм служить основою для нових алгоритмів побудови як суфіксних дерев, так і [[суфіксний масив|суфіксних масивів]].

== Властивості ==

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

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

Суфіксні дерева та суфіксні масиви знаходять широке застосування для розв'язання задач на рядках у прийнятний час. Наприклад, задача з'ясувати, чи входить взірець ''P'' до рядка ''S'' із побудованим суфіксним деревом може бути розв'язана за час ''O''(|''P''|), найбільше загальне підстроювання двох рядків, лінеаризація циклічного рядка, завдання про підстроку для бази зразків. Узагальненні суфіксні дерева знаходять застосування при пошуку [[Пошук найдовшого спільного підрядка|найдовшого спільного підрядка]]<ref>{{harvtxt|Gusfield|1999}}</ref>.

== Примітки ==
{{reflist|2}}

== Література ==

* {{citation
 | last = Weiner | first = P.
 | contribution = Linear pattern matching algorithm
 | doi = 10.1109/SWAT.1973.13
 | pages = 1–11
 | title = [[Symposium on Foundations of Computer Science|14th Annual IEEE Symposium on Switching and Automata Theory]]
 | year = 1973
 | ref = harv}}
* {{citation
 | last = Gusfield | first = Dan
 | isbn = 0-521-58519-8
 | publisher = Cambridge University Press
 | title = Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology
 | year = 1999
 | ref = harv}}
* {{cite book | title = Handbook of Data Structures and Applications | chapter = 29. Suffix Trees and Suffix Arrays | author = Srinivas Aluru | editor = Dinesh P. Mehta, Sartaj Sahni | publisher = Chapman & Hall/CRC | isbn = 1-58488-435-5 | year = 2005 } | ref = harv }}

== Див. також ==

* [[Суфіксний масив]]
* [[Префіксне дерево]]


{{Datastructure-stub}}

{{Дерева (інформатика)}}
{{Рядки}}

[[Категорія:Дерева (структури даних)]]
[[Категорія:Рядкові алгоритми]]