Сжатие данных

Сжа́тие да́нных (англ. data compression) — алгоритмическое преобразование данных, производимое с целью уменьшения занимаемого ими объёма. Применяется для более рационального использования устройств хранения и передачи данных. Синонимы — упаковка данных, компрессия, сжимающее кодирование, кодирование источника. Обратная процедура называется восстановлением данных (распаковкой, декомпрессией).

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

Принципы сжатия данных

В основе любого способа сжатия лежит модель источника данных, или, точнее, модель избыточности. Иными словами, для сжатия данных используются некоторые априорные сведения о том, какого рода данные сжимаются. Не обладая такими сведениями об источнике, невозможно сделать никаких предположений о преобразовании, которое позволило бы уменьшить объём сообщения. Модель избыточности может быть статической, неизменной для всего сжимаемого сообщения, либо строиться или параметризоваться на этапе сжатия (и восстановления). Методы, позволяющие на основе входных данных изменять модель избыточности информации, называются адаптивными. Неадаптивными являются обычно узкоспециализированные алгоритмы, применяемые для работы с данными, обладающими хорошо определёнными и неизменными характеристиками. Подавляющая часть достаточно универсальных алгоритмов являются в той или иной мере адаптивными.

Все методы сжатия данных делятся на два основных класса:

• Сжатие без потерь
• Сжатие с потерями

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

Характеристики алгоритмов сжатия и их применимость

Коэффициент сжатия

Коэффициент сжатия — основная характеристика алгоритма сжатия. Она определяется как отношение объёма исходных несжатых данных к объёму сжатых, то есть: <math>k=\frac{S_o}{S_c}</math>, где k — коэффициент сжатия, S_o — объём исходных данных, а S_c — объём сжатых. Таким образом, чем выше коэффициент сжатия, тем алгоритм эффективнее. Следует отметить:

• если k = 1, то алгоритм не производит сжатия, то есть выходное сообщение оказывается по объёму равным входному;
• если k < 1, то алгоритм порождает сообщение большего размера, нежели несжатое, то есть, совершает «вредную» работу.

Ситуация с k < 1 вполне возможна при сжатии. Принципиально невозможно получить алгоритм сжатия без потерь, который при любых данных образовывал бы на выходе данные меньшей или равной длины. Обоснование этого факта заключается в том, что поскольку число различных сообщений длиной n бит составляет ровно 2ⁿ, число различных сообщений с длиной меньшей или равной n (при наличии хотя бы одного сообщения меньшей длины) будет не больше 2ⁿ. Это значит, что невозможно однозначно сопоставить все исходные сообщения сжатым: либо некоторые исходные сообщения не будут иметь сжатого представления, либо нескольким исходным сообщениям будет соответствовать одно и то же сжатое, а значит их нельзя отличить. Однако даже когда алгоритм сжатия увеличивает размер исходных данных, легко добиться того, чтобы их объём гарантировано не мог увеличиться более, чем на 1 бит. Тогда даже в самом худшем случае будет иметь место неравенство:
<math>k\geqslant\frac{S_o}{S_o+1}</math>
Делается это следующим образом: если объём сжатых данных меньше объёма исходных, возвращаем сжатые данные, добавив к ним «1», иначе возвращаем исходные данные, добавив к ним «0»).

Коэффициент сжатия может быть как постоянным (некоторые алгоритмы сжатия звука, изображения и т. п., например А-закон, μ-закон, ADPCM, усечённое блочное кодирование), так и переменным. Во втором случае он может быть определён либо для каждого конкретного сообщения, либо оценён по некоторым критериям:

• средний (обычно по некоторому тестовому набору данных);
• максимальный (случай наилучшего сжатия);
• минимальный (случай наихудшего сжатия);

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

Допустимость потерь

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

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

Системные требования алгоритмов

Различные алгоритмы могут требовать различного количества ресурсов вычислительной системы, на которых они реализованы:

• оперативной памяти (под промежуточные данные);
• постоянной памяти (под код программы и константы);
• процессорного времени.

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

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

Алгоритм сжатия требует больших вычислительных ресурсов, нежели алгоритм восстановления.

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

Алгоритмы сжатия и восстановления требуют приблизительно равных вычислительных ресурсов.

Наиболее приемлемый вариант для линий связи, когда сжатие и восстановление происходит однократно на двух её концах (например, в цифровой телефонии).

Алгоритм сжатия существенно менее требователен, чем алгоритм восстановления.

Такая ситуация характерна для случаев, когда процедура сжатия реализуется простым, часто портативным устройством, для которого объём доступных ресурсов весьма критичен, например, космический аппарат или большая распределённая сеть датчиков. Это могут быть также данные, распаковка которых требуется в очень малом проценте случаев, например запись камер видеонаблюдения.

Алгоритмы сжатия данных неизвестного формата

Имеется два основных подхода к сжатию данных неизвестного формата:

• На каждом шаге алгоритма сжатия очередной сжимаемый символ либо помещается в выходной буфер сжимающего кодера как есть (со специальным флагом, помечающим, что он не был сжат), либо группа из нескольких сжимаемых символов заменяется ссылкой на совпадающую с ней группу из уже закодированных символов. Поскольку восстановление сжатых таким образом данных выполняется очень быстро, такой подход часто используется для создания самораспаковывающихся программ.
• Для каждой сжимаемой последовательности символов однократно либо в каждый момент времени собирается статистика её встречаемости в кодируемых данных. На основе этой статистики вычисляется вероятность значения очередного кодируемого символа (либо последовательности символов). После этого применяется та или иная разновидность энтропийного кодирования, например, арифметическое кодирование или кодирование Хаффмана, для представления часто встречающихся последовательностей короткими кодовыми словами, а редко встречающихся — более длинными.

См. также

• Архив (информатика)
• Список алгоритмов
• Энтропийное кодирование
• Теория информации
• Теория вероятностей
• Статистика

Литература

• Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. — Диалог-МИФИ, 2002. — С. 384. — ISBN 5-86404-170-X. 3000 экз.
• Д. Сэломон. Сжатие данных, изображения и звука. — М.: Техносфера, 2004. — С. 368. — ISBN 5-94836-027-X. 3000 экз.

Ссылки

• [compression.ru/ compression.ru — ресурс, посвященный сжатию данных]

Отрывок, характеризующий Сжатие данных

– A vos places! [По местам!] – вдруг закричал голос.
Между пленными и конвойными произошло радостное смятение и ожидание чего то счастливого и торжественного. Со всех сторон послышались крики команды, и с левой стороны, рысью объезжая пленных, показались кавалеристы, хорошо одетые, на хороших лошадях. На всех лицах было выражение напряженности, которая бывает у людей при близости высших властей. Пленные сбились в кучу, их столкнули с дороги; конвойные построились.
– L'Empereur! L'Empereur! Le marechal! Le duc! [Император! Император! Маршал! Герцог!] – и только что проехали сытые конвойные, как прогремела карета цугом, на серых лошадях. Пьер мельком увидал спокойное, красивое, толстое и белое лицо человека в треугольной шляпе. Это был один из маршалов. Взгляд маршала обратился на крупную, заметную фигуру Пьера, и в том выражении, с которым маршал этот нахмурился и отвернул лицо, Пьеру показалось сострадание и желание скрыть его.
Генерал, который вел депо, с красным испуганным лицом, погоняя свою худую лошадь, скакал за каретой. Несколько офицеров сошлось вместе, солдаты окружили их. У всех были взволнованно напряженные лица.
– Qu'est ce qu'il a dit? Qu'est ce qu'il a dit?.. [Что он сказал? Что? Что?..] – слышал Пьер.
Во время проезда маршала пленные сбились в кучу, и Пьер увидал Каратаева, которого он не видал еще в нынешнее утро. Каратаев в своей шинельке сидел, прислонившись к березе. В лице его, кроме выражения вчерашнего радостного умиления при рассказе о безвинном страдании купца, светилось еще выражение тихой торжественности.
Каратаев смотрел на Пьера своими добрыми, круглыми глазами, подернутыми теперь слезою, и, видимо, подзывал его к себе, хотел сказать что то. Но Пьеру слишком страшно было за себя. Он сделал так, как будто не видал его взгляда, и поспешно отошел.
Когда пленные опять тронулись, Пьер оглянулся назад. Каратаев сидел на краю дороги, у березы; и два француза что то говорили над ним. Пьер не оглядывался больше. Он шел, прихрамывая, в гору.
Сзади, с того места, где сидел Каратаев, послышался выстрел. Пьер слышал явственно этот выстрел, но в то же мгновение, как он услыхал его, Пьер вспомнил, что он не кончил еще начатое перед проездом маршала вычисление о том, сколько переходов оставалось до Смоленска. И он стал считать. Два французские солдата, из которых один держал в руке снятое, дымящееся ружье, пробежали мимо Пьера. Они оба были бледны, и в выражении их лиц – один из них робко взглянул на Пьера – было что то похожее на то, что он видел в молодом солдате на казни. Пьер посмотрел на солдата и вспомнил о том, как этот солдат третьего дня сжег, высушивая на костре, свою рубаху и как смеялись над ним.
Собака завыла сзади, с того места, где сидел Каратаев. «Экая дура, о чем она воет?» – подумал Пьер.
Солдаты товарищи, шедшие рядом с Пьером, не оглядывались, так же как и он, на то место, с которого послышался выстрел и потом вой собаки; но строгое выражение лежало на всех лицах.


Депо, и пленные, и обоз маршала остановились в деревне Шамшеве. Все сбилось в кучу у костров. Пьер подошел к костру, поел жареного лошадиного мяса, лег спиной к огню и тотчас же заснул. Он спал опять тем же сном, каким он спал в Можайске после Бородина.
Опять события действительности соединялись с сновидениями, и опять кто то, сам ли он или кто другой, говорил ему мысли, и даже те же мысли, которые ему говорились в Можайске.
«Жизнь есть всё. Жизнь есть бог. Все перемещается и движется, и это движение есть бог. И пока есть жизнь, есть наслаждение самосознания божества. Любить жизнь, любить бога. Труднее и блаженнее всего любить эту жизнь в своих страданиях, в безвинности страданий».
«Каратаев» – вспомнилось Пьеру.
И вдруг Пьеру представился, как живой, давно забытый, кроткий старичок учитель, который в Швейцарии преподавал Пьеру географию. «Постой», – сказал старичок. И он показал Пьеру глобус. Глобус этот был живой, колеблющийся шар, не имеющий размеров. Вся поверхность шара состояла из капель, плотно сжатых между собой. И капли эти все двигались, перемещались и то сливались из нескольких в одну, то из одной разделялись на многие. Каждая капля стремилась разлиться, захватить наибольшее пространство, но другие, стремясь к тому же, сжимали ее, иногда уничтожали, иногда сливались с нею.
– Вот жизнь, – сказал старичок учитель.
«Как это просто и ясно, – подумал Пьер. – Как я мог не знать этого прежде».
– В середине бог, и каждая капля стремится расшириться, чтобы в наибольших размерах отражать его. И растет, сливается, и сжимается, и уничтожается на поверхности, уходит в глубину и опять всплывает. Вот он, Каратаев, вот разлился и исчез. – Vous avez compris, mon enfant, [Понимаешь ты.] – сказал учитель.
– Vous avez compris, sacre nom, [Понимаешь ты, черт тебя дери.] – закричал голос, и Пьер проснулся.
Он приподнялся и сел. У костра, присев на корточках, сидел француз, только что оттолкнувший русского солдата, и жарил надетое на шомпол мясо. Жилистые, засученные, обросшие волосами, красные руки с короткими пальцами ловко поворачивали шомпол. Коричневое мрачное лицо с насупленными бровями ясно виднелось в свете угольев.
– Ca lui est bien egal, – проворчал он, быстро обращаясь к солдату, стоявшему за ним. – …brigand. Va! [Ему все равно… разбойник, право!]
И солдат, вертя шомпол, мрачно взглянул на Пьера. Пьер отвернулся, вглядываясь в тени. Один русский солдат пленный, тот, которого оттолкнул француз, сидел у костра и трепал по чем то рукой. Вглядевшись ближе, Пьер узнал лиловую собачонку, которая, виляя хвостом, сидела подле солдата.
– А, пришла? – сказал Пьер. – А, Пла… – начал он и не договорил. В его воображении вдруг, одновременно, связываясь между собой, возникло воспоминание о взгляде, которым смотрел на него Платон, сидя под деревом, о выстреле, слышанном на том месте, о вое собаки, о преступных лицах двух французов, пробежавших мимо его, о снятом дымящемся ружье, об отсутствии Каратаева на этом привале, и он готов уже был понять, что Каратаев убит, но в то же самое мгновенье в его душе, взявшись бог знает откуда, возникло воспоминание о вечере, проведенном им с красавицей полькой, летом, на балконе своего киевского дома. И все таки не связав воспоминаний нынешнего дня и не сделав о них вывода, Пьер закрыл глаза, и картина летней природы смешалась с воспоминанием о купанье, о жидком колеблющемся шаре, и он опустился куда то в воду, так что вода сошлась над его головой.
Перед восходом солнца его разбудили громкие частые выстрелы и крики. Мимо Пьера пробежали французы.
– Les cosaques! [Казаки!] – прокричал один из них, и через минуту толпа русских лиц окружила Пьера.
Долго не мог понять Пьер того, что с ним было. Со всех сторон он слышал вопли радости товарищей.
– Братцы! Родимые мои, голубчики! – плача, кричали старые солдаты, обнимая казаков и гусар. Гусары и казаки окружали пленных и торопливо предлагали кто платья, кто сапоги, кто хлеба. Пьер рыдал, сидя посреди их, и не мог выговорить ни слова; он обнял первого подошедшего к нему солдата и, плача, целовал его.
Долохов стоял у ворот разваленного дома, пропуская мимо себя толпу обезоруженных французов. Французы, взволнованные всем происшедшим, громко говорили между собой; но когда они проходили мимо Долохова, который слегка хлестал себя по сапогам нагайкой и глядел на них своим холодным, стеклянным, ничего доброго не обещающим взглядом, говор их замолкал. С другой стороны стоял казак Долохова и считал пленных, отмечая сотни чертой мела на воротах.
– Сколько? – спросил Долохов у казака, считавшего пленных.
– На вторую сотню, – отвечал казак.
– Filez, filez, [Проходи, проходи.] – приговаривал Долохов, выучившись этому выражению у французов, и, встречаясь глазами с проходившими пленными, взгляд его вспыхивал жестоким блеском.
Денисов, с мрачным лицом, сняв папаху, шел позади казаков, несших к вырытой в саду яме тело Пети Ростова.


С 28 го октября, когда начались морозы, бегство французов получило только более трагический характер замерзающих и изжаривающихся насмерть у костров людей и продолжающих в шубах и колясках ехать с награбленным добром императора, королей и герцогов; но в сущности своей процесс бегства и разложения французской армии со времени выступления из Москвы нисколько не изменился.
От Москвы до Вязьмы из семидесятитрехтысячной французской армии, не считая гвардии (которая во всю войну ничего не делала, кроме грабежа), из семидесяти трех тысяч осталось тридцать шесть тысяч (из этого числа не более пяти тысяч выбыло в сражениях). Вот первый член прогрессии, которым математически верно определяются последующие.
Французская армия в той же пропорции таяла и уничтожалась от Москвы до Вязьмы, от Вязьмы до Смоленска, от Смоленска до Березины, от Березины до Вильны, независимо от большей или меньшей степени холода, преследования, заграждения пути и всех других условий, взятых отдельно. После Вязьмы войска французские вместо трех колонн сбились в одну кучу и так шли до конца. Бертье писал своему государю (известно, как отдаленно от истины позволяют себе начальники описывать положение армии). Он писал:
«Je crois devoir faire connaitre a Votre Majeste l'etat de ses troupes dans les differents corps d'annee que j'ai ete a meme d'observer depuis deux ou trois jours dans differents passages. Elles sont presque debandees. Le nombre des soldats qui suivent les drapeaux est en proportion du quart au plus dans presque tous les regiments, les autres marchent isolement dans differentes directions et pour leur compte, dans l'esperance de trouver des subsistances et pour se debarrasser de la discipline. En general ils regardent Smolensk comme le point ou ils doivent se refaire. Ces derniers jours on a remarque que beaucoup de soldats jettent leurs cartouches et leurs armes. Dans cet etat de choses, l'interet du service de Votre Majeste exige, quelles que soient ses vues ulterieures qu'on rallie l'armee a Smolensk en commencant a la debarrasser des non combattans, tels que hommes demontes et des bagages inutiles et du materiel de l'artillerie qui n'est plus en proportion avec les forces actuelles. En outre les jours de repos, des subsistances sont necessaires aux soldats qui sont extenues par la faim et la fatigue; beaucoup sont morts ces derniers jours sur la route et dans les bivacs. Cet etat de choses va toujours en augmentant et donne lieu de craindre que si l'on n'y prete un prompt remede, on ne soit plus maitre des troupes dans un combat. Le 9 November, a 30 verstes de Smolensk».