Cairn
algorithms · approximate match · O(k·min(m,n))

↩ back to Approximate Match

Banded Edit Distance (Ukkonen's Algorithm)

Edit Distance's table fills all (m+1)(n+1) cells to answer "what's the fewest edits, whatever that number turns out to be?" Often the real question is narrower: "is it within k edits?" — a spell checker doesn't care that two words are 40 edits apart, only that they aren't within 2. Ukkonen's observation: cell dp[i][j] can only ever be reached by at least |i − j| inserts or deletes, just to close the length gap between a prefix of length i and one of length j — so any cell with |i − j| > k is guaranteed to hold a value greater than k before a single comparison runs. Skip those cells entirely, compute only the diagonal band |i − j| ≤ k, and the answer comes out identical whenever k is large enough — for a fraction of the work.

Try it

Same pair Edit Distance uses, so the answer is already known: A = "kitten", B = "sitting", true distance 3. Pick a band width k and press Step or Run — cells inside the band fill in exactly as they would in the full table; cells outside it are never touched by a correct implementation, shown dim. At k = 0 the band can't even reach the bottom-right corner (the strings differ in length by 1, more than 0), and a correct implementation has to say so rather than guess. At k = 1, the band is already wide enough to find the true distance of 3 while computing just 20 of the full table's 56 cells — check the stats line.

Switch sentinel to buggy (0 default, no ∞) to run the broken variant Pitfalls describes, live: instead of treating an out-of-band or not-yet-computed cell as "infinitely far" (so it's correctly ignored by the surrounding min), this variant reads it straight off a plain array that JavaScript defaults to 0. Watch the out-of-band cells now render as 0 instead of dim — and watch the final answer quietly shrink to match k instead of reporting the true distance, or "impossible," for every k below 3.

step 0
Press Step or Run.

Why it works

The band bound is a lower bound on path length, not a heuristic guess. Any way of turning the first i characters of A into the first j characters of B has to account for a length difference of |i − j| somehow — every substitution and every match leaves the length gap unchanged, only insert and delete move it, one character at a time. So reaching dp[i][j] at all costs at least |i − j| edits, regardless of what the two prefixes actually contain. If a k-edit budget is all that's being asked about, any cell with |i − j| > k is provably irrelevant before its characters are even compared — this is the same bound Bitap with Edit Distance enforces a different way, by only ever tracking k+1 error levels in a bit-parallel word instead of restricting which table cells exist.

The recurrence inside the band is unchanged from Edit Distance's own three-way minimum — match for free, or pay one edit for the cheapest of substitute, delete, insert. What changes is what a lookup means when it lands on a neighbor outside the band: a cell at the band's own edge (|i − j| = k) has a neighbor one step further off the diagonal (|i − j| = k+1), which was never computed because it can't matter — reaching it would already cost more than k. Treating that missing neighbor as infinitely expensive is what correctly propagates "not reachable within budget" outward from the band's edge to the final answer. Get that substitution wrong and the propagation breaks — see Pitfalls.

Reference implementation

Only ever visits O(k) cells per row instead of O(n), and returns Infinity — not a number — when k isn't big enough:

function bandedEditDistance(a, b, k) {
  const m = a.length, n = b.length;
  const inBand = (i, j) => Math.abs(i - j) <= k;
  const written = new Set();
  const dp = new Map();
  const get = (i, j) => (inBand(i, j) && written.has(i + ',' + j)) ? dp.get(i + ',' + j) : Infinity;

  for (let i = 0; i <= m; i++) {
    const lo = Math.max(0, i - k), hi = Math.min(n, i + k);
    for (let j = lo; j <= hi; j++) {
      let val;
      if (i === 0 && j === 0) {
        val = 0;
      } else if (i > 0 && j > 0 && a[i - 1] === b[j - 1]) {
        val = get(i - 1, j - 1);
      } else {
        const sub = (i > 0 && j > 0) ? get(i - 1, j - 1) + 1 : Infinity;
        const del = i > 0 ? get(i - 1, j) + 1 : Infinity;
        const ins = j > 0 ? get(i, j - 1) + 1 : Infinity;
        val = Math.min(sub, del, ins);
      }
      dp.set(i + ',' + j, val);
      written.add(i + ',' + j);
    }
  }
  return get(m, n); // Infinity means "more than k edits apart"
}

Pitfalls

Skip the infinity sentinel and the algorithm doesn't crash — it lies, plausibly. Build the same band from a plain Array(...).fill(0) table instead of a map guarded by inBand, and every out-of-band or not-yet-written cell silently reads back 0 — "free," not "unreachable." Checked against the shipped page's own broken-sentinel mode on "kitten"/"sitting" (true distance 3): at k = 0 the correct version reports "impossible" (the length gap alone exceeds the budget), the buggy version reports 0. At k = 1, correct reports 3 (the true answer, already reachable at this band width); buggy reports 1. At k = 2, correct still reports 3; buggy reports 2. The pattern is exact and easy to miss in production: the buggy version always reports min(k, true distance) — a number that looks exactly like a legitimate answer, changes sensibly as k grows, and only stops being wrong once k happens to reach the true distance. Nothing about the output looks broken; only comparing it against the untouched full table (or, as here, against the correct-sentinel mode run on the identical input) exposes it.

An off-by-one band width doesn't corrupt answers — it just quietly demands a bigger k than it should. Define the band with a strict inequality, |i − j| < k, instead of |i − j| ≤ k, and the sentinel logic above still saves every genuinely out-of-band cell correctly — but the band itself is now one column narrower than the budget promised. Checked in a scratch variant: on the same pair, the strict-inequality band needs k = 2 to compute the same 20 cells and reach the same answer (3) that the correct ≤ band reaches at k = 1; at k = 1 the strict version reports "impossible" even though a width-1 band is genuinely enough. No wrong finite numbers come out of this version — only a budget that silently buys one less unit of slack than requested, a different failure shape from the sentinel bug above (wrong answer vs. overly conservative "no").

The band only pays off when k stays small relative to the strings. As k grows toward max(m, n), the band widens until it covers the whole table and the savings vanish — try k = 4 above and watch the stats line close in on 56 of 56. This is the same trade Bitap with Edit Distance's Pitfalls section makes from the opposite direction: both algorithms are only cheap because they assume the answer, or the budget worth caring about, is small. That reasoning is sound as far as it goes, but it's a cell-count argument, not a measured one — see measuring the real crossover below for how much smaller "small" turns out to mean in practice, for the implementation actually shown on this page.

Measuring the real crossover

The paragraph above reasons from cell counts alone: the band visits roughly 2k+1 cells per row against the full table's min(m,n)+1, so a geometric reading says the two methods should only tie once k grows close to max(m,n) and the band swallows the whole table. Measured directly, the real crossover lands far earlier — k in the low single digits of a percent of the string length, not anywhere near the full width.

Timed the shown bandedEditDistance above against Edit Distance's own shipped editDistance on random equal-length strings. Correctness cross-checked first against the one guarantee this page's implementation actually makes (not every finite answer is the true distance — see Pitfalls above): whenever k is at least the true distance, banded reproduces it exactly, 7,450/7,450 trials across three alphabet sizes, zero mismatches; whenever the strings' own length gap exceeds k, banded correctly reports "impossible" every time, also zero mismatches.

Wall-clock, in Node on this machine, two string lengths:

N=1,000 (full table: 22.2 ms)
  k=5   (0.5% of N):    6.5 ms   0.29× (banded faster)   91× fewer cells
  k=10  (1.0% of N):   13.5 ms   0.61× (banded faster)   48× fewer cells
  k=15  (1.5% of N):   19.2 ms   0.86× (banded faster)   33× fewer cells
  k=20  (2.0% of N):   31.4 ms   1.41× (banded SLOWER)   25× fewer cells
  k=30  (3.0% of N):   42.5 ms   1.92× (banded SLOWER)   17× fewer cells
  k=50  (5.0% of N):   90.2 ms   4.06× (banded SLOWER)   10× fewer cells

N=5,000 (full table: 740.7 ms)
  k=25  (0.5% of N):  244.3 ms   0.33× (banded faster)   98× fewer cells
  k=50  (1.0% of N):  557.5 ms   0.75× (banded faster)   50× fewer cells
  k=75  (1.5% of N):  915.6 ms   1.24× (banded SLOWER)   33× fewer cells
  k=100 (2.0% of N): 1,391.8 ms   1.88× (banded SLOWER)   25× fewer cells

The crossover sits around k/N ≈ 1.5–2% at both sizes — if anything narrowing slightly as N grows rather than widening — nowhere near needing k to approach max(m,n). And right at the crossover, banded is still computing 25×– 33× fewer cells than the full table — the cell-count argument isn't wrong about the work being done, it's the cost per cell that breaks the intuition. The shown reference implementation stores every cell in a Map behind a string-concatenated key (i + ',' + j) with a Set existence check guarding it; the full table above is one flat, pre-allocated array read by plain integer index. That gap in per-cell cost is large enough to erase a 25×–33× advantage in raw cell count by the time k is only a couple of percent of the string length. A flat-array, two-diagonal rolling implementation — the same trick the Complexity section below already credits to Edit Distance's own space-optimized mode — would push this crossover back out much closer to the geometric one; that isn't what's shown above, though, and "the band only pays off when k stays small" turns out to understate just how small, for the algorithm as actually written on this page.

Complexity

Time: O(k·min(m, n)) — each of roughly min(m, n) rows computes at most 2k+1 cells, versus O(m·n) for the unrestricted table. Space: O(k·min(m, n)) for the same reason, or O(k) if only the two most recent diagonals are kept — the same rolling-row trick Edit Distance's own space-optimized mode uses on the unrestricted table.

This only ever helps when the answer (or the threshold worth reporting) is known to be small — exactly the assumption spell checkers, approximate diff, and DNA read alignment tools make when they use a bounded edit distance instead of the full table. For a different way of exploiting the same bound, packing the whole error budget into the bits of one machine word instead of restricting which table cells exist, see Bitap with Edit Distance (Wu–Manber). A sixth entry, Jaro-Winkler Similarity, bounds a search window too — but around individual characters rather than table cells, trading the exact edit count this page and its siblings compute for a cheaper similarity score. For a side-by-side comparison across all thirteen approximate-match entries, see Choosing an Approximate String Matcher.