Най-дълга обща подредица и diff в JavaScript

Проблем

Какво се промени в настройките?

Магазинът пази настройките си в текстов файл. Клиент пише, че доставката изведнъж е по-евтина. В системата има две версии на файла, вчерашната и днешната, и трябва да видиш кое точно е сменено, ред по ред, както го показва git diff.

Първата идея е да сравниш ред 1 с ред 1, ред 2 с ред 2 и така нататък:

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

Програмата казва, че от шест реда са сменени четири. Всъщност някой е добавил един ред (vat=20), сменил един (цената на доставката) и махнал един (плащането в брой). Добавеният ред е избутал всички след себе си с едно място надолу и сравнението по номер вече не ги познава.

Идеята

Редовете, които са останали

Обърни въпроса. Вместо да търсиш какво е сменено, намери кое е останало: най-много редове, които са и в двете версии, в същия ред. Всичко друго е махнато („-“) или добавено („+“).

Тези редове не са непременно един до друг: между тях стоят новите и махнатите. Затова се казва подредица: пази реда, но може да прескача. Най-многото такива редове е най-дългата обща подредица (LCS, longest common subsequence).

Да ги намериш, като пробваш всяка подредица, е безнадеждно: файл с n реда има 2ⁿ подредици. Но задачата има онова, което видя при рестото и раницата: отговорът за два файла се строи от отговорите за по-къси части от тях. Нека dp[i][j] е дължината на LCS на първите i реда от старата версия и първите j от новата. Тогава:

ако ред i и ред j са еднакви, той е общ: dp[i][j] = dp[i − 1][j − 1] + 1;
ако са различни, поне един от двата не влиза в общата подредица. Махни единия или другия и вземи по-доброто: dp[i][j] = max(dp[i − 1][j], dp[i][j − 1]);
ред 0 и колона 0 са нули: празен файл няма общо с нищо.

Виж го

Таблицата

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 с функция прави нов ред за всеки индекс. Капанът е new Array(n + 1).fill(new Array(m + 1).fill(0)): fill слага един и същ ред на всяко място, и запис в dp[1] сменя всички.

Двете версии на файла и таблицата, която програмата смята за тях:

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;
}

Стъпка по стъпка, с думи

Старата версия е отляво (was), новата отгоре (now). Ред 0 и колона 0 са нули: празен файл няма общи редове с нищо.
Ред 1: shop=Bookstore е същият като първия ред на now. Еднакви редове: диагоналът + 1. Клетката става зелена.
Различни редове: по-голямото от горната и от лявата клетка. Нов общ ред няма, само най-доброто досега.
currency=EUR също съвпада: 1 + 1 = 2. shipping=4.99 на ред 3 не съвпада с нищо, затова редът само пренася двойките.
По-надолу съвпадат free_from=50 и pay=card, и числата растат до 3 и 4.
Ъгълът dp[6][6] = 4: двете версии имат 4 общи реда. Кои са, казва обратният път.
Обратният път тръгва от ъгъла. pay=cash ≠ pay=card, горе е 4, а вляво 3: нагоре. pay=cash е махнат: „- pay=cash“.
pay=card = pay=card: общ ред, по диагонала. Същото за free_from=50.
shipping=4.99 ≠ shipping=3.99, а числата горе и вляво са равни: наляво, „+ shipping=3.99“. После „+ vat=20“.
Горе е 2, вляво 1: нагоре, „- shipping=4.99“. После двата общи реда по диагонала, до нулата в ъгъла.
Пътят е вървял от края към началото, затова result.reverse() обръща редовете. Това е diff-ът: vat=20 е нов, shipping е сменен, pay=cash го няма.

Числото в долния десен ъгъл е 4: четири реда са останали. Кои са, казва обратният път.

Пробвай

Предвиди изхода

Маршрутът на куриера във вторник и в сряда. Колко спирки са в същия ред и в двата дни?

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 = [
  "Склад", "Лозенец", "Център", "Младост", "Дружба",
];
const wednesday = [
  "Склад", "Център", "Лозенец", "Дружба",
];
const dp = lcsTable(tuesday, wednesday);
console.log(dp[tuesday.length][wednesday.length]);

Отговор

Идеята

Обратният път: diff

Таблицата помни как е получено всяко число. Тръгни от ъгъла dp[n][m] и върви назад:

редовете са еднакви: общ ред, пиши го с интервал и иди по диагонала;
лявата клетка не е по-малка от горната: ред j от новата версия не е в общата подредица, пиши го с „+“ и иди наляво;
иначе ред i от старата версия го няма в новата: пиши го с „-“ и иди нагоре.

Когато стигнеш края на едната версия, всичко останало от другата е само „+“ или само „-“. Пътят върви от последните редове към първите, затова накрая списъкът се обръща.

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

Сега се вижда истината: vat=20 е нов, shipping е сменен (махнат стар ред и добавен нов), pay=cash го няма. Изборът „наляво, ако числата са равни“ слага „-“ преди „+“ на същото място, както git.

Пробвай

Намери грешката

Колега е писал таблицата. Програмата пуска същия diff, но с неговата таблица:

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 е и махнат, и добавен, макар че не е пипан. На кой ред е грешката?

Избери реда с грешката.

Идеята

Колко струва

Таблицата има (n + 1) · (m + 1) клетки и всяка се смята с едно сравнение на два реда. Времето е O(n · m), паметта също (виж паметта). Пусни двата начина: всички подредици на старата версия, една по една, и таблицата. Броят се проверените подредици и клетките на таблицата. И двете версии са с по n реда:

Всички подредици O(2ⁿ)
Таблицата dp[i][j] O(n²)

Алгоритъм	n = 10	n = 20	n = 1000	n = 3000	n = 100 000
Всички подредици	1024	1 048 576	≈ 10³⁰¹	≈ 10⁹⁰³	≈ 10³⁰¹⁰²
Таблицата dp[i][j]	100	400	1 000 000	9 000 000	≈ 10 000 000 000

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

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;
}

При 20 реда подредиците са вече 1 048 576, а таблицата е 400 клетки. При 1000 реда таблицата е 1 000 000 клетки, при 3000 реда 9 000 000. Файл с 100 000 реда обаче иска 10 000 000 000 клетки, а с по 4 байта на клетка това са 40 GB памет. Затова истинските diff инструменти не пълнят цялата таблица.

По-точно, за любопитните

Алгоритъмът на Майърс (Eugene Myers, 1986) търси същия най-кратък diff, но тръгва от въпроса „колко най-малко реда трябва да махна и добавя“. Ако това число е D, времето е O((n + m) · D). Две версии на файл обикновено се различават с малко редове, затова D е малко и алгоритъмът е почти линеен. Той е подразбирането в git diff и в GNU diff. В git има и други: --patience и --histogram дават по-четими diff-ове при преместени блокове код, а --minimal търси по-упорито най-краткия.

Ако ти трябва само дължината на LCS, стигат два реда от таблицата: ред i ползва само ред i − 1. Паметта става O(m). Алгоритъмът на Хиршберг (1975) пази и пътя с O(n + m) памет, като разделя задачата наполовина.

Как е в езиците:

Python има difflib в стандартната библиотека: difflib.unified_diff(was, now) печата diff като git. Той търси най-дългия общ блок от поредни редове и повтаря отляво и отдясно, затова diff-ът му не винаги е най-краткият;
Java и C# нямат diff в стандартната библиотека. Ползват се библиотеки: java-diff-utils в Java, DiffPlex в C#, и двете с алгоритъма на Майърс;
JavaScript също няма. Пакетът diff в npm (jsdiff) ползва Майърс.

Идеята

Същата таблица, друг въпрос: „Имахте предвид…“

Клиент търси „латоп“ и не намира нищо. Търсачката на магазина трябва да предложи „лаптоп“: думата от каталога, която е най-близо до написаното.

Близостта се мери с разстоянието на Левенщайн: колко най-малко букви трябва да вмъкнеш, да изтриеш или да смениш, за да стане едната дума другата. „латоп“ → „лаптоп“ е 1: вмъкваш „п“.

Таблицата е същата като при LCS, само въпросът е друг. d[i][j] е разстоянието между първите i букви на търсенето и първите j на думата:

ред 0 и колона 0 вече не са нули: d[i][0] = i (изтриваш всичките i букви), d[0][j] = j;
иначе d[i][j] е най-малкото от три хода: изтриване (d[i − 1][j] + 1), вмъкване (d[i][j − 1] + 1) и смяна (d[i − 1][j − 1], плюс 1, ако буквите са различни).

Това ще напишеш в упражнението.

По-точно, за любопитните

Истинските търсачки не спират дотук. Броят и колко често се търси всяка дума („лаптоп“ е по-вероятно от „лампа“, дори ако разстоянието е същото), колко близо са буквите на клавиатурата и дали две букви са само разменени. Разменените съседни букви са най-честата грешка, а Левенщайн ги брои за 2. Вариантът на Дамерау брои размяната за 1.

LCS и Левенщайн са роднини: ако позволиш само вмъкване и изтриване, без смяна, разстоянието е n + m − 2 · LCS. Всяка буква извън общата подредица се трие от едната дума или се вмъква в другата.

Упражнение

„Имахте предвид…“

Реши задачата в редактора си.

Предложения. Каталогът е „лаптоп“, „лампа“, „таблет“, „телефон“, „слушалки“ и „монитор“, а клиентите са търсили „латоп“, „телфон“, „таблте“ и „мониор“. Напиши distance(query, word) с таблицата на Левенщайн и за всяко търсене изведи най-близката дума от каталога и разстоянието (при равенство първата в каталога):

латоп → лаптоп (1)
телфон → телефон (1)
таблте → таблет (2)
мониор → монитор (1)

Още задачи

Размяната за 1. Добави ход „размяна на две съседни букви“ (Дамерау–Левенщайн). Колко става „таблте“ → „таблет“?
Само при близко. Не предлагай нищо, ако най-близката дума е на разстояние повече от една трета от дължината на търсенето.
diff на думи. Пусни diff от урока не на редове, а на думите на две описания на продукт, разделени с интервал.

Тест

Провери се

1. Защо сравнението „ред i от старата версия с ред i от новата“ показва почти всичко като сменено?Защото редовете са с различна дължинаЗащото сравнява текстовете с ==Един вмъкнат ред измества всички след него с една позиция

2. Какво пише в dp[i][j], когато ред i на старата версия и ред j на новата са еднакви?max(dp[i − 1][j], dp[i][j − 1]) + 1dp[i − 1][j] + dp[i][j − 1]dp[i − 1][j − 1] + 1

3. Два файла имат по 10 000 реда. Колко клетки пълни таблицата?20 000100 000 00010 000

4. Обратният път тръгва от dp[n][m]. Защо накрая списъкът се обръща?Пътят върви от последните редове към първитеОбръщането поправя грешките в таблицатаЗа да станат „-“ преди „+“

5. Подредица ли е [shop=Bookstore, free_from=50, pay=card] на новата версия, макар че между редовете има други?Не: редовете трябва да са един до другСамо ако е и на старата версияДа: подредицата пази реда, но може да прескача

Най-дълга обща подредица и diff

Бисквитки