Суфиксно стабло

Суфиксно стабло за стринг BANANA. Сваки подстринг се завршава симболом $. Путање од корена до листа одговарају суфиксима (6 суфикса - 6 путања) A$, NA$, ANA$, NANA$, ANANA$ и BANANA$. Бројеви у листовима означавају почетну позицију одговарајућег суфикса.

Суфиксно стабло представља структуру података која описује интерну структуру стринга (ниске) на врло исцрпан начин. Суфиксно стабло може да се употреби да би се решио проблем тачног тражења за линерано време (постижући исту сложеност у најгорем случају коју су постигли алгоритми КМП (Кнутх-Моррис-Пратт) и Бојер-Мур (Боyер-Мооре), али њихова предност је у могућности примене у алгоритмима линеарне сложености за проблеме са стринговима сложенијим од тачног тражења. Штавише, суфиксна стабла обезбеђују мост између проблема тачног тражења и приближног тражења.

Историја

Аутор првог алгоритма за конструкцију суфиксних стабала линеарне временске сложености је Вајнер (Wеинер) 1973. године, при чему је он за то стабло користио термин стабло позиција. Другачији, и што се тиче штедње простора приликом градње суфиксних стабала бољи алгоритам, дао је МекКрејт (МцЦраигхт) неколико година касније. Након тога, Уконен (Укконен) је развио концептуално другачији линерани алгоритам за изградњу суфиксних стабала који има све предности МекКрејтовог алгоритма (а детаљнија анализа показује да се он може сматрати варијантом МекКрејтовог алгоритма), али нуди много једноставније објашњење.

Ови алгоритми су линеарне временске сложености за азбуке константне дужине, и у најгорем случају имају временску сложеност $O(n\log n)$. Фарах (Фарацх) је 1997. осмислио први алгоритам за конструкцију суфиксних стабала који даје оптималне резултате за азбуке било којих величина. Фарахов алгоритам је постао основа за све новије алгоритаме за конструкцију суфиксних стабала и низова.

Дефиниција

Суфиксно стабло за стринг $S$ дужине знакова $m$ је коренско оријентисано стабло са тачно $m$ листова нумерисаних од $1$ до $m$. Сваки унутрашњи чвор различит од корена има најмање два сина и свака грана је означена непразним подстрингом за $S$. Никоје две гране које излазе из чвора не могу да имају ознаке гране које почињу истим знаком. Пошто не постоји суфиксно стабло које задовољава дату дефиницију за све стрингове, на $S$ се додаје један знак за крај, који није у алфабету, најчешће A$. Овим се осигурава да ни један суфикс коначног стринга не може да буде префикс ни једног другог суфикса. Кључна особина код суфиксних стабала је та, да за сваки лист $i$, конкатенација ознака грана на путу од корена до листа $i$, је једнака суфиксу $S$ који почиње на позицији $i$. Односно, да је $S[i..m]$ .

Уопштено суфиксно стабло

Уопштено суфиксно стабло је суфиксно стабло за више речи и садржи све суфиксе из те групе речи. Свака реч у оваквом стаблу мора бити завршена различитим терминалним симболом или речју.

Сложеност алгоритма

За азбуке константне величине, сложеност алгоритма суфиксног стабла $S$ дужине $n$ је $\Theta (n)$. За случај велике азбуке сложеност се повећава на $O(n\log n)$.

Сложеност за азбуке константне величине

За суфиксно стабло стринга $S$ дужине $n$, или генерализовано суфиксно стабло низа стрингова $D=\{S_{1},S_{2},\dots ,S_{K}\}$ укупне дужине $n=|n_{1}|+|n_{2}|+\cdots +|n_{K}|$ може се:

• Претраживати
  • Да ли је стринг $P$ дужине $m$ подстринг, за време $O(m)$.
  • Пронаћи прво појављивање секвенце стрингова $P_{1},\dots ,P_{q}$ укупне дужине $m$ као подстрингова, за време $O(m)$.
  • Пронаћи свих з појављивања секвенце стрингова $P_{1},\dots ,P_{q}$ укупне дужине $m$ као подстрингова, за време $O(m+z)$.
  • Тражити регуларни израз П за време линеарно $n$.
  • За сваки суфикс секвенце $P$, наћи дужину најдужег поклапања префикса из $P[i\dots m]$ са $D$, за време $\Theta (m)$. Ово се назива статистика поклапања за $P$
• Тражити својства стрингова
  • Наћи најдужи заједнички подстринг стрингова $S_{i}$ и $S_{j}$ за време $\Theta (n_{i}+n_{j})$.
  • Наћи ЛЗW декомпозицију за време $\Theta (n)$.
  • Наћи најдуже понављајуће подстрингове за време $\Theta (n)$.
  • Наћи најпонављаније стрингове одредјене дужине за време $\Theta (n)$.
  • Наћи најкраће стрингове из $\Sigma$ који се не појављују у $D$, за време $O(n+z)$, ако постоји $z$ таквих стрингова.
  • Наћи најкраће подстрингове који се појављују само једном за време $\Theta (n)$.
  • Наћи, за свако $i$, најкараћи подстринг $S_{i}$ који се не појављује нигде другде у $D$ за време $\Theta (n)$.

Примене

Суфиксна стабла имају сироку примену у решавању проблема при едитовању и претрази текста, компјутерској биологији и другим областима. Нека од примарних поља примене су:

• Тражење најдужег понављајућег подстринга
• Тражење најдужег заједничког подстринга
• Тражење најдужег палиндорма у стрингу

Једно од основних поља примене суфиксних стабала је биоинформатика. Проучавање генома је у највећој мери засновано на претраживању стрингова и налажењу одређених узорака у оквиру њих. Суфиксна стабла се такодје примењују на пољу компресије података и неке врсте ЛЗW компресије користе суфиксна стабла (ЛЗСС).

Конструкција суфиксног стабла

Еско Уконен (Еско Укконен) је направио алгоритам за конструкцију суфиксног стабла у линеарном времену који је концептуално најлакши алгоритам за конструкцију у линеарном времену.

Уконенов алгоритам конструише имплицитно суфиксно стабло $S_{i}$ за сваки префикс $S_{i}[1..n]$ за $S$, почевши од $I_{1}$ увећава за и док стабло $I_{m}$ не буде конструисано. Право суфиксно стабло $S$ за је конструисано из $I_{m}$ а време потрошено за цео алгоритам је $O(m)$. Уконенов алгоритам иницијално конструише стабло у времену $O(m^{3})$ да би се конструисала сва стабла $I_{i}$ а затим се оптимизовањем његове имплементације добија временски ниво сложености $O(m)$.

Основна структура Уконеновог алгоритма

Konstruiše stablo $T_{i}$
for i=1 to m-1
begin {faza i+1 }
      for j=1 to i+1
            begin {produženje j}
            Polazeći od korena nalazi se kraj puta označenog sa u tekućem stablu.
            Ako je potrebno, taj put se produžava dodavanjem znaka ,
            i time osigurava da je string u stablu.
      end;
end;

За разлику од Уконеновог алгоритма, Вајнеров алгоритам почиње целим стрингом $S$. Као и код Уконеновог алгоритма, уноси се по један суфикс у растуће стабло, али у битно различитом распореду. Вајнеров алгоритам конструише стабла од $T_{m}+1$ на доле до $T_{i}$.

Литература

• Gusfield, Dan (1999), Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, Cambridge University Press. ISBN 978-0-521-58519-4..
• МцЦреигхт, Едwард M. (1976), „А Спаце-Ецономицал Суффиx Трее Цонструцтион Алгоритхм”, Јоурнал оф тхе АЦМ, 23 (2): 262—272, дои:10.1145/321941.321946 .
• Фарацх, Мартин (1997), „Оптимал Суффиx Трее Цонструцтион wитх Ларге Алпхабетс”, 38тх ИЕЕЕ Сyмпосиум он Фоундатионс оф Цомпутер Сциенце (ФОЦС '97) (ПДФ), стр. 137—143, Архивирано из оригинала (ПДФ) 26. 05. 2018. г., Приступљено 01. 06. 2013 .
• МцЦреигхт, Едwард M. (1976), „А Спаце-Ецономицал Суффиx Трее Цонструцтион Алгоритхм”, Јоурнал оф тхе АЦМ, 23 (2): 262—272, дои:10.1145/321941.321946 .
• Укконен, Е. (1995), „Он-лине цонструцтион оф суффиx треес” (ПДФ), Алгоритхмица, 14 (3): 249—260, дои:10.1007/БФ01206331 .