Слияние версий документа. Долблюсь дальше:(

Sikoz 01.02.2005 11:58

задача: есть две версии документа, одну сделал Вася, другую Петя. Они оба использовали для модификации версию Акакия. Как сделать, чтобы правки и Васи, и Пети автоматически поместились в один документ?

Народ советует rsync: http://citforum.proc.ru/nets/articles/rsync/
Текст можно резать lsplit'ом, хэшировать куски с помощью math:crypt или md5. По сравнению с условиями для того алгоритма имеем в плюсе наличие небольших документов и следовательно - некритичность к ресурсам.
Чего я не понял: как сделать, чтобы этот алгоритм работал не только до первого найденного различия, а до всех, и уверенно находил общий текст после различий? Ведь происходит смещение шага.

Вариант второй:
Берем во всех текстах последовательности слов (например, по 10 слов) и их хэшируем с перехлестом по 1 слову (т.е. сначала с 1 по 10 слова, затем со 2 по 11, с 3 по 12 и т.д.)

$tab_Vasya[^Vasya_text.split[v; ]]
$Vasya_hash[
  $.1[^math:md5[^getrows[$tab_Vasya;1;10]]]
  $.2[...]
]

По идее, таких хэшей может быть сколько угодно. При этом последний по времени обладает большим приоритетом.
За достоверность ключа ручаются два положения:
1) происходит последовательный перебор от начала к концу
2) если в двух документах, один из которых унаследован от другого, повторяются фразы из 20 слов (перебор-то последовательный, значит 10 + 10), то эти фразы относятся к одной и той же смысловой части документа.
Тут вопрос такой: наверняка не я первый придумал этот алгоритм, и где-то уже есть его описание со всеми подводными камнями - мож кто знает?

P.S. Понимаю, что это не тривиальная для парсера задача, но полноценной CMS без нее не сделать. А хочется, ибо остальное уже готово и скоро будет доступно по GNU GPL.

---