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

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

Размещено на 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. Распаковка файлов, упаковка файлов и папок в общий архив.

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

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

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

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

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

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

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

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

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

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

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

где 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] Тематики картография цифровая Обобщающие термины методы и технологии… … Справочник технического переводчика

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

Основоположником науки о сжатии информации принято считать Клода Шеннона. Его теорема об оптимальном кодировании показывает, к чему нужно стремиться при кодировании информации и насколько та или иная информация при этом сожмется. Кроме того, им были проведены опыты по эмпирической оценке избыточности английского текста. Шенон предлагал людям угадывать следующую букву и оценивал вероятность правильного угадывания. На основе ряда опытов он пришел к выводу, что количество информации в английском тексте колеблется в пределах 0,6 – 1,3 бита на символ. Несмотря на то, что результаты исследований Шеннона были по-настоящему востребованы лишь десятилетия спустя, трудно переоценить их значение .

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

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

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

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

Алфавит кода – множество всех символов входного потока. При сжатии англоязычных текстов обычно используют множество из 128 ASCII кодов. При сжатии изображений множество значений пиксела может содержать 2, 16, 256 или другое количество элементов.

Кодовый символ – наименьшая единица данных, подлежащая сжатию. Обычно символ – это 1 байт , но он может быть битом, тритом {0,1,2}, или чем-либо еще.

Кодовое слово – это последовательность кодовых символов из алфавита кода. Если все слова имеют одинаковую длину (число символов), то такой код называется равномерным (фиксированной длины) , а если же допускаются слова разной длины, то – неравномерным (переменной длины) .

Код – полное множество слов.

Токен – единица данных, записываемая в сжатый поток некоторым алгоритмом сжатия. Токен состоит из нескольких полей фиксированной или переменной длины.

Фраза – фрагмент данных, помещаемый в словарь для дальнейшего использования в сжатии.

Кодирование – процесс сжатия данных.

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

Отношение сжатия – одна из наиболее часто используемых величин для обозначения эффективности метода сжатия.

Коэффициент сжатия – величина, обратная отношению сжатия.

Значения больше 1 обозначают сжатие, а значения меньше 1 – расширение.

Средняя длина кодового слова – это величина, которая вычисляется как взвешенная вероятностями сумма длин всех кодовых слов.

L cp =p 1 L 1 +p 2 L 2 +...+p n L n ,

где – вероятности кодовых слов;

L 1 ,L 2 ,...,L n – длины кодовых слов.

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

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

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

Рассмотрим несколько известных алгоритмов сжатия данных более подробно.

Метод Хаффмана

Этот алгоритм кодирования информации был предложен Д.А. Хаффманом в 1952 году. Хаффмановское кодирование (сжатие) – это широко используемый метод сжатия, присваивающий символам алфавита коды переменной длины, основываясь на вероятностях появления этих символов.

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

Префиксный код – это код, в котором никакое кодовое слово не является префиксом любого другого кодового слова. Эти коды имеют переменную длину.

Оптимальный префиксный код – это префиксный код , имеющий минимальную среднюю длину.

Алгоритм Хаффмана можно разделить на два этапа.

1. Определение вероятности появления символов в исходном тексте.

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

2. Нахождение оптимального префиксного кода.

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

Коды Хаффмана имеют уникальный префикс , что и позволяет однозначно их декодировать, несмотря на их переменную длину.

Пример 1 . Программная реализация метода Хаффмана.

#include "stdafx.h" #include using namespace std; void Expectancy(); long MinK(); void SumUp(); void BuildBits(); void OutputResult(char **Result); void Clear(); const int MaxK = 1000; long k, a, b; char bits; char sk; bool Free; char *res; long i, j, n, m, kj, kk1, kk2; char str; int _tmain(int argc, _TCHAR* argv){ char *BinaryCode; Clear(); cout << "Введите строку для кодирования: "; cin >> str; Expectancy(); SumUp(); BuildBits(); OutputResult(&BinaryCode); cout << "Закодированная строка: " << endl; cout << BinaryCode << endl; system("pause"); return 0; } //описание функции обнуления данных в массивах void Clear(){ for (i = 0; i < MaxK + 1; i++){ k[i] = a[i] = b[i] = 0; sk[i] = 0; Free[i] = true; for (j = 0; j < 40; j++) bits[i][j] = 0; } } /*описание функции вычисления вероятности вхождения каждого символа в тексте*/ void Expectancy(){ long *s = new long; for (i = 0; i < 256; i++) s[i] = 0; for (n = 0; n < strlen(str); n++) s]++; j = 0; for (i = 0; i < 256; i++) if (s[i] != 0){ j++; k[j] = s[i]; sk[j] = i; } kj = j; } /*описание функции нахождения минимальной частоты символа в исходном тексте*/ long MinK(){ long min; i = 1; while (!Free[i] && i < MaxK) i++; min = k[i]; m = i; for (i = m + 1; i <= kk2; i++) if (Free[i] && k[i] < min){ min = k[i]; m = i; } Free[m] = false; return min; } //описание функции подсчета суммарной частоты символов void SumUp(){ long s1, s2, m1, m2; for (i = 1; i <= kj; i++){ Free[i] = true; a[i] = 0; b[i] = 0; } kk1 = kk2 = kj; while (kk1 > 2){ s1 = MinK(); m1 = m; s2 = MinK(); m2 = m; kk2++; k = s1 + s2; a = m1; b = m2; Free = true; kk1--; } } //описание функции формирования префиксных кодов void BuildBits(){ strcpy(bits,"1"); Free = false; strcpy(bits],bits); strcat(bits] , "0"); strcpy(bits],bits); strcat(bits] , "1"); i = MinK(); strcpy(bits[m],"0"); Free[m] = true; strcpy(bits],bits[m]); strcat(bits] , "0"); strcpy(bits],bits[m]); strcat(bits] , "1"); for (i = kk2 - 1; i > 0; i--) if (!Free[i]) { strcpy(bits],bits[i]); strcat(bits] , "0"); strcpy(bits],bits[i]); strcat(bits] , "1"); } } //описание функции вывода данных void OutputResult(char **Result){ (*Result) = new char; for (int t = 0; i < 1000 ;i++) (*Result)[t] = 0; for (i = 1; i <= kj; i++) res] = bits[i]; for (i = 0; i < strlen(str); i++) strcat((*Result) , res]); } Листинг.

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

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

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

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

Принцип неравномерного кода для уменьшения информационного объема сообщения был реализован в азбуке Морзе. Однако, применение кода переменной длины создавало трудности разделения сообщения на отдельные кодовые слова. Эта проблема была решена Морзе путем применения символа-разделителя – паузы.

Префиксные коды

Теоретические исследования К. Шеннона и Р. Фано показали, что можно построить эффективный неравномерный код без использования разделителя. Для этого он должен удовлетворять условию Фано : ни одно кодовое слово не является началом другого кодового слова . Коды, удовлетворяющие условию Фано называются префиксными.

Префиксный код - это код, в котором ни одно кодовое слово не является началом другого кодового слова.

Шеннон и Фано предложили алгоритм построения эффективных сжимающих кодов переменной длины (алгоритм Шеннона – Фано). Однако, в некоторых случаях алгоритм давал неоптимальное решение.

Код Хаффмана

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

Построим код Хаффмана для текста «ОКОЛО КОЛОКОЛА КОЛ»

1. Строим список свободных узлов, упорядоченных по убыванию частоты появления буквы.
2. Выберем две наименее вероятные буквы и построим для них узел-предок («псевдобуква») с частотой, равной сумме частот узлов-потомков.
3. Менее вероятной букве ставим в соответствие 1, более вероятной – 0 (в следующем проходе соблюдаем порядок расстановки 0 и 1).
4. Удаляем обе буквы из списка, оставив их узел-предок.
5. Повторяем шаги, начиная с пункта 2, до тех пор, пока не останется один узел («метабуква»). Этот узел будет считаться корнем дерева.

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

• О – 00
• К – 01
• Л – 10
• Пробел – 110
• А - 111