The longest common subsequence and diff in JavaScript

Problem

What changed in the settings?

The shop keeps its settings in a text file. A customer writes that delivery is suddenly cheaper. The system has two versions of the file, yesterday's and today's, and you need to see exactly what changed, line by line, as git diff shows it.

The first idea is to compare line 1 with line 1, line 2 with line 2, and so on:

const was = [
  "shop=Bookstore", "currency=EUR", "shipping=4.99",
  "free_from=50", "pay=card", "pay=cash",
];
const now = [
  "shop=Bookstore", "currency=EUR", "vat=20",
  "shipping=3.99", "free_from=50", "pay=card",
];
for (let i = 0; i < was.length; i++) {
  if (was[i] === now[i]) {
    console.log("  " + was[i]);
  } else {
    console.log("- " + was[i]);
    console.log("+ " + now[i]);
  }
}

  shop=Bookstore
  currency=EUR
- shipping=4.99
+ vat=20
- free_from=50
+ shipping=3.99
- pay=card
+ free_from=50
- pay=cash
+ pay=card

The program says four of six lines changed. In fact someone added one line (vat=20), changed one (the delivery price) and removed one (cash payment). The added line pushed every line after it one place down, and comparing by number no longer recognises them.

The idea

The lines that stayed

Turn the question around. Instead of looking for what changed, find what stayed: as many lines as possible that are in both versions, in the same order. Everything else was removed ("-") or added ("+").

These lines are not necessarily next to each other: the new and removed ones stand between them. That is why it is called a subsequence: it keeps the order but may skip. The most such lines is the longest common subsequence (LCS).

Finding them by trying every subsequence is hopeless: a file with n lines has 2ⁿ subsequences. But the task has what you saw with change and the knapsack: the answer for two files is built from the answers for shorter parts of them. Let dp[i][j] be the length of the LCS of the first i lines of the old version and the first j of the new one. Then:

if line i and line j are equal, it is common: dp[i][j] = dp[i − 1][j − 1] + 1;
if they are different, at least one of the two is not in the common subsequence. Drop one or the other and take the better: dp[i][j] = max(dp[i − 1][j], dp[i][j − 1]);
row 0 and column 0 are zeros: an empty file has nothing in common with anything.

See it

The table

function lcsTable(was, now) {
  const n = was.length;
  const m = now.length;
  const dp = Array.from({ length: n + 1 }, () =>
    new Array(m + 1).fill(0),
  );
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      if (was[i - 1] === now[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        const up = dp[i - 1][j];
        const left = dp[i][j - 1];
        dp[i][j] = Math.max(up, left);
      }
    }
  }
  return dp;
}

Array.from with a function makes a new row for every index. The trap is new Array(n + 1).fill(new Array(m + 1).fill(0)): fill puts one and the same row in every place, and writing to dp[1] changes them all.

The two versions of the file and the table the program computes for them:

const was = [
  "shop=Bookstore", "currency=EUR", "shipping=4.99",
  "free_from=50", "pay=card", "pay=cash",
];
const now = [
  "shop=Bookstore", "currency=EUR", "vat=20",
  "shipping=3.99", "free_from=50", "pay=card",
];
for (const row of lcsTable(was, now)) {
  console.log(row.join(" "));
}

0 0 0 0 0 0 0
0 1 1 1 1 1 1
0 1 2 2 2 2 2
0 1 2 2 2 2 2
0 1 2 2 2 3 3
0 1 2 2 2 3 4
0 1 2 2 2 3 4

function diff(was, now) {
  const dp = lcsTable(was, now);
  const result = [];
  let i = was.length;
  let j = now.length;
  while (i > 0 && j > 0) {
    if (was[i - 1] === now[j - 1]) {
      result.push("  " + was[i - 1]);
      i--;
      j--;
    } else if (dp[i][j - 1] >= dp[i - 1][j]) {
      result.push("+ " + now[j - 1]);
      j--;
    } else {
      result.push("- " + was[i - 1]);
      i--;
    }
  }
  for (; j > 0; j--) result.push("+ " + now[j - 1]);
  for (; i > 0; i--) result.push("- " + was[i - 1]);
  return result.reverse();
}

function lcsTable(was, now) {
  const n = was.length;
  const m = now.length;
  const dp = Array.from({ length: n + 1 }, () =>
    new Array(m + 1).fill(0),
  );
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      if (was[i - 1] === now[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        const up = dp[i - 1][j];
        const left = dp[i][j - 1];
        dp[i][j] = Math.max(up, left);
      }
    }
  }
  return dp;
}

Step by step, in words

Old version on the left (was), new on top (now). Row 0 and column 0 are zeros: an empty file has no lines in common with anything.
Row 1: shop=Bookstore is the same as the first line of now. Equal lines: the diagonal + 1. The cell turns green.
Different lines: the bigger of the cell above and the cell on the left. No new common line, only the best so far.
currency=EUR matches too: 1 + 1 = 2. shipping=4.99 in row 3 matches nothing, so the row only copies the 2s.
free_from=50 and pay=card match lower down, and the numbers grow to 3 and 4.
The corner dp[6][6] = 4: the two versions have 4 lines in common. Which ones, the way back tells.
The way back starts in the corner. pay=cash ≠ pay=card, above is 4 and left is 3: up. pay=cash was removed: “- pay=cash”.
pay=card = pay=card: a common line, along the diagonal. The same for free_from=50.
shipping=4.99 ≠ shipping=3.99, and the numbers above and left are equal: left, “+ shipping=3.99”. Then “+ vat=20”.
Above is 2, left is 1: up, “- shipping=4.99”. Then the two common lines along the diagonal, back to the 0 in the corner.
The way went from the end to the start, so result.reverse() turns the lines around. The diff: vat=20 is new, shipping changed, pay=cash is gone.

The number in the bottom right corner is 4: four lines stayed. Which ones, the way back tells.

Try it

Predict the output

The courier's route on Tuesday and on Wednesday. How many stops are in the same order on both days?

function lcsTable(was, now) {
  const n = was.length;
  const m = now.length;
  const dp = Array.from({ length: n + 1 }, () =>
    new Array(m + 1).fill(0),
  );
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      if (was[i - 1] === now[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        const up = dp[i - 1][j];
        const left = dp[i][j - 1];
        dp[i][j] = Math.max(up, left);
      }
    }
  }
  return dp;
}

const tuesday = [
  "Depot", "Riverside", "Centre", "Hillside", "Oldtown",
];
const wednesday = [
  "Depot", "Centre", "Riverside", "Oldtown",
];
const dp = lcsTable(tuesday, wednesday);
console.log(dp[tuesday.length][wednesday.length]);

Answer

The idea

The way back: diff

The table remembers how every number was obtained. Start in the corner dp[n][m] and walk back:

the lines are equal: a common line, write it with a space and go along the diagonal;
the cell on the left is not smaller than the one above: line j of the new version is not in the common subsequence, write it with "+" and go left;
otherwise line i of the old version is not in the new one: write it with "-" and go up.

When you reach the end of one version, everything left of the other is only "+" or only "-". The way goes from the last lines to the first, so at the end the list is turned around.

function diff(was, now) {
  const dp = lcsTable(was, now);
  const result = [];
  let i = was.length;
  let j = now.length;
  while (i > 0 && j > 0) {
    if (was[i - 1] === now[j - 1]) {
      result.push("  " + was[i - 1]);
      i--;
      j--;
    } else if (dp[i][j - 1] >= dp[i - 1][j]) {
      result.push("+ " + now[j - 1]);
      j--;
    } else {
      result.push("- " + was[i - 1]);
      i--;
    }
  }
  for (; j > 0; j--) result.push("+ " + now[j - 1]);
  for (; i > 0; i--) result.push("- " + was[i - 1]);
  return result.reverse();
}

for (const line of diff(was, now)) {
  console.log(line);
}

  shop=Bookstore
  currency=EUR
- shipping=4.99
+ vat=20
+ shipping=3.99
  free_from=50
  pay=card
- pay=cash

Now the truth shows: vat=20 is new, shipping changed (an old line removed and a new one added), pay=cash is gone. The choice "left when the numbers are equal" puts "-" before "+" at the same place, as git does.

Try it

Find the bug

A colleague wrote the table. The program runs the same diff, but with their table:

function lcsTable(was, now) {
  const n = was.length;
  const m = now.length;
  const dp = Array.from({ length: n + 1 }, () =>
    new Array(m + 1).fill(0),
  );
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      if (was[i - 1] === now[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        const up = dp[i - 1][j];
        const left = dp[i][j - 1];
        dp[i][j] = Math.max(up, left) + 1;
      }
    }
  }
  return dp;
}

for (const line of diff(was, now)) {
  console.log(line);
}

  shop=Bookstore
- currency=EUR
- shipping=4.99
- free_from=50
- pay=card
- pay=cash
+ currency=EUR
+ vat=20
+ shipping=3.99
+ free_from=50
+ pay=card

currency=EUR is both removed and added, though nobody touched it. Which line is the bug on?

Pick the line with the bug.

The idea

What it costs

The table has (n + 1) · (m + 1) cells and each one takes one comparison of two lines. The time is O(n · m), and so is the memory (see memory). Run both ways: every subsequence of the old version, one by one, and the table. We count the subsequences checked and the cells of the table. Both versions have n lines:

Every subsequence O(2ⁿ)
The table dp[i][j] O(n²)

Algorithm	n = 10	n = 20	n = 1,000	n = 3,000	n = 100,000
Every subsequence	1,024	1,048,576	≈ 10³⁰¹	≈ 10⁹⁰³	≈ 10³⁰¹⁰²
The table dp[i][j]	100	400	1,000,000	9,000,000	≈ 10,000,000,000

The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.

function lcsTable(was, now) {
  const n = was.length;
  const m = now.length;
  const dp = Array.from({ length: n + 1 }, () =>
    new Array(m + 1).fill(0),
  );
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      if (was[i - 1] === now[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        const up = dp[i - 1][j];
        const left = dp[i][j - 1];
        dp[i][j] = Math.max(up, left);
      }
    }
  }
  return dp;
}

At 20 lines there are already 1,048,576 subsequences, and the table is 400 cells. At 1000 lines the table is 1,000,000 cells, at 3000 lines 9,000,000. A file of 100,000 lines, though, needs 10,000,000,000 cells, and at 4 bytes a cell that is 40 GB of memory. That is why real diff tools do not fill the whole table.

More precisely, if you are curious

Myers' algorithm (Eugene Myers, 1986) finds the same shortest diff, but starts from the question "how few lines do I need to remove and add". If that number is D, the time is O((n + m) · D). Two versions of a file usually differ in few lines, so D is small and the algorithm is nearly linear. It is the default in git diff and in GNU diff. Git has others too: --patience and --histogram give more readable diffs when blocks of code move, and --minimal tries harder for the shortest one.

If you only need the length of the LCS, two rows of the table are enough: row i only uses row i − 1. The memory becomes O(m). Hirschberg's algorithm (1975) keeps the way too, with O(n + m) memory, by splitting the task in half.

How it is in the languages:

Python has difflib in the standard library: difflib.unified_diff(was, now) prints a diff like git. It looks for the longest common block of consecutive lines and repeats on the left and on the right, so its diff is not always the shortest;
Java and C# have no diff in the standard library. Libraries are used: java-diff-utils in Java, DiffPlex in C#, both with Myers' algorithm;
JavaScript has none either. The diff package on npm (jsdiff) uses Myers.

The idea

The same table, another question: “Did you mean…”

A customer searches for "lapop" and finds nothing. The shop's search should suggest "laptop": the catalogue word closest to what was typed.

Closeness is measured with the Levenshtein distance: how few letters you must insert, delete or change to turn one word into the other. "lapop" → "laptop" is 1: you insert "t".

The table is the same as for the LCS, only the question is different. d[i][j] is the distance between the first i letters of the query and the first j of the word:

row 0 and column 0 are no longer zeros: d[i][0] = i (you delete all i letters), d[0][j] = j;
otherwise d[i][j] is the smallest of three moves: delete (d[i − 1][j] + 1), insert (d[i][j − 1] + 1) and change (d[i − 1][j − 1], plus 1 if the letters differ).

You will write this in the exercise.

More precisely, if you are curious

Real search engines do not stop here. They count how often each word is searched ("laptop" is more likely than "lamp", even at the same distance), how close the letters are on the keyboard, and whether two letters are only swapped. Swapped neighbouring letters are the most common typo, and Levenshtein counts them as 2. The Damerau variant counts a swap as 1.

LCS and Levenshtein are relatives: if you allow only inserting and deleting, without changing, the distance is n + m − 2 · LCS. Every letter outside the common subsequence is deleted from one word or inserted into the other.

Exercise

“Did you mean…”

Solve the task in your editor.

Suggestions. The catalogue is "laptop", "lamp", "tablet", "phone", "headphones" and "monitor", and customers searched for "lapop", "phnoe", "tablte" and "moniter". Write distance(query, word) with the Levenshtein table and, for every query, print the closest catalogue word and the distance (on a tie, the first in the catalogue):

lapop → laptop (1)
phnoe → phone (2)
tablte → tablet (2)
moniter → monitor (1)

More tasks

A swap for 1. Add the move "swap two neighbouring letters" (Damerau–Levenshtein). What does "tablte" → "tablet" become?
Only when close. Suggest nothing if the closest word is further than a third of the query's length.
A diff of words. Run the lesson's diff not on lines but on the words of two product descriptions, split on spaces.

Test

Check yourself

1. Why does comparing "line i of the old version with line i of the new one" show almost everything as changed?Because it compares the texts with ==One inserted line shifts every line after it by one positionBecause the lines have different lengths

2. What goes into dp[i][j] when line i of the old version and line j of the new one are equal?dp[i − 1][j] + dp[i][j − 1]dp[i − 1][j − 1] + 1max(dp[i − 1][j], dp[i][j − 1]) + 1

3. Two files have 10,000 lines each. How many cells does the table fill?100,000,00020,00010,000

4. The way back starts at dp[n][m]. Why is the list turned around at the end?The way goes from the last lines to the firstTurning it around fixes mistakes in the tableSo that "-" comes before "+"

5. Is [shop=Bookstore, free_from=50, pay=card] a subsequence of the new version, even though other lines stand between them?Yes: a subsequence keeps the order but may skipNo: the lines must be next to each otherOnly if it is also one of the old version

The longest common subsequence and diff

Cookies