Сравнение данных

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

• 1 Примеры
• 2 Проблемы
• 3 Связь со сжатием данных
• 4 Ссылки

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

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

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

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

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

Наилучшие результаты достигаются, когда кто-то знает сравниваемые данные и другие ограничения: diff разработан для строчно-ориентированных текстовых файлов, в частности исходного кода, и лучше всего подходит для них; алгоритм rsync используется на основе того, что источник и цель находятся в сети друг от друга, а обмен данными является медленным, поэтому он минимизирует данные, которые необходимо передать; а обновления для Google Chrome используют алгоритм, настроенный для архива и исполняемого формата данных программы.

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

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

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