http://sange.fi/~atehwa/cgi-bin/piki.cgi/ Recent changes in hierarkkisten tietorakenteiden diff-algoritmi http://sange.fi/~atehwa/cgi-bin/piki.cgi/hierarkkisten%20tietorakenteiden%20diff-algoritmi http://sange.fi/~atehwa/cgi-bin/piki.cgi/#1119876124 <p><ins>Ensinnäkin, diff-algoritmi on menetelmä, jolla etsitään kahden (enimmäkseen samankaltaisen) asian väliset eroavaisuudet (''diff''erences). 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.</ins> <p><ins>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.</ins> <p><ins>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.</ins> <p><ins>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</ins> <p><ins>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</ins> <p><ins>[kategoria: projektit]</ins> Mon, 27 Jun 2005 12:42:04 +0000