Построчный diff на PHP без библиотек: как показать «было → стало»
Было → стало ♡
Своими руками ♡
Когда сервис пишет «страница изменилась», это полдела. Человеку нужно понять, что именно: цена, пара слов или целый абзац. Для этого нужен diff, то есть список того, что удалено и что добавлено. Готовых библиотек вагон, но тут задача настолько узкая, что я написала свою. Получилось около полутора сотен строк вместе с комментариями, и половина из них про то, как не уронить сервер.
Идея: найти то, что не изменилось
Классический способ найти различия заключается в том, чтобы сначала найти общее. Берём две версии текста, разбитые на строки, и ищем наибольшую общую подпоследовательность, то есть самую длинную цепочку строк, которая встречается в обеих версиях в одном порядке. Всё, что в старой версии вне этой цепочки, считается удалённым, а всё, что в новой вне цепочки, считается добавленным.
Строится это таблицей: для каждой пары позиций хранится длина общей части справа от них, а потом по таблице проходим от начала и на каждом шаге решаем, совпали строки, удалили мы строку или добавили. Память и время растут как произведение длин, поэтому дальше начинаются хитрости.
Хитрость первая: срезать общие края
На практике страница меняется в паре мест, а остальной текст идентичен. Перед тем как строить таблицу, я сравниваю тексты с начала и с конца и отбрасываю одинаковые строки. Таблица строится только для серединки, где реально что-то происходит. Если поменялась цена в одной строке, вместо таблицы на тысячи ячеек получится таблица из одной.
Что делается с результатом
- Оставляются только изменённые строки и по одной строке контекста вокруг них, чтобы было понятно, где это происходит.
- Длинные одинаковые участки схлопываются в многоточие, полный неизменный текст в изменении не хранится.
- Для уведомления собирается короткая сводка. Если удалённых и добавленных строк поровну и их не больше трёх, она выглядит как «было → стало», иначе показываются первые строки со знаками минус и плюс и пометка «и ещё столько-то изменений».
Хитрость вторая: аварийный режим
Таблица в три тысячи на три тысячи ячеек это девять миллионов чисел в памяти ради одной проверки. Поэтому у сравнения есть потолок: если в любой из версий больше трёх тысяч строк, включается грубое сравнение. Оно просто выписывает строки, которых нет в другой версии, без учёта порядка и не более двухсот штук с каждой стороны. Точность хуже, зато сервер жив.
Для тех, кто следит за ценой в карточке или за одним абзацем в документе, этого за глаза. Как исходный текст вообще получается из страницы, описано в предыдущей записи.
Про тесты
С такими алгоритмами главное не верить собственному коду на слово, а гонять его на подлых мелочах вроде пустой старой версии или двух переставленных строк. Похожая история про недоверие к своему коду есть в записи про тест, который нашёл дыру.
Комментарии
Буду рада вашим мыслям, идеям и вопросам!
Давайте обсуждать ♡
Делитесь
своими мыслями
— мне очень
это важно ♡