Üldistatud teisenduskaugus ja selle rakendamine sõnastike päringumootorites

Sissejuhatus

Veebisõnastike ja -teatmeteoste päringumootorite puhul on kõige olulisemaks nõudeks see, et olemasolev informatsioon jõuaks kindlasti kasutajani - eeldusel, et kasutaja sisestab selle leidmiseks korrektse(d) otsisõna(d). Märksa vähem on tähelepanu pööratud juhtudele, kus kasutaja eksib otsisõna sisestamisel, olgu siis põhjuseks kiirustamisel tehtud trükiviga või tegelik teadmatus sõna kirjapildi suhtes.

Kasutajasõbralikud päringumootorid pakuvad sellistel juhtudel omalt poolt välja otsisõnega kõige sarnasemad vasted, enamasti lubades eksimusi paari tähe ulatuses. Kui aga seejuures lubatakse suvaliste tähtede äravahetamist, asendamist, kustutamist või lisamist, võib sarnaste vastete hulk paisuda suureks (eriti just lühikeste sõnade korral) ning sisaldada palju mitteintuitiivseid vasteid, mille seost otsisõnega on kasutajal raske näha.

Käesolevas veebiliideses kasutatakse üldistatud teisenduskaugust, et muuta infopäringuid paindlikumaks, lubades näiteks ladina tähtede kasutamist venekeelsetest tekstidest otsimisel ning inglisekeelsete sõnade otsimist hääldussarnasuse alusel.

Algoritmist

Üldistatud teisenduskauguse algoritm laiendab tavalist teisenduskaugust (Levenshteini kaugust), lubades lisaks tavalistele teisendusoperatsioonidele tekstispetsiifiliste lisateisenduste kasutamist. Alljärgnevalt võrdleme kahe näite abil tavalist teisenduskaugust ja üldistatud teisenduskaugust. Olgu otsisõneks "sõidab" ning me soovime leida selle sõna esinemisi eesti vanemast kirjakeelest (täpsemalt - Stahli tekstidest, vt veebiliidese sõnafail "Vana-Eesti sõnad"). Püüdes tavalise teisenduskauguse abil leida lähimat sarnast vastet, peame lubama vähemalt 3 viga ning saame tulemuseks küllaltki suure ligikaudsete vastete loendi (29 sõna), kus on muuhulgas

— teisenduskaugusel 3.0: südda söitap söimas söhda södda söda suddal sudda souda ...

Teine vaste on ilmselt see, mis meid tegelikult huvitab, ning üldistatud teisenduskauguse abil on võimalik see ülejäänud vastete seast esile tuua. Võtame kasutusele lisateisendused õ→ö, d→t, b→p koos piisavalt madala kaaluga (0.1) ning järgmine päring sama otsisõnega annab lähimaks vasteks

— teisenduskaugusel 0.3: söitap

Loodud lisateisendused võimaldavad ka teisi vanema kirjakeele sõnu nüüdisaegsetele lähendada, nt sõda→söda, seisab→seisap, heidab→heitap.

Paindlik otsing vene sõnastikus

Mitmed vene sõnastike päringuliidesed nõuavad enne kasutamist klaviatuuri seadistamist venekeelseks. Mõnikord pakutakse alternatiivina ka kirillitsa sümbolitega nuppe, et oleks võimalik nendele klikkides sõna tähthaaval sisestada. Otsinguliideseid, mis lubaksid translitereeritud tähtede kasutamist, küll leidub (vt näiteks Online dictionary), aga need toetavad enamasti üht kindlat transliteratsiooniviisi ega ole eksimuste suhtes (nt nn susisevate tähtede äravahetamine) piisavalt paindlikud. Näiteks TRANSLIT.CC konverteerib automaatselt klaviatuurilt sisestatud ladina sümbolid kirillitsasse, võimaldab sisestada ka pikki tekste ning suunata neid edasi teistesse otsimootoritesse (nt tõlke leidmiseks). Teise näitena võib vaadata Webster'i Vene-Inglise sõnastikku, mis on tervenisti üles ehitatud translitereeritud vene sõnadele ning kirillitsat üldse ei kasuta. Eesti veebipõhistes sõnastikes nõutakse valdavalt otsisõna esitamist kirillitsas, nt EKI Vene-Eesti sõnaraamat ning ASE Computers'i Vene-Eesti-Vene sõnaraamat; kasutajatele, kel puudub venekeelne klaviatuuriseadistus, pakutakse sõna sisestamiseks kirillitsa sümbolitega nuppe.

Sõna sisestamine ekraanil olevatele nuppudele klikkides on tülikas ja aeganõudev. Translitereeritud otsisõnu lubav päringuliides on kasutaja jaoks küll märksa mugavam, aga nõuab siiski eelteadmisi kasutatavate transliteratsioonireeglite kohta. Kui aga kasutaja on kuulnud ainult sõna hääldust ning tal pole täpselt teada, kuidas sõna kirjutatakse, ei anna ka jäigalt transliteratsioonireeglitest kinnipidav otsing häid tulemusi. Üldistatud teisenduskaugust kasutav päringumootor võimaldab siin suuremat paindlikkust, võimaldades üheaegselt:

• Otsida vasteid kirillitsas esitatud otsisõnade järgi;
• Otsida vasteid translitereeritud otsisõnade järgi, lubades ka samaaegselt mitme erineva transliteratsioonireeglite komplekti kasutamist;
• Lubada otsingul kõrvalekaldeid sõna kirjapildist hääldussarnasuse kasuks (nt tähtede s ja š äravahetamine);
• Lubada otsingul vigu (nt 1-2 tähe kustutamist, asendamist või lisamist);

Käesolevas veebiliideses on realiseeritud sellise päringuliidese prototüüp (vt otsingut koos sõnafailiga "Venekeelsed sõnad").

Paindlik otsing inglise sõnastikus

Üks võimalus muuta inglise sõnastiku päringuliidest paindlikumaks on lubada sõnade otsingut hääldussarnasuse alusel. Töölauarakendustena on loodud mitmeid inglise sõnastikke (nt Writerpress Phonetic Finder, TheSage's English Dictionary and Thesaurus), mis toetavad ka foneetilist otsingut üle transkribeeritud sõnastiku ning lubavad paindlikuma otsingu eesmärgil metamärkide (wildcards) kasutamist. Selline otsing aga nõuab, et kasutaja tunneks transkriptsioonisümboleid. Kasutaja jaoks oleks ilmselt mugavam, kui ta saaks otsingul kasutada ka omakeelseid häälikuid ja tähti.

Käesolevas projektis on proovitud hääldussarnasusele tuginevat otsingut üles ehitada kahel viisil:

• Defineerides kirjapildile toetuvad lisateisendused, näiteks ait→ight sõnades knight, right, night ning oo→aw sõnades awesome, law, saw.


• Defineerides foneetilisele transkriptsioonile toetuvad lisateisendused, näiteks o→ɔ sõnades saw [sɔ:], shaw [ʃɔ:], law [lɔ:] ning ä→æ sõnades land [ˈlænd], apple [ˈæp(ə)l], catch [kætʃ].

Esimene lähenemisviis - kirjapildile toetuvad teisendused - toob paraku kaasa ka ebatäpsuse: sarnaste vastete hulka ilmub sageli sõnu, mille tegelik hääldus ei vasta etteantud hääldusele ning kasutaja peab muule informatsioonile/oma intuitsioonile tuginedes kindlaks määrama, milline tagastatud vastetest on õige. Meetodi plussiks on see, et kui on välja töötatud piisavalt universaalne lisateisenduste hulk, võib selle abil otsinguid sooritada mistahes inglise sõnastikul või tekstikorpusel.

Teine lähenemisviis on küll märksa täpsem - lubab päringu tulemusena tagastada tõesti ainult need vasted, mis - otsustades foneetilise transkriptsiooni järgi - on ka häälduse poolest sarnased. Ent kuna ei saa eeldada, et kasutajad oskavad hääldust "täpselt" kirja panna - nii mõnigi kord on sisestatud otsisõna segu kirjapildist ja hääldusest - ei pruugi ka ainuüksi seda meetodit kasutav otsing olla piisavalt paindlik.

Esimest meetodit kasutav otsing on realiseeritud ka käesolevas veebiliideses (vt otsingut koos sõnafailiga "EN-Inglise-Eesti"). Suuremat paindlikkust lubab kahe eeltoodud meetodi kombinatsioon, st päringuliides, mis viib otsingu läbi nii tavalisel kui transkibeeritud sõnastikul ning ühildab saadud tulemused. Sellise otsinguliidese prototüübina oleme realiseerinud veebiliidese "Ligikaudne otsing inglise sõnastikus". Testimine 500 juhuslikult valitud otsisõne peal näitas, et otsitud vaste satub 99 % juhtudest küll päringutulemuste hulka, ent 4 % juhtudest pole selle positsioon järjestatud tulemuste loendis esimeste vastete seas. Võimalik, et tulemusi annaks parandada täiendavate heuristikute kasutuselevõtuga:

• Arvestada päringutulemuste hindamisel otsisõne pikkust. Testimine on näidanud, et pikemate otsisõnede puhul võib saadud tulemustes kindlam olla ning lühikesed otsisõned (kuni ~7 sümboli pikkused) võivad vajada täiendavat loogikat otsitud vaste esiletoomiseks.


• Soodustada vasteid, milles otsisõne ja vaste prefiks langevad kokku.

Lisateisenduste loomine

Üldistatud teisenduskaugust kasutava päringumootori efektiivsus sõltub kasutatavast lisateisenduste hulgast. Järgnevalt vaatame võimalusi lisateisenduste hulga koostamiseks.

Käsitsi koostamine

Teisenduste käsitsi koostamisel tuleks tähelepanu pöörata järgmisele:

• Vaikimisi on suvalise tähe kustutamise/lisamise/asendamise hinnaks 1.0. Et loodud lisateisendus leiaks ka kasutamist, peaks see olema odavam, kui tavaliste teisendusoperatsioonide järjestrakendamine sama teisenduse saavutamiseks.
  • Kaalude määramisel võiks seada eesmärgiks, et "head vasted" jäävad teisenduskaugusele < 1.5. Kui vaste ja otsisõne vaheline teisenduskaugus on suurem kui 1.0, peaks see tähendama, et otsisõnes on (vähemalt) ühe tähega eksitud.


• Teisenduste rakendamine toimub paralleelselt: kord juba teisenduse läbi teinud sõneosasid enam uuesti ei teisendata. Näiteks teisendust aa→a ei saa rekursiivselt rakendada, et asendada teisendust aaaa→a.


• Sagedamini esinevad teisendused peaksid saama väiksemad kaalud. Merli Uus ja Markko Merzin, kes koostasid kirjapildile toetuvad hääldusteisendused (vt otsing sõnafailiga "EN-Inglise-Eesti" ning poster), kasutasid teisendusele kaalu määramiseks järgmist valemit:
  
  w(x→y) = (esinemistearv(x) / esinemistearv(x→y)⋅100)

Automaatne genereerimine

Automaatsel genereerimisel püütakse lisateisendused ja nende kaalud õppida etteantud sõnapaaridelt. Järgnevalt tutvustame lühidalt, milliseid lahendusi on automaatseks genereerimiseks välja pakutud.

• Parimatelt teisendusteedelt ja samasusteisenduste vahelt lisateisenduste õppimine.
  • Leiame parimad teisendusteed etteantud sõnepaaride vahel. Näiteks sõnepaari tuleb→tulleb vahel on parimaid teisendusteid kaks:

       t   u   l       e   b
       |   |   |       |    
       t   u   l   l   e   p
       ----------------------
       t   u       l   e   b
       |   |       |   |    
       t   u   l   l   e   p
               

  • Eraldame samasusteisenduste vahele jäävad teisendused. Eeltoodud näitepaari tuleb→tulleb puhul saame teisendused (_ tähistab tühisõnet):

       _ -> l
       b -> p
       b -> _
       _ -> p
               

  • Määrame genereeritud lisateisendustele kaalud.
    • Üks võimalus selleks on leida teisendusele kaal arvestades selle kasutamise tõenäosust õppesõnadel. Antud meetodi täpsem kirjeldus on toodud Reina Kääriku bakalaureusetöös "Üldistatud teisenduskauguse rakendamine sõnede sarnasuse hindamisel" (vt ptk "Üldistatud teisenduskauguse teisendustele kaalude leidmine").
    • Teine võimalus on läheneda iteratiivselt: genereerida igal iteratsioonil kõik (samasusteisenduste vahele jäävad) teisendused ning määrata kaalud vaid n kõige sagedamini esinevale teisendusele. Algoritmi täpsema kirjelduse leiab sellelt veebilehelt.


• Lisateisenduste genereerimine iteratiivselt, arvestades kaalude määramisel teisenduste rakendamissagedusi.
  • Erinevalt eelmises punktis toodud lahendustest ei genereerita lisateisendusi ainult samasusteisenduste vahelt, vaid genereeritakse kõik võimalikud (asendus-)teisendused, mis võivad aset leida ühe õppesõna teisendamisel teiseks. Lisamis- ja kustutamisteisendusi ei genereerita.
  • Kaalu määramisel võetakse arvesse nii teisi sama vasaku ja parema poolega teisendusi kui ka teisendatava ja saadava sõneosa pikkuseid.
  • Täpsemalt algoritmi tutvustuse leiab Martin Pettai projektitöö postrilt.