Tolerant Client-Side Search in the Context of a Learning Application
No Thumbnail Available
URL
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu |
Master's thesis
Authors
Date
2022-06-13
Department
Major/Subject
Computer Science
Mcode
SCI3042
Degree programme
Master’s Programme in Computer, Communication and Information Sciences
Language
en
Pages
91+7
Series
Abstract
The retrieval of documents from a dataset based on a search query is an important feature of user-facing services providing access to significant volumes of textual content. This thesis investigates and evaluates available methods for providing client-side full-text search functionality, capable of tolerating typographical errors and inflected word forms, in the context of a learning application with a focus on content in Finnish, Swedish, and English. Using one literary work for each language as a corpus, a selection of example queries is evaluated on several configurations of search systems. This provides a comparison between the capabilities of traditional inverted indices combined with a stemmer and a trie-based inverted index that performs approximate matching and retrieval, insight into the effects of utilizing n-gram indices for typographical-error tolerance and querying based on compound words or their components, as well as insight into the effects of performing an inflection-eliminating step. The results of each query are plotted on a recall-precision graph and compared. The results indicate significantly improved recall at the cost of a degree of precision resulting from the utilization of a trie-based index performing approximate matching for Finnish, with minor improvements in recall for English and Swedish. The use of an n-gram index for tolerance of typographical errors and compound-word-based search queries using a naive implementation demonstrates some degree of both efficacy and unreliability. Query speed measurements indicate that the use of n-gram indices and trie-based inverted indices incurs a significant cost on query speed, although average query duration does not exceed 60 milliseconds on the utilized datasets. It can be concluded that the utilization of a trie-based inverted index performing approximate matching offers a commendable solution for inflection tolerance in a highly inflectional language such as Finnish, at least on modest datasets, whereas the use of a stemmer alongside a traditional inverted index may be adequate for English and Swedish. In both cases, the addition of an n-gram index for the tolerance of typographical errors and compound-word-based retrieval offers modest improvements. The utilized techniques are generalizable to a wide variety of languages, although languages without word separators or strongly directional inflectional morphology may necessitate alternative techniques.Asiakirjojen paikantaminen aineistosta hakukyselyn perusteella on tärkeä toiminnallisuus käyttäjille kohdistuvissa palveluissa, jotka tarjoavat pääsyn laajaan kirjoon kirjallista sisältöä. Tämä työ tutkii ja arvostelee menetelmiä asiakasohjelman sisäisen sekä kirjoitusvirheitä ja sanojen taivutettuja muotoja sietävän tekstihaun toteuttamista varten suomen-, ruotsin- ja englanninkieliseen sisältöön keskittyvän opiskelusovelluksen asiayhteydessä. Joukko esimerkkikyselyjä suoritetaan ja kyselyjen tulokset arvioidaan useilla hakujärjestelmän konfiguraatioilla käyttäen yhtä kirjallista teosta kutakin tarkasteltua kieltä kohden koeaineistona. Tuloksena on vertailu perinteisen karsijalla varustetun käänteisindeksin ja etuliitepuuhun pohjautuvan epätäsmällisiä hakuja suorittavan käänteisindeksin välillä, näkymä n-grammi-indeksiin pohjautuvan kirjoitusvirheiden sietokykyä sekä yhdyssanojen ja yhdyssanojen osien perusteella hakemista tukevan kerroksen vaikutuksesta hakuprosessiin sekä katsaus sanojen taivutusta karsivan vaiheen vaikutuksesta hakuprosessiin. Kunkin testikyselyn tulokset piirretään saantitarkkuus -käyrälle ja testikyselyiden saantitarkkuus-käyriä vertaillaan. Tulokset osoittavat saannin parantuvan merkittävästi lievällä kustannuksella tarkkuudelle hyödyntäessä etuliitepuuhun pohjautuvaa käänteistä indeksiä suoritettaessa hakuja suomenkieliselle aineistolle, hyödyt suorittaessa hakuja englannin- ja ruotsinkielisille aineistoille jäädessä vähäisemmiksi. Kirjoitusvirheiden sietokyvyn sekä yhdyssanojen ja yhdyssanojen osien perusteella hakemisen yksinkertainen toteutus n-grammi-indeksillä osoittautuu toimivaksi mutta epäluotettavaksi. Hakukyselyjen nopeusmittaukset osoittavat, että n-grammi-indeksin ja etuliitepuuhun pohjautuvan käänteisindeksin käyttö hidastavat hakukyselyjä merkittävästi, vaikka hakukyselyjen keskimääräinen kesto ei ylitä 60 ms hyödynnetyillä testiaineistoilla. Tuloksista voidaan päätellä, että etuliitepuuhun pohjautuvan käänteisindeksin toimivuus suomen kaltaiselle vahvasti sanoja taivuttavalle kielelle on ainakin pienien aineistojen kohdalla erinomainen, kun taas englannin- ja ruotsinkielisille aineistoille perinteinen karsijalla varustettu käänteisindeksi saattaisi olla riittävä ratkaisu. Molemmissa tapauksissa n-grammi-indeksin lisäys kirjoitusvirheiden sietämisen sekä yhdyssanojen ja yhdyssanojen osien perusteella hakemisen saavuttamiseksi parantaa hakutuloksia. Hyödynnettyjä lähestymistapoja voi yleistää laajaan kirjoon kieliä, vaikkakin kielet, jotka eivät kirjoita sanoja erilleen tai suosi tiettyä suunnallisuutta taivutuksessaan saattavat vaatia vaihtoehtoisia lähestymistapoja.Description
Supervisor
Malmi, LauriThesis advisor
Virolainen, MattiTilanterä, Artturi
Keywords
information retrieval, inverted index, trie, Finnish, English, Swedish