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

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

У информатици, уопштено суфиксно стабло је суфиксно стабло за скуп ниски. За дати скуп ниски $D=S_1,S_2,\dots ,S_d$ укупне дужине $n$, то је радикс стабло које садржи свих $n$ суфикса ниски. Углавном се користи у биоинформатици.Шаблон:Ref

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

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

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

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

Пример

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

Алтернативе

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

Референце

• Шаблон:Note Шаблон:Cite conferenceШаблон:Мртва веза
• Шаблон:Note Шаблон:Cite conference
• Шаблон:Note Шаблон:Cite book