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

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

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

Визначення

Суфіксне дерево 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.

Див. також


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.