Diff

A diff fájlösszehasonlító program, amely két bemeneti fájl közötti különbségeket írja a kimenetre. A klasszikus diff szövegfájlokat hasonlított össze soronként, de a modernebb implementációk már bináris fájlokon is tudnak dolgozni.[1]

A diff program kimenetét hívják diff-nek vagy patch-nek. Az utóbbi elnevezés a patch program nevéből jön, ami a diff kimenetét tudja alkalmazni valamely fájlra.

Történet

A diff programot a 70-es évek elején kezdték fejleszteni Unix operációs rendszeren. Az első prototípust James W. Hunt készítette. A végső verzió, amely a Unix ötödik verziójában jelent meg 1974-ben, teljes egészében Douglas McIlroy munkája. Az ezzel kapcsolatos kutatási eredményeket 1976-ban tették közzé közösen írott cikkükben.[2]

Később a GNU Projekt is megalkotta és diffutil csomagként közzétette a saját diff eszközét, amely az Eugene W. Myers által leírt algoritmus szerint működik.[3] Ez egy nyílt forráskódú implementáció, a GNU GPL licenc alatt használható. A legtöbb Linux disztribúciónak részét képezi a GNU diff, de léteznek Windows platformokra lefordított bináris változatai is.

Algoritmus

A diff működése a leghosszabb közös részsorozat probléma megoldásán alapul. Keresendő két adott sorozatra egy olyan harmadik sorozat, amely mindkét sorozatnak részsorozata. További feltétel, hogy a leghosszabb ilyen sorozatot kell meghatározni.

Legyen például a két adott sorozat a következő:

       a b c d f g h j q z

       a b c d e f g i j k r x y z

Olyan sorozatot keresünk, amely előáll mindkét bemeneti sorozatból elemek törlésével. Az ilyen részsorozatok közül keresendő a leghosszabb. Esetünkben ez a következő:

       a b c d f g j z

A leghosszabb közös részsorozat meghatározása után már csak egy kis lépés a diff-szerű kimenet előállítása:

       e   h i   k   q r x y 
       +   – +   +   – + + +

Használat

A diff használatakor két bemeneti fájlt kell megadni:

diff eredeti új

Ekkor a diff kimenete azon változások listája lesz, amelyeket ahhoz kell végrehajtani, hogy az eredeti fájlból megkapjuk az új fájlt. Ha az eredeti és az új fájlok könyvtárak, akkor az eltérések listája a könyvtárakban található minden fájlra vonatkozik. A -r opció megadásakor a program rekurzívan működik, azaz bejárja a teljes alkönyvtárrendszert a megadott könyvtárak alatt:

diff -r eredeti új

Források

1. MacKenzie et al. "Binary Files and Forcing Text Comparison" in Comparing and Merging Files with GNU Diff and Patch. Letöltés: 2007. április 28.[1]
2. James W. Hunt and M. Douglas McIlroy (June 1976). „An Algorithm for Differential File Comparison”. Computing Science Technical Report, Bell Laboratories 41. 
3. Eugene W. Myers (1986). „[An O(ND) Difference Algorithm and its Variations]”. Algorithmica No. 2 1, 251-266. o. 

diffutil manual