Лекция 9 "Сжатие данных"
Характерной особенностью большинства типов данных является их избыточность. Степень избыточности данных зависит от типа данных. Например, для видеоданных степень избыточности в несколько раз больше чем для графических данных, а степень избыточности графических данных, в свою очередь, больше чем степень избыточности текстовых данных. Другим фактором, влияющим на степень избыточности является принятая система кодирования. Примером систем кодирования могут быть обычные языки общения, которые являются ни чем другим, как системами кодирования понятий и идей для высказывания мыслей. Так, установлено, что кодирование текстовых данных с помощью средств русского языка дает в среднем избыточность на 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 байт памяти. Коэффициент сжатия, характеризующий степень сжатия, можно вычислить по формуле:
где Vx- объем памяти, необходимый для хранения выходной (результирующей) последовательности данных, Vn- входной последовательности данных.
Чем меньше значение коэффициента сжатия, тем эффективней метод сжатия. Понятно, что алгоритм RLE будет давать лучший эффект сжатия при большей длине повторяющейся последовательности данных. В случае рассмотренного выше примера, если входная последовательность будет иметь такой вид: 1 1 1 1 1 1 3 4 4 4, то коэффициент сжатия будет равен 60%. В связи с этим большая эффективность алгоритма RLE достигается при сжатии графических данных (в особенности для однотонных изображений).
Алгоритмы группы KWE
В основе алгоритма сжатия по ключевым словам положен принцип кодирования лексических единиц группами байт фиксированной длины. Примером лексической единицы может быть обычное слово. На практике, на роль лексических единиц выбираются повторяющиеся последовательности символов, которые кодируются цепочкой символов (кодом) меньшей длины. Результат кодирования помещается в таблице, образовывая так называемый словарь.
Существует довольно много реализаций этого алгоритма, среди которых наиболее распространенными являются алгоритм Лемпеля-Зіва (алгоритм LZ) и его модификация алгоритм Лемпеля-Зіва-Велча (алгоритм LZW). Словарем в данном алгоритме является потенциально бесконечный список фраз. Алгоритм начинает работу с почти пустым словарем, который содержит только одну закодированную строку, так называемая NULL-строка. При считывании очередного символа входной последовательности данных, он прибавляется к текущей строке. Процесс продолжается до тех пор, пока текущая строка соответствует какой-нибудь фразе из словаря. Но рано или поздно текущая строка перестает соответствовать какой-нибудь фразе словаря. В момент, когда текущая строка представляет собой последнее совпадение со словарем плюс только что прочитанный символ сообщения, кодер выдает код, который состоит из индекса совпадения и следующего за ним символа, который нарушил совпадение строк. Новая фраза, состоящая из индекса совпадения и следующего за ним символа, прибавляется в словарь. В следующий раз, если эта фраза появится в сообщении, она может быть использована для построения более длинной фразы, что повышает меру сжатия информации.
Алгоритм LZW построен вокруг таблицы фраз (словаря), которая заменяет строки символов сжимаемого сообщения в коды фиксированной длины. Таблица имеет так называемое свойством опережения, то есть для каждой фразы словаря, состоящей из некоторой фразы w и символа К, фраза w тоже заносится в словарь. Если все части словаря полностью заполнены, кодирование перестает быть адаптивным (кодирование происходит исходя из уже существующих в словаре фраз).
Алгоритмы сжатия этой группы наиболее эффективны для текстовых данных больших объемов и малоэффективны для файлов маленьких размеров (за счет необходимости сохранение словаря).
Алгоритм Хаффмана
В основе алгоритма Хаффмана лежит идея кодирования битовыми группами. Сначала проводится частотный анализ входной последовательности данных, то есть устанавливается частота вхождения каждого символа, встречащегося в ней. После этого, символы сортируются по уменьшению частоты вхождения.
Основная идея состоит в следующем: чем чаще встречается символ, тем меньшим количеством бит он кодируется. Результат кодирования заносится в словарь, необходимый для декодирования. Рассмотрим простой пример, иллюстрирующий работу алгоритма Хаффмана.
Пусть задан текст, в котором бурва 'А' входит 10 раз, буква 'В' - 8 раз, 'С'- 6 раз , 'D' - 5 раз, 'Е' и 'F' - по 4 раза. Тогда один из возможных вариантов кодирования по алгоритму Хаффмана приведен в таблицы 1.
Таблица 1.
Символ
Частота вхождения
Битовый код
A
10
00
B
8
01
C
6
100
D
5
101
E
4
110
F
4
111
Как видно из таблицы 1, размер входного текста до сжатия равен 37 байт, тогда как после сжатия - 93 бит, то есть около 12 байт (без учета длины словаря). Коэффициент сжатия равен 32%. Алгоритм Хаффмана универсальный, его можно применять для сжатия данных любых типов, но он малоэффективен для файлов маленьких размеров (за счет необходимости сохранение словаря).
На практике программные средства сжатия данных синтезируют эти три "чистых" алгоритмы, поскольку их эффективность зависит от типа и объема данных. В таблице 2 приведены распространенные форматы сжатия и соответствующие им программыи-архиваторы, использующиеся на практике.
Таблица 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
Кроме того, современные архиваторы предоставляют пользователю полный спектр услуг для работы с архивами, основными из которых являются:
создание нового архива;
добавление файлов в существующий архив;
распаковывание файлов из архива;
создание самораспаковающихся архивов (self-extractor archive);
создание распределенных архивов фиксированного размера для носителей маленькой емкости;
защита архивов паролями от несанкционированного доступа;
просмотр содержимого файлов разных форматов без предварительного распаковывания;
поиск файлов и данных внутри архива;
проверка на вирусы в архиве к распаковыванию;
выбор и настройка коэффициента сжатия.
WinZip
WinZip — условно-бесплатный файловый архиватор и компрессор для Microsoft Windows фирмы Corel. PKZIP является основным форматом, хотя поддерживаются и другие архивные форматы.
Возможности
Создание, дополнение, извлечение из архивов ZIP.
Поддержка алгоритмов компрессии JPEG, LZMA, bzip2, PPMd и специальных алгоритмов для звуковых файлов (на основе WavPack), что позволяет уменьшить архив за счёт потенциального увеличения времени сжатия и извлечения (особенно при использовании PPMd).
Декомпрессия файлов .bz2, .rar, .iso, .img, 7-zip
Встроенная поддержка архивов LHA (.lha и .lzh)
Настраиваемая интеграция в оболочку Microsoft Windows.
Поддержка 128- и 256-битных ключей шифрования AES. Это позволило заменить менее надёжный метод шифрования PKZIP 2.0 используемый в ранних версиях. Версия 9 также осуществляет поддержку 64-битного шифрования в PKZIP.
Дополнительные возможности
Прямая запись архивов на CD / DVD
Автоматизация резервного копирования
Поддержка протокола FTP
Отправка ZIP архивов по электронной почте
Поддержка Юникода (c версии 11.2)
7-Zip
7-Zip — файловый архиватор с высокой степенью сжатия. Программа свободно распространяется на условиях лицензии GNU LGPL.
Основные характеристики 7-Zip
Поддерживаемые форматы:
Полностью: 7z, ZIP (кроме WinZip 11 версии), gzip, bzip2, tar.
Частично (только распаковка и просмотр): CAB (англ.), RAR, ARJ[2], cpio (англ.), RPM, deb, (ar),
Очень высокая степень сжатия в новом формате 7z благодаря использованию усовершенствованного алгоритма Лемпела-Зива.
Для форматов ZIP и GZIP степень сжатия на 2—10 % выше, чем у PKZip и WinZip.
Возможность создания самораспаковывающихся архивов для формата 7z.
В формате 7z возможно создавать многотомные архивы (в наст. время за исключением самораспаковывающихся)
Возможность шифрования архивов, алгоритмом AES с длиной ключа 256 бит (для формата 7z).
Интеграция в оболочку Microsoft Windows и Windows NT.
Плагин для программы FAR Manager.
Плагин для программ Total Commander и Unreal Commander.
Мультиязычный графический интерфейс (только для Windows) с функциями двухоконного файлового менеджера.
Степень сжатия
Результаты по степени сжатия сильно зависят от сжимаемых данных. Обычно 7-Zip сжимает в формат 7z на 30—50% лучше, чем в формат zip, а в формат ZIP — на 2—10% лучше, чем другие ZIP-совместимые архиваторы.
В большинстве случаев степень сжатия выше, чем у RAR, за исключением некоторых мультимедиа-данных. Скорость сжатия при этом ниже, но не критично (как правило, не более чем на 30%).
Более того, считается, что по степени сжатия 7-Zip уступает только архиваторам PAQ и его GUI-модификации KGB, которые, однако, имеют на порядок большее время сжатия.
Недостатки
при высоком уровне сжатия, скорость сжатия данных заметно ниже, чем у многих популярных архиваторов;
при сжатии некоторых мультимедиа?данных уступает RAR;
отсутствие возможности создавать многотомные SFX-архивы;
неполные 7-zip архивы невозможно открыть (например, если архив был закачан не до конца) — у таких архивов невозможно ни ознакомиться со списком сжатых файлов, ни разархивировать файлы, которые находятся в частично скачанной части (например, WinRAR позволяет это делать со своими недокачанными архивами);
Формат файла 7z не предназначен для использования с потоками. (p7zip)
При открытии или запуске файла из архива автоматически не разархивируется вся папка, что не удобно при открытии, например, html файлов т.к. рисунки будут недоступны
WinRAR
WinRAR — это файловый архиватор для Windows с высокой степенью сжатия, является одним из лучших архиваторов по соотношению степени сжатия к скорости работы. Распространяется по shareware-лицензии. Версия для платформы Pocket PC имеет лицензию Freeware.
Разработанная российским программистом Евгением Рошалем программа WinRAR позволяет работать с ZIP-архивами, но основным форматом для нее является RAR (также разработка Рошаля). Дистрибутив WinRAR — EXE-файл объемом около 650 Кбайт, после инсталляции пакет занимает почти 1,5 Мбайт. Имеются версии архиватора на английском и русском языке. Окно архиватора напоминает системную утилиту «Мой компьютер», архивы выглядят и ведут себя подобно обычным папкам. Пополнять архивы и извлекать из них объекты можно с помощью перетаскивания. Для просмотра упакованных файлов в программе имеется встроенный модуль визуализации, но можно подключать и внешнюю утилиту просмотра. Программа снабжена весьма обстоятельной справочной системой.
Основные возможности
Создание архивов форматов RAR и ZIP.
Распаковка файлов формата CAB, ARJ, LZH, TAR, GZ, ACE, UUE, BZ2, JAR, ISO, 7z, Z.
Оригинальный высокоэффективный алгоритм сжатия данных с длиной ключа 128 бит.
Специальный алгоритм мультимедиа-сжатия.
Возможность работы с файлами размером до 8,589 трлн (1012) гигабайт.
Создание самораспаковывающихся, непрерывных и многотомных архивов.
Добавление в архивы дополнительной информации для восстановления архива в случае его повреждения, в том числе создание специальных томов восстановления, позволяющих восстановить многотомный архив при повреждении частей с информацией.
Полная поддержка файловой системы NTFS и имен файлов в Юникоде.
Поддержка командной строки
Лаборатория Касперского
«Лаборато?рия Каспе?рского» — международная группа компаний с центральным офисом в Москве, специализирующаяся на разработке систем защиты от вирусов, спама и хакерских атак. Компания входит в пятерку ведущих мировых разработчиков программного обеспечения для защиты информации от интернет-угроз.
Основана как самостоятельная компания 21 июля 1997 года.
Собственники и руководство
Компания принадлежит шести сотрудникам. Контрольный пакет находится у Евгения Касперского. Председатель Совета директоров — бывшая жена Евгения Наталья Касперская, владеющая блокирующим пакетом. Генеральным директором с 8 августа 2007 года является основатель компании — Евгений Касперский.
Деятельность
Лаборатория Касперского — это международная группа компаний с центральным офисом в Москве и представительствами в Великобритании, Китае, Франции, США, Германии, Румынии, Японии, Южной Корее, Нидерландах, Польше, ОАЭ и Канаде. Обладает партнёрской сетью, объединяющей более 500 компаний более чем в 60 странах мира.
Общая численность персонала компании — около 900 человек. Ведущие вирусные аналитики «Лаборатории Касперского» — члены международной Computer Anti-Virus Research Organization (CARO).
Доходы компании за 2006 год составили $ 67,3 млн, что эквивалентно 98,7 % всего российского рынка антивирусной защиты.
Продукты
Актуальные продукты
Лаборатория Касперского разрабатывает решения для защиты как домашних пользователей, так и корпоративных сетей любого масштаба. Продуктовая линейка компании включает в себя решения для всех популярных операционных систем (Windows, Linux и т. д.)
Программное ядро Антивируса Касперского используют в своих продуктах такие разработчики, как: Microsoft (США), Check Point Software Technologies (Израиль, США), Juniper (США), Nokia ICG (США), F-Secure (Финляндия), Aladdin (Израиль), Sybari (США), G Data (Германия), Deerfield (США), Alt-N (США), Microworld (Индия), BorderWare (Канада) и т. д.
Продукты «Лаборатории Касперского» сертифицированы ведущими поставщиками аппаратного и программного обеспечения: Microsoft®, IBM®, Intel®, Cisco Systems®, Red Hat®, Citrix Systems®, Novell® и другими
Продукты для дома
Антивирус Касперского — защита персонального компьютера от вирусов и другого вредоносного ПО;
Kaspersky Internet Security — защита компьютера от вирусов и другого вредоносного ПО, а также от хакерских атак и спама;
Kaspersky Mobile Security — защита мобильного устройства от сетевых атак, вредоносного ПО и SMS-спама.
Продукты для офиса
Компания выпускает решения для защиты всех типов сетевых узлов. Помимо продуктов, разработанных для защиты отдельных узлов сети, Лаборатория Касперского предлагает комплексные решения, например, Kaspersky Open Space Security. Линейка Open Space включает в себя четыре продукта, каждый из которых предназначен для защиты сетевых узлов в определенной комбинации.
Dr.Web
Dr. Web — антивирусы этого семейства предназначены для защиты от почтовых и сетевых червей, руткитов, файловых вирусов, троянских программ, стелс-вирусов, полиморфных вирусов, бестелесных вирусов, макровирусов, вирусов, поражающих документы MS Office, скрипт-вирусов, шпионского ПО (spyware), программ-похитителей паролей, клавиатурных шпионов, программ платного дозвона, рекламного ПО (adware), потенциально опасного ПО, хакерских утилит, программ-люков, программ-шуток, вредоносных скриптов и других вредоносных объектов, а также от спама, скаминг-, фарминг-, фишинг-сообщений и технического спама.
Характерные особенности
Характерной особенностью антивируса Dr. Web является возможность установки на зараженную машину. В процессе установки производится сканирование памяти и файлов автозагрузки, перед сканированием производится обновление вирусной базы. При этом выпуски обновлений вирусных баз производятся с периодичностью в несколько часов и менее.
Origins Tracing — алгоритм несигнатурного обнаружения вредоносных объектов, который дополняет традиционные сигнатурный поиск и эвристический анализатор, даёт возможность значительно повысить уровень детектирования ранее неизвестных вредоносных программ.
Dr. Web Shield — механизм борьбы с руткитами, реализованный в виде драйвера компонент антивирусного сканера обеспечивает доступ к вирусным объектам, скрывающимся в глубинах операционной системы.
поддержка большинства существующих форматов упакованных файлов и архивов, в том числе, многотомных и самораспаковывающихся архивов. На данный момент имеется поддержка около 4000 видов различных архивов и упаковщиков.
обновления вирусных баз производятся немедленно по мере выявления новых вирусов, до нескольких раз в час. Разработчики антивирусного продукта отказались от выпуска обновлений вирусных баз по какому-либо графику, поскольку вирусные эпидемии не подчиняются таковым.
компактная вирусная база и небольшой размер обновлений. Одна запись в вирусной базе позволяет определять десятки, в ряде случаев, тысячи подобных вирусов.
небольшой размер дистрибутива.
кроссплатформенность — используется единая вирусная база и единое ядро антивирусного сканера.
возможность полноценной работы сканера без инсталляции, что позволяет использовать антивирус для лечения зараженных систем с использованием носителей в режиме только для чтения.
обнаружение и лечение сложных полиморфных, шифрованных вирусов и руткитов