Tiivistetty loppuosapuu

Normaali loppuosapuu ei täyty hyvän indeksitietorakenteen vaatimuksia, koska sen koko, eikä täten myöskään muodostamisaika, ole aina lineaarinen tekstin kokoon verrattuna. Loppuosapuutietorakennetta sopivasti modifioimalla saadaan kuitenkin tiiviimpi tietorakenne, Tiivistetty loppuosapuu. Tiivistetyn loppuosapuun koko on aina lineaarinen tekstin kokoon nähden. Loppuosapuu voidaan tiivistää kahdella eri menetelmällä:

1. Tiivistämällä ketjut, eli polut jotka muodostuvat solmuista, joista lähtee vain yksi linkki (kuva 5)-
2. Yhdistämällä puun yhteiset alipuut, mikä johtaa osasanaverkkoon (engl. directed acyclic word graph, dawg) (kuva 6).

Molempia menetelmiä voidaan käyttää yhdessä tai erikseen. Metodilla yksi muodostetussa puussa on kahdenlaisia kaaria, mikä aiheuttaa käytännön (ratkeavia) ongelmia. Metodilla kaksi muodostetut osasanaverkot eivät enää ole puita. Osasanaverkon polun päättävään solmuun voi liittyä monta loppuosaa. Tämä vaikeuttaa esimerkiksi loppuosien tekstipositioiden löytämistä.

Merkitään tekstistä $S$ muodostettua tiivistettyä loppuosapuuta $T(S)$:llä. Jokainen $T(S)$:n ketju tiivistetään yhdeksi kaareksi, johon liitetään yksittäisen merkin sijasta osoittimet ketjun merkkijonon muodostavaan tekstin $S$ alimerkkijonoon (kuva 5). Puulla $T(S)$ on korkeintaan $\vert S\vert-1$ lehtisolmua, koska jokaista $S$:n loppuosaa kohti on korkeintaan yksi lehtisolmu. Tästä seuraa, että $T(S)$:llä on korkeintaan $n-1$ sisäistä solmua, koska jokaisella solmulla on ainakin kaksi lasta. Näin ollen $\vert T(S)\vert \leq 2n-1$. Tiivistetyn loppuosapuun koko on siis aina enintään lineaarinen tekstin kokoon verrattuna.

Tiivistetty loppuosapuu voidaan muodostaan vastaavalla algoritmilla kuin normaali loppuosapuu ajassa $O(\vert T(S)\vert)= O(\vert S\vert)$ [Ukk93]. Tiivistetty loppuosapuu täyttää siis kaikki hyvän indeksitietorakenteen kriteerit.

Kuva 5: Tekstin $S = aabbabd$ tiivistetty loppuosapuu $T(S)$

Kuva 6: Tekstin $S = aabbabd$ osasanaverkko $Dawg(S)$

Kirjan [CR94] luvussa 6 osoitetaan osasanaverkon tilavaatimuksen olevan pahimmassa tapauksessa $O(n)$. Samassa luvussa esitetään algoritmi osasanaverkon muodostamiseksi lineaarisessa ajassa.