Создание патчей: алгоритмы
Какой вопрос такой ответ.
Существует.
Он перебирает все патчи длины 1 (их конечное количество) , потом все патчи длины 2 (их тоже конечное количество ... пока не найдет подходящий.
Клевая штука теория алгоритмов
Существует.
Он перебирает все патчи длины 1 (их конечное количество) , потом все патчи длины 2 (их тоже конечное количество ... пока не найдет подходящий.
Клевая штука теория алгоритмов
А какой чаще всего используется?
Есть и получше алгоритмы. Что-то типа такого:
динамика по длине "правильного" префикса. В ячейках таблицы <длина полученного слова>x<длина правильного префикс> ставим минимальное число необходимых для ее достижения операций.
Задача прийти из точки (n,0) в точку (m,m). n, m - длины соответственно исходного слова и конечного слова.
При правильном подходе такая идея должна давать квадратичный по длине слов алгоритм.
динамика по длине "правильного" префикса. В ячейках таблицы <длина полученного слова>x<длина правильного префикс> ставим минимальное число необходимых для ее достижения операций.
Задача прийти из точки (n,0) в точку (m,m). n, m - длины соответственно исходного слова и конечного слова.
При правильном подходе такая идея должна давать квадратичный по длине слов алгоритм.
О! Спасибо. Есть надежда, что это получится реализовать.
Не думаю. Памяти не хватит. На сколь нибудь больших входах.
/*
здесь был написан следующий бред:
расход памяти растет линейно от длины: храним только 2 слоя таблицы.
*/
А на самом деле ты прав: где есть нормальной длины бинарные данные, там почти всегда проще передать новые целиком, чем париться и пытаться патч сделать. Кроме того такой набор операций в природе не встречается... Интерес в этой задаче скорее академический.
здесь был написан следующий бред:
расход памяти растет линейно от длины: храним только 2 слоя таблицы.
*/
А на самом деле ты прав: где есть нормальной длины бинарные данные, там почти всегда проще передать новые целиком, чем париться и пытаться патч сделать. Кроме того такой набор операций в природе не встречается... Интерес в этой задаче скорее академический.
Задача: генерить патчи к почти одинаковым файлам, в которых отличаются 10-1000 байт, т.е. расход памяти не такой уж и значительный. А почему такой набор операций не встречается в природе?
вот есть такая программка:
elta
если серьёзно интересна проблема, посмотри в исходниках diff'а в файле analyze.c есть ссылка на статьи:
elta
если серьёзно интересна проблема, посмотри в исходниках diff'а в файле analyze.c есть ссылка на статьи:
"An O(ND) Difference Algorithm and its Variations", Eugene Myers,и
Algorithmica Vol. 1 No. 2, 1986, pp. 251-266;
"Algorithms for Approximate String Matching", E. Ukkonen,Правда это про текстовые файлы, но рыская в гугле в поисках первой статьи, я нашёл что-то про применение к бинарным, и потом вышел на elta.
Information and Control Vol. 64, 1985, pp. 100-118.
Раход памяти здесь не зависит от длины патча. Впрочем, ты можешь попытаться что-то в этом изменить. Например, если все изменения локализованы в небольшой области, то это поможет.
А насчет набора операций: гоню. Даже знаю как такой патч к файлу присобачивать. Правда опять за время, зависящее от длины файла, а не патча.
А насчет набора операций: гоню. Даже знаю как такой патч к файлу присобачивать. Правда опять за время, зависящее от длины файла, а не патча.
Выступлю в роле психотерапевта. 
Тебе это не нужно!
Нет, серьезно,
Тебе нужно не это!
Чего велосипеды то изобретать, раз нет популярного тула, который такие патчи строит, значит на это есть причины. И никакие статьи тут не помогут.
Я фсе сказал
Тебе это не нужно!
Нет, серьезно,
Тебе нужно не это!
Задача: генерить патчи к почти одинаковым файлам, в которых отличаются 10-1000 байтЭти почти одинаковые файлы, наверное получились один из другого исходя из каких-то соображений? Вот и пересылай эти соображения, а не какие-то непонятные патчи...
Чего велосипеды то изобретать, раз нет популярного тула, который такие патчи строит, значит на это есть причины. И никакие статьи тут не помогут.
Я фсе сказал
Эти почти одинаковые файлы, наверное получились один из другого исходя из каких-то соображений? Вот и пересылай эти соображения, а не какие-то непонятные патчи...респект. хотя ты и не совсем прав.
Приведу аналогию с популярным diff'ом. Вместо того, чтобы применить автомат и получить патч человек должен сам написать, что он и куда добавил. Короче, попахивает ручной работой. И потом, когда изменения сделаны кем-то третьим, не всегда вообще можно вычленить какие-то соображения.
Но действительно, привязка к конкретной области может очень сильно упростить задачу.
Да есть популярные тулзы. Сам видел, правда названия не помню, а гуглить влом - чуваку нужно, пусть сам и гуглит.
elta ?
Кстати насчет diff, есть же wdiff, он как раз не построково я побайтово работает. Правда боюсь, что его эвристика заточена все таки под текстовую информацию.
Да есть популярные тулзыНу так и замечательно тогда! Значит надо искать. Меня вот такой подход удивил:
Есть надежда, что это получится реализовать.Все что можно написать, уже написано давно... ну почти все
2: Спасибо за ссылки, посмотрю
Эти почти одинаковые файлы, наверное получились один из другого исходя из каких-то соображений? Вот и пересылай эти соображения, а не какие-то непонятные патчи...Соображения неизвестны.
Да есть популярные тулзы. Сам видел, правда названия не помню, а гуглить влом - чуваку нужно, пусть сам и гуглит.Где-то на моих компактах есть целая пачка. Но они без исходников.
Все что можно написать, уже написано давно... ну почти всеПолучится реализовать: фраза, учитывающая кривизну моих рук
Но они без исходников.А зачем тебе писать самому, если они и так уже есть?
В образовательных целях
Оставить комментарий
Vladislav177Rus
Существует ли алгоритм создания патча минимальной длины, если под единицей длины считается замена/удаление/вставка одного байта?