Методы сжатия данных. Сжатие данных

Характерной особенностью большинства типов данных является их избыточность. Степень избыточности данных зависит от типа данных. Например, для видеоданных степень избыточности в несколько раз больше чем для графических данных, а степень избыточности графических данных, в свою очередь, больше чем степень избыточности текстовых данных. Другим фактором, влияющим на степень избыточности является принятая система кодирования. Примером систем кодирования могут быть обычные языки общения, которые являются ни чем другим, как системами кодирования понятий и идей для высказывания мыслей. Так, установлено, что кодирование текстовых данных с помощью средств русского языка дает в среднем избыточность на 20-25% большую чем кодирование аналогичных данных средствами английского языка.

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

В зависимости от того, в каком объекте размещены данные, подлежащие сжатию различают:

1. Сжатие (архивация) файлов: используется для уменьшения размеров файлов при подготовке их к передаче каналами связи или к транспортированию на внешних носителях маленькой емкости;

2. Сжатие (архивация) папок: используется как средство уменьшения объема папок перед долгим хранением, например, при резервном копировании;

3. Сжатие (уплотнение) дисков: используется для повышения эффективности использования дискового просторную путем сжатия данных при записи их на носителе информации (как правило, средствами операционной системы).

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

Если при сжатии данных происходит изменение их содержимого, то метод сжатия называется необратимым , то есть при восстановлении (разархивировании) данных из архива не происходит полное восстановление информации. Такие методы часто называются методами сжатия с регулированными потерями информации. Понятно, что эти методы можно применять только для таких типов данных, для которых потеря части содержимого не приводит к существенному искажению информации. К таким типам данных относятся видео- и аудиоданные, а также графические данные. Методы сжатия с регулированными потерями информации обеспечивают значительно большую степень сжатия, но их нельзя применять к текстовым данным. Примерами форматов сжатия с потерями информации могут быть:

· JPEG - для графических данных;

· MPG - для для видеоданных;

· MP3 - для аудиоданных.

Если при сжатии данных происходит только изменение структуры данных, то метод сжатия называется обратимым . В этом случае, из архива можно восстановить информацию полностью. Обратимые методы сжатия можно применять к любым типам данных, но они дают меньшую степень сжатия по сравнению с необратимыми методами сжатия. Примеры форматов сжатия без потери информации:

· GIF, TIFF - для графических данных;

· AVI - для видеоданных;

· ZIP, ARJ, RAR, CAB, LH - для произвольных типов данных.

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

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

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

1. Информация. Её виды и свойства

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

Сведения об окружающем мире и протекающих в нем процессах, воспринимаемые человеком или специальным устройством.

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

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

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

Для этого в настоящее время изобретено множество способов хранения информации на внешних (относительно мозга человека) носителях и ее передачи на огромные расстояния.

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

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

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

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

· числовая - количественная мера объектов и их свойств в окружающем мире; особенно большое значение приобрела с развитием торговли, экономики и денежного обмена; аналогично текстовой информации для ее отображения используется метод кодирования специальными символами - цифрами, причем системы кодирования (счисления) могут быть разными;

· видеоинформация - способ сохранения «живых» картин окружающего мира, появившийся с изобретением кино.

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

С появлением компьютеров (или, как их вначале называли в нашей стране, ЭВМ - электронные вычислительные машины) вначале появилось средство для обработки числовой информации. Однако в дальнейшем, особенно после широкого распространения персональных компьютеров (ПК), компьютеры стали использоваться для хранения, обработки, передачи и поиска текстовой, числовой, изобразительной, звуковой и видеоинформации. С момента появления первых персональных компьютеров - ПК (80-е годы 20 века) - до 80% их рабочего времени посвящено работе с текстовой информацией.

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

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

Свойства информации

Можно привести немало разнообразных свойств информации. Каждая научная дисциплина рассматривает те, которые ей более важны. С точки зрения информатики, наиболее важными представляются следующие свойства:

1. Объективность и субъективность информации. Более объективной принято считать ту информацию, в которую методы вносят меньшую субъективный элемент. В ходе информационного процесса степень объективности информации всегда понижается.

2. Полнота информации. Полнота информации во многом характеризует качество информации и определяет достаточность данных для принятия решений или для создания новых данных на основе имеющихся.

3. Достоверность информации. Данные возникают в момент регистрации сигналов, но не все сигналы являются «полезными» - всегда присутствует уровень посторонних сигналов.

5. Доступность информации.

6. Актуальность.

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

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

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

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

Алгоритмы сжатия текстов / файлов неизвестного формата

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

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

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

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

3. Программные средства сжатия данных

Если методы сжатия информации применяют к готовым документам. То нередко термин «сжатие данных» подменяют термином «архивация данных», а программные средства, выполняющие эти операции, называют архиваторами.

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

Итак, архивация может пригодиться:

1) При хранении копий файлов и флоппи-дисках, т.к. флоппи-диск ограничен по размеру;

2) Для освобождения места на жестком диске;

3) При передачи информации по сети.

Архивация информации - это такое преобразование информации, при котором ее объем не уменьшается, а количество информации остается прежним.

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

Степень сжатия информации зависит от типа исходного файла, от используемой программы, а также от выбранного метода упаковки. Наиболее хорошо сжимаются файлы графических объектов, текстовые файлы и файлы данных, для которых степень сжатия может достигать 5-40%, меньше сжимаются файлы исполняемых программ и загрузочных модулей -60-90%.

Различными разработчиками созданы много программ-архиваторов. Среди них наиболее распространенные для Windows - WINRAR, WINZIP.

По своей популярности архиватор WinRAR, без сомнения, находится на первом месте в России, и на одном из первых - во всем мире. Архиватор был разработан Евгением Рошалом в 2003 году. Программа обеспечивает полное управление файлами в архивах, восстановление поврежденных архивов, шифрование, создание самораспаковывающихся и многотомных архивов.

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

Сам Zip - алгоритм свободно используется в десятках программ, тем не менее для очень многих пользователей Windows ИМЕННО WinZip является стандартной программой для работы с архивами. Встроенные средства обработки архивов WinZIP позволяют упаковывать, просматривать и извлекать файлы из широко распространенных форматов архивов, таких как ZIP, CAB, Microsoft Compress, GZIP, TAR и т.д. WinZip очень прост и удобен в работе.

Однако не всегда оправдано использовать отдельные архиваторы с их собственными графическими оболочками. Наиболее удобной оболочкой для архиваторов является обычный файловый менеджер, например, Windows Commander, который имеет возможность просматривать и распаковывaть файлы архивов форматов ZTP, ARJ, RAR, TAR, GZ, CAB, ACE. Всё-таки большинство операций с файлами, в том числе и с архивами, выполняются именно в таких менеджерах.

4. Сжатие данных с потерями информации

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

Типы сжатия с потерями

Существуют две основных схемы сжатия с потерями:

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

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

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

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

Преимущество методов сжатия с потерями над методами сжатия без потерь состоит в том, что первые существенно превосходят по степени сжатия, продолжая удовлетворять поставленным требованиям.

Методы сжатия с потерями часто используются для сжатия звука или изображений.

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

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

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

Фотографии, записанные в формате JPEG, могут быть приняты судом (несмотря на то, что данные прошли сжатие с потерями). Но при этом должен быть предоставлен фотоаппарат, которым они сделаны, или соответствующая фототаблица цветопередачи.

Методы сжатия данных с потерями

v Компрессия изображений:

· Снижение глубины цвета;

· Метод главных компонент;

· Фрактальное сжатие;

v Компрессия видео:

· Flash (также поддерживает движущиеся изображения JPEG);

· MPEG-1 Part 2;

· MPEG-2 Part 2;

· MPEG-4 Part 2;

v Компрессия звука:

· MP3 - Определён спецификацией MPEG-1;

· Ogg Vorbis (отличается отсутствием патентных ограничений и более высоким качеством);

· AAC, AAC+ - существует в нескольких вариантах, определённых спецификациями MPEG-2 и MPEG-4, используется, например, в Apple Computer;

· eAAC+ - формат, предлагаемый Sony, как альтернатива AAC и AAC+;

· WMA - собственность Microsoft;

информация сжатие архиватор потеря

5. Сжатие данных без потерь информации

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

Сжатие данных без потерь используется во многих приложениях. Например, оно используется в популярном файловом формате ZIP и Unix-утилите Gzip. Оно также используется как компонент в сжатии с потерями.

Сжатие без потерь используется, когда важна идентичность сжатых данных оригиналу. Обычный пример - исполняемые файлы и исходный код. Некоторые графические файловые форматы, такие как PNG или GIF, используют только сжатие без потерь; тогда как другие (TIFF, MNG) могут использовать сжатие как с потерями, так и без.

Техника сжатия без потерь

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

Многоцелевые алгоритмы сжатия отличаются тем, что способны уменьшать широкий диапазон данных - исполняемые файлы, файлы данных, тексты, графику и т.д., и применяются в архиваторах. Специализированные же алгоритмы рассчитаны на некоторый тип файлов (текст, графику, звук и т.д.), зато сжимают такие файлы намного сильнее. Например: архиваторы сжимают звук примерно на треть (в 1,5 раза), в то время как FLAC - в 2,5 раза. Большинство специализированных алгоритмов малопригодны для файлов «чужих» типов: так, звуковые данные плохо сжимаются алгоритмом, рассчитанным на тексты.

Большинство алгоритмов сжатия без потерь работают в две стадии: на первой генерируется статистическая модель для входящих данных, вторая отображает входящие данные в битовом представлении, используя модель для получения «вероятностных» (то есть часто встречаемых) данных, которые используются чаще, чем «невероятностные».

Статистические модели алгоритмов для текста (или текстовых бинарных данных, таких как исполняемые файлы) включают:

Преобразование Барроуза - Уилера (блочно-сортирующая предобработка, которая делает сжатие более эффективным)

LZ77 и LZ78 (используется DEFLATE)

Алгоритмы кодирования через генерирование битовых последовательностей:

· Алгоритм Хаффмана (также используется DEFLATE)

· Арифметическое кодирование

Методы сжатия без потерь

· Многоцелевые

· Кодирование длин серий - простая схема, дающая хорошее сжатие данных, которые содержат много повторяющихся значений

· LZW - используется в gif и во многих других.

· Deflate - используется в gzip, усовершенствованной версии zip и как часть процесса сжатия PNG.

· LZMA - используется в 7-zip.

v Сжатие аудио:

· Apple Lossless - ALAC (Apple Lossless Audio Codec);

· Audio Lossless Coding - также известен как MPEG-4 ALS;

· Direct Stream Transfer - DST;

· Free Lossless Audio Codec - FLAC;

v Сжатие графики

· ABO - Adaptive Binary Optimization;

· GIF - (без потерь только для изображений содержащих менее 256 цветов);

· JBIG2 - (с потерями или без Ч/Б изображений);

· JPEG-LS - (стандарт сжатия без потерь / почти без потерь);

· JPEG 2000 - (включает сжатие без потерь; также, испытан Sunil Kumar, профессором университета штата Сан-Диего);

· PGF - Progressive Graphics File (сжатие с/без потерь);

· PNG - Portable Network Graphics;

· WMPhoto - (включая метод сжатия без потерь);

v Сжатие видео

· Animation codec;

· CamStudio Video Codec;

6. Хранение информации (текстовой, графической, звуковой)

Хранение информации происходит с помощью определенных носителей информации. Человек хранит свои знания либо в собственной памяти, либо на каких-то внешних носителях.

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

Носитель информации может быть разной природы: бумажный. Механический, магнитный, электрический. Информация, записанная на носители, может иметь вид символа, понятный человеку, или закодированный вид. Информация для магнитофона, видеомагнитофона, киноаппарата - звуковая храниться на специальных устройствах: аудиокассетах, видеокассетах, кинолентах. С помощью микрофона и других устройств звуковая информация записывается на магнитную ленту.

В ЭВМ в качестве устройств для записи, чтения информации стали использоваться: устройства чтения перфокарт; накопители на магнитной ленте, накопители на гибких (дисковод) и жестких (винчестер) магнитных дисках; накопители на компакт-дисках (CD-ROM) и другие более современные устройства накопления и хранения информации.

Библиографический список

1. Федеральный закон Российской Федерации «Об информации, информатизации и защите информации» от 27.07.2006 №149-ФЗ.

2. Левин А.Ш. Самоучитель работы на компьютере. - СПб.: Питер, 2006. - 655 с.

3. Романова Н.И. Основы информатики. - СПб.: Политехника, 2004. -224 с.

4. Симонович С.В. Информатика. Базовый курс. - СПб.: Питер, 2008 -640 с.

Размещено на Allbest.ru

Подобные документы

Типы сжатия данных: с потерями (lossy) и без потерь (lossless). Сжатие с минимальной избыточностью. Кодирование методом Шеннона-Фано. Проверка работы программы по сжатию файлов формата bmp и xls. Реализация на Delphi алгоритма сжатия Шеннона и Хаффмана.

курсовая работа , добавлен 26.01.2011

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

курсовая работа , добавлен 17.03.2011

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

презентация , добавлен 06.01.2014

Исследование основных видов программ-архиваторов. Сжатие файлов при архивации. Показатель степени сжатия файлов. Оценка функциональности самых популярных программ-упаковщиков. Технические характеристики процессов сжатия. Методы архивации без потерь.

реферат , добавлен 05.12.2013

Раскрытие цели сжатия файлов и характеристика назначения архиваторов как программ, осуществляющих упаковку и распаковку файлов в архив для удобства переноса и хранения. Основные типы архиваторов: файловые, программные, дисковые. Метод сжатия без потерь.

презентация , добавлен 05.04.2011

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

контрольная работа , добавлен 12.03.2011

Краткий обзор основных теорий сжатия. Концепции идей и их реализация. Сжатие данных с использованием преобразования Барроуза-Вилера. Статический алгоритм Хафмана. Локально адаптивный алгоритм сжатия. Алгоритм Зива-Лемпеля (Welch) и метод Шеннона-Фано.

практическая работа , добавлен 24.04.2014

Энтропия и количество информации. Комбинаторная, вероятностная и алгоритмическая оценка количества информации. Моделирование и кодирование. Некоторые алгоритмы сжатия данных. Алгоритм арифметического кодирования. Приращаемая передача и получение.

курсовая работа , добавлен 28.07.2009

Применение алгоритмов, обеспечивающих высокую степень сжатия, для увеличения скорости передачи данных по каналам связи. Особенности и методы нахождения сингулярного разложения. Разработка программы, реализующей сжатие изображения с помощью SVD-сжатия.

дипломная работа , добавлен 13.10.2015

Программы для создания архивов. Эффективность сжатия данных как важнейшая характеристика архиваторов. Основные методы сжатия данных. Характеристика программы для упаковки текстов и программ WinRar. Распаковка файлов, упаковка файлов и папок в общий архив.

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

Михаил Сваричевский

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

Все алгоритмы сжатия делятся на два типа: с потерями и без.

Сжатие с потерями позволяет достичь гораздо бóльшей степени сжатия (до 1/30 и менее от исходного объема).
Например, видеофильм, занимающий в неупакованном виде гигабайт 30, удается записать на 1 CD.
Однако, алгоритмы сжатия с потерями приводят к некоторым изменениям самих данных; поэтому применять такие алгоритмы можно только к тем данным, для которых небольшие искажения несущественны: видео, фото-изображения (алгоритмы JPEG), звук (алгоритм MP3).

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

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

Словарные методы

Словарные методы отличаются высокой скоростью сжатия/распаковки, но несколько худшим сжатием. Словом называется некоторая последовательность символов. В общем - речь, конечно, идет не о символах, а о байтах; но для простоты в примерах будут использоваться ASCII-символы.

Словарь содержит некоторое количество слов (обычно 2x; например, 4096).
Сжатие достигается за счет того, что номер слова в словаре обычно гораздо короче самого слова.
Алгоритмы словарного сжатия делятся на две группы:
1) использующие словарь в явной форме(алгоритмы LZ78, LZW, LZC, LZT, LZMV, LZJ, LZFG)
Например, по словарю
1. "Большинство"
2. "сжатия"
3. "без"
4. "потерь"
5. "алгоритмов"
текст "Большинство алгоритмов сжатия без потерь" сжимается в "15234".

2) указывающие вместо номера слова - позицию относительно текущей позиции и длину повторяющегося участка (алгоритмы LZ77, LZR, LZSS, LZB, LZH)
Например, текст "абаббабаббабвгббабв"
сжимается в "05абабб5504абвг65", где:
"05абабб" – позиция 0 означает, что далее 5 символов идут без сжатия.
"55" – 5 букв с позиции, отстоящей от текущей на 5 символов назад.
"04абвг" – еще 4 символа не сжимается.
"65" –5 букв с позиции, отстоящей от текущей на 6 символов назад.

Модификации LZ-алгоритмов отличаются только способами представления словаря, поиска и добавления слов. Одни сжимают быстрее, но хуже; другие требуют больше памяти.

Рассмотрим подробнее модифицированный алгоритм LZ77.
Архив будет состоять из записей следующего вида:
(n,m) – означает, что с позиции n начинается такая же строка длиной m, что и с текущей позиции.
(0,m,"m символов") – означает, что далее следует m символов, которые не удалось сжать.

Алгоритм сжатия будет заключаться в следующем: ищем в файле место, начиная с которого идет самая длинная последовательность, совпадающая с последовательностью, начинающейся на текущем байте. Если ее длина больше 3, то в архив записываем начало и длину последовательности; иначе - записываем 0, длину последовательности и сами несжатые символы. Распаковка еще проще: пока файл архива не кончился, читаем по 2 числа(n,m). Если n=0, то m символов из архива сразу помещаем в буфер (эти символы нам еще понадобятся) и записываем в выходной файл. Если n<>0 то из буфера с позиции n копируем m элементов в буфер и выходной файл.

Однако есть две проблемы:
1) Ограниченный размер буфера: если нам нужно будет сжать файл размеров в 100МБ, мы его в буфер никак не поместим. Поэтому, когда он будет заполнен (скажем, на 75%), придется сдвинуть данные в нем к началу (напр., на 25%;конечно, самые старые символы при этом потеряются). Это ухудшит сжатие, но сделает алгоритм нетребовательным к памяти.
2) Скорость работы программы сжатия очень мала. В самом деле, если нужно будет сжать файл размеров 10КБ, то это потребует от нас проведения как минимум около 10000*10000/2 операций (10000 раз нам нужно будет искать совпадающую подпоследовательность, а каждый такой поиск займет в среднем 10000/2 операций). Для того, чтобы ускорить операцию поиска, можно хранить в отдельном массиве номера позиций последовательностей, начинающихся на символ chr(0), chr(2) … chr(255). Тогда при поиске нам нужно будет проверить только те комбинации, первая буква которых совпадает с первой буквой искомой последовательности.

Статистические методы

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

1) Коды Хаффмана: все символы кодируются целым количеством бит; причем так, что раскодирование всегда однозначно (например, если букве "а" соответствует последовательность бит "1001", а "b" – "10010", то раскодирование неоднозначно). Достоинство - высокая скорость сжатия. Недостатки - неоптимальное сжатие, сложности при реализации адаптивного варианта. Так как в последнее время скорость собственно алгоритма кодирования играет все меньшую роль (алгоритмы накопления статистической информации работают все медленнее и медленнее, и даже 2-х кратное увеличение времени работы кодировщика практически не влияет на скорость), этот алгоритм не имеет существенных преимуществ перед арифметическим кодированием.

2) Арифметическое кодирование: для каждого символа определяется промежуток на отрезке и в зависимости от ширины этого отрезка может выделяться разное количество бит, условно говоря, даже дробное (например: пусть строке "a" соответствует0 , а строке "ab" - 1, тогда строка "aba" закодируется в 2 бита, т.е в среднем 2/3 бита на символ). Этот метод точнее использует статистическую информацию, и всегда сжимает не хуже алгоритма Хаффмана, но медленнее. Достоинства - максимальная теоретически достижимая степень сжатия, простая реализация адаптивного варианта. Недостатки - несколько меньшая скорость.

Принцип работы арифметического кодирования:

Например, мы присвоили символу "a" промежуток , "b" – и "c" – . Тогда, если у нас будет число 0.4, то мы можем сказать, что закодирована буква "b"(0.3<=0.4<=0.6), а если 0.9 – то c(0.6<=0.9<=1). Итак, у нас получилось закодировать 1 букву в число. Как же закодировать 2 буквы? Очень просто: например, если первая буква – "b", то интервал равен . Разделим этот интервал на части, в отношении наших первоначальных отрезков. Тогда 2-м буквам "ba" будет соответствовать интервал , "bb" – и "bc" – . Для раскодирования нам достаточно знать любое число из этого интервала.

Попробуем раскодировать: пусть дано число 0.15. Это число попадает в интервал буквы "a", значит первая закодированная буква – "a". Для того, чтобы узнать вторую букву, нужно преобразовать число, чтобы оно указывало букву в интервале не , а . Для этого от числа отнимем нижнюю границу исходного интервала (0) и разделим на ширину интервала (0.3-0=0.3). Получим новое число(0.15-0)/0.3 = 0.5. Повторив те же действия, мы узнаем, что вторая буква – "b". Если бы было закодировано 3 и более букв, то, многократно повторяя этот процесс, мы нашли бы все буквы.

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

Алгоритм сжатия:
Для каждого символа мы должны присвоить соответствующий промежуток в соответствии с частотой (вероятностью встречи) в данных: пусть символ "а"имеет вероятность 0.4, "b" – 0,3 и "c" – тоже 0.3; тогда символу "а" будет соответствовать промежуток , "b" – , "c" – . Т.е мы делим имеющийся у нас промежуток между всеми необходимыми буквами в соответствии с вероятностью их встречи (более вероятному символу соответствует больший промежуток).

В процессе сжатия у нас есть 2 границы: верхняя и нижняя, назовем их соответственно hiи lo. Пусть нам нужно закодировать символ, которому мы отвели промежуток . Тогда в наш промежуток "вставляется" промежуток символа, и lo будет равен нижней границе вставляемого промежутка, hi – верхней. В итоге по мере кодирования промежуток между loи hi становится все уже и уже. Наконец, когда мы закодировали все данные, выбираем любое число из получившегося промежутка и выводим. Оно и будет сжатыми данными.

Распаковка:
Построим промежутки для символов, как и для сжатия. Символ, в промежуток которого попадает число-архив, и есть первый символ данных. "Растягиваем" промежуток символа вместе с числом-архивом до промежутка (т.е отнимаем нижнюю границу интервала только что раскодированного символа, и делим на ширину этого интервала), затем повторяем операцию, пока все не раскодируем.

Проблемы:
Если бы все было так просто… На самом деле, для хранения числа-архива нужна будет очень большая точность (десятки и сотни тысяч знаков), поэтому на практике приходится пользоваться обычными типами данных. Чтобы этого добиться, будем смотреть на старшие биты/цифры числа-архива. Как только у hi и lo они совпадут, мы можем сразу записать их в архив и "отсечь". При распаковке наоборот, когда увидим, что мы довольно много раз расширяли промежуток до , считаем из файла-архива несколько цифр и допишем их в конец нашего числа-архива.
Часто используется модификация арифметического кодирования - range coder. Основное отличие - начальный интервал - . Это позволяет выводить данные сразу по байту, а не наскребать по биту, что отражается на скорости работы. В конце статьи приведена реализация именно этого варианта.

Определение вероятностей символов

Основной процесс, влияющий на скорость и степень сжатия – определение вероятностей символов. В простейшем случае будем считать вероятностью символа - количество его встреч в уже закодированной части данных, делённое на общее количество символов в данных. Для текстов это дает приблизительно 2-кратное сжатие. Чтобы его увеличить, можно учитывать такие факты, как, например, то, что вероятность встречи символа "я" после "ю" практически равна 0, а "o" после "с" – около 0.25. Поэтому для каждого предыдущего символа будем отдельно считать вероятности.

Предположения, которые мы делаем относительно сжимаемых данных (например, зависимость вероятности от предыдущих символов) называются вероятностной моделью. Модель, вероятности в которой не зависят от предыдущих символов, называется моделью 0-го порядка. Если вероятности зависят от 1 предыдущего символа, то это модель 1-го порядка, если от 2-х последних – то 2-го и т.д. Для эффективного вычисления вероятностей символов в моделях высокого порядка существуют специальная группа алгоритмов – PPM и его модификации.
Модели могут быть неадаптивными, полуадаптивными и адаптивными. В неадаптивных методах вероятности всех символов жестко зашиты в программу. В полуадаптивных по входным данным делается 2 прохода: 1-й - для определения вероятностей, 2-й – собственно для сжатия. Адаптивный – вероятности символов изменяются в процессе сжатия. Адаптивные модели самые медленные, но они обычно сжимают данные сильнее неадаптивных и полуадаптивных моделей. В общем, среди всех моделей лучше сжимают использующие наибольшее кол-во информации о сжимаемых данных - зависимость от предыдущих символов, некоторые факты, например: в текстах после точки обычно следует большая буква и т.д.

Алгоритмы, используемые в популярных архиваторах:

ZIP,ARJ,RAR - LZ+Хаффман
HA - PPM+Арифметическое кодирование
BOA - BWT+Арифметическое кодирование
UHARC - LZ+PPM+Арифметическое кодирование
(Здесь "+" означает, что результат работы алгоритма, написанного слева от знака, далее сжимается алгоритмом, записанным справа).
Как видно, в архиваторах ZIP,ARJ,RAR ,разрабатывавшихся в конце 80-х - начале 90-х, используются уже довольно устаревшие алгоритмы; поэтому они по тестам проигрывают более современным.

Пример программы адаптивного сжатия/распаковки 0-го порядка:

Данные: compr – тут хранятся сжатые данные
Data- тут хранятся исходные данные
Freq – частоты символов

Procedure compress_range; {Процедура сжатия}
Var
cum_freq: Extended;
Begin
{- Инициализация модели и кодера -}
For q:= 0 To 255 Do
freq [q] := 1; {Все символы в начале имеют одинаковую вероятность}
freq := freq - 0.20000;
total:= 256; {Сумма частот всех символов.}
{ В freq - небольшой остступ от 0 и макс.значения}
PC:= 0;{Кол-во уже закодированых байт }
Lo:= 0; range:= 256;
{- Кодирование -}
For q:= 1 To Size Do
Begin
{Нахождение интервала, соответствующего кодируемому символу}
cum_freq:= 0.1; {Начинаем накапливать вероятность}
For w:= 0 To data [q] - 1 Do
cum_freq:= cum_freq + freq [w];
{Изменяем range&lo}
range:= range / total;
Lo:= Lo + range * (cum_freq);
range:= range * freq ];
{Нормализация т.е вывод байтов, одинаковых у Lo и Hi(Hi=Lo+Range)}

Begin
Inc (PC);
compr := Trunc (Lo);
Lo:= Frac (Lo) * 256;
range:= range * 256;
End;
{Обновления модели}
freq ] := freq ] + 1;
{Присваеваем кодируемому символу на 1 большую вероятность}
total:= total + 1;
End;
{Сжатие закончено, выводим остаток}
Lo:= Lo + range / 2;
Inc (PC);
compr := Trunc (Lo);
Lo:= Frac (Lo) * 256;
range:= range * 256;
End;

Procedure decompress_range;{Процедура распаковки}
Var
temp: Extended;
ee: Extended;
Begin
{Инициализация модели и кодера}
For q:= 0 To 255 Do
freq [q] := 1;
freq := freq - 0.20000; { В freq - небольшой остступ от 0 и макс.значения}
total:= 256;
PC:= 4; {PC - номер байта, которые мы считываем}
code:= 0;
Lo:= 0; range:= 256;
{Считываем начальное, приближенное значение code.}
For q:= 1 To 4 Do
Begin
code:= code * 256 + compr [q] / 65536 / 256;
End;
w:= 0; {W- кол-во верно распакованных байт}
{Собственно расжатие}
While True Do
Begin
{Нахождения вероятности следующего символа}
temp:= (code- Lo) * total / range;
{Поиск символа, в интервал которого попадает temp}
sum:= 0.1; ssum:= 0.1;
For e:= 0 To 255 Do
Begin
sum:= sum + freq [e];
If sum > temp Then Break;
ssum:= sum;
End;
Inc (w);
{Проверка правильности распаковки}
{Сейчас в e – распакованный байт, и его можно выводить в файл}
If data [w] <> e Then Break; {Если неправильно распаковали - выходим}
If w = Size Then Begin Inc (w); Break End; {Если все распаковали выходим,}
{и модель не обновляем:-)}
{Обновления Lo&Hi(Растягивание)}
range:= range / total;
Lo:= Lo + range * (ssum);
range:= range * (freq [e]);
{Обновление модели(Делаем символ e более вероятным)}
freq [e] := freq [e] + 1;
total:= total + 1;
{Нормализация, уточнение числа}
While Trunc (Lo) = Trunc (Lo + range) Do
Begin
Inc (PC);
temp:=compr;
code:= (code - trunc(code)) * 256 + temp / 16777216;
Lo:= Frac (Lo) * 256;
range:= range * 256;
End;
End;
Dec (w);
{DONE_DECOMPRESS}
End;

Другим фактором , влияющим на степень избыточности, является принятая система кодирования. Примером систем кодирования могут быть обычные языки общения, которые являются ни чем другим, как системами кодирования понятий и идей для высказывания мыслей. Так, установлено, что кодирование текстовых данных с помощью средств русского языка дает в среднем избыточность на 20-25% большую, чем кодирование аналогичных данных средствами английского языка.

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

В зависимости от того, в каком объекте размещены данные, подлежащие сжатию, различают:

· Сжатие (архивация) файлов: используется для уменьшения размеров файлов при подготовке их к передаче каналами связи или к транспортированию на внешних носителях маленькой емкости;

· Сжатие (архивация) папок: используется как средство уменьшения объема папок перед долгим хранением, например, при резервном копировании;

· Сжатие (уплотнение) дисков: используется для повышения эффективности использования дискового просторную путем сжатия данных при записи их на носителе информации (как правило, средствами операционной системы).

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

· первый способ состоит в изменении содержимого данных,

· второй - в изменении структуры данных,

· третий - в одновременном изменении как структуры, так и содержимого данных.

Если при сжатии данных происходит изменение их содержимого, то метод сжатия называется необратимым , то есть при восстановлении (разархивировании) данных из архива не происходит полное восстановление информации. Такие методы часто называются методами сжатия с регулированными потерями информации . Понятно, что эти методы можно применять только для таких типов данных, для которых потеря части содержимого не приводит к существенному искажению информации. К таким типам данных относятся видео- и аудиоданные, а также графические данные. Методы сжатия с регулированными потерями информации обеспечивают значительно большую степень сжатия, но их нельзя применять к текстовым данным . Примерами форматов сжатия с потерями информации могут быть:

· JPEG - для графических данных;

· MPG - для для видеоданных;

· MP3 - для аудиоданных.

Если при сжатии данных происходит только изменениеструктуры данных,
то метод сжатия называется обратимым . В этом случае, из архива можно восстановить информацию полностью. Обратимые методы сжатия можно применять к любым типам данных, но они дают меньшую степень сжатия по сравнению с необратимыми методами сжатия. Примеры форматов сжатия без потери информации:

· GIF, TIFF - для графических данных;

· AVI - для видеоданных;

· ZIP, ARJ, RAR, CAB, LH - для произвольных типов данных.

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

· алгоритм RLE (Run Length Encoding);

· алгоритмы группы KWE(KeyWord Encoding);

· алгоритм Хаффмана.

Алгоритм RLE

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

1 1 1 1 2 2 3 4 4 4

В алгоритме RLE предлагается заменить ее следующей структурой: 1 4 2 2 3 1 4 3, где первое число каждой пары чисел - это код данных, а второе - коэффициент повторения. Если для хранения каждого элемента данных входной последовательности отводится 1 байт, то вся последовательность будет занимать 10 байт памяти, тогда как выходная последовательность (сжатый вариант) будет занимать 8 байт памяти. Коэффициент сжатия , характеризующий степень сжатия, вычисляется по формуле.

Чем меньше значение коэффициента сжатия, тем эффективней метод сжатия. Понятно, что алгоритм RLE будет давать лучший эффект сжатия при большей длине повторяющейся последовательности данных. В случае рассмотренного выше примера, если входная последовательность будет иметь такой вид: 1 1 1 1 1 1 3 4 4 4, то коэффициент сжатия будет равен 60%. В связи с этим большая эффективность алгоритма RLE достигается при сжатии графических данных (в особенности для однотонных изображений).

Алгоритмы группы KWE

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

Существует довольно много реализаций этого алгоритма, среди которых наиболее распространенными являются алгоритм Лемпеля-Зіва (алгоритм LZ) и его модификация алгоритм Лемпеля-Зіва-Велча (алгоритм LZW). Словарем в данном алгоритме является потенциально бесконечный список фраз. Алгоритм начинает работу с почти пустым словарем, который содержит только одну закодированную строку, так называемая NULL-строка. При считывании очередного символа входной последовательности данных, он прибавляется к текущей строке. Процесс продолжается до тех пор, пока текущая строка соответствует какой-нибудь фразе из словаря. Но рано или поздно текущая строка перестает соответствовать какой-нибудь фразе словаря. В момент, когда текущая строка представляет собой последнее совпадение со словарем плюс только что прочитанный символ сообщения, кодер выдает код, который состоит из индекса совпадения и следующего за ним символа, который нарушил совпадение строк. Новая фраза, состоящая из индекса совпадения и следующего за ним символа, прибавляется в словарь. В следующий раз, если эта фраза появится в сообщении, она может быть использована для построения более длинной фразы, что повышает меру сжатия информации.

Алгоритм LZW построен вокруг таблицы фраз (словаря), которая заменяет строки символов сжимаемого сообщения в коды фиксированной длины. Таблица имеет так называемое свойством опережения, то есть для каждой фразы словаря, состоящей из некоторой фразы w и символа К, фраза w тоже заносится в словарь. Если все части словаря полностью заполнены, кодирование перестает быть адаптивным (кодирование происходит исходя из уже существующих в словаре фраз).

Алгоритмы сжатия этой группы наиболее эффективны для текстовых данных больших объемов и малоэффективны для файлов маленьких размеров (за счет необходимости сохранение словаря).

Алгоритм Хаффмана

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

Основная идея состоит в следующем: чем чаще встречается символ, тем меньшим количеством бит он кодируется. Результат кодирования заносится в словарь, необходимый для декодирования.

Принципы сжатия информации

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

Любой метод сжатия информации включает в себя два преобразования обратных друг другу:

преобразование сжатия;
преобразование расжатия.

Преобразование сжатия обеспечивает получение сжатого сообщения из исходного. Разжатие же обеспечивает получение исходного сообщения (или его приближения) из сжатого.

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

без потерь,
с потерями.

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

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

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

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

k = S o /S c ,

где k - коэффициент сжатия, S o - размер несжатых данных, а S c - размер сжатых. Таким образом, чем выше коэффициент сжатия, тем алгоритм лучше. Следует отметить:

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

Ситуация с k < 1 вполне возможна при сжатии. Невозможно получить алгоритм сжатия без потерь, который при любых данных образовывал бы на выходе данные меньшей или равной длины. Обоснование этого факта заключается в том, что количество различных сообщений длиной n Шаблон:Е:бит составляет ровно 2 n . Тогда количество различных сообщений с длиной меньшей или равной n (при наличии хотя бы одного сообщения меньшей длины) будет меньше 2 n . Это значит, что невозможно однозначно сопоставить все исходные сообщения сжатым: либо некоторые исходные сообщения не будут иметь сжатого представления, либо нескольким исходным сообщениям будет соответствовать одно и то же сжатое, а значит их нельзя отличить.

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

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

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

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

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

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

Однако сжатие с потерями позволяет добиться гораздо больших коэффициентов сжатия за счёт отбрасывания незначащей информации, которая плохо сжимается. Так, например алгоритм сжатия звука без потерь FLAC , позволяет в большинстве случаев сжать звук в 1,5-2,5 раза, в то время как алгоритм с потерями Vorbis , в зависимости от установленного параметра качетсва может сжать до 15 раз с сохранением приемлемого качества звучания.

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

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

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

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

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

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

См. также

Wikimedia Foundation . 2010 .

Смотреть что такое "Сжатие информации" в других словарях:

сжатие информации - уплотнение информации — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом Синонимы уплотнение информации EN information reduction …

СЖАТИЕ ИНФОРМАЦИИ - (сжатие данных) представление информации (данных) меньшим числом битов по сравнению с первоначальным. Основано на устранении избыточности. Различают С. и. без потери информации и с потерей части информации, несущественной для решаемых задач. К… … Энциклопедический словарь по психологии и педагогике

адаптивное сжатие информации без потерь - — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN adaptive lossless data compressionALDC … Справочник технического переводчика

уплотнение/сжатие информации - — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN compaction … Справочник технического переводчика

цифровое сжатие информации - — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN compression … Справочник технического переводчика

Звук является простой волной, а цифровой сигнал является представлением этой волны. Это достигается запоминанием амплитуды аналогового сигнала множество раз в течение одной секунды. Например, в обыкновенном CD сигнал запоминается 44100 раз за… … Википедия

Процесс, обеспечивающий уменьшение объема данных путем сокращения их избыточности. Сжатие данных связано с компактным расположением порций данных стандартного размера. Различают сжатия с потерей и без потери информации. По английски: Data… … Финансовый словарь

сжатие цифровой картографической информации - Обработка цифровой картографической информации в целях уменьшения ее объема, в том числе исключения избыточности в пределах требуемой точности ее представления. [ГОСТ 28441 99] Тематики картография цифровая Обобщающие термины методы и технологии… … Справочник технического переводчика