Mikähän olisi sopiva hakualgoritmi seuraavassa ongelmassa:
On pitkä jono lukuja, esim
34,12,14,10,29,15,16,14,17,36,15,12,16,14,33,14,
sitten minulla on pieni etsittävä lukujono, esim
32,17,14,16,12
Algoritmin pitäisi etsiä alkuperäisestä lukujoukosta eniten tuota etsittävää lukujonoa muistuttava pätkä.
Mikäpä lienee sopiva algoritmi tähän hommaan?
Vastaava algoritmi lienee käytössä esimerkiksi puiden vuosilustojen analysoijilla, dendrokronologeilla. Heillä on tiedossa parin tuhannen vuoden ajalta puiden vuosilustojen suhteelliset paksuudet. Kun jostain vanhasta rakennuksesta kairataan näyte ja mitataan siitä lustojen leveydet, niin nämä näytteet voidaan sijoittaa alkuperäiseen lustokarttaan, ja saadaan selville tarkka rakennuksen rakentamisvuosi.
Entä jos tuosta minun etsittävästä lukujoukosta puuttuu joku luku tai siinä on ylimääräinen luku, löytyykö oikea kohta siitä huolimatta? Ainakin nuo dendrokronologit osaavat etsiä oikean kohdan, vaikka joitakin lustoja puuttuu, tai laskennassa on joku ylimääräinen lusto, tosin heillä on pitemmät etsittävät jonot.
(Algoritmin haku Googlella tms ei onnistu, kun en keksi oikeita hakusanoja.)
No tuossa on kyllä aika epämääräistä, että millä tavalla "eniten muistuttava".
Käytännössä voinet käydä jokaisen lukujonon kohdan läpi ja laskea ko. kohdalle "hyvyysarvon", mutta se miten tuo lasketaan riippuu tarpeistasi. Ymmärsin että et kuitenkaan niitä vuosilustoja ollut hakemassa, vai?
Btw, en usko että vuosilustojen perusteella saisi selville rakennuksen tarkkaa rakennusvuotta. Niistä voi ehkä parhaimmillaankin saada selville, minä vuonna rakennuksessa käytetyt puut on kaadettu.
Tosiaan mitä tarkoittaa tarkalleen "eniten muistuttava"? Pieni ero tämän asian määrittelyssä voi vaikuttaa merkittävästi algoritmiin. Miten paljon lukuja voi olla yhteensä ja miten pitkä etsittävä lukujono voi olla? (Suuruusluokka riittää: kymmeniä, tuhansia vai miljoonia?)
Tässä voisi kuitenkin olla sopiva algoritmi:
Minulla tuo lukujono on noin 300 lukua. Etsittävä pätkä on noin 20 lukua.
Alkuperäisessä esimerkissä lähin vastine etsittävälle lienee lukusarja alkaen luvusta 36. Kai joku algoritmi osaisi todistaa tämän?
Täytyy tutkiskella tuota Levensteiniä, tosin se ei ehkä sovellu tuohon, mutta sivulla on mainittu myös muita algoritmeja. Hyviä vihjeitä otetaan edelleen vastaan.
Tuo puiden lustoesimerkki on ihan hyvä. 2000 vuoden ajalta on siis olemassa suhteelliset leveydet. Tutkittava puu (100 - 200 vuotta) on voinut kasvaa esim kalliolla, jolloin lustot ovat hyvin kapeita, tai puu on voinut kasvaa rehevässä maassa, jolloin lustot ovat leveitä. Puiden eliniän aikana on saattanut sattua esim myrskytuho, jolloin viereiset puut ovat kaatuneet, ja kyseinen puu on yhtäkkiä päässyt elelemään leveästi, ja lustot ovat yhtäkkiä kaikki leveämpiä siitä lähtien, kunnes ympäröivä metsä on taas alkanut vähitellen varjostaa. Tai tulipalo on polttanut neulasia, jolloin sinä vuonna on kasvu ollut tilapäisesti huomattavasti normaalia pienempi. Näistä huolimatta lustosarjoille löytyy yleensä aina sopiva kohta. Lustosarjat tehdään kai jollain tietokoneohjelmalla, eikä niiden algoritmista ole tietoa.
PS. Minun veneeni on venemökissä, jonka hirret on kaadettu vuonna 1793. Aluksi hirsistä on kai rakennettu savupirtti, sitten niistä on tehty heinälato, ja nyt se on siis venemökkinä. Entisaikoina hirret rakennuksiin on kaadettu yleensä edellisenä talvena, joten savupirtti lienee rakennettu vuonna 1794. Mikään muu ajoitusmenetelmä ei anna näin tarkkaa vuosilukua.
Levenštein-etäisyydessä voi säätää kolmea asiaa:
- kuinka paljon haittaa, jos välistä puuttuu lukuarvo
- kuinka paljon haittaa, jos välissä on ylimääräinen lukuarvo
- kuinka paljon haittaa, jos luvut eroavat
Esimerkiksi lukujonot 32, 15, 47, 26, 50 ja 30, 15, 23, 51 ovat melko lähellä toisiaan, koska ensimmäisen saa toiseksi poistamalla luvun 47 ja korjaamalla lukuja 32->30, 26->23 ja 50->51. Tässä Levenštein-etäisyys olisi luvun poistamisen haitta-arvo sekä lukumuunnosten haitta-arvot laskettuna yhteen. Jälkimmäiset olisivat varmaan pieniä, koska luvut ovat niin lähellä toisiaan.
Jos yllä oleva tapa tarkastella asiaa vaikuttaa järkevältä, ongelma on suunnilleen sama kuin likimääräinen hahmonsovitus (approximate pattern matching). Tämä liitetään usein merkkijonoihin, mutta yhtä hyvin kelpaavat lukujonot. Tässä on vielä toinen aiheeseen liittyvä linkki:
http://en.wikipedia.org/wiki/
Jos voidaan kuitenkin olettaa, että lukujonoista ei puutu lukuja eikä niissä ole ylimääräisiä lukuja, on helpompaa noudattaa Grezin neuvoa eli käydä läpi kaikki mahdolliset kohdat, joissa lyhyt lukujono voi esiintyä pitkässä lukujonossa, laskea jokaisessa kohdassa haitta-arvo jollain tavalla sekä valita pienimmän haitta-arvon tuottava kohta.
Aihe on jo aika vanha, joten et voi enää vastata siihen.