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
[szerkesztés]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
[szerkesztés]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
[szerkesztés]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
[szerkesztés]- ↑ 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]
- ↑ James W. Hunt and M. Douglas McIlroy (June 1976). „An Algorithm for Differential File Comparison”. Computing Science Technical Report, Bell Laboratories 41.
- ↑ Eugene W. Myers (1986). „[An O(ND) Difference Algorithm and its Variations]”. Algorithmica No. 2 1, 251-266. o.
