Сжатие данных (data compression) — технический прием сокращения объема (размеров) записи данных на их носителе (жестком магнитном диске, дискете, магнитной ленте); реализуется разными методами, преимущественно использующими кодирование (повторяющихся слов, фраз, символов).
Можно выделить две группы режимов сжатия данных:
· статический и динамический;
· различают также физическое и логическое сжатие;
· симметричное и асимметричное сжатие;
· адаптивное, полуадаптивное и неадаптивное кодирование;
· сжатие без потерь, с потерями и минимизацией потерь.
Способы (виды) сжатия данных:
Статическое сжатие данных (static data compression) — используется для длительного хранения и архивации; выполняется при помощи специальных сервисных программ-архиваторов, например ARJ, PKZIP/PKUNZIP. После восстановления (декомпрессии) исходная запись восстанавливается.
Динамическое сжатие (сжатие в реальном времени; dynamic compression, compression in real time) — предназначено для сокращения занимаемой области дисковой памяти данными, требующими оперативного доступа и вывода на внешние устройства ЭВМ (в том числе на экран монитора). Динамическое сжатие данных и их восстановление производится специальными программными средствами автоматически и «мгновенно».
ЗАРАБОТОК В ИНТЕРНЕТЕ БЕЗ ВЛОЖЕНИЙ // СОКРАЩАЙ ССЫЛКИ И ПОЛУЧАЙ ПРИБЫЛЬ // SHAREM
Физическое сжатие (physical compression) — методология сжатия, при которой данные перестраиваются в более компактную форму «формально», то есть без учета характера содержащейся в них информации.
Логическое сжатие (logical compression) — методология, в соответствии с которой один набор алфавитных, цифровых или двоичных символов заменяется другим. При этом смысловое значение исходных данных сохраняется. Примером может служить замена словосочетания его аббревиатурой. Логическое сжатие производится на символьном или более высоком уровне и основано исключительно на содержании исходных данных. Логическое сжатие не применяется для изображений.
Симметричное сжатие (symmetric compression) — методология сжатия, в соответствии с которой принципы построения алгоритмов упаковки и распаковки данных близки или тесно взаимосвязаны. При использовании симметричного сжатия время, затрачиваемое на сжатие и распаковку данных, соизмеримо. В программах обмена данными обычно используется симметричное сжатие.
Асимметричное сжатие (asymmetric compression) — методология, в соответствии с которой при выполнении работ «в одном направлении» времени затрачивается больше, чем при выполнении работ в другом направлении. На сжатие изображений обычно затрачивается намного больше времени и системных ресурсов, чем на их распаковку. Эффективность этого подхода определяется тем, что сжатие изображений может производиться только один раз, а распаковываться с целью их отображения – многократно. Алгоритмы асимметричные «в обратном направлении» (на сжатие данных затрачивается меньше времени, чем на распаковку) используется при выполнении резервного копирования данных.
Сжатие данных. Пример на python
Адаптивное кодирование (adaptive encoding) — методология кодирования при сжатии данных, которая заранее не настраивается на определенный вид данных. Программы, использующие адаптивное кодирование, настраиваются на любой тип сжимаемых данных, добиваясь максимального сокращения их объема.
Неадаптивное кодирование (nonadaptive encoding) — методология кодирования, ориентированная на сжатие определенного типа или типов данных. Кодировщики, построенные по этому принципу, имеют в своем составе статические словари «предопределенных подстрок», о которых известно, что они часто появляются в кодируемых данных. Примером может служить метод сжатия Хаффмена.
Полуадаптивное кодирование (half-adaptive coding) — методология кодирования при сжатии данных, которая использует элементы адаптивного и неадаптивного кодирования. Принцип действия полуадаптивного кодирования заключается в том, что кодировщик выполняет две группы операций: вначале — просмотр массива кодируемых данных и построение для них словаря, а затем — собственно кодирование.
Сжатие без потерь (lossless compression) — методология сжатия, при которой ранее закодированная порция данных восстанавливается после их распаковки полностью без внесения изменений.
Сжатие с потерями (lossy compression) — методология, при которой для обеспечения максимальной степени сжатия исходного массива часть содержащихся в нем данных отбрасывается. Для текстовых, числовых и табличных данных использование программ, реализующих подобные методы сжатия, является неприемлемой. Однако для программ, работающих с графикой, это часто бывает целесообразно.
Качество восстановленного изображения зависит от характера графического материала и корректности реализованного в программе алгоритма сжатия. Существует ряд алгоритмов сжатия, учитывающих допустимые уровни потерь исходного графического образа в конкретных вариантах использования его восстановленного изображения, например, путем просмотра его на экране монитора, распечатки принтером, в полиграфии. Эти методы имеют общее наименование «сжатия с минимизацией потерь».
Сжатие изображения (image compression) — технический прием или метод сокращения объема (размеров) записи графических изображений (рисунков, чертежей, схем) на их носителе (например, на магнитном диске, магнитной ленте). По существу, «сжатие изображения» является разновидностью динамического сжатия. Для его реализации используются различные способы кодирования данных, которые ориентированы на элементы графики, составляющие изображение, включая и движущиеся объекты. Применяется также при передаче факсимильной информации по каналам связи, в системах мультимедиа, видеофонах.
Сжатие диска (disk compression) — технический прием, основанный на динамическом сжатии в процессе их записи на диск, а при считывании — их автоматическом восстановлении в исходную форму. Сжатие диска используется с целью увеличения емкости диска. В зависимости от характера записей емкость диска может быть увеличена примерно от 1,5 до 5 раз. Сжатие диска осуществляется специальными прикладными программами, например, DoubleSpace, Stacker, SuperStor.
Методы и средства сжатия данных:
Метод сжатия Хаффмена (Huffman compression method, кодирование CCITT) разработан в 1952 году Дэвидом Хаффменом (David Huffman). Международный консультативный комитет по телефонии и телеграфии (CCITT) разработал на его основе ряд коммуникативных протоколов для факсимильной передачи черно-белых изображений по телефонным каналам и сетям передачи данных (Стандарт T.4 CCIT и T.6 CCITT, они же — сжатие CCITT group 3 и сжатие CCITT group 4).
Фрактальное сжатие (fractal compression) — метод сжатия растровых изображений путем преобразования их в так называемые фракталы. Хранение изображений в виде фракталов требует в четыре раза меньше дисковой памяти, нежели в пикселях.
ART — метод для сжатия текста, графики, аудио и видео. Принцип работы алгоритма сжатия основан на анализе изображения и выявлении его ключевых признаков (цвет, помехи, края, повторяющиеся особенности).
AC3 Dolby — метод и формат сжатия, который позволяет сжимать, хранить и передавать в одном файле со скоростью от 32 до 640 кбит/с до 6 каналов аудиоданных.
DJVU (DjVu, djvu, deja vu) — технология и формат динамического сжатия отсканированных страниц изданий, содержащих текстовые и иллюстративные материалы.
DVI (Digital Video Interactive) — система динамического сжатия и восстановления аудио- и видеозаписей в цифровой форме. Ее использование позволяет записать на CD-ROM полноформатный видеофильм вместе со звуковым сопровождением.
EAD (Encoded Archival Description) — стандарт кодирования, разработанный подразделением Network Development and MARC Standards Office Библиотеки Конгресса США в сотрудничестве с Society of American Archivists в 1998 году (обновление — 2002 г.). Стандарт устанавливает принципы создания, разработки и поддержки схем кодирования для архивных и библиотечных помощников поиска (finding aids).
Image compression manager — программа управления динамическим сжатием изображений, которая обеспечивает возможность использования различных методов сжатия/восстановления изображений (MPEG, JPEG).
JBIG (Joint Bi-level Image Experts Group) — метод сжатия двухуровневых (двухцветных) изображений без потерь, создан Объединенной группой экспертов по двухуровневым изображениям ISO и CCIT в 1988 году. Метод JBIG в 1993 году утвержден как стандарт кодирования двухуровневых данных вместо менее эффективных алгоритмов сжатия MR (Modified READ) и MMR (Modified Modified READ).
LZW (Lempel-Ziv-Welch) — метод динамического сжатия, основанный на поиске во всем файле и сохранении в словаре одинаковых последовательностей данных (они называются фразы). Каждой уникальной последовательности данных присваиваются более короткие маркеры (ключи).
MP3 (Moving Pictures Experts Group, Layer 3) — метод (алгоритм) динамического сжатия и специальный формат записи файлов аудиоданных. MP3 обеспечивает высокую степень сжатия звуковых записей, используется в приложениях мультимедиа, в частности, в цифровых проигрывателях (плейерах) и Интернете.
RLE (Run Length Encoding) — метод динамического сжатия графических данных, в первую очередь изображений, основанный на уменьшении физического размера повторяющихся строк символов.
В формате MP3 используется алгоритм сжатия с потерями, разработанный для существенного уменьшения размера данных, необходимых для воспроизведения записи и обеспечения качества воспроизведения звука очень близкого к оригинальному (по мнению большинства слушателей), хотя аудиофилы говорят об ощутимом различии. При создании MP3 со средним битрейтом 128 кбит/с в результате получается файл, размер которого примерно равен 1/11 от оригинального файла с CD-Audio.
Само по себе несжатое аудио формата CD-Audio имеет битрейт 1411,2 кбит/с. MP3-файлы могут создаваться с высоким или низким битрейтом, который влияет на качество файла-результата. Принцип сжатия заключается в снижении точности некоторых частей звукового потока, что практически неразличимо для слуха большинства людей. Данный метод называют кодированием восприятия.
При этом на первом этапе строится диаграмма звука в виде последовательности коротких промежутков времени, затем на ней удаляется информация, не различимая человеческим ухом, а оставшаяся информация сохраняется в компактном виде. Данный подход похож на метод сжатия, используемый при сжатии картинок в формат JPEG.
Как и формат JPEG, MP3 использует спектральные отсечения, согласно психоакустической модели. Звуковой сигнал разбивается на равные по продолжительности отрезки, каждый из которых после обработки упаковывается в свой фрейм (кадр). Разложение в спектр требует непрерывности входного сигнала, посему для расчётов используется также предыдуший и следующий фрейм.
В звуковом сигнале есть гармоники с меньшей амплитудой и гармоники, лежащие вблизи более интенсивных — такие гармоники отсекаются, так как среднестатистическое человеческое ухо не всегда сможет определить присутствие либо отсутствие таких гармоник. Такая особенность слуха называется эффектом маскировки.
Также возможна замена двух и более близлежащих пиков одним усреднённым (что как правило и приводит к искажению звука). Критерий отсечения определяется требованием к выходному потоку. Поскольку весь спектр актуален, высокочастотные гармоники не отсекаются, как в JPEG, а только выборочно удаляются, чтобы уменьшить поток информации за счёт разрежения спектра.
После спектральной «зачистки» применяются математические методы сжатия и упаковка во фреймы. Каждый фрейм может иметь несколько контейнеров, что позволяет хранить информацию о нескольких потоках (левый и правый канал либо центральный канал и разница каналов). Степень сжатия можно варьировать, в том числе в пределах одного фрейма. Интервал возможных значений битрейта составляет 8-320 кбит/c.
JPEG(англ. Joint Photographic Experts Group, по названию организации-разработчика) — один из популярных графических форматов, применяемый для хранения фотоизображений и подобных им изображений. Файлы, содержащие данные JPEG, обычно имеют расширения (суффиксы).jpeg,.jfif,.jpg,.JPG, или.JPE. Однако из них.jpg является самым популярным на всех платформах
Алгоритм JPEG в наибольшей степени пригоден для сжатия фотографий и картин, содержащих реалистичные сцены с плавными переходами яркости и цвета. Наибольшее распространение JPEG получил в цифровой фотографии и для хранения и передачи изображений с использованием сети Интернет.
С другой стороны, JPEG малопригоден для сжатия чертежей, текстовой и знаковой графики, где резкий контраст между соседними пикселами приводит к появлению заметных артефактов. Такие изображения целесообразно сохранять в форматах без потерь, таких как TIFF, GIF или PNG.
JPEG (как и другие методы искажающего сжатия) не подходит для сжатия изображений при многоступенчатой обработке, так как искажения в изображения будут вноситься каждый раз при сохранении промежуточных результатов обработки.
JPEG не должен использоваться и в тех случаях, когда недопустимы даже минимальные потери, например, при сжатии астрономических или медицинских изображений.
Источник: studopedia.org
Лекция 10 Сжатие данных
Характерной особенностью большинства типов данных является их избыточность. Степень избыточности данных зависит от типа данных. Например, для видеоданных степень избыточности в несколько раз больше чем для графических данных, а степень избыточности графических данных, в свою очередь, больше чем степень избыточности текстовых данных.
Другим фактором, влияющим на степень избыточности является принятая система кодирования. Примером систем кодирования могут быть обычные языки общения, которые являются ни чем другим, как системами кодирования понятий и идей для высказывания мыслей. Так, установлено, что кодирование текстовых данных с помощью средств русского языка дает в среднем избыточность на 20-25% большую чем кодирование аналогичных данных средствами английского языка.
Для человека избыточность данных часто связана с качеством информации, поскольку избыточность, как правило, улучшает понятность и восприятие информации. Однако, когда речь идет о хранении и передаче информации средствами компьютерной техники, то избыточность играет отрицательную роль, поскольку она приводит к возрастанию стоимости хранения и передачи информации. Особенно актуальной эта проблема стает в случае обработки огромных объемов информации при незначительных объемах носителей данных. В связи с этим, постоянно возникает проблема уменьшения избыточности или сжатия данных. Если методы сжатия данных применяются к готовым файлам, то часто вместо термина «сжатие данных» употребляют термин «архивация данных», сжатый вариант данных называют архивом, а программные средства, которые реализуют методы сжатия называются архиваторами.
В зависимости от того, в каком объекте размещены данные, подлежащие сжатию различают:
1. Сжатие (архивация) файлов: используется для уменьшения размеров файлов при подготовке их к передаче каналами связи или к транспортированию на внешних носителях маленькой емкости;
2. Сжатие (архивация) папок: используется как средство уменьшения объема папок перед долгим хранением, например, при резервном копировании;
3. Сжатие (уплотнение) дисков: используется для повышения эффективности использования дискового просторную путем сжатия данных при записи их на носителе информации (как правило, средствами операционной системы).
Существует много практических алгоритмов сжатия данных, но все они базируются на трех теоретических способах уменьшения избыточности данных. Первый способ состоит в изменении содержимого данных, второй — в изменении структуры данных, а третий — в одновременном изменении как структуры, так и содержимого данных.
Если при сжатии данных происходит изменение их содержимого, то метод сжатия называется необратимым, то есть при восстановлении (разархивировании) данных из архива не происходит полное восстановление информации. Такие методы часто называются методами сжатия с регулированными потерями информации. Понятно, что эти методы можно применять только для таких типов данных, для которых потеря части содержимого не приводит к существенному искажению информации. К таким типам данных относятся видео- и аудиоданные, а также графические данные. Методы сжатия с регулированными потерями информации обеспечивают значительно большую степень сжатия, но их нельзя применять к текстовым данным. Примерами форматов сжатия с потерями информации могут быть:
· JPEG — для графических данных;
· MPG — для для видеоданных;
· MP3 — для аудиоданных.
Если при сжатии данных происходит только изменение структуры данных, то метод сжатия называется обратимым. В этом случае, из архива можно восстановить информацию полностью. Обратимые методы сжатия можно применять к любым типам данных, но они дают меньшую степень сжатия по сравнению с необратимыми методами сжатия. Примеры форматов сжатия без потери информации:
· GIF, TIFF — для графических данных;
· AVI — для видеоданных;
· ZIP, ARJ, RAR, CAB, LH — для произвольных типов данных.
В таблице 2 приведены распространенные форматы сжатия и соответствующие им программыи-архиваторы, использующиеся на практике.
| Формат сжатия | Операционная система MS DOS | Операционная система Windows | ||
| Программа архивации | Программа разархивации | Программа архивации | Программа разархивации | |
| ARJ | Arj.exe | Arj.exe | WinArj.exe | WinArj.exe |
| RAR | Rar.exe | Unrar.exe | WinRar.exe | WinRar.exe |
| ZIP | Pkzip.exe | Pkunzip.exe | WinZip.exe | WinZip.exe |
Кроме того, современные архиваторы предоставляют пользователю полный спектр услуг для работы с архивами, основными из которых являются:
1. создание нового архива;
2. добавление файлов в существующий архив;
3. распаковывание файлов из архива;
4. создание самораспаковающихся архивов (self-extractor archive);
5. создание распределенных архивов фиксированного размера для носителей маленькой емкости;
6. защита архивов паролями от несанкционированного доступа;
7. просмотр содержимого файлов разных форматов без предварительного распаковывания;
8. поиск файлов и данных внутри архива;
9. проверка на вирусы в архиве к распаковыванию;
10. выбор и настройка коэффициента сжатия.
Лекция 11 «Компьютерные вирусы»
Компьютерный вирус — это небольшая программа, написанная программистом высокой квалификации, способная к саморазмножению и выполнению разных деструктивных действий. На сегодняшний день известно свыше 50 тыс. компьютерных вирусов.
Вирусы действуют только программным путем. Они, как правило, присоединяются к файлу или проникают в тело файла. В этом случае говорят, что файл заражен вирусом. Вирус попадает в компьютер только вместе с зараженным файлом. Для активизации вируса нужно загрузить зараженный файл, и только после этого, вирус начинает действовать самостоятельно.
Некоторые вирусы во время запуска зараженного файла становятся резидентными (постоянно находятся в оперативной памяти компьютера) и могут заражать другие загружаемые файлы и программы. Другая разновидность вирусов сразу после активизации может быть причиной серьезных повреждений, например, форматировать жесткий диск. Действие вирусов может проявляться по разному: от разных визуальных эффектов, мешающих работать, до полной потери информации. Большинство вирусов заражают исполнительные программы, то есть файлы с расширением.EXE и.COM, хотя в последнее время большую популярность приобретают вирусы, распространяемые через систему электронной почты.
Следует заметить, что компьютерные вирусы способны заражать лишь компьютеры. Поэтому абсолютно абсурдными являются разные утверждения о влиянии компьютерных вирусов на пользователей компьютеров.
Основные источники вирусов:
· дискета, на которой находятся зараженные вирусом файлы;
· компьютерная сеть, в том числе система электронной почты и Internet;
· жесткий диск, на который попал вирус в результате работы с зараженными программами;
· вирус, оставшийся в оперативной памяти после предшествующего пользователя.
Основные ранние признаки заражения компьютера вирусом:
· уменьшение объема свободной оперативной памяти;
· замедление загрузки и работы компьютера;
· непонятные (без причин) изменения в файлах, а также изменения размеров и даты последней модификации файлов;
· ошибки при загрузке операционной системы;
· невозможность сохранять файлы в нужных каталогах;
· непонятные системные сообщения, музыкальные и визуальные эффекты и т.д.
Признаки активной фазы вируса:
· форматирование жесткого диска;
· невозможность загрузки файлов или операционной системы.
Существует очень много разных вирусов. Условно их можно классифицировать следующим образом:
1) загрузочные вирусы или BOOT-вирусы заражают boot-секторы дисков. Очень опасные, могут привести к полной потере всей информации, хранящейся на диске;
2) файловые вирусы заражают файлы. Делятся на:
· вирусы, заражающие программы (файлы с расширением.EXE и.COM);
· макровирусы вирусы, заражающие файлы данных, например, документы Word или рабочие книги Excel;
· вирусы-спутники используют имена других файлов;
· вирусы семейства DIR искажают системную информацию о файловых структурах;
3) загрузочно-файловые вирусы способные поражать как код boot-секторов, так и код файлов;
4) вирусы-невидимки или STEALTH-вирусы фальсифицируют информацию прочитанную из диска так, что программа, какой предназначена эта информация получает неверные данные. Эта технология, которую, иногда, так и называют Stealth-технологией, может использоваться как в BOOT-вирусах, так и в файловых вирусах;
5) ретровирусы заражают антивирусные программы, стараясь уничтожить их или сделать нетрудоспособными;
6) вирусы-черви снабжают небольшие сообщения электронной почты, так называемым заголовком, который по своей сути есть Web-адресом местонахождения самого вируса. При попытке прочитать такое сообщение вирус начинает считывать через глобальную сеть Internet свое ‘тело’ и после загрузки начинает деструктивное действие. Очень опасные, так как обнаружить их очень тяжело, в связи с тем, что зараженный файл фактически не содержит кода вируса.
Если не принимать меры для защиты от компьютерных вирусов, то следствия заражения могут быть очень серьезными. В ряде стран уголовное законодательство предусматривает ответственность за компьютерные преступления, в том числе за внедрение вирусов. Для защиты информации от вирусов используются общие и программные средства.
К общим средствам, помогающим предотвратить заражение и его разрушительных последствий относят:
· резервное копирование информации (создание копий файлов и системных областей жестких дисков);
· избежание пользования случайными и неизвестными программами. Чаще всего вирусы распространяются вместе с компьютерными программами;
· перезагрузка компьютера перед началом работы, в частности, в случае, если за этим компьютером работали другие пользователи;
· ограничение доступа к информации, в частности физическая защита дискеты во время копирования файлов с нее.
К программным средствам защиты относят разные антивирусные программы (антивирусы). Антивирус — это программа, выявляющая и обезвреживающая компьютерные вирусы. Следует заметить, что вирусы в своем развитии опережают антивирусные программы, поэтому даже в случае регулярного пользования антивирусов, нет 100% гарантии безопасности.
Антивирусные программы могут выявлять и уничтожать лишь известные вирусы, при появлении нового компьютерного вируса защиты от него не существует до тех пор, пока для него не будет разработан свой антивирус. Однако, много современных антивирусных пакетов имеют в своем составе специальный программный модуль, называемый эвристическим анализатором, который способен исследовать содержимое файлов на наличие кода, характерного для компьютерных вирусов. Это дает возможность своевременно выявлять и предупреждать об опасности заражения новым вирусом.
Различают такие типы антивирусных программ:
1) программы-детекторы: предназначены для нахождения зараженных файлов одним из известных вирусов. Некоторые программы-детекторы могут также лечить файлы от вирусов или уничтожать зараженные файлы. Существуют специализированные, то есть предназначенные для борьбы с одним вирусом детекторы и полифаги, которые могут бороться с многими вирусами;
2) программы-лекари: предназначены для лечения зараженных дисков и программ. Лечение программы состоит в изъятии из зараженной программы тела вируса. Также могут быть как полифагами, так и специализированными;
3) программы-ревизоры: предназначены для выявления заражения вирусом файлов, а также нахождение поврежденных файлов. Эти программы запоминают данные о состоянии программы и системных областей дисков в нормальном состоянии (до заражения) и сравнивают эти данные в процессе работы компьютера. В случае несоответствия данных выводится сообщение о возможности заражения;
4) лекари-ревизоры: предназначены для выявления изменений в файлах и системных областях дисков и, в случае изменений, возвращают их в начальное состояние.
5) программы-фильтры: предназначены для перехвата обращений к операционной системе, которые используются вирусами для размножения и сообщают об этом пользователя. Пользователь может разрешить или запретить выполнение соответствующей операции. Такие программы являются резидентными, то есть они находятся в оперативной памяти компьютера.
6) программы-вакцины: используются для обработки файлов и boot-секторов с целью предупреждения заражения известными вирусами (в последнее время этот метод используется все чаще).
Следует заметить, что выбор одного «наилучшего» антивируса крайне ошибочное решение. Рекомендуется использовать несколько разных антивирусных пакетов одновременно. Выбирая антивирусную программу следует обратить внимание на такой параметр, как количество распознающих сигнатур (последовательность символов, которые гарантированно распознают вирус).
Второй параметр — наличие эвристического анализатора неизвестных вирусов, его присутствие очень полезно, но существенно замедляет время работы программы. На сегодняшний день существует большое количество разнообразных антивирусных программ. Рассмотрим коротко, распространенные в странах СНГ.
Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:
Источник: studopedia.ru
Сжатие данных без потерь. Алгоритм Хаффмана
Современные пользователи довольно часто сталкиваются с проблемой нехватки свободного пространства на жестком диске. Многие, в попытке освободить хоть немного свободного пространства, пытаются удалить с жесткого диска всю ненужную информацию. Более продвинутые пользователи используют для уменьшения объема данных особые алгоритмы сжатия. Несмотря на эффективность этого процесса, многие пользователи никогда о нем даже не слышали. Давайте же попробуем разобраться, что подразумевается под сжатием данных, какие алгоритмы для этого могут использоваться.
На сегодняшний день сжатие информации является достаточно важной процедурой, которая необходима каждому пользователю ПК. Сегодня любой пользователь может позволить себе приобрести современный накопитель данных, в котором предусмотрена возможность использования большого объема памяти.
Подобные устройства, как правило, оснащаются высокоскоростными каналами для транслирования информации. Однако, стоит отметить, что с каждым годом объем необходимой пользователям информации становится все больше и больше. Всего $10$ лет назад объем стандартного видеофильма не превышал $700$ Мб. В настоящее время объем фильмов в HD-качестве может достигать нескольких десятков гигабайт.
Когда необходимо сжатие данных?
Не стоит многого ждать от процесса сжатия информации. Но все-таки встречаются ситуации, в которых сжатие информации бывает просто необходимым и крайне полезным. Рассмотрим некоторые из таких случаев.
- Передача по электронной почте. Очень часто бывают ситуации, когда нужно переслать большой объем данных по электронной почте. Благодаря сжатию можно существенно уменьшить размер передаваемых файлов. Особенно оценят преимущества данной процедуры те пользователи, которые используют для пересылки информации мобильные устройства.
- Публикация данных на интернет-сайтах и порталах. Процедура сжатия часто используется для уменьшения объема документов, используемых для публикации на различных интернет-ресурсах. Это позволяет значительно сэкономить на трафике.
- Экономия свободного места на диске. Когда нет возможности добавить в систему новые средства для хранения информации, можно использовать процедуру сжатия для экономии свободного пространства на диске. Бывает так, что бюджет пользователя крайне ограничен, а свободного пространства на жестком диске не хватает. Вот тут-то на помощь и приходит процедура сжатия.
«Сжатие данных без потерь. Алгоритм Хаффмана»
Готовые курсовые работы и рефераты
Решение учебных вопросов в 2 клика
Помощь в написании учебной работы
Кроме перечисленных выше ситуаций, возможно еще огромное количество случаев, в которых процесс сжатия данных может оказаться очень полезным. Мы перечислили только самые распространенные.
Способы сжатия информации
Все существующие способы сжатия информации можно разделить на две основные категории. Это сжатие без потерь и сжатие с определенными потерями. Первая категория актуальна только тогда, когда есть необходимость восстановить данные с высокой точностью, не потеряв ни одного бита исходной информации. Единственный случай, в котором необходимо использовать именно этот подход, это сжатие текстовых документов.
В том случае, если нет особой необходимости в максимально точном восстановлении сжатой информации, необходимо предусмотреть возможность использования алгоритмов с определенными потерями при сжатии.
Сжатие без потери информации
Данные методы сжатия информации интересуют прежде всего, так как именно они применяются при передаче больших объемов информации по электронной почте, при выдаче выполненной работы заказчику или при создании резервных копий информации, хранящейся на компьютере. Эти методы сжатия информации не допускают потерю информации, поскольку в их основу положено лишь устранение ее избыточности, информация же имеет избыточность практически всегда, если бы последней не было, нечего было бы и сжимать.
Приведем простой пример. Русский язык включает в себя $33$ буквы, $10$ цифр и еще примерно $15$ знаков препинания и других специальных символов. Для текста, записанного только прописными русскими буквами (например как в телеграммах) вполне хватило бы $60$ разных значений.
Тем не менее, каждый символ обычно кодируется байтом, содержащим, как нам известно, 8 битов, и может выражаться $256$ различными кодами. Это один из первых факторов, характеризующих избыточность. Для телеграфного текста вполне хватило бы и $6$ битов на символ.
Рассмотрим другой пример. В международной кодировке символов ASCII для кодирования любого символа выделяется одинаковое количество битов ($8$), в то время, как всем давно и хорошо известно, что наиболее часто встречающиеся символы имеет смысл кодировать меньшим количеством знаков. Так, к примеру, в азбуке Морзе буквы «Е» и «Т», которые встречаются очень часто, кодируются $1$ знаком (соответственно это точка и тире). А такие редкие буквы, как «Ю» ($• • — -$) и «Ц» ($- • — •$), кодируются $4$ знаками.
Замечание 1
Неэффективная кодировка является вторым фактором, характеризующим избыточность. Программы, благодаря которым выполняется сжатие информации, могут вводить свою кодировку, причем она может быть разной для разных файлов, и приписывать ее к сжатому файлу в виде таблицы (словаря), из которой распаковывающая программа будет считывать информацию о том, как в данном файле закодированы те или иные символы или их группы.
Алгоритмы, в основу которых положено перекодирование информации, называются алгоритмами Хаффмана.
Алгоритм Хаффмана
В данном алгоритме сжатие информации осуществляется путем статистического кодирования или на основе словаря, который предварительно был создан. Согласно статистическому алгоритму Хаффмана каждому входному символу присваивается определенный код. При этом наиболее часто используемому символу — наиболее короткий код, а наиболее редко используемому — более длинный.
В качестве примера на диаграмме приведено распределение частоты использования отдельных букв английского алфавита (рис.1). Такое распределение может быть построено и для русского языка. Таблицы кодирования создаются заранее и имеют ограниченный размер. Этот алгоритм обеспечивает наибольшее быстродействие и наименьшие задержки. Для получения высоких коэффициентов сжатия статистический метод требует больших объемов памяти.
Рисунок 1. Распределение английских букв по их частоте использования
Величина сжатия определяется избыточностью обрабатываемого массива бит. Каждый из естественных языков обладает определенной избыточностью. Среди европейских языков русский имеет самый высокий уровней избыточности. Об этом можно судить по размерам русского перевода английского текста. Обычно он примерно на $30%$ больше.
Если речь идет о стихотворном тексте, избыточность может быть до $2$ раз выше.
Замечание 2
Самая большая сложность с кодами заключается в необходимости иметь таблицы вероятностей для каждого типа сжимаемых данных. Это не представляет проблемы, если известно, что сжимается английский или русский текст. В этом случае мы просто предоставляем кодеру и декодеру подходящее для английского или русского текста кодовое дерево. В общем же случае, когда вероятность символов для входных данных неизвестна, статические коды Хаффмана работают неэффективно.
Решением этой проблемы является статистический анализ кодируемых данных, выполняемый в ходе первого прохода по данным, и составление на его основе кодового дерева. Собственно кодирование при этом выполняется вторым проходом.
Еще одним недостатком кодов является то, что минимальная длина кодового слова для них не может быть меньше единицы, тогда как энтропия сообщения вполне может составлять и $0,1$, и $0,01$ бит/букву. В этом случае код становится существенно избыточным. Проблема решается применением алгоритма к блокам символов, но тогда усложняется процедура кодирования/декодирования и значительно расширяется кодовое дерево, которое нужно в конечном итоге сохранять вместе с кодом.
Данные коды никак не учитывают взаимосвязей между символами, которые присутствуют практически в любом тексте.
Замечание 3
Сегодня, в век информации, несмотря на то, что практически каждому пользователю доступны высокоскоростные каналы для передачи данных и носители больших объемов, вопрос сжатия данных остается актуальным. Существуют ситуации, в которых сжатие данных является просто необходимой операцией. В частности, это касается пересылки данных по электронной почте и размещения информации в Интернете.
Источник: spravochnick.ru