Пређи на садржај

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

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

У информатици, уопштено суфиксно стабло је суфиксно стабло за скуп ниски. За дати скуп ниски укупне дужине , то је радикс стабло које садржи свих суфикса ниски. Углавном се користи у биоинформатици.[1]

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

[уреди | уреди извор]

Стабло се може конструисати у временској и просторној сложености и може се искористити да се пронађе свих појављивања ниске дужине у времену, што је асимптотски оптимално (под условом да је величина азбуке константна, видети [2], pp. 119).

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

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

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

Алтернативе

[уреди | уреди извор]

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

Референце

[уреди | уреди извор]