Git-versiohallinnan matemaattiset perusteet
Pysyvä osoite
Verkkojulkaisu
DOI
Tiivistelmä
Työssä esitetään Git-versiohallintajärjestelmään liittyviä tietorakenteita ja toimintoja
matemaattisesta näkökulmasta. Kuvaillaan Gitin käyttämä tietojen tallennustapa ja
annetaan yleiskuva Gitin tärkeimmistä toiminnoista. Erityisen tarkasti Gitin toiminnoista
esitetään pakkausmenetelmä, tiedostojen erojen vertailu ja pakettitiedostoissa käytettävä
deltapakkaus.
Deflate-pakkausmenetelmästä tutustutaan sen käyttämään Huffman-koodaukseen, LZ77-
koodaukseen ja koodauskaavioiden pakkaukseen. Lisäksi määritellään deflate-pakatun
tietovirran rakenne.
Esitetään tiedostojen erojen vertailun matemaattinen määritelmä sekä näytetään miten
tähän liittyvä pisimmän yhteisen alijonon hakeva algoritmi voidaan toteuttaa erilaisilla
menetelmillä, joiden aikakompleksisuudet poikkeavat merkittävästi toisistaan.
Kuvaillaan Gitin pakettitiedoston rakenne ja sen muodostamisen algoritmeja. Lisäksi
annetaan matemaattinen määritelmä siinä käytetylle deltapakkaukselle ja esitetään deltapakkauksen
algoritmi ja siinä käytetty Rabinin sormenjälki.
Esitettävissä algoritmeissa esiintyy muutamia perusmenetelmiä kuten dynaaminen ohjelmointi,
ahnas algoritmi sekä hajota ja hallitse -menetelmä.
Kuvaus
Siirretty Doriasta