Mikä on WikiWiki?
nettipäiväkirja
koko wiki (etsi)
viime muutokset
Ensinnäkin, diff-algoritmi on menetelmä, jolla etsitään kahden (enimmäkseen samankaltaisen) asian väliset eroavaisuudet (differences). Unixissa on aina ollut ohjelma nimeltä diff, joka vertailee kahta tiedostoa rivi riviltä ja kertoo, mitkä rivit ovat toisessa tiedostossa mutta toisesta puuttuvat, mitkä ovat sisällöltään erilaiset näissä kahdessa tiedostossa ja niin edelleen.
Rivi-diffiä sanotaan lineaariseksi diffiksi, koska se käsittelee lineaarisia jonoja, nimittäin kahden tiedoston rivien jonoja. Yleisempi diff-algoritmi on sellainen, jolla voi käsitellä hierarkkisia tietorakenteita. Hierarkkiset tietorakenteet ovat tyypillisesti jonoja, jotka voivat sisältää atomeita (eli tietotyyppejä, joiden sisäiseen rakenteeseen ei kiinnitetä huomiota) tai toisia samantyyppisiä hierarkkisia tietorakenteita. Esimerkiksi lista, joka voi sisältää huomautuksia ja toisia listoja, on hierarkkinen tietorakenne.
Hierarkkisen diffin olennaisin ongelma on päättää, kun tarkasteltavina ovat toisistaan eriävät tietorakenteet, onko muutos tietorakenteen sisäinen vai sen ulkopuolinen. Eli onko kyse "periaatteessa samasta" tietorakenteesta, johon on vain tehty muutoksia, vai onko kyse siitä, että kyseisestä kohdasta (sen sisältävässä tietorakenteessa) on poistettu, lisätty tai vaihdettu kokonainen alitietorakenne.
Hierarkkista diff-algoritmia varten on tehty paljon tutkimusta. En ole jaksanut perehtyä kunnolla aiheeseen, mutta ainakin täältä löytyy jotain: http://diffxml.sourceforge.net/docs/docs.html
Oma algoritmini yksinkertaisesti vertailee jokaista jonon 1 ja jonon 2 elementtiä ja valitsee sen vaihtoehdon (lisäys, poisto tai sisäinen muutos), joka tuottaa pienimmän muutosten summan. Muutosten määrä määritellään muutettujen atomien ja tyhjien jonojen määrän suhteena atomien ja jonojen kokonaismäärään. Nähtävissä täällä: http://sange.fi/~atehwa/credit/diff.ss