Най-дълга обща подредица и diff
Накратко: Най-дългата обща подредица (LCS) на две поредици се намира с таблица за O(n · m) и стои под diff: редовете извън нея са изтритите и добавените.
Проблем
Какво се промени в настройките?
Магазинът пази настройките си в текстов файл. Клиент пише, че доставката изведнъж е по-евтина. В системата има две версии на файла, вчерашната и днешната, и трябва да видиш кое точно е сменено, ред по ред, както го показва git diff.
Първата идея е да сравниш ред 1 с ред 1, ред 2 с ред 2 и така нататък:
was = [ "shop=Bookstore", "currency=EUR", "shipping=4.99", "free_from=50", "pay=card", "pay=cash",]now = [ "shop=Bookstore", "currency=EUR", "vat=20", "shipping=3.99", "free_from=50", "pay=card",]for old, new in zip(was, now): if old == new: print(" " + old) else: print("- " + old) print("+ " + new) 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 са нули: празен файл няма общо с нищо.
Виж го
Таблицата
def lcs_table(was, now): n, m = len(was), len(now) dp = [[0] * (m + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(1, m + 1): if was[i - 1] == now[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: up = dp[i - 1][j] left = dp[i][j - 1] dp[i][j] = max(up, left) return dpfor _ in range(n + 1). Изкушението [[0] * (m + 1)] * (n + 1) е капан: това са n + 1 указателя към един и същ ред, и запис в dp[1] сменя всички редове наведнъж.Двете версии на файла и таблицата, която програмата смята за тях:
was = [ "shop=Bookstore", "currency=EUR", "shipping=4.99", "free_from=50", "pay=card", "pay=cash",]now = [ "shop=Bookstore", "currency=EUR", "vat=20", "shipping=3.99", "free_from=50", "pay=card",]for row in lcs_table(was, now): print(*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 4def diff(was, now): dp = lcs_table(was, now) result = [] i, j = len(was), len(now) while i > 0 and j > 0: if was[i - 1] == now[j - 1]: result.append(" " + was[i - 1]) i -= 1 j -= 1 elif dp[i][j - 1] >= dp[i - 1][j]: result.append("+ " + now[j - 1]) j -= 1 else: result.append("- " + was[i - 1]) i -= 1 while j > 0: result.append("+ " + now[j - 1]) j -= 1 while i > 0: result.append("- " + was[i - 1]) i -= 1 result.reverse() return resultdef lcs_table(was, now): n, m = len(was), len(now) dp = [[0] * (m + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(1, m + 1): if was[i - 1] == now[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: up = dp[i - 1][j] left = dp[i][j - 1] dp[i][j] = 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: четири реда са останали. Кои са, казва обратният път.
Пробвай
Предвиди изхода
Маршрутът на куриера във вторник и в сряда. Колко спирки са в същия ред и в двата дни?
def lcs_table(was, now): n, m = len(was), len(now) dp = [[0] * (m + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(1, m + 1): if was[i - 1] == now[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: up = dp[i - 1][j] left = dp[i][j - 1] dp[i][j] = max(up, left) return dp
tuesday = [ "Склад", "Лозенец", "Център", "Младост", "Дружба",]wednesday = [ "Склад", "Център", "Лозенец", "Дружба",]dp = lcs_table(tuesday, wednesday)print(dp[-1][-1])Идеята
Обратният път: diff
Таблицата помни как е получено всяко число. Тръгни от ъгъла dp[n][m] и върви назад:
- редовете са еднакви: общ ред, пиши го с интервал и иди по диагонала;
- лявата клетка не е по-малка от горната: ред j от новата версия не е в общата подредица, пиши го с „+“ и иди наляво;
- иначе ред i от старата версия го няма в новата: пиши го с „-“ и иди нагоре.
Когато стигнеш края на едната версия, всичко останало от другата е само „+“ или само „-“. Пътят върви от последните редове към първите, затова накрая списъкът се обръща.
def diff(was, now): dp = lcs_table(was, now) result = [] i, j = len(was), len(now) while i > 0 and j > 0: if was[i - 1] == now[j - 1]: result.append(" " + was[i - 1]) i -= 1 j -= 1 elif dp[i][j - 1] >= dp[i - 1][j]: result.append("+ " + now[j - 1]) j -= 1 else: result.append("- " + was[i - 1]) i -= 1 while j > 0: result.append("+ " + now[j - 1]) j -= 1 while i > 0: result.append("- " + was[i - 1]) i -= 1 result.reverse() return resultfor line in diff(was, now): print(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, но с неговата таблица:
def lcs_table(was, now): n, m = len(was), len(now) dp = [[0] * (m + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(1, m + 1): if was[i - 1] == now[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: up = dp[i - 1][j] left = dp[i][j - 1] dp[i][j] = max(up, left) + 1 return dpfor line in diff(was, now): print(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] = 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 |
def lcs_table(was, now): n, m = len(was), len(now) dp = [[0] * (m + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(1, m + 1): if was[i - 1] == now[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: up = dp[i - 1][j] left = dp[i][j - 1] dp[i][j] = 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от урока не на редове, а на думите на две описания на продукт, разделени с интервал.
Тест