M.Sc. Pengfei Xu väittelee perjantaina 19.2.2021 klo 14 Helsingin yliopiston Exactum-rakennuksen auditoriossa CK112 (Pietari Kalmin katu 5, pohjakerros) aiheesta Efficient Approximate String Matching with Synonyms and Taxonomies. Vastaväittäjänä toimii professori Jan Holub (Czech Technical University in Prague, Tšekin tasavalta) ja kustoksena professori Jiaheng Lu (Helsingin yliopisto). Väitöstilaisuus pidetään englanniksi. Väitöstilaisuutta voi seurata suorana verkkolähetyksenä osoitteessa https://helsinki.zoom.us/j/65651477920?pwd=K0NibW9OVTNpWGZCcnJ1M2d3NGtEUT09.
Pengfei Xun väitöskirja on osa Helsingin yliopiston tietojenkäsittelytieteen osastolla ja Unified Database Management Systems -ryhmässä tehtävää tutkimusta. Väitöskirjatyön ohjaajana on toiminut professori Jiaheng Lu (Helsingin yliopisto).
Tehokas likimääräinen merkkijonojen yhteensovittaminen synonyymien ja taksonomioiden avulla
Merkkijonoja esiintyy kaikkialla. Kun merkkijonoja kerätään erilaisista lähteistä, ne ovat usein yhteensopimattomia. Tämä tarkoittaa, että niillä voi olla sama merkitys riippumatta siitä, että ne ovat eri muodossa. Muotoon liittyvät eroavaisuudet voivat johtua esimerkiksi typografisista virheistä. Samanlaisten merkkijonojen löytäminen yhteensopimattomista tietoaineistoista on laajasti tutkittu kysymys viime vuosien aikana. Yhteisnimitys tälle suuntauksella on likimääräinen merkkijonojen yhteensovittaminen (approximate string matching).
Tämän työn päämääränä on parantaa merkkijonojen likimääräistä yhteensovittamista ottamalla typografisten virheiden lisäksi huomioon merkkijonojen merkitys. Tässä työssä keskitymme erityisesti hyödyntämään synonyymeja sekä taksonomisia luokittelujärjestelmiä, koska kummatkin ovat yleisesti saatavilla olevia tietolähteitä. Tutkimuksessamme on kummankin tyyppistä lähdettä käytetty joko kysely- tai liitostehtävissä. Kyselytehtävässä tarkoituksena on löytää annettua merkkijonoa vastaavat merkkijonot. Liitostehtävässä tarkoituksena on löytää ne merkkijonoparit, jotka vastaavat toisiaan. Tuloksena saadaan joko kaikki vastaavat merkkijonot haluttuun vastaavuuteen asti (all-match) tai ensimmäiset k kappaletta (top-k) eniten toisiaan vastaavia merkkijonoja.
Tämän työn ensimmäisen vastauksen top-k kyselyongelmaan annamme synonyymien avulla. Kehittämissämme algoritmeissa pyrimme erilaisiin optimaalisiin ratkaisuihin, kuten käytetyn muistin minimointiin, suoritusnopeuden maksimointiin sekä näiden yhdistelmään, jossa nopeus maksimoidaan samalla rajoittaen muistinkäyttöä. Jälkimmäinen ongelma on erikoistapaus 0/1 knapsack ongelmasta, ja ratkaisemme ongelman tehokkaan haarauta ja rajoita paradigman avulla (branch and bound paradigm).
Työn toinen vastaus top-k liitosongelmaan annetaan taksonomisten relaatioiden avulla. Tätä varten olemme kehittäneet kolme algoritmia, joista kaksi perustuu järjestettyihin listoihin ja yksi etuliitepuutietorakenteeseen (trie). Listojen läpikäymistä nopeutetaan etukäteen suoritettavilla alustuksilla. Etuliitepuihin perustuvaa algoritmia tehostetaan ennakoivasti poistamalla turhat haut puurakenteeseen. Kokeiden perusteella etuliitepuihin perustuvalla algoritmilla on erittäin nopea vastausaika, kun kyseessä on iso tietoaineisto.
Kolmas vastaus työssä käsittelee all-match liitosongelmaa taksonomisten relaatioiden tapauksessa. Osoitamme millä tavalla standardi etuliiterajausperiaate (prefix filtering principle) on vajavainen ja vastauksena tähän kehitämme mukautuvan rajausalgoritmin, joka on säädettävissä siten, että liitoksen muodostamiseen tarvittava aika voidaan minimoida. Tämän lisäksi laadimme datasta poimittaviin näytteisiin perustuvan algoritmin, jonka avulla voidaan arvioida paras parametri lyhyessä ajassa korkealla tarkkuudella.
Lopuksi työssä tutkimme all-match liitosongelmaa yhdistämällä typografiset virheet sekä synonyymien ja taksonomioiden käytön samanaikaisesti. Avainratkaisut tässä osassa pitävät sisällään yhtenäisen mitan merkkijonojen samankaltaisuudelle, jossa hyödynnämme useita vastaavaan tarkoitukseen kehitettyjä mittoja. Tähän liittyen kehitämme epätriviaalin algoritmin, jolla ongelmaa voidaan approksimoida ja jolla on vahva teoreettinen perusta. Lisäksi laadimme kaksi etuliiterajaukseen liittyvää periaatetta: nopean heuristisen periaatteen ja tarkan dynaamiseen ohjelmointiin perustuvan periaatteen. Näillä pyritään minimoimaan liitoksen muodostamiseen kuluva aika.
Väitöskirjan saatavuus
Väitöskirjan elektroninen versio on saatavilla Helsingin yliopiston e-thesis-palvelussa osoitteessa http://urn.fi/URN:ISBN:978-951-51-6988-4.
Painettuja väitöskirjoja voi tiedustella väittelijältä itseltään: pengfei.xu@helsinki.fi.