@krkarma777/string-diff

Fast text diff and string comparison library for JavaScript and TypeScript. Compare two strings by word, character, line, locale-aware word, or grapheme and get an exact shortest edit script (equal / insert / delete) by default, powered by Myers' O(ND) algorithm on typed arrays. An opt-in heuristic bounds search work on pathological inputs but may return a non-minimal script. Zero dependencies, Unicode-safe (Korean, CJK, emoji), ~3.9 KB min+gzip in the browser.

Use it for text comparison UIs, document revision history, editor change tracking, test output diffing, or anywhere you need to highlight the difference between two strings — in Node.js or any browser. Try the live demo.

Features

• Exact shortest edit script by default — the default path uses the exact Myers algorithm with the linear-space divide-and-conquer refinement (the same family git uses), and its output is verified optimal against a reference DP in the test suite. Opt-in { heuristic: true } bounds search work but may return a non-minimal script.
• Extreme constant-factor tuning — every token is interned to an integer once, so the hot loops compare Int32Array elements instead of strings; search state lives in two preallocated typed-array scratch buffers reused across the whole recursion (zero GC pressure); common prefixes/suffixes are stripped in O(N).
• Unicode-aware boundaries — word mode recognizes Unicode letter and digit runs, while opt-in intl-word mode uses Intl.Segmenter for unspaced scripts such as Japanese, Chinese, and Thai.
• Grapheme-safe output — char mode is code-point safe, and opt-in grapheme mode keeps ZWJ emoji and combining sequences together.
• Fully synchronous, zero dependencies — no worker gymnastics, no async overhead. ~3.9 KB min+gzip browser bundle.

Why another diff library?

This package is for applications that need predictable correctness without giving up a controlled response to pathological input:

• Exact by default — the normal path returns a shortest edit script, verified against a reference dynamic-programming implementation in the test suite.
• Explicit escape hatch — { heuristic: true } trades guaranteed minimality for bounded search work only when the caller chooses it. Run npm run perf:smoke to exercise the repository's seeded ~8 KB completely-different character path in both modes; on the documented environment, heuristic timing was roughly 8 ms versus roughly 233 ms for exact mode.
• Unicode-aware boundaries — scanner modes cover fast Unicode-aware word, code-point, and line diffs; Intl.Segmenter modes add locale-aware words and grapheme clusters.
• UI-ready output — use merged text entries for rendering or, with ignoreCase and ignoreWhitespace disabled, diffRanges() for UTF-16 offsets that slice both original inputs without converting between output models.

Typical benchmark inputs are already around a millisecond across the compared libraries, so those differences rarely decide an application. See the full benchmark table and bench/compare.mjs, then run npm run bench on the target environment for the cross-library comparison. Use npm run perf:smoke for the seeded ~8 KB exact-versus-heuristic timing path; timings vary by environment.

Install

npm install @krkarma777/string-diff

Usage

import { diff } from '@krkarma777/string-diff';

diff('the quick fox', 'the slow fox');
// [
//   { operation: 'equal',  text: 'the ' },
//   { operation: 'delete', text: 'quick' },
//   { operation: 'insert', text: 'slow' },
//   { operation: 'equal',  text: ' fox' },
// ]

diff('안녕하세요 세계', '안녕하세요 지구');
// [
//   { operation: 'equal',  text: '안녕하세요 ' },
//   { operation: 'delete', text: '세계' },
//   { operation: 'insert', text: '지구' },
// ]

CommonJS works too:

const { diff } = require('@krkarma777/string-diff');

Browser (IIFE bundle, global StringDiff):

<script src="https://unpkg.com/@krkarma777/string-diff/dist/string-diff.min.js"></script>
<script>
  StringDiff.diff('a b c', 'a x c');
</script>

API

diff(a, b, options?)

Returns DiffEntry[] — an exact shortest edit script between a and b by default. With { heuristic: true }, the result remains a valid edit script but may be non-minimal.

option	type	default	description
mode	'word' | 'char' | 'line' | 'intl-word' | 'grapheme'	'word'	tokenization granularity
locale	string | string[]	runtime locale	BCP 47 locale(s) for the Intl.Segmenter modes
refine	boolean	false	re-diff each delete/insert pair one level finer (line→word, word→char), e.g. quick→quicker reports just +er
heuristic	boolean	false	bound search work on pathological inputs; the result may be non-minimal, but stays identical to exact mode while the edit distance is small; use npm run perf:smoke for the seeded exact-versus-heuristic timing path
ignoreCase	boolean	false	compare tokens case-insensitively
ignoreWhitespace	boolean	false	whitespace runs compare equal (line mode: lines compared trimmed); whitespace with no counterpart still diffs

With ignoreCase/ignoreWhitespace, equal texts are taken from b, so concatenating non-delete texts reproduces b exactly; a-side reconstruction holds only up to the ignored differences.

• word — runs of Unicode letters/digits/underscore, whitespace runs, symbol runs

• char — individual code points (surrogate-pair safe)

• line — lines with their terminators attached

• intl-word — locale-aware words via Intl.Segmenter: splits unspaced scripts (Japanese, Chinese, Thai) that word mode sees as one token

  diff('私は猫が好きです', '私は犬が好きです', { mode: 'intl-word', locale: 'ja' });
  // equal '私は' · delete '猫' · insert '犬' · equal 'が好きです'

• grapheme — grapheme clusters via Intl.Segmenter: ZWJ emoji (👨‍👩‍👧) and combining sequences stay whole where char mode would split code points

The Intl.Segmenter modes are opt-in because they're slower than the scanner modes; they throw a clear TypeError on runtimes without Intl.Segmenter (Node < 16, older browsers).

diffRanges(a, b, options?)

Returns the same diff as offset tuples instead of text entries — useful for editors, highlighters, and other callers that want ranges rather than merged text. Each [aStart, aEnd, bStart, bEnd] says a[aStart, aEnd) was replaced by b[bStart, bEnd) (either side may be empty for pure insertions/deletions; offsets are UTF-16 code units).

When offsets must slice both original inputs, keep ignoreCase and ignoreWhitespace disabled (the defaults). With either option enabled, equal text comes from b, so ranges may not be valid for slicing both original inputs and an a-side endpoint can exceed a.length.

diffRanges('the quick fox', 'the slow fox');
// [[4, 9, 4, 8]]  — "quick" → "slow"

diffTokens(aTokens, bTokens, options?)

Lower-level API: diff two pre-tokenized string[] sequences with any tokenization you like (heuristic, ignoreCase, and ignoreWhitespace supported).

tokenize(text, mode?)

The built-in tokenizer, exported for reuse.

DiffEntry

interface DiffEntry {
  operation: 'equal' | 'insert' | 'delete';
  text: string;
}

Within a changed region, delete always precedes insert, and adjacent tokens with the same operation are merged into a single entry. With the default normalization options, concatenating all non-insert texts reproduces a, and all non-delete texts reproduce b. With ignoreCase or ignoreWhitespace, b-side reconstruction remains exact while a-side reconstruction holds only up to the ignored differences.

Benchmarks

Against the popular npm diff libraries — diff (jsdiff) v9.0.0, diff-match-patch v1.0.5, and fast-myers-diff v3.2.0 — each driven through its own idiomatic API, timed end-to-end from raw strings (npm run bench, Node v24, Apple Silicon, median of repeated runs; this package uses its default exact mode, and ratios are relative to it):

scenario	string-diff	jsdiff	diff-match-patch (default)	diff-match-patch (exact)	fast-myers-diff
word diff, 44 KB text, 10 edits	0.97 ms	0.89 ms (0.9×)	—	—	0.84 ms (0.9×)
char diff, 44 KB text, 10 edits	0.62 ms	1.38 ms (2.2×)	0.34 ms (0.5×)	0.31 ms (0.5×)	2.23 ms (3.6×)
line diff, 44 KB text, 10 changed lines	0.27 ms	0.14 ms (0.5×)	—	—	0.25 ms (1.0×)
char diff, ~8 KB completely different (worst case)	233 ms	2,360 ms (10.1×)	727 ms (3.1×)	664 ms (2.9×)	603 ms (2.6×)

How to read this honestly:

• On typical inputs every library here is sub-millisecond-ish — the differences are fractions of a millisecond and won't matter to most applications.
• The worst case is where libraries separate, and it's the row that decides whether your UI freezes on pathological input: in this documented run, this package's default exact mode measured 2.6–10× faster than everything tested while returning a provably minimal diff. The opt-in heuristic can reduce search time further but may return a non-minimal script; run npm run perf:smoke for the seeded exact-versus-heuristic timing path.
• diff-match-patch (default) trades exactness for speed by design — its documented timeout heuristics can return non-minimal diffs. This package's default exact mode does not; its opt-in heuristic may also return a non-minimal script.
• fast-myers-diff has no tokenizer and emits index ranges rather than text entries, so its rows do less output work (word/line rows reuse our tokenizer); diff-match-patch has no built-in word or line API.

Notes for fairness are in bench/compare.mjs. For history: versus the Hirschberg LCS implementation this repository originally shipped, typical scenarios are ~1,000× faster (npm run bench:legacy).

How it works

1. Scan, don't tokenize: one pass over each input records token boundary offsets and a per-token FNV-1a hash (word: Unicode-property class runs, line: terminator-attached lines, char: the code point itself is the id) — no token substrings are ever materialized.
2. Strip the common token prefix/suffix, filtering with integer hash comparisons, so a localized edit in a large document skips nearly all downstream work.
3. Intern the remaining tokens into dense integer ids with an open-addressed hash table that reads characters straight out of the originals — the entire search then runs over two Int32Arrays, never touching strings.
4. Myers middle-snake search: forward and backward D-paths meet in the middle, recursing on the two halves — O((N+M)·D) time, O(N+M) space, with both direction-state arrays allocated exactly once.
5. Rebuild merged equal/delete/insert entries from the changed-token flags; every output text is a single slice of the original input.

Demo

Hosted: krkarma777.github.io/string-diff (deployed from master by CI).

Prefilled examples

• Korean word replacement
• Japanese locale-aware words
• Grapheme-safe family emoji
• Ignore case and whitespace

Locally:

npm run demo
open demo/index.html

Development

npm test              # node:test — unit + 1,100 fuzz round-trips + 300 optimality checks
npm run typecheck
npm run build         # tsup → ESM + CJS + IIFE + .d.ts
npm run bench         # vs jsdiff / diff-match-patch / fast-myers-diff (build first)
npm run perf:smoke    # seeded ~8 KB exact/heuristic timing path
npm run bench:legacy  # vs the original Hirschberg LCS implementation

Contributing

Issues and pull requests are welcome. See the contribution guide for the Node.js setup, TDD workflow, verification gate, and performance-testing requirements.

References

• Myers, E. W. — An O(ND) Difference Algorithm and Its Variations (1986)
• Hunt & McIlroy — An Algorithm for Differential File Comparison
• Neil Fraser — Diff Strategies
• Google — diff-match-patch

License

MIT