Построчный diff на PHP без библиотек: как показать «было → стало»

0

Было → стало ♡

Построчный diff на PHP без библиотек: как показать «было → стало»
Было → стало.
Своими руками ♡

Когда сервис пишет «страница изменилась», это полдела. Человеку нужно понять, что именно: цена, пара слов или целый абзац. Для этого нужен diff, то есть список того, что удалено и что добавлено. Готовых библиотек вагон, но тут задача настолько узкая, что я написала свою. Получилось около полутора сотен строк вместе с комментариями, и половина из них про то, как не уронить сервер.

Идея: найти то, что не изменилось

Классический способ найти различия заключается в том, чтобы сначала найти общее. Берём две версии текста, разбитые на строки, и ищем наибольшую общую подпоследовательность, то есть самую длинную цепочку строк, которая встречается в обеих версиях в одном порядке. Всё, что в старой версии вне этой цепочки, считается удалённым, а всё, что в новой вне цепочки, считается добавленным.

Строится это таблицей: для каждой пары позиций хранится длина общей части справа от них, а потом по таблице проходим от начала и на каждом шаге решаем, совпали строки, удалили мы строку или добавили. Память и время растут как произведение длин, поэтому дальше начинаются хитрости.

Хитрость первая: срезать общие края

На практике страница меняется в паре мест, а остальной текст идентичен. Перед тем как строить таблицу, я сравниваю тексты с начала и с конца и отбрасываю одинаковые строки. Таблица строится только для серединки, где реально что-то происходит. Если поменялась цена в одной строке, вместо таблицы на тысячи ячеек получится таблица из одной.

Что делается с результатом

  1. Оставляются только изменённые строки и по одной строке контекста вокруг них, чтобы было понятно, где это происходит.
  2. Длинные одинаковые участки схлопываются в многоточие, полный неизменный текст в изменении не хранится.
  3. Для уведомления собирается короткая сводка. Если удалённых и добавленных строк поровну и их не больше трёх, она выглядит как «было → стало», иначе показываются первые строки со знаками минус и плюс и пометка «и ещё столько-то изменений».

Хитрость вторая: аварийный режим

Таблица в три тысячи на три тысячи ячеек это девять миллионов чисел в памяти ради одной проверки. Поэтому у сравнения есть потолок: если в любой из версий больше трёх тысяч строк, включается грубое сравнение. Оно просто выписывает строки, которых нет в другой версии, без учёта порядка и не более двухсот штук с каждой стороны. Точность хуже, зато сервер жив.

Для тех, кто следит за ценой в карточке или за одним абзацем в документе, этого за глаза. Как исходный текст вообще получается из страницы, описано в предыдущей записи.

Про тесты

С такими алгоритмами главное не верить собственному коду на слово, а гонять его на подлых мелочах вроде пустой старой версии или двух переставленных строк. Похожая история про недоверие к своему коду есть в записи про тест, который нашёл дыру.

Комментарии

Буду рада вашим мыслям, идеям и вопросам!
Давайте обсуждать ♡

Пока никто не написал.
Станьте первым! ♡

Поддержать проект

Угостить кофе по СБП

Перевод через Систему быстрых платежей, сумма любая. Спасибо, что вы здесь ♡

QR-код для перевода по СБП
Дневник на почте

Подписаться на блог

Когда выйдет новая запись, я пришлю письмо со ссылкой. Без рассылок «просто так» и без спама. Отписаться можно одним нажатием.

Или следить в Telegram