Diffalgoritmes

Diffalgoritmes zijn procedures die twee reeksen data vergelijken om verschillen te vinden en een bewerkingsscriptt te produceren dat de ene reeks in de andere omzet. Ze worden vooral gebruikt bij tekstbestanden en broncodebeheer, maar ook bij binaire patches, synchronisatie en detectie van wijzigingen. Het resultaat wordt vaak weergegeven als een set toegevoegde, verwijderde of gewijzigde lijnen of segmenten.

Er bestaan verschillende benaderingen met eigen kenmerken. Veelgebruikte klassen zijn algoritmes gebaseerd op de langste gemeenschappelijke subsequentie (LCS), zoals het klassieke Myers-algoritme dat in O(ND)-tijd werkt, en Hunt–Szymanski die efficiënter is bij veel gedeelde elementen. Dynamische programmering (Wagner–Fischer) berekent edit distances maar kan duur zijn in tijd en geheugen. Patience- en histogram-algoritmes zijn heuristischer: ze leveren vaak menselijk leesbaardere verschillen en zijn sneller in praktijkgevallen. Voor binaire bestanden bestaan gespecialiseerde algoritmes zoals bsdiff die kleine, compacte patches maken.

Keuzes tussen algoritmes hangen af van prestaties, geheugengebruik en de wens om minimale versus heuristische oplossingen te produceren. Sommige systemen detecteren verplaatste blokken, andere niet. Implementaties verschijnen in gereedschappen als diff, git en versiebeheersystemen, die vaak meerdere strategieën aanbieden en tunen voor leesbaarheid en efficiëntie.