Edit Distance

The foundational edit distance metric measuring the minimum number of single-character insertions, deletions, and substitutions required to transform one string into another. Each operation carries a uniform cost of 1. For example, transforming 'kitten' to 'sitting' requires three operations: substitute 'k' for 's', substitute 'e' for 'i', and insert 'g' at the end. This algorithm, published by Vladimir Levenshtein in 1965, remains the most widely implemented string distance measure and forms the conceptual basis for more complex document-level diff algorithms.

An extension of the standard Levenshtein distance that adds adjacent character transposition as a fourth permitted operation. This is critical for legal document comparison because it correctly handles common human typing errors such as 'recieve' vs 'receive' or 'judgment' vs 'judgement'. Each transposition carries a cost of 1. The algorithm is particularly valuable in fuzzy matching of party names, case citations, and defined terms where minor character swaps should not trigger false-positive change flags.

A dynamic programming algorithm that identifies the longest sequence of characters or lines appearing in the same relative order in two documents, though not necessarily contiguously. The LCS directly yields the minimal edit script: characters not in the LCS are deletions from the source, and characters not in the LCS from the target are insertions. For example, the LCS of 'ABCDEF' and 'ACBDF' is 'ABDF', revealing that 'C' was moved and 'E' was deleted. This algorithm underpins the standard Unix diff utility and is the computational engine behind most line-based document comparison tools.

An O(ND) greedy algorithm that finds the shortest edit script between two sequences by exploring an edit graph, where D is the number of differences and N is the total sequence length. Published by Eugene Myers in 1986, it operates by simultaneously exploring paths from both the top-left and bottom-right of the edit graph, converging at a middle snake. This algorithm is the actual implementation inside Git, Mercurial, and most modern version control systems. For legal documents, its efficiency is critical when comparing multi-hundred-page contracts where D is small relative to N.

A string similarity measure optimized for short strings such as names, giving higher weight to matching characters near the beginning of the string. The Jaro component measures the proportion of matching characters within a sliding window, while the Winkler modification boosts scores for strings sharing a common prefix of up to four characters. This is particularly effective for party name matching in legal documents where entities like 'Acme Corp' and 'Acme Corporation' should register as highly similar, while 'Acme Corp' and 'Zeta Corp' should not.

A semantic comparison method that converts text chunks into high-dimensional vector embeddings using models like BERT or Legal-BERT, then measures the cosine of the angle between them. Unlike character-level edit distance, this detects meaning-level changes even when wording is entirely different. For example, 'The Lessee shall indemnify the Lessor' and 'Tenant must hold Landlord harmless' would show high cosine similarity despite zero character overlap. This is essential for semantic differencing of legal clauses where parties rephrase obligations without changing their legal effect.