Алгоритм для системы управления исходным кодом?
Я должен записать простую систему управления исходным кодом и задаться вопросом, какой алгоритм я использовал бы для различий в файле?
Я не хочу изучать существующий исходный код, должный лицензировать проблемы. У меня должен быть лицензируемый под MPL, таким образом, я не могу посмотреть ни на одну из существующих систем как CVS или Подвижный, поскольку они - весь лицензируемый GPL.
Только для предоставления некоторого фона мне просто нужны некоторые действительно простые функции - двоичные файлы в папке. никакие подпапки и каждый файл не ведут себя как свой собственный репозиторий. Никакие Метаданные за исключением некоторых полномочий.
Полный действительно простой материал, мое единственное беспокойство действительно - то, как сохранить только различия файла от пересмотра до пересмотра, не тратя впустую слишком много пространства, но также и не будучи слишком неэффективным (Возможно, хранят полную версию каждые X изменений, немного как Ключевые кадры в Видео?)
7 ответов
Алгоритмы самой длинной общей подпоследовательности являются основным механизмом используется инструментами, подобными diff, и может использоваться системой управления исходным кодом.
«Обратные дельты» - это распространенный подход к хранению, поскольку вам в первую очередь необходимо вернуться назад во времени от самой последней ревизии.
Как насчет того, чтобы посмотреть исходный код Subversion ? под лицензией Apache License 2.0
Джин Майерс написал хорошую статью Разностный алгоритм O (ND) и его вариации . Когда дело доходит до сравнения последовательностей, Майерс - лучший выбор. Вам, вероятно, также следует прочитать статью Уолтера Тичи о RCS; в нем объясняется, как сохранить набор файлов, сохранив самую последнюю версию и различия.
Я на самом деле думал о чем-то похожем на днях ... (странно, да?)
У меня нет для вас отличного ответа, но я пришел к выводу, что если бы я написал инструмент сравнения файлов, который я бы сделал с помощью алгоритма (для поиска различий), который функционирует примерно так же, как REGEXes с их жадностью.
Что касается хранения DIFF ... На вашем месте вместо хранения DIFF, обращенных вперед (т. Е. Вы начинаете с исходного файла, а затем компьютер 150 сравнивает его, когда вы работаете с версией 151), используйте сохраненные DIFF. для вашей истории, но сохраните ваш последний файл как полную версию. Если вы сделаете это таким образом, то всякий раз, когда вы работаете с последним файлом (что, вероятно, в 99% случаев), вы получите максимальную производительность.
Идея хранения дельт (вперед или назад) является классической в отношении управления версиями. Проблема всегда заключалась в том, «какую дельту вы храните?»
. Многие системы управления версиями хранят дельты, вычисленные по существу с помощью «diff», например, строчно-ориентированное дополнение самых длинных общих подпоследовательностей. Но вы можете вычислить дельты для определенных типов документов способом, специфичным для этих документов, чтобы получить меньшие (и часто более понятные) дельты.
Для исходного кода языков программирования можно вычислить расстояния Левенштейна по программным структурам. Набор инструментов для этого для множества популярных языков программирования можно найти на Smart Differencer
. Если вы храните нетекстовые файлы, вы можете воспользоваться их структурой для вычисления меньших дельт. .
Конечно, если вам нужна минимальная реализация, то просто сохранить полный образ каждой версии файла легко. Терабайтные диски делают это решение работоспособным, если не красивым. (Для этого неявно использовалась файловая система PDP10).
Хотя fossil является GPL, дельта-алгоритм основан на rsync и описан здесь
Patience Diff - хороший алгоритм для поиска различий между двумя файлами, которые могут быть понятны людям. Это часто дает лучшие результаты, чем наивный алгоритм «самой длинной общей подпоследовательности», но результаты субъективны.
При этом многие современные системы контроля версий хранят полные файлы на каждом этапе и вычисляют фактические различия позже, только когда это необходимо. Для двоичных файлов (которые, вероятно, не очень-то сжимаются), вы можете обнаружить, что хранение обратных дельт может быть в конечном итоге более эффективным.