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

Из Википедије, слободне енциклопедије
Суфикс стабло за ниске ABAB и BABA. Суфиксне везе нису приказане.

У информатици, уопштено суфиксно стабло је суфиксно стабло за скуп ниски. За дати скуп ниски 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. Бројеви у лисним чворовим су број ниске и почетну позицију. Уочите како пролаз кроз лисне чворове слева у десно одговара сортираном поретку суфикса. Крајеви се могу означити нискама или јединственим симболима. Гране ка $ од корена нису приказане у овом примеру.

Алтернативе[уреди]

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

Референце[уреди]