Text parsing ·
Local string diffing: how Levenshtein distance works in JavaScript
Levenshtein distance is the minimum insertions, deletions, and substitutions between two strings. The classic DP table is (n+1)*(m+1) integers. Two 100k-character documents will exhaust a tab. Production diff uses Myers or Hunt-McIlroy on tokens. All of it can run in JavaScript. None of it requires uploading contracts.
The DP recurrence
dp[i][j] = min of delete, insert, substitute. Space can be two rows. Time remains O(nm). That bound is the reason we do not naively distance whole files.
Myers and the npm diff package
Line hashing, then longest common subsequence style edits. The text-diff tool uses this family. Good enough for patches humans read.
Tokenization
Split lines, then words. Unicode: reuse Segmenter ideas from the word-counter article. Regex split is the usual footgun.
Privacy of redlines
Legal and HR compare is confidential. Cloud “diff this PDF” is Post 7 again. Keep both versions in Blobs in the tab.
Progress and cancellation
AbortController into a worker. Show percent on line chunks. Same UX as file hashing.
Frequently asked questions
Is Levenshtein what Git uses?
No. Git uses Myers and variants on lines. Levenshtein is the teaching distance and a poor default for documents.
Word-level or character-level?
Word-level is faster and more readable for prose. Character-level is for code and legal exactness. Offer both.
Why a worker?
Diff is CPU-bound. A 2 MB vs 2 MB compare will hitch input handlers if it runs on the UI thread.