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

У информатици, уопштено суфиксно стабло је суфиксно стабло за скуп ниски. За дати скуп ниски $D=S_{1},S_{2},\dots ,S_{d}$ укупне дужине $n$ , то је радикс стабло које садржи свих $n$ суфикса ниски. Углавном се користи у биоинформатици.^[1]

Функционисање

Стабло се може конструисати у $\Theta (n)$ временској и просторној сложености и може се искористити да се пронађе свих $z$ појављивања ниске $P$ дужине $m$ у $O(m+z)$ времену, што је асимптотски оптимално (под условом да је величина азбуке константна, видети ^[2], pp. 119).

Приликом прављења оваквог дрвета, свака ниска мора бити ограничена јединственим означавајућим симболом (или ниском) који је ван азбуке, како би се осигурало да ниједан суфикс није подниска неке друге, гарантујући да је сваки суфикс представљен јединственим лисним чвором.

Алгоритми за прављење УСТ укључују Уконенов алгоритам (1993) и МекКрејтов алгоритам (1976).

Пример

Суфиксно стабло за ниске ABAB и BABA је приказано на горњој слици. Ограничене су јединственим завршним нискама $0 и $1. Бројеви у лисним чворовим су број ниске и почетну позицију. Уочите како пролаз кроз лисне чворове слева удесно одговара сортираном поретку суфикса. Крајеви се могу означити нискама или јединственим симболима. Гране ка $ од корена нису приказане у овом примеру.

Алтернативе

Алтернатива за прављење уопштеног суфиксног стабла је да се ниске споје у једну, а потом да се направи обично суфиксно дрво или суфиксни низ за резултујућу ниску. Када се проналасци оцењују након претраге, глобалне позиције се мапирају унутар докумената, а локалне позиције уз помоћ неког алгоритма и/или структуре података, као што је бинарна претрага од почетка или краја документа.

Референце

^ Lucas Chi Kwong Hui (1992). „Color Set Size Problem with Applications to String Matching”. Combinatorial Pattern Matching, Lecture Notes in Computer Science, 644. стр. 230—243. ^{[мртва веза]}
^ Paul Bieganski; John Riedl; John Carlis & Ernest F. Retzel (1994). „Generalized Suffix Trees for Biological Sequence Data”. Biotechnology Computing, Proceedings of the Twenty-Seventh Hawaii International Conference on. стр. 35—44.
^ Gusfield, Dan (1999) [1997]. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. ISBN 0-521-58519-8.

[1]

[2]