Различие данных - Data differencing

В Информатика и теория информации, различие данных или же дифференциальное сжатие производит техническое описание разницы между двумя наборами данных - источником и целью. Формально алгоритм дифференцирования данных принимает в качестве входных исходных данных и целевых данных и создает данные разности, так что с учетом исходных данных и данных разности можно восстановить целевые данные ("исправление "источник с разницей, чтобы произвести цель).

Примеры

Один из самых известных примеров различения данных - это разница утилита, которая выводит построчную разницу текстовые файлы (а в некоторых реализациях двоичные файлы, таким образом являясь универсальным инструментом дифференцирования). Различие общих двоичных файлов проходит под рубрикой дельта-кодирование, широко используемым примером является алгоритм, используемый в rsync. Стандартизованный универсальный формат сравнения: VCDIFF, реализованный в таких утилитах, как Xdelta версия 3. Высокоэффективная программа сравнения (небольшие файлы патчей) - это bsdiff, которая использует bzip2 как заключительный этап сжатия на сгенерированной дельте.^[1]

Обеспокоенность

Основные проблемы, связанные с различием данных: удобство использования и эффективность использования пространства (размер патча).

Если кто-то просто желает восстановить цель с учетом источника и патча, можно просто включить целую цель в патч и «применить» патч, отбросив источник и вывести цель, которая была включена в патч; аналогично, если источник и цель имеют одинаковый размер, можно создать простой патч, XORing источник и цель. В обоих случаях размер патча будет равен размеру мишени. Как показывают эти примеры, если единственной проблемой является реконструкция цели, это легко сделать за счет большого патча, а основная проблема для двоичного разностного анализа общего назначения - это уменьшение размера патча.

В частности, в отношении структурированных данных есть другие проблемы, которые в основном относятся к «удобству использования» - например, если сравнивают два документа, обычно нужно знать который разделы изменились, или, если некоторые разделы были перемещены - хочется понять как документы различаются. Например, «здесь« кошка »было заменено на« собака », а пункт 13 был перемещен в пункт 14». Можно также пожелать иметь крепкий различия - например, если два документа A и B отличаются в параграфе 13, кто-то может захотеть применить этот патч, даже если кто-то изменил параграф 7 из A. Пример этого находится в diff, который показывает, какие строки изменились, и где контекстный формат обеспечивает надежность и улучшает удобочитаемость.

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

Наилучшие результаты достигаются, когда человек знает сравниваемые данные и другие ограничения: разница предназначен для строчно-ориентированных текстовых файлов, особенно исходного кода, и лучше всего подходит для них; в rsync алгоритм используется на основе того, что источник и цель находятся в сети друг от друга, а связь медленная, поэтому он минимизирует данные, которые должны быть переданы; и обновления для Гугл Хром использовать алгоритм, адаптированный к архиву и исполняемому формату данных программы.^[2][3]

Подключение со сжатием данных

Основная статья: Сжатие данных

Сжатие данных можно рассматривать как частный случай различения данных^[4][5] - дифференциация данных заключается в создании разница учитывая источник и цель, с исправлением, производящим цель учитывая источник и разница, в то время как сжатие данных состоит в создании сжатого файла по заданному целевому объекту, а распаковка заключается в создании целевого файла из только сжатого файла. Таким образом, сжатие данных можно рассматривать как разность данных с пустыми исходными данными, причем сжатый файл соответствует «отличию от ничего». Это то же самое, что и абсолютное энтропия (соответствующий сжатию данных) как частный случай относительная энтропия (соответствует разности данных) без исходных данных.

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

Словарь, переводящий терминологию этих двух полей, представлен как:

сжатие	различение
никто	источник
несжатый	цель
сжатый	разница, дельта
сжатие	различение
декомпрессия	исправление

Рекомендации

1. Колин Персиваль, Наивные различия исполняемого кода, http://www.daemonology.net/bsdiff/, 2003.
2. Блог Chromium: Меньше значит быстрее (и безопаснее)
3. Обновления программного обеспечения: Courgette (проекты Chromium)
4. RFC  3284
5. Korn, D.G .; Во, К. (1995), Б. Кришнамурти (ред.), Vdelta: различие и сжатие, Практическое программное обеспечение Unix многократного использования, Джон Уайли и сыновья