Algorithmic Foundations of Diffing
Text diff checkers rely on computer science algorithms designed to solve the Longest Common Subsequence (LCS) problem. The LCS of two sequences is the longest sequence of elements that appears in both inputs in the exact same relative order, but not necessarily contiguously. By finding this shared backbone, a diffing engine can determine which parts of the text were deleted from the original version and which parts were added to create the new version.
Most modern diff engines implement the Myers Diff Algorithm, created by Eugene Myers in 1986. Myers' algorithm uses a greedy coordinate search on an edit graph to find the shortest edit script (SES)—the minimum number of insertions and deletions needed to transform string A into string B. The distance metric is closely related to the Levenshtein distance, which calculates the edit distance between strings. We can represent the similarity between two texts using the normalized formula:
; Similarity = 1 - \(D_L(A, B))/(; max(|A|, |B|))\
where D_L(A, B) is the Levenshtein distance, and |A| and |B| represent the character lengths of the two text inputs.