Applications of S-grams in Natural Language Information Retrieval

Abstract

Menetelmiä luonnollisen kielen variaation hallintaan tiedonhaussa

Tiedonhakujärjestelmät perustuvat ajatukseen, että dokumenteissa esiintyvät sanat kuvaavat niitä aihepiirejä joihin dokumentti liittyy. Tiedonhakujärjestelmät toimivat sitten siten että tiedonhakijan (käyttäjän) järjetelmälle esittämiä hakusanoja verrataan dokumenttien sanoihin. Dokumentit joiden sanastossa hakusanat ovat keskeisiä liittyvät todennäköisesti siihen aihepiiriin jota hakusanat kuvaavat ja ovat siten mahdollisesti relevantteja tiedonhakijalle.

Sanat esiintyvät teksteissä monissa eri muodoissa: sanat taipuvat ja sisältävät virheitä, niiden kirjoitusasu vaihtelee ajan myötä ja eri kielissä. Väitöskirjassani tutkin menetelmiä joiden avulla luonnollisessa kielessä esiintyvää variaatiota voidaan hallita siten että tiedonhakujärjestelmät voivat tunnistaa saman sanan eri muodot yhteenkuuluviksi. Esimerkiksi perusmuodossa esitetty hakusana pitäisi tunnistaa samaksi sanaksi kuin dokumenteissa esiintyvät taivutusmuodot. Olen keskittynyt tutkimuksessani yhden sumean merkkijonotäsmäytysmenetelmän, s-grammien, eri sovellusalueiden tutkimiseen. Olen käyttänyt menetelmää käännöksessä läheisten sukulaiskielten välillä, monikielisessä kuvatiedonhaussa, sekä historiallisten dokumenttien haussa.

Tutkimustulokseni osoittavat että yksinkertaisilla ja kieliriippumattomilla menetelmillä voidaan saavuttaa hyviä tuloksia. Etenkin s-grammit ovat sovellettavissa tilanteissa joissa korkealaatuisia kielitieteellistä informaatiota soveltavia menetelmiä ei ole syystä tai toisesta saatavilla.

Several phenomena cause words to occur in different surface forms in natural language texts including variation and fluctuations in the orthographical rules of languages, morphological variation, historical variation, and variation due to errors in optical character recognition (OCR) of digitized documents. This string level variation interferes with the word matching and weighting mechanisms of information retrieval. This thesis examines the use of approximate string matching methods for handling the string level variation occurring in alphabetic languages. An approximate string matching technique called classified s-gram matching is used for query translation and expansion in cross-lingual and historical retrieval scenarios. Test collection based evaluation methodology is adopted and three different test collections are used for analyzing the variation occurring in different types of collections, in different text domains and between different language pairs: (1) between the closely related languages Norwegian and Swedish in the news text domain, (2) between several European languages in a collection of lightly annotated photographic images, and (3) between contemporary and historical Finnish in a digitized historical document collection. The findings show that classified s-gram matching is a useful approach to handling the variety of string level variation that occurs in natural language document collections. It is well suited for modelling cross-lingual, historical and morphological variation in strings, as well as the most common OCR errors. The linguistic relations between the source and target languages, the text domain, and the morphological complexity affect the performance of the classified s-gram matching technique. It is best suited for applications where the target index can be expected to contain many relevant variants of the query words, and where query expansion through adding several of them to the queries is desirable. The optimal number of s-gram variants to be added to the target language queries depends on the target language and the collection. Only a few variants are needed for query translation in clean, lemmatized, bilingual collections, while dozens of variants may beneficially be added to queries in collections where combinations of many productive string level variation types occur.