Trie-puu

Kuva 3: Tekstin $S = aabbabd$ loppuosista muodostettu Trie-puu

Eräs yleisimmin käytetyistä sanakirjatietorakenteista on trie-puu. Tässä tutkielmassa trie-puut esitellään johdantona luvun 5.2 loppuosapuihin, sekä eräänä menetelmänä luvun 5.4 käänteistiedostojen toteuttamiseen. Eräs trie-puun sovellus, Aho-Corasick-automaatti esiteltiin jo aiemmin luvussa 4.4.

Määritellään $S_i$ tekstin $S$ kohdasta $i$ alkavaksi loppuosaksi $s_is_{i+1} ... s_n$. Koska jokaisesta tekstin positiosta $i$ alkaa loppuosa $S_i$, on selvää, että jokainen tekstin kohdasta $i$ alkava hahmo on tekstin loppuosan $S_i$ alkuosa. Näin ollen hahmontunnistus voidaan palauttaa hahmolla alkavan loppuosan paikantamiseen tekstistä. Yksinkertaisuuden vuoksi tekstin ajatellaan päättyvän loppumerkkiin, joka ei esiinny missään muualla tekstissä. Näin yksikään tekstin loppuosa ei voi olla toisen tekstin loppuosan aito alkuosa.

Kuvassa 3 on tekstin $S = aabbabd$ loppuosista muodostettu trie-puu. Merkitään tekstistä $S$ muodostettua trie-puuta $Trie(S)$:llä. Trie-puussa jokaiseen solmusta sen lapsiin lähtevään linkkiin on liitetty yksi tekstin merkki. Loppuosista muodostetun trie-puun jokaisen juuresta lehteen kulkevan polun linkkeihin liitetyt merkit muodostavat yhden tekstin loppuosan. Toisaalta kaikkia tekstin loppuosia kohden trie-rakenteessa on yksi lehti ja yksi loppuosan muodostava polku juuresta kyseiseen lehteen. Tällaista loppuosista muodostettua trie-puuta kutsutaan myös normaaliksi loppuosapuuksi.