Дано: две строки, $str1 и $str2 (предположим, старая и новая версии статьи). Задача: сравнить и определить, что в новой версии добавилось, что исчезло, что осталось без изменений. Пример: $str1="У Мэри был ягненок."; $str2="У Мэри был ягненок, и она его любила."; Результат: структура примерно такого вида: Код (Text): array( array( "type"=>"unchanged" "text"=>"У Мэри был ягненок" ) array( "type"=>"added" "text"=>", и она его любила" ) array( "type"=>"unchanged" "text"=>"." ) ) Соответственно есть 3 типа блоков: unchanged, added и removed. Есть хорошие идеи, как такое реализовать?
Первое, что приходит в голову: 1. Разбиваем строки на слова (получаем массив слов) 2. Последовательно сравниваем значения массивов. 2.1. Если значения ключей равны, то едемдальше. 2.2. Если не равны, то ищем в «новом» массиве следующее значение «старого» массива. Разница по сути и есть «добавление». Ну и едем дальше. Недостаток: надо продумать такой момент: удаление из исходной строки какого-либо слова.
как вариант: из одной строки делаем регулярку типа Код (Text): /^(.*?)(a?)(.*?)(b?)(.*?)(c?)(.*?)$/ - это для строки "abc" c помощью этой регулярки во второй строке находим "костяк" - группы символов (и их координаты), которые не изменились. затем находим изменившиеся подстроки между элементами "костяка".
Пара пожеланий/уточнений к алгоритму: - он не должен разбивать слова (как упомянул AlexGousev); - если два фрагмента поменялись местами, то желательно, чтобы больший из них пометился как не изменившийся, а меньший - как удаленный в одном месте и добавленный в другом. Пока что, как мне кажется, задача сводится лишь к поиску одинаковых фрагментов, все остальное несложно...
Значит, для начала, надо определиться, на какие фрагменты разбивать строку, чтобы производить сравнение. diff разбивает по строчкам. Можно разбивать по предложениям, словам, парам-тройкам слов и т.п. Соответственно и поиск изменений будет производится именно с той точностью, какую выберем при разбивке.
Dagdamor зачем велосипед изобретать, возьми исходники svn(C), или eventum(php), да посмотри как это реализовано там.
Davil Ну как тебе сказать, я изложил задачу в первой мессаге, а ты предложил решение для другой задачи А так никаких проблем.
AlexGousev Разбиваем с точностью до символа, но слова не трогаем. То есть разбивка по словам, а за пределами слов - посимвольная. Слово - [a-zA-Zа-яА-Я_]+. Вроде такой вариант звучит наиболее логично. Davil Насколько я понял, diff, который ты предлагаешь, сравнивает фрагменты с точностью до строки, а здесь понятия строки вообще нет - текст идет сплошным потоком. Переносы строк могут быть, но они не являются разделителями, просто часть текста.
AlexGousev Кстати - что значит фраза "стандартный diff"? В каком смысле стандартный? dark-demon Пишу библиотеку, которая потребуется плагину для моего движка. Смысл в том, чтобы не выводить два экземпляра статьи слева и справа, как в Википедии, а отобразить статью целиком, фоновым цветом подкрасив изменившиеся (удаленные и добавленные) области.
Dagdamor я не предлагаю diff. Я предлагаю реализацию. А diff заменить на что-то другое - это такая серьезная проблема?
Dagdamor, тогда проще производить редактирование через специальный редактор на базе design-mode, который бы при нажатии на del обрамлял бы выделенное тэгом <del>, а набираемый текст - тегом <ins>