Алгоритм для системы управления версиями?

Question

Мне нужно написать простую систему управления версиями и задаться вопросом, какой алгоритм я буду использовать для различий файлов?

Я не хочу изучать существующий исходный код из-за проблем с лицензией. Мне нужно иметь лицензию в MPL, чтобы я не мог смотреть на какие-либо существующие системы, такие как CVS или Mercurial, поскольку они все лицензированы GPL.

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

В целом очень простые вещи, моя единственная проблема заключается в том, как хранить только различия в файле от пересмотра до ревизии, не тратя слишком много места, но также не будучи слишком неэффективным (возможно, хранить полную версию, каждый X изменяется, немного как ключевые кадры в видео?)

Answer 1

Самые длинные алгоритмы Common Subsequence являются основным механизмом, используемым средствами сравнения, и могут быть использованы системой управления исходным кодом.

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

Answer 2

Я был на самом деле думает о чем-то похожее на это в другой день ... (нечетное, да?)

У меня нет большой ответ для вас, но я пришел к выводу, что если бы я был написать файл diff tool, чтобы я сделал это с помощью алгоритма (для поиска diff), который функционирует примерно так же, как функция REGEXes работает с их жадностью.

Что касается хранения DIFF ... Если бы я был вами, вместо хранения передних DIFF (то есть вы начинаете с исходного файла, а затем компьютер 150 отличается от него при работе с версией 151), используйте сохраненные DIFF для вашей истории, но ваш последний файл хранится как полная версия. Если вы сделаете это так, то всякий раз, когда вы работаете с последним файлом (что, вероятно, в 99% случаев), вы получите максимальную производительность.

Answer 3

Как насчет того, чтобы посмотреть исходный код Subversion? его под лицензией Apache License 2.0

Answer 4

Хотя окаменелость GPL, алгоритм дельта основан на Rsync и описал here

Answer 5

Patience Diff хороший алгоритм для нахождения дельт между двумя файлами, которые могут иметь смысл для людей. Это часто дает лучшие результаты, чем наивный алгоритм «самой длинной общей подпоследовательности», но результаты субъективны.

Сказав, что многие современные системы контроля версий хранят полные файлы на каждом этапе и вычисляют фактические различия позже, только когда это необходимо. Для двоичных файлов (которые, вероятно, не очень сжимаются) вы можете обнаружить, что сохранение обратных дельт может быть в конечном итоге более эффективным.

Answer 6

Джин Майерс написал хорошую бумагу An O(ND) Difference Algorithm and its Variations. Когда дело доходит до сравнения последовательностей, Майерс - это человек. Вероятно, вам также следует прочитать статью Уолтера Тичи о RCS; в нем объясняется, как хранить набор файлов, сохраняя самую последнюю версию плюс различия.

Answer 7

Идея хранения дельт (вперед или назад) является классикой в ​​отношении контроля версий. Вопрос всегда был: «Какую дельта вы храните?«

Многие системы управления источниками хранят дельта, которые вычисляются по существу« diff », например, линейно-ориентированное дополнение к самым длинным общим подпоследовательностям. Но вы можете вычислить дельт для конкретных типов документов таким образом, который подходит для этих документов , чтобы получить более мелкие (и часто более понятные) дельта.

Для исходного кода языков программирования можно вычислить расстояния Левенштейна над структурами программ. Набор инструментов для выполнения этого для множества популярных программируемых языков можно найти по адресу Smart Differencer

Если вы храните нетекстовые файлы, вы можете использовать их структуру для вычисления s деликатесы.

Конечно, если вы хотите, это минимальная реализация, то просто сохранить полное изображение каждой версии файла легко. Террабайтные диски делают это решение работоспособным, если не красивым. (Файловая система PDP10 использовала это неявно).