Sanojen vertailua

Seuraa 
Viestejä3654
Liittynyt9.10.2008

Tässäpä pieni pähkinä purtavaksi: tehtävänä olisi kehittää algoritmi, joka vertailee kahta sanaa ja palauttaa luvun väliltä [0,1] sen mukaan, kuinka "samankaltaisia" annetut sanat ovat. Sanoilla tarkoitetaan äärellismittaisia kirjainpötköjä. Etukäteen en halua tarkalleen määrätä sitä, mitä tuo samankaltaisuus tarkoittaa, mutta joitain reunaehtoja algoritmin toiminnalle kuitenkin asetan.

Merkitään f(x,y):llä algoritmin antamaa lukua sanoille x ja y.
Algoritmin pitää täyttää seuraavat ehdot:

1. f(x,y) = 1 täsmälleen silloin kun x=y (sanat ovat kirjain kirjaimelta samoja, esim. x="kissa" ja y="kissa")

2. f(x,y) = 0 täsmälleen silloin kun sanoilla x ja y ei ole yhtään yhteistä kirjainta (esim. x="kissa" ja y="lehmä")

3. f(x,y) = f(y,x) kaikilla x,y

4. f(x,y) > n/m , jos x ja y ovat m:n pituisia sanoja, joilla on samoilla paikolla n kirjainta ja eroavista kirjaimista jotkut esiintyvät molemmissa sanoissa. Esimerkiksi f("sika", "aika") > 0,75.

5. f(x,y) = n/m, jos x ja y ovat m:n pituisia sanoja, joilla on samoilla paikolla n kirjainta ja kukin eroava kirjain esiintyy vain toisessa sanoista. Esimerkiksi f("raha", "paha") = 0,75 (3/4 kirjaimista samoilla paikoilla ja eroavat kirjaimet r ja p esiintyvät kumpikin vain toisessa sanassa).

Mitään valmista algoritmia ei tarvitse tänne tuutata, vaan pienetkin ideat ovat tervetulleita. Ja jos tuntuu siltä, että jotain samankaltaisuussääntöjä pitää muuttaa tai lisätä, niin siitä vaan. Ihan hatusta nämäkin on vedetty.

EDIT: korjasin numeroinnin
EDIT2: poistin yhden säännön...
EDIT3: ... ja lisäsin yhden (vähän haetaan ajatusta )

We're all mad here.

Kommentit (15)

Vierailija

Ihan nopeasti hatusta vedetty tämäkin:

Mitäs jos laskisi sanoille hashin ja vertailisikin sitä?

Silloin sanojen samankaltaisuuden voisi hakea vaikkapa puusta.

No joo.
*hakee takkinsa*

pöhl
Seuraa 
Viestejä875
Liittynyt19.3.2005

Mikä kohdista 1.,...,5.tuottaa ongelmia? Mielestäni haastavin noista kohdista on numero 4, joka sekin ratkeaa valitsemalla f(x,y)=(n/m+1)/2.

abskissa
Seuraa 
Viestejä3654
Liittynyt9.10.2008
Puuhikki
Mikä kohdista 1.,...,5.tuottaa ongelmia? Mielestäni haastavin noista kohdista on numero 4, joka sekin ratkeaa valitsemalla f(x,y)=(n/m+1)/2.



Pitäisi saada siis jonkinlainen perusteltu samanlaisuusarvio -- pelkästään noiden reunaehtojen täyttäminen ei riitä.

Yksi mahdollisuus olisi hyödyntää vaikkapa sanojen Levenshtein (tai Damerau–Levenshtein) -etäisyyttä DL(x,y) ja asettaa sitten

f(x,y) = 1 - DL(x,y) / max {len(x), len(y)}.

Mutta 4. kohta ei toteudu tuolla tavalla.

We're all mad here.

Vierailija

Tuosta tulee mieleen geenisekvenssien vertailu. Siellä samankaltaisuutta arvioidaan juuri kirjaimia vertailemalla. Ensimmäinen sekvenssi laitetaan x-akselille ja toinen y-akselille. Niiden väliin jäävään alueeseen muodostetaan matriisi, joka vetaa yksitellen kirjaimia. Matriisiin muodostuvat luvut voi laskea monella eri tavalla. Laskentakaavoissa huomiodaan sekvenssiin jäävät aukot. Jos siis esim ajatellaan sanaa "kisa" ja "kissa", pitäisi ensimmäiseen laittaa pieni tyhjä aukko (gap), että sekvenssit täsmäisivät. Gäpeistä saa sakkopisteitä, ja niiden pituutta ja tiehyttä voi säädellä ja rajoittaa ohjelman asetuksista.

Jos oletetaan että tällä kertaa rakennetaan matriisi, jossa 0=oikea kirjain 1=lähellä on oikea kirjain 2=vähän kauempana 3=vielä kauempana jne. Tällöin matriisiin muodostuu parhaimmillaan kulmasta kulmaan nollarivi. Jos sekaan jää aukkoja tai täsmäämättömä kirjaimia, ei nollariviä voida seurata aivan suoraa. Laitetaan ohjelma laskemaan pienimmän pistemäärän tuottava reitti matriisin kulmasta kulmaan, siten että se ynnää yhteen läpikuljettujen solujen arvot.

[code:1p5vkcz7]
a b c
a 0 1 2
g 1 1 1
c 2 1 0

[/code:1p5vkcz7]

Vierailija

Sanojen vertailussa ei liene merkitystä ovatko vertailtavat kirjaimet aakkosissa lähellä tai kaukana toisistaan mutta kylläkin äänneasultaan samankaltaisia, esim. ovat vokaaleja tai konsonantteja molemmat. Lisäksi samanlaisen kirjain sekvenssin esiintyminen molemmissa sanoissa vaikkakin hieman eri kohdissa osoittaa samankaltaisuutta, esim "petos" ja "tossu" vaikkei ainuttakaan kirjainta ole kohdakkain. Tässä nyt vain yksi näistä alussa toivotuista ajatuksista.

abskissa
Seuraa 
Viestejä3654
Liittynyt9.10.2008

Tuo geenisekvenssien vertailutapa muistuttaa jonkin verran Levehnstein-etäisyyden laskemista. Sanojen Levehnstein-etäisyys on siis yhtä kuin vaadittujen muutosten (kirjaimen poistaminen, lisääminen tai muuttaminen) määrä sanasta toiseen ja sen laskeminen onnistuu helpoiten juuri matriisin avulla.

korantin ehdotus ottaa kirjainten "etäisyydet" huomioon on myös mielenkiintoinen. Yksi vaihtoehto kirjainten samankaltaisuuden määrittämiseen äänneasujen sijaan olisi laskea etäisyydet QWERTY-näppäinkaaviosta. Tällöin sanojen vertailusta olisi hyötyä vaikkapa typojen korjaamisessa.

Luulisin, että Levehnstein-etäisyyttä vähän tuunamalla voisi saada tuon 4. kohdankin toimimaan. Jos vaikka kirjaimen lisääminen sanaan laskettaisiin vain 0,5 askeleeksi silloin kun toisessa sanassa esiintyy lisättävä kirjain, niin tuloksena voisi olla kaikki kohdat täyttävä algoritmi. Samalla voisi tietenkin viritellä kirjainten muuttamiseen noita ääntämis- tai typojuttuja. Entä jos esim. b:n muuttaminen p:ksi olisi vaikka vain 0,3 askeleen toimenpide kun taas vokaali<->konsonantti -muunnos olisi täyden 1 askeleen operaatio?

We're all mad here.

Vierailija

Keksin kurkata wikipediaan ja sieltäpä tulikin vastaan tähän liittyviä juttuja.

Sequence alignment on yksi taikasana, joka liittyy tähän threadiin erottamattomasti.
wikipedia: Sequence alignment

Aika hyvin naulan kantaan iskee myös Needleman-Wunsch algoritmi
wikipedia: Needleman-Wunsch algorithm

Siellä on myös valmista if-else koodia, jota hieman soveltamalla saattaisi päästä hyvin alkuun tässä sanapulmassa. Muitakin samankaltaisia algoritmeja on ja niihin kukin voi vielä keksiä itseään eniten miellyttävän pisteytyksen. Proteiini- ja DNA-sekvenssien "sovittelussa" (alignment mikä sitten onkaan suomeksi). Anyway pointtina oli vain vihjata, ettei tulta tarvitse uudestaan keksiä. Sen kun vain menee lähimmälle huoltsikalle ja ostaa sytkärin ja kaasugrillin. Tieteessähän pääsääntöisesti seistään jättiläisten hartioilla ja kurkotetaan vain millin verran ylöspäin, mutta silti ylemmäksi mitä edeltäjät ylsivät.

Vierailija

Tai sitten voisi syntetisoida noihin sanojen lausuntaan liittyvän foneettisen sonnan (soinnin), ja laskea raa'asti, mitä se signaali on syönyt. Sopivalla kvantisoinnilla öytpyt tuottaisi esimerkiksi skaalan:

- Ei mitään yhteistä
- Jonkin verran yhteistä
- Kohtalaisen paljon yhteistä
- Melko paljon yhteistä
- Aivan saatanasti yhteistä
- Perkele, ihan samoja sanoja, kaikki yhteistä

- torstai

Vierailija

Suomessahan onneksi sanat lausutaan ja kirjoitetaan samalla tavalla (poislukien muutamat harvat poikkeukset), joten IPA-foneettinen kirjoitus ei tässä hommassa ole mitenkään välttämätöntä. Englannin ja ranskan kohdalla sanojen samankaltaisuutta tai pikemminkin homofoonisuutta voisi näppärästi verrata juuri IPA kirjoitusasussa.

kts wikipedia: IPA

salai
Seuraa 
Viestejä7264
Liittynyt17.3.2005

Millähän systeemillä nuo oikolukuohjelmat ehdottavat korjauksia väärin kirjoitettuihin sanoihin, eikö niissä ole valmiita algoritmeja? Vai onko tarkoitus parantaa sellaista tai yleisemminkin rakentaa keinoälyä?

Muistelen jostain liki 30 vuoden takaa totena kerrotun (ainakin amerikoissa) oikolukua harrastetun siten, että kaksi kirjoittajaa latoi saman tekstin ja niitä tietokoneella vertaamalla etsittiin virheitä.

Tuossa oli kyllä sellainen ongelma, että tietynlaisiin sanoihin tekevät useat kirjoittajat samanlaisia virheitä mallia kilpailu -> kilapilu ja kypärä -> kyräpä - jollei pahempaakin.

Mitä tahansa edellä esitetyistä väitteistä saa epäillä ja ne voidaan muuttaa toisiksi ilman erillistä ilmoitusta. Kirjoittaja pyrkii kuitenkin toimimaan rehellisesti ja noudattamaan voimassa olevia lakeja.

Ding Ding
Seuraa 
Viestejä9031
Liittynyt16.3.2005
salai
Muistelen jostain liki 30 vuoden takaa totena kerrotun (ainakin amerikoissa) oikolukua harrastetun siten, että kaksi kirjoittajaa latoi saman tekstin ja niitä tietokoneella vertaamalla etsittiin virheitä.

Tuossa oli kyllä sellainen ongelma, että tietynlaisiin sanoihin tekevät useat kirjoittajat samanlaisia virheitä mallia kilpailu -> kilapilu ja kypärä -> kyräpä - jollei pahempaakin.


Tuolla menetelmällä löydetään varmaankin yli 99% tahattomista kirjoitusvirheistä. Se kai on hyvin epätodennäköistä, että kaksi latojaa tekee samassa sanassa samalla hetkellä täsmälleen saman kirjoitusvirheen, etenkin jos kumpikin yrittää olla huolellinen. Ellei kyseessä ole jokin "vakiintunut" kirjoitusvirhe kuten "San Fransisco", "Ruotsalainen" isolla kirjaimella kirjoitettuna tms.

Vierailija

Jos on tarkoitus etsiä kirjoitusvirheitä niin silloin tosiaan qwerty-näppiksessä vierekkäiset kirjaimet edustavat samankaltaisuutta. Juuri sivusuunnassa sormi harhautuu herkästi väärän näppäimen päälle ainakin itselläni.

kuningas
Seuraa 
Viestejä1246
Liittynyt10.12.2007

Laskisin korrelaation Ascii-koodattujen sanojen välille. Samat sanat tuottavat tällöin automaattisesti arvon 1.

War doesn't determine who's right but who's left.

There is no such thing as an atheist in a foxhole.

abskissa
Seuraa 
Viestejä3654
Liittynyt9.10.2008

Jep, kts ideoista.

Kirjoitusasun samanlaisuuden arviointi hoituu ilmeisen yksinkertaisesti jonkinlaisella "edit distance" -funktiolla. Jos pohjana käyttää vaikka tuota Damerau-Levehnstein-etäisyyttä ja muokkaa sopivasti editointitoimenpiteiden painokertoimia, saa aikaiseksi vaikka minkälaista typojen korjausta. Isojen sanastojen kanssa pelatessa pitäisi tietysti käyttää jotain indeksointia. Mutta noiden esittämieni 5 vaatimuksen täyttäminen ei loppujen lopuksi paljon vaadi.

Jos taas haluaa ottaa huomioon kirjainsekvenssit, asia mutkistunee oleellisesti. Wikipedian artikkelissa

http://en.wikipedia.org/wiki/Fuzzy_string_searching

mainitaan (suomalainen?) lähde (E. Ukkonen, Algorithms for approximate string matching), jossa pitäisi olla kuvattu sekvenssejäkin käsittelevä "edit-distance" -funktio.

Foneettisen asun samankaltaisuuden tunnistamiseen pelkkä IPA-asujen edit distance -vertailu ei luultavasti pelittäisi niin hyvin kuin toivoisi, ellei sitten jotenkin saisi hienosäädettyä editointioperaatioiden painokertoimia kohdalleen. Mielenkiintoinen ajatus sekin tosin: jos jostain saisi sopivassa muodossa hyvän ja laajan IPA - englanti - sanakirjan, voisi vaikka kirjoittaa ohjelman, joka korvaa annetusta tekstitiedostosta osan sanoista joillakin ääntämisasultaan hyvin lähellä olevilla sanoilla.

Mitä taas tulee pyörän uudelleen keksimiseen, niin sehän tässä vähän olikin pointtina: irroittaa vähän erilaisia lähestymistapoja ja ideoita ihan puhtaalta pöydältä ennen kuin kurkistaa niitä valmiita ratkaisuja.

We're all mad here.

Vierailija

Netissähän on dictionary.com, jossa tuo IPA on myös näytillä. Se ei tietenkään ole nätisti yhdessä tiedostossa daunittavissa, mutta äkkiäkös joku nikkaroi webcrawlerin tallentamaan moisen sanaluettelon. Oletettavasti tuommoinenkin lista on jo jossain olemassa... Tässähän on internet kyseessä. Siellähän on jo kaikki valmiiksi. Sen kun vain daunii ne jostain. Jos ei keksi mistä daunia, niin sitten vain rakentaa webcrawlerin tuohon hommaan ja laittaa sen viikon ajaksi surffailemaan taustalle.

Uusimmat

Suosituimmat