Различие данных
В информатике и теории информации различие данных или дифференциальное сжатие дает техническое описание разницы между двумя наборами данных — источником и целью. Формально, алгоритм дифференцирования данных принимает в качестве входных исходные данные и целевые данные и создает разностные данные, так что, учитывая исходные данные и разностные данные, можно реконструировать целевые данные (« исправление » источника с разницей для создания целевых данных). .
Примеры
[ редактировать ]Одним из наиболее известных примеров дифференцирования данных является утилита diff , которая создает построчные различия текстовых файлов (а в некоторых реализациях и двоичных файлов , таким образом являясь инструментом дифференцирования общего назначения). Различие обычных двоичных файлов относится к категории дельта-кодирования , широко используемым примером является алгоритм, используемый в rsync . Стандартизированным общим форматом разностей является VCDIFF , реализованный в таких утилитах, как Xdelta версии 3. Высокоэффективной (небольшие файлы исправлений) программой разностей является bsdiff, которая использует bzip2 в качестве последнего этапа сжатия сгенерированной разности. [1]
Обеспокоенность
[ редактировать ]Основными проблемами при различении данных являются удобство использования и эффективность использования пространства (размер патча).
Если кто-то просто желает реконструировать цель с учетом источника и исправления, можно просто включить всю цель в исправление и «применить» исправление, отбросив источник и выведя цель, которая была включена в исправление; аналогично, если источник и цель имеют одинаковый размер, можно создать простой патч, выполнив XOR для источника и цели. В обоих случаях патч будет такого же размера, как и цель. Как показывают эти примеры, если единственной проблемой является реконструкция цели, это легко сделать за счет большого патча, а основной проблемой при двоичном дифференцировании общего назначения является уменьшение размера патча.
Особенно в отношении структурированных данных возникают другие проблемы, которые в основном подпадают под «удобство использования» — например, если сравниваются два документа, обычно хочется знать, какие разделы были изменены, или если некоторые разделы были перемещены — нужно понять , чем отличаются документы. Например, «здесь слово «кошка» заменено на «собака», а пункт 13 перенесен в пункт 14». Можно также захотеть иметь надежные различия — например, если два документа A и B различаются в параграфе 13, можно применить это исправление, даже если кто-то изменил параграф 7 документа A. Примером этого является diff. , который показывает, какие строки были изменены и где формат контекста обеспечивает надежность и удобочитаемость для человека.
Другие проблемы включают вычислительную эффективность, а также сжатие данных: поиск небольшого патча может занять очень много времени и памяти.
Наилучшие результаты достигаются тогда, когда вы знаете сравниваемые данные и другие ограничения: diff предназначен для строковых текстовых файлов, особенно исходного кода, и лучше всего работает для них; алгоритм rsync используется на основе того, что источник и цель находятся в сети друг от друга, а связь медленная, поэтому он сводит к минимуму данные, которые необходимо передать; а обновления для Google Chrome используют алгоритм, адаптированный к архивному и исполняемому формату данных программы. [2] [3]
Соединение со сжатием данных
[ редактировать ]Сжатие данных можно рассматривать как частный случай различия данных. [4] [5] – Различие данных состоит из создания разницы с учетом источника и цели , при этом исправление создает цель с учетом источника и разницы, в то время как сжатие данных состоит из создания сжатого файла с учетом цели, а распаковка состоит из создания цели с учетом только сжатый файл. Таким образом, можно рассматривать сжатие данных как различие данных с пустыми исходными данными, причем сжатый файл соответствует «отличию от ничего». Это то же самое, что рассматривать абсолютную энтропию (соответствующую сжатию данных) как частный случай относительной энтропии (соответствующей различению данных) при отсутствии исходных данных.
Если кто-то хочет подчеркнуть связь, можно использовать термин «дифференциальное сжатие» для обозначения различия данных.
Словарь, переводящий терминологию двух полей, имеет вид:
| сжатие | различие |
|---|---|
| никто | источник |
| несжатый | цель |
| сжатый | разница, дельта |
| сжатие | различие |
| декомпрессия | исправление |
Ссылки
[ редактировать ]- ^ Колин Персиваль , Наивные различия исполняемого кода, http://www.daemonology.net/bsdiff/ , 2003.
- ^ Блог Chromium: Чем меньше, тем быстрее (и безопаснее)
- ^ Обновления программного обеспечения: Кабачки (Проекты Chromium)
- ^ RFC 3284
- ^ Корн, Д.Г.; Во, КП (1995), Б. Кришнамурти (редактор), Vdelta: дифференцирование и сжатие , Практическое многоразовое программное обеспечение Unix, John Wiley & Sons