Helsinki, December 3rd, 1999

Repetition-Based Text Indexes

Document archives, collections of World Wide Web pages and biological sequence databases are examples of large collections of textual data. Finding a specific piece of information in such data can take a lot of time, even by a computer. Text indexes are used for making the task faster. A familiar example of a text index is the index at the end of a book. Computerized versions of text indexes are used, for example, by Internet search engines.

An index at the end of a book lists only a selected set of words and phrases. If the relevant word or phrase is not among the selected ones, the index is of little help. This thesis studies text indexes that can find any string in the text. The size of such an index can be quite large, which is a problem with many known methods.

The thesis presents a new scheme for constructing text indexes. The idea of the scheme is to analyze the text to find information about repetitions in the text, and to use that information to build the index. An example of a repetition is a word that occurs several times in the text. All text indexes use repetition information in some form, and indeed, many known text indexes can be seen as special cases of the new scheme.

The thesis also presents new text indexes derived using the scheme. The new indexes do not use all the repetition information, only a selected subset of it. This way the size of the index is smaller. The small size comes at the cost of slower searching, but sometimes the smaller size is more important. Theoretical analysis shows that the new text indexes are better than previously known text indexes, when small size is required.

Helsinki, 3.12.1999

Toisteisuutta hyödyntävät tekstihakemistot

Elektroniset dokumenttiarkistot, World Wide Web -sivujen kokoelmat ja biosekvenssitietokannat ovat esimerkkejä suurista tekstimuotoisista tietovarastoista. Tietyn tiedon löytäminen tällaisesta tietovarastosta on työlästä jopa tietokoneelle. Tehtävää voidaan helpottaa käyttämällä tekstihakemistoja. Tuttu esimerkki tekstihakemistosta on kirjan lopussa oleva hakemisto. Tietokoneissa tekstihakemistoja käytetään mm. Internet-hakupalveluissa.

Kirjan lopussa oleva hakemisto sisältää vain joukon valittuja sanoja. Jos kiinnostava sana ei ole valittujen joukossa, hakemistosta ei ole paljon apua. Väitöskirjassa tarkastellaan tekstihakemistoja, joiden avulla voi löytää minkä tahansa merkkijonon tekstistä. Tällaisen hakemiston koko voi olla varsin suuri, mikä onkin ongelma monien tunnettujen hakemistorakenteiden tapauksessa.

Väitöskirja esittelee uuden menetelmän tekstihakemistojen muodostamiseen. Menetelmän ideana on analysoida tekstissä esiintyvää toisteisuutta ja käyttää näin saatua tietoa hakemiston rakentamiseen. Toisteisuutta on esimerkiksi sana, joka toistuu useasti tekstissä. Kaikki hakemistot käyttävät toisteisuutta jollain lailla hyväkseen ja monet tunnetut hakemistorakenteet voidaankin nähdä uuden menetelmän erikoistapauksina.

Väitöskirjassa johdetaan menetelmää käyttäen myös uudenlaisia hakemistorakenteita. Uudet hakemistot eivät hyödynnä kaikkea mahdollista tietoa toisteisuudesta vaan ainoastaan valikoitua osaa siitä. Tämän ansiosta hakemiston koko on pienempi kuin aiemmilla hakemistorakenteilla. Pienen koon hinta on hitaampi hakuaika, mutta joskus pieni koko on tärkeämpi. Teoreettinen analyysi osoittaa, että uudet hakemistot ovat aiempia parempia, kun pieni koko on oleellinen.

Helsingfors, 3.12.1999

Textindex baserade på upprepningar

Dokumentarkiv, samlingar med webbsidor och biologiska sekvensdatabaser är exempel på stora textbaserade datalager. Att hitta specifik information i sådana data kan vara tidskrävande även för en datamaskin. Uppgiften kan förenklas med hjälp av textindex. Ett välkänt exempel på ett textindex är registret i slutet av en bok. Datoriserade versioner av textindex används t.ex. i Internets sökmaskiner.

Ett bokregister innehåller bara en utvald mängd ord. Om det sökta ordet inte finns med i registret, har man inte mycket nytta av detta. I avhandlingen granskas index med vars hjälp man kan hitta vilken teckenföljd som helst i en text. Ett sådant index kan vara mycket stort, vilket ofta utgör ett problem vad gäller de flesta kända indexeringsmetoder.

Avhandlingen presenterar en ny metod för att konstruera textindex. Metoden går ut på att analysera de upprepningar som förekommer i texten och använda den erhållna informationen för att bygga ett index. Ett exempel på upprepning är ett ord som förekommer flera gånger i texten. Alla index använder sådan information om upprepningar på något sätt och flera kända indexstrukturer kan ses som specialfall av denna nya metod.

Avhandlingen visar även några nya textindex som konstruerats enligt den nya indexeringsmetoden. Dessa nya index baserar sig bara på en del av den information som finns om upprepningar i texten. På grund av detta är indexen mindre jämfört med äldre indexstrukturer. Priset för ett mindre index är en långsammare söktid, men ibland är den mindre storleken viktigare. Teoretisk analys visar att nya index är bättre än tidigare då storleken spelar en viktig roll.