Най-дълга обща подредица и diff
Накратко: Най-дългата обща подредица (LCS) на две поредици се намира с таблица за O(n · m) и стои под diff: редовете извън нея са изтритите и добавените.
Проблем
Какво се промени в настройките?
Магазинът пази настройките си в текстов файл. Клиент пише, че доставката изведнъж е по-евтина. В системата има две версии на файла, вчерашната и днешната, и трябва да видиш кое точно е сменено, ред по ред, както го показва git diff.
Първата идея е да сравниш ред 1 с ред 1, ред 2 с ред 2 и така нататък:
string[] was =[ "shop=Bookstore", "currency=EUR", "shipping=4.99", "free_from=50", "pay=card", "pay=cash",];string[] now =[ "shop=Bookstore", "currency=EUR", "vat=20", "shipping=3.99", "free_from=50", "pay=card",];for (int i = 0; i < was.Length; i++){ if (was[i] == now[i]) { Console.WriteLine(" " + was[i]); } else { Console.WriteLine("- " + was[i]); Console.WriteLine("+ " + 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 са нули: празен файл няма общо с нищо.
Виж го
Таблицата
static int[,] LcsTable(string[] was, string[] now){ int n = was.Length, m = now.Length; var dp = new int[n + 1, m + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (was[i - 1] == now[j - 1]) { dp[i, j] = dp[i - 1, j - 1] + 1; } else { int up = dp[i - 1, j]; int left = dp[i, j - 1]; dp[i, j] = Math.Max(up, left); } } } return dp;}new int[n + 1, m + 1] е правоъгълен масив, пълен с нули: клетката е dp[i, j], а не dp[i][j] като в масив от масиви.Двете версии на файла и таблицата, която програмата смята за тях:
string[] was =[ "shop=Bookstore", "currency=EUR", "shipping=4.99", "free_from=50", "pay=card", "pay=cash",];string[] now =[ "shop=Bookstore", "currency=EUR", "vat=20", "shipping=3.99", "free_from=50", "pay=card",];var dp = LcsTable(was, now);for (int i = 0; i < dp.GetLength(0); i++){ var row = Enumerable.Range(0, dp.GetLength(1)).Select(j => dp[i, j]); Console.WriteLine(string.Join(" ", row));}0 0 0 0 0 0 00 1 1 1 1 1 10 1 2 2 2 2 20 1 2 2 2 2 20 1 2 2 2 3 30 1 2 2 2 3 40 1 2 2 2 3 4static List<string> Diff(string[] was, string[] now){ var dp = LcsTable(was, now); var result = new List<string>(); int i = was.Length, j = now.Length; while (i > 0 && j > 0) { if (was[i - 1] == now[j - 1]) { result.Add(" " + was[i - 1]); i--; j--; } else if (dp[i, j - 1] >= dp[i - 1, j]) { result.Add("+ " + now[j - 1]); j--; } else { result.Add("- " + was[i - 1]); i--; } } for (; j > 0; j--) result.Add("+ " + now[j - 1]); for (; i > 0; i--) result.Add("- " + was[i - 1]); result.Reverse(); return result;}static int[,] LcsTable(string[] was, string[] now){ int n = was.Length, m = now.Length; var dp = new int[n + 1, m + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (was[i - 1] == now[j - 1]) { dp[i, j] = dp[i - 1, j - 1] + 1; } else { int up = dp[i - 1, j]; int 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: четири реда са останали. Кои са, казва обратният път.
Пробвай
Предвиди изхода
Маршрутът на куриера във вторник и в сряда. Колко спирки са в същия ред и в двата дни?
static int[,] LcsTable(string[] was, string[] now){ int n = was.Length, m = now.Length; var dp = new int[n + 1, m + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (was[i - 1] == now[j - 1]) { dp[i, j] = dp[i - 1, j - 1] + 1; } else { int up = dp[i - 1, j]; int left = dp[i, j - 1]; dp[i, j] = Math.Max(up, left); } } } return dp;}
string[] tuesday =[ "Склад", "Лозенец", "Център", "Младост", "Дружба",];string[] wednesday =[ "Склад", "Център", "Лозенец", "Дружба",];var dp = LcsTable(tuesday, wednesday);Console.WriteLine(dp[tuesday.Length, wednesday.Length]);Идеята
Обратният път: diff
Таблицата помни как е получено всяко число. Тръгни от ъгъла dp[n][m] и върви назад:
- редовете са еднакви: общ ред, пиши го с интервал и иди по диагонала;
- лявата клетка не е по-малка от горната: ред j от новата версия не е в общата подредица, пиши го с „+“ и иди наляво;
- иначе ред i от старата версия го няма в новата: пиши го с „-“ и иди нагоре.
Когато стигнеш края на едната версия, всичко останало от другата е само „+“ или само „-“. Пътят върви от последните редове към първите, затова накрая списъкът се обръща.
static List<string> Diff(string[] was, string[] now){ var dp = LcsTable(was, now); var result = new List<string>(); int i = was.Length, j = now.Length; while (i > 0 && j > 0) { if (was[i - 1] == now[j - 1]) { result.Add(" " + was[i - 1]); i--; j--; } else if (dp[i, j - 1] >= dp[i - 1, j]) { result.Add("+ " + now[j - 1]); j--; } else { result.Add("- " + was[i - 1]); i--; } } for (; j > 0; j--) result.Add("+ " + now[j - 1]); for (; i > 0; i--) result.Add("- " + was[i - 1]); result.Reverse(); return result;}foreach (string line in Diff(was, now)){ Console.WriteLine(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, но с неговата таблица:
static int[,] LcsTable(string[] was, string[] now){ int n = was.Length, m = now.Length; var dp = new int[n + 1, m + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (was[i - 1] == now[j - 1]) { dp[i, j] = dp[i - 1, j - 1] + 1; } else { int up = dp[i - 1, j]; int left = dp[i, j - 1]; dp[i, j] = Math.Max(up, left) + 1; } } } return dp;}foreach (string line in Diff(was, now)){ Console.WriteLine(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=cardcurrency=EUR е и махнат, и добавен, макар че не е пипан. На кой ред е грешката?
Избери реда с грешката.
Когато редовете са различни, нов общ ред няма: най-доброто е по-голямото от двете съседни клетки, без +1. С +1 всяка клетка расте при всяка стъпка, числата вече не казват кои редове са общи, а обратният път тръгва в погрешна посока. Правилно е dp[i, j] = Math.Max(up, left);.
Идеята
Колко струва
Таблицата има (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 |
static int[,] LcsTable(string[] was, string[] now){ int n = was.Length, m = now.Length; var dp = new int[n + 1, m + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (was[i - 1] == now[j - 1]) { dp[i, j] = dp[i - 1, j - 1] + 1; } else { int up = dp[i - 1, j]; int 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от урока не на редове, а на думите на две описания на продукт, разделени с интервал.
Тест