Diffalgoritme: hoe software ziet wat er precies is veranderd
Stel je hebt twee versies van hetzelfde Word-document: een oude en een nieuwe. Je wilt niet het hele document opnieuw doorlezen, maar alleen weten wélke zinnen zijn toegevoegd, verwijderd of aangepast. Een diffalgoritme (van het Engelse woord "difference", verschil) is precies daarvoor gemaakt: het is een stukje rekenÂmethode dat twee versies van een tekst of bestand met elkaar vergelijkt en zo compact mogelijk aangeeft wat er is veranderd.
Diffalgoritmes zitten verstopt in software die de meeste mensen dagelijks gebruiken zonder het te beseffen. Programmeurs gebruiken ze om bij te houden wie welke regel code heeft aangepast. Google Docs gebruikt ze om wijzigingen tussen apparaten te synchroniseren. Wikipedia laat er de "geschiedenis"-pagina van een artikel mee zien, met rode en groene tekstblokken voor verwijderde en toegevoegde stukken. Het idee is steeds hetzelfde: twee versies van iets vergelijken en de kleinste, meest logische lijst van wijzigingen vinden die de ene versie in de andere verandert.
Wat is het precies?
Een tekstbestand kun je zien als een rij regels, elk met een eigen inhoud. Een diffalgoritme splitst beide versies op in zulke regels (of, bij fijnere vergelijkingen, in woorden of losse tekens) en gaat op zoek naar de langste reeks regels die in beide versies ongewijzigd voorkomt, in dezelfde volgorde. Dit staat bekend als het "longest common subsequence"-probleem, kortweg LCS: de langste gedeelde deelreeks.
Alles wat niet in die gedeelde reeks past, wordt gemarkeerd als verwijderd (het stond alleen in de oude versie) of toegevoegd (het staat alleen in de nieuwe versie). Het resultaat heet een "edit script": een lijst instructies als "verwijder regel 12", "voeg na regel 40 twee nieuwe regels toe". Die lijst is precies wat je ziet als een diff-weergave, meestal met een min-teken voor verwijderde en een plus-teken voor toegevoegde regels.
Het probleem is dat een letterlijke, brute-force vergelijking van elke regel met elke andere regel bij grote bestanden onwerkbaar traag wordt. Daarom zijn er slimmere algoritmes ontwikkeld. Het bekendste is dat van informaticus Eugene Myers, die in 1986 een methode publiceerde die het probleem herschrijft als het zoeken naar de kortste route door een soort rooster van mogelijke wijzigingen. Zijn algoritme werkt in een tijd die evenredig is met het aantal verschillen tussen de bestanden, in plaats van met de totale bestandsgrootte, wat het in de praktijk snel maakt voor de meeste documenten en broncode.
Latere varianten proberen niet alleen snel te zijn, maar ook "leesbare" diffs te maken. Een puur wiskundig kleinste verschil is niet altijd het verschil dat een mens het meest logisch vindt. Zo bestaat er "patience diff", dat zich eerst richt op regels die maar één keer voorkomen in beide versies als ankerpunten, en "histogram diff", een snellere variant daarvan. Deze worden vooral gebruikt in versiebeheersystemen voor broncode, omdat programmeurs vaak liever een diff zien die aansluit bij hoe zij de wijziging zelf zouden beschrijven.
Wat wil men ermee bereiken?
Het hoofddoel van een diffalgoritme is efficiëntie: in plaats van een heel bestand opnieuw te versturen of op te slaan wanneer er maar een paar regels veranderen, hoeft alleen het verschil te worden bewaard of doorgestuurd. Dat scheelt opslagruimte en internetverkeer, en het maakt het mogelijk om de volledige geschiedenis van een document te bewaren zonder telkens complete kopieën te hoeven maken.
Een tweede doel is begrijpelijkheid. Programmeurs die samenwerken aan dezelfde code moeten snel kunnen zien wat een collega heeft gewijzigd, zonder het hele bestand opnieuw te lezen. Een goede diff maakt reviewen van wijzigingen sneller en vermindert de kans dat fouten onopgemerkt blijven.
Een derde doel is het mogelijk maken van samenvoegen ("merging"): als twee mensen tegelijk aan hetzelfde document werken, moet software kunnen bepalen of hun wijzigingen elkaar tegenspreken of naast elkaar kunnen bestaan. Dat proces, bekend als een "drieweg-vergelijking" (diff3), bouwt voort op hetzelfde basisprincipe maar vergelijkt drie versies tegelijk: de gemeenschappelijke basis en de twee aangepaste versies.
Voorbeelden uit de praktijk
Het Unix-commando diff, dat teksten regel voor regel vergelijkt, gaat terug tot een technisch rapport van James W. Hunt en Douglas McIlroy bij Bell Labs uit 1976. Hun methode legde de basis voor decennia aan latere verbeteringen en is de reden dat "diff" ook als los werkwoord in programmeursjargon is beland.
De GNU-variant hiervan, GNU diffutils, is de vrije-software-implementatie die op de meeste Linux-systemen standaard aanwezig is en ook de commando's diff3 en sdiff voor samenvoegen bevat.
Het versiebeheersysteem Git, ontwikkeld door Linus Torvalds en sindsdien de standaard voor het bijhouden van broncode, gebruikt van oorsprong een variant van het Myers-algoritme, maar laat gebruikers ook kiezen voor patience- of histogram-diff wanneer de standaardweergave onoverzichtelijk is, bijvoorbeeld bij grote herstructureringen van code.
Google publiceerde de opensource-bibliotheek diff-match-patch, geschreven door ontwikkelaar Neil Fraser, die diff-, match- en patch-functies combineert voor platte tekst. Deze bibliotheek is gebruikt in producten die tekst tussen apparaten moeten synchroniseren, zoals samenwerkfuncties in tekstverwerking.
Buiten de klassieke, regelgerichte diff bestaat er onderzoek naar "semantische" diff-tools, die niet naar regels maar naar de boomstructuur van code kijken (de zogeheten "abstract syntax tree" of AST). Een bekend academisch voorbeeld is GumTree, voorgesteld door onderzoeker Jean-Rémy Falleri en collega's in 2014, dat verplaatste of hernoemde codeblokken beter herkent dan regel-voor-regel-diffs.
Hoe ver is de techniek?
Voor gewone tekst en broncode is diffalgoritmiek een volwassen en breed uitontwikkeld vakgebied. De kernalgoritmes zijn tientallen jaren oud, grondig onderzocht en efficiënt genoeg om vrijwel overal probleemloos te werken, ook op grote bestanden. Verrassingen zijn hier zeldzaam; het is meer gevestigde techniek dan een snel evoluerend onderzoeksveld.
Waar nog wel actief aan gewerkt wordt, is het beter omgaan met situaties waarin een letterlijke regelvergelijking niet de meest logische uitleg van een wijziging oplevert. Denk aan code die is verplaatst naar een andere plek in hetzelfde bestand, of aan structurele herschrijvingen waarbij de betekenis gelijk blijft maar de tekst er compleet anders uitziet. Volledig boomgebaseerde (AST-)diff is rekenkundig lastiger dan regelgebaseerde diff: het exact vergelijken van boomstructuren is in het algemene geval een computationeel zwaar probleem, waardoor praktische tools met slimme benaderingen werken in plaats van met een garantie op de wiskundig kleinste oplossing.
Een recentere ontwikkeling is dat diff-uitvoer steeds vaker als invoer dient voor AI-gebaseerde code-reviewtools, die op basis van een diff in gewone taal samenvatten wat een wijziging betekent of waar risico's zitten. Dat is overigens geen nieuw diffalgoritme, maar een extra laag bovenop de bestaande, klassieke technieken. Hoe betrouwbaar zulke AI-samenvattingen in de praktijk zijn, verschilt sterk per tool en staat los van de onderliggende diffberekening zelf.
Wie werken eraan?
Diffalgoritmiek is grotendeels een opensource- en academische aangelegenheid, zonder één dominant bedrijf of land. Belangrijke basiswerken komen van individuele onderzoekers, zoals Hunt en McIlroy bij Bell Labs en Eugene Myers, destijds verbonden aan de universiteit van Arizona. Het GNU-project onderhoudt de veelgebruikte diffutils als vrije software. Google heeft met medewerker Neil Fraser een eigen, veelgebruikte diff-bibliotheek opengesteld. De ontwikkeling van Git en zijn diff-varianten gebeurt via een wereldwijde gemeenschap van vrijwillige bijdragers, met steun van bedrijven als GitHub en GitLab die op Git-technologie voortbouwen. Onderzoek naar geavanceerdere, structuurgerichte diff-methodes zoals GumTree komt vooral uit universitaire software-engineeringgroepen, gepubliceerd op internationale vakconferenties.