Priesagų medis

Priesagų medis (angl. suffix tree) – paieškos algoritmuose naudojama duomenų struktūra. Priesagų medis gali būti sukurtas kiekvienai netuščiai simbolių eilutei (T). Jis turi vieną šaknį ir tiek lapų, kiek eilutėje yra simbolių. Lapai sunumeruoti nuo 0 iki n-1, lapo numeriui atitinkant vienos iš galimų priesagų pradžią eilutėje. Iš viso gali būti tiek priesagų, kiek eilutėje yra simbolių (visa eilutė irgi laikoma priesagos variantu).

Kiekvienai šakai ar lapui i priskirta tokia simbolių seka, jog einant taku nuo lapo i iki šaknies, perskaitoma (atvirkščia tvarka) priesaga nuo eilutės simbolio T_i iki eilutės pabaigos. Nė viena šaka neturi dviejų kitų šakų ar lapų, kurių žymė prasidėtų tuo pačiu simboliu.

Priesagų medžio struktūra labai paranki įvairioms paieškoms eilutėje vykdyti. Tokie medžiai sėkmingai naudojami kuomet eilučių ilgis siekia daugelį milijonų simbolių (gyvųjų organizmų DNR sekos).

Trivialūs algoritmai priesagų medžiui sukurti reikalauja O(n²) operacijų ir bent kiek ilgesnėms eilutėms netinka. Bent du žinomi algoritmai (Ukkonen'o ir Weiner'io) sukuria priesagų medį naudodami tik O(n) operacijų. Priesagų medžiai naudojami vienoje populiariausių bioinformatikos programų .

Pavydys: sekos NA NELABAI NEGERAI priesagų medis, kuriame atlikta fragmento NE paieška (sklaustuose nurodyti anksčiau minėti lapų numeriai). Matyti, jog abiem šios eilutės pasirodymams surasti pakako vos trijų algoritmo žingsnių, per kuriuos paaiškėjo, jog fragmentas pasirodo dukart (padėtys 3 ir 11). '$' žymi eilutės pabaigą ir šiame pavyzdyje laikomas specialiu simboliu.

Iš pavyzdžio galėtų atrodyti jog medžiui saugoti reikia daug daugiau atminties nei užėmė pradinis eilutės tekstas. Iš tiesų taip nėra, nes teskto fragmentai medyje kartojasi ir naudojant nuorodas juos galima įsiminti tik vienąkart.

Šaltiniai

1. Gusfield, Dan (1999) [1997]. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. ISBN 0-521-58519-8.