Myersalgoritmen

Myersalgoritmen, ofta kallad Myers differensalgoritm, är en metod för att beräkna det kortaste editskript som krävs för att omvandla en sträng A till en sträng B. Den utvecklades av Eugene W. Myers och publicerades 1986 i artikeln An O(ND) Difference Algorithm and its Variations. Algoritmen används främst i diffverktyg, patch-system och i versionskontrollprocesser för att visa och skapa skillnader mellan filer. Den hanterar insättningar och borttagningar som grundläggande redigeringar, medan substitution oftast tolkas som en borttagning följt av en insättning.

Algoritmen modellerar redigeringen som en graf mellan två strängar där varje punkt (i, j) motsvarar att i tecken från A och j tecken från B har behandlats. Vid varje steg D, som motsvarar antalet redigeringar som används hittills, undersöks diagonalerna k mellan -D och D. För varje diagonal lagras den längsta räknade x-koordinaten (furthest reaching). Därefter görs så kallade snake-rörelser där tecken som matchar räknas utan kostnad. När slutpunkten (N, M) nås har man ett kortaste editskript som beskriver hur man övergår från A till B.

Komplexiteten är vanligt uttryckt som O((N+M)D) tid och O(N+M) minne, där D är editdistansen mellan strängarna. I praktiken presterar algoritmen bra när D är litet, och minnes krav är begränsat till en linjär mängd. Eftersom substitutioner normalt beaktas som en deletion plus en insertion används Myersalgoritmen ofta direkt för att generera patchar och diffar, vilket gör den central i många diff- och versionshanteringsverktyg.