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

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

Курсовая работа

Архивация и сжатие файлов



Введение

архивация компьютерный сжатие алгоритм

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

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

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

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



1. Понятие процесса архивации файлов

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

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

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

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

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



2. Назначение программ архиваторов

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

3. Методы сжатия компьютерных файлов

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

Кодирование длин серий (RLE - сокращение от run-lengthencoding - кодирование длин серий)

Метод, в котором последовательная серия одинаковых элементов данных заменяется на два символа: элемент и число его повторений. Широко используется как дополнительный, так и промежуточный метод. В качестве самостоятельного метода применяется, например, в графическом формате BMP.

Словарный метод (LZ - сокращение от LempelZiv - имена авторов)

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

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

Энтропийный метод (Huffman - кодирование Хаффмена, Arithmeticcoding - арифметическое кодирование)

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

Метод контекстного моделирования (CM - сокращение от contextmodeling - контекстное моделирование)

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

PPM (PPM - PredictionbyPartialMatching - предсказание по частичному совпадению)

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

Предварительные преобразования или фильтрация

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

Метод сортировки блока данных (BWT - сокращение от BurrowsWheelerTransform - по имени авторов)

Это особый вид или группа преобразований, в основе которых лежит сортировка. Такому преобразованию можно подвергать почти любые данные. Сортировка производится над блоками, поэтому данные предварительно разбиваются на части. Основным параметром является размер блока, который подвергается сортировке. Для распаковки данных необходимо проделать почти те же действия, что и при упаковке. Поэтому скорость и требования к оперативной памяти почти одинаковы. Архиваторы, которые используют данный метод, обычно показывают высокую скорость и степень сжатия для текстовых данных.

4. Программы архиваторы

Следует различать собственно программу-архиватор, формат архивов и методы сжатия. Даже один и тот же метод сжатия может иметь варианты реализации. Например, существует более десятка программ-архиваторов, которые могут создавать архивы в формате ZIP. В свою очередь данные в формате ZIP могут быть сжаты различными методами: Deflate, Deflate64, BZip2. Метод Deflate имеет несколько реализаций с разной скоростью и степенью сжатия. С помощью этого метода архиватор 7-zip позволяет создавать архивы в формате ZIP и 7Z.

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

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

- Сжатие некоторых файлов и целых директорий;

- Создание самораспаковывающихся (SFX) архивов. То есть для распаковки архива программа-архиватор не требуется;

- Изменение содержимого архива;

- Шифрование содержимого архива;

- Информация для восстановления архива при частичном повреждении и возможность восстановления поврежденных архивов;

- Разбивка архива на несколько частей или томов;

- Консольная версия программы для работы из командной строки;

- Графическая (GUI) версия программы.

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

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

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

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

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

Далее рассмотрим популярные программы архиваторы.

WinRAR

Версия 2.90 Final

Автор: Евгений Рошал (roshal@rarsoft.com)

Поддерживаемые платформы: Windows, Linux, BeOSand DOS-32

WinRAR - 32-разрядная версия архиватора RAR для Windows. Помимо полной поддержки RAR и ZIP, WinRAR 2.90 может распаковывать UUE, GZ, TAR, ARJ, LZH, ACE, CAB, BZIP2, JAR (JavaARchive) и ACE 2.0 архивов. WinRAR имеет оригинальный алгоритм сжатия, обладающий высокими показателями коэффициента сжатия, особенно на исполняемых файлах, больших текстовых файлах и т.д. При этом количество входящих в архив сжатых файлов не ограничено.

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

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

Также имеются дополнительные функции, например шифрование, добавление архивных комментариев, протоколирование ошибок и пр.

WinZip

Версия v8.1

Автор: NicoMak (support@winzip.com)

Поддерживаемые платформы: Win9x, WinNT, Mac

Одна из самых популярных в Интернете программ. Сам ZIP-алгоритм свободно используется в десятках, если не в сотнях программ, и, тем не менее, для большинства пользователей Windows именно WinZIP служит стандартной программой для работы с архивами. WinZipпрост в работе, имеет поддержку длинных имен и оптимизирован для работы в среде Windows.

WinZIP умеет просматривать и извлекать файлы из прочих, менее распространенных форматов архивов, таких как ARJ, LZH, ARC, TAR, TAZ, TGZ, Z, GZ, CAB, UUE, XXE, UU, B64, HQX, BHX. Есть функции инсталляции программ, экранных тем и скрин-сэйверов из архивов, выполнения многих операций через пошаговые Wizard'ы, сжатия и отправки файлов по почте, проверки содержимого архивов внешним антивирусом, управления закладками избранных архивных директорий, поддерживается возможность интеграции с Проводником Windows (добавление команд в контекстные меню). Имеются отдельные утилиты для работы из командной строки, интеграции с популярными Интернет-браузерами, создания самораспаковывающихся архивов.

WinZip имеет весьма удобную функцию автоматической инсталляции для программного продукта, распространяемого в виде Zip-файлов.

Для упрощенного архивирования / разархивирования файлов WinZipпредлагает мастер-программуWinZipWizard. Имеется возможность организации файлов в «любимые» папки (FavoriteZipFolders). WinZip позволяет организовать Zip-файлы в виде одного «листа», который помогает легче объединять и сортировать Zip-файлы независимо от того, где они физически хранятся. Функция поиска позволяет найти любые Zip-файлы, «потерянные» на жестком диске. Имеется возможность создавать саморазархивирующиеся файлы. WinZip можно настроить для работы с большинством современных антивирусных сканеров.

WaveZip

Версия 2.0

Автор: GadgetLabs

Поддерживаемые платформы: Win9x, WinNT, Mac

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

WaveZIPпрост в работе и позволяет быстро находить, селектировать и конвертировать файлы. Поддерживается функция Drag-and-drop из Windows Explorer.

В программе реализована специальная технология MUSICompress от компании SoundspaceAudio. Компрессия происходит абсолютно без потерь, алгоритмы оптимизированы именно под задачи сжатия WAV-формата (средняя степень сжатия в зависимости от типа файла достигает 30-60%).

WavPack

Версия 3.92

Автор: DavidBryant (david@wavpack.com)

Поддерживаемые платформы: Win9x, WinNT, Mac

Консольный компрессор, специализирующийся на аудиосжатии. Предоставляет возможность упаковки / распаковки без потерь 16/24-битных моно- и стереофайлов в WAV-формате. WavPack показывает высокую скорость работы, обеспечивает 25-50-процентное сжатие поп-музыки и немного лучшее сжатие для классической музыки и композиций с широким динамическим диапазоном. Максимальный достижимый уровень упаковки - 87% (для периодов тишины). Предоставляется настраиваемый режим сжатия с потерями (до 67% с неслышимыми потерями и до 77% с заметным шумом), возможно сжатие «сырых» аудиофайлов неизвестных форматов, поддерживается быстрый режим упаковки, есть WinAMP-плагин для проигрывания сжатых WavPack'ом файлов.

PowerArchiver

Версия v7.02

Автор: Ivan Petrovic (ivanpetrov@ipsoft.cjb.net)

Поддерживаемыеплатформы: Win9x, WinNT

Мощнаямногоформатная Windows GUI-оболочка, позволяющаяработатьсархивамивформатах ZIP, RAR, CAB, ARJ, LHA, ACE, ARC, TAR, BZIP2, TAR.BZ2, GZ, BH, ZOO, XXE, UUE. Помимо стандартных операций PowerArchiver может производить переименование файлов в архивах, инсталлировать из них программы, проверять содержимое на вирусы, конвертировать архивы из одного формата в другой, защищать их паролем, чинить, создавать многотомные и самораспаковывающиеся (SFX) архивы. Программа также позволяет своими средствами просматривать файлы TXT, RTF, BMP, ICO, GIF, WMF, EMF и JPG, распечатывать списки архивных файлов или экспортировать их в TXT- и HTML-форматах. Имеются средства управления списком быстрого доступа к часто используемым директориям, изменения внешнего вида кнопочной панели с помощью скинов, произведения операций резервирования данных с помощью скриптов, поиска обновлений программы в Интернете, создания отдельного архива для каждого сжимаемого файла.

PowerArchiver имеет удобный переключаемый интерфейс в стиле Office 2000 с подробной справочной системой и интегрируется с Проводником Windows, обеспечивая поддержку операций Drag&Drop и удобных контекстных меню.

ZipMagic

Версия 4.0

Поддерживаемые платформы: Win9x, WinNT

Компания Mijenix выпустила обновленную версию своей популярной программы ZipMagic. Цель программы - обеспечить возможность работать с архивами как с обыкновенными дисковыми папками. То есть все zip-файлы, имеющиеся на дисках, магическим образом «превращаются» в обычные директории. При этом ни Проводник, ни NortonCommander, ни любая другая программа не подозревают, что имеют дело с архивами. Пользователь может работать с псевдопапками: переименовывать их, запускать и инсталлировать из них программы, игры, просматривать, редактировать, копировать, переименовывать файлы, создавать и удалять поддиректории и т.д. ZipMagic незаметно будет производить операции сжатия / распаковки, причем значительно быстрее, чем большинство известных zip-упаковщиков.

В новой версии программы добавлена поддержка большинства новых форматов архивов и кодировок. Среди них: RC, ARJ, CAB, GZ, LHA/LZH, RAR, TAR, ZOO, UU/XXEncode и многие другие. При этом для работы с файлами этих форматов вам не понадобятся сами утилиты, создавшие их. Для работы с ними предназначена поставляемая с ZipMagic утилита ZipTools. Все вышеупомянутые типы файлов автоматически ассоциируются в реестре с этой утилитой и, естественно, ею и открываются.

ZipTools представляет собой некое подобие Проводника, с помощью которого можно выполнять все стандартные функции, присущие файл-менеджерам (копирование, перенос, переименование файлов, поддержка Drag&Drop, настройка панелей, сортировка, многооконность и т.п.), а также специфические функции типа UU-кодирования, конвертирования в ZIP, форматирования дисков, поиска файлов / компьютеров и тому подобное. Кроме того, ZipTools позволяет быстро просматривать более 60 форматов файлов / документов, в том числе мультимедийных, не выходя из программы.

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

Помимо этого с программой поставляются специальныеzip-плагины для браузеров и e-mail. Первый - ZipSurfer - предназначен для работы в NetscapeNavigator, NetscapeCommunicator и Internet Explorer и позволяет распаковывать, просматривать свежескачанные из Интернета архивы, инсталлировать из них программы и выполнять прочие операции с архивами, не выходя из браузера (нечто подобное имеется в известном WinZip).

Второй плагин - ZipMail - представляет собой дополнение к таким программам, как EudoraLight, EudoraPro, Microsoft Exchange, Outlook 97 и Outlook 98.

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

5. Примеры алгоритмы архивации и сжатия информации с применением различных программных средств

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

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

- оперативной памяти (под промежуточные данные);

- постоянной памяти (под код программы и константы);

- процессорного времени.

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

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

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

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

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

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

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

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

Описание и особенности некоторых алгоритмов архивации

Рассмотрим следующие алгоритмы сжатия:

1) RLE

2) коды Хаффмана

3) метод «стопкикниг» (MTF - Move to Font)

4) арифметическое кодирование

RLE

Алгоритм RLE (RunLengthEncoding, упаковка, кодирование длин серий), является самым быстрым, простым и понятным алгоритмом сжатия данных и при этом иногда оказывается весьма эффективным. Именно подобный алгоритм используется для сжатия изображений в файлах PCX. Он заключается в следующем: любой последовательности повторяющихся входных символов ставится в соответствие набор из трех выходных символов: первый-байт префикса, говорящий о том, что встретилась входная повторяющаяся последовательность, второй-байт, определяющий длину входной последовательности, третий-сам входной символ - <prefix, length, symbol>. Лучше всего работу алгоритма пояснить на конкретном примере.

Например: пусть имеется (шестнадцатиричный) текст вида

05 05 05 05 05 05 01 01 03 03 03 03 03 03 05 03 FF FFFFFF

из 20 байт. Выберем в качестве префикса байт FF. Тогда на выходе архиватора мы получим последовательность

FF 06 05 FF 02 01 FF 06 03 FF 01 05 FF 01 03 FF 04 FF

Ее длина-18 байт, то есть достигнуто некоторое сжатие. Однако, нетрудно заметить, что при кодировании некоторых символов размер выходного кода возрастает (например, вместо 01 01 - FF 02 01). Очевидно, одиночные или дважды (трижды) повторяющиеся символы кодировать не имеет смысла - их надо записывать в явном виде. Получим новую последовательность:

FF 06 05 01 01 FF 06 03 05 03 FF 04 FF

длиной 13 байт. Достигнутая степень сжатия: 13/20 = 65%.

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

FF то же самое, что и FF 01 FF (три байта вместо одного).

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

Можно сделать следующий шаг, повышающий степень сжатия, если объединить префикс и длину в одном байте. Пусть префикс-число F0…FF, где вторая цифра определяет длину length от 0 до 15. В этом случае выходной код будет двухбайтным, но мы сужаем диапазон представления длины с 255 до 15 символов и еще более ограничиваем себя в выборе префикса. Выходной же текст для нашего примера будет иметь вид:

F6 05 F2 01 F6 03 05 03 F4 FF

Длина-10 байт, степень сжатия-50%.

Далее, так как последовательность длиной от 0 до 3 мы условились не кодировать, код length удобно использовать со смещением на три, то есть 00=3, 0F=18, FF=258, упаковывая за один раз более длинные цепочки.

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

06 05 02 01 06 03 01 05 01 03 04 FF

Длина-12 байт, степень сжатия-60%.

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

01 05 07 01 09 03 0F 05 10 03 11 FF

Таблица 1. Вывод по алгоритму RLE

Алгоритм	Степень сжатия	Скорость	Память	Сжатие без потерь	Проходы	РО	ВИ
RLE	2-3	10	10	Да	1	Нет	Возм.



Здесь и далее приняты следующие обозначения: РО - распространение ошибки, ВИ - возрастание избыточности. Степень сжатия, скорость и используемая оперативная память оцениваются по десятибалльной системе с точки зрения автора. Чем больше величина, тем лучше указанный параметр (выше скорость работы, выше степень сжатия и меньшая потребляемая память).

Работа: в реальном масштабе времени и в потоке.

Основное применение: РСХ, сжатие изображений.

Коды Хаффмана.

Наиболее эффективным кодом переменной длины, в котором ни одно слово не совпадает с началом другого (т.е. префиксный код) является код Хаффмана.

Пусть l1,…, lk-положительные целые числа (k>0). Для того, чтобы существовал префиксный код, длины слов которого равны l1,…, lk, необходимо и достаточно выполнение неравенства Крафта:

Все префиксные коды являются кодами со свойством однозначного декодирования, но не наоборот (например, однозначно декодируемый код 0, 01, 011, 0111,… не является префиксным). Избыточность дешифрируемого кодирования неотрицательна. Для кода Хаффмана (Шеннона) избыточность не превышает 1, т.е. 0 R 1. Длина кода Шеннона равна

|ai| = -log (p(ai)),

а длина кода Хаффмана не превышает величины |ai|.

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

Рассмотрим построение кода Хаффмана на простом примере:

пусть есть текст ABACCADAА. При кодировке двоичным кодом постоянной длины вида:

A - 00, B - 01, C - 10, D - 11

мы получим сообщение 000100101000110000 длиной 18 бит. Теперь построим код Хаффмана, используя дерево Хаффмана.

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

A - 0, B - 110, C - 10, D - 111

Исходное сообщение после кодирования станет 011001010011100 (15 бит). Степень сжатия: 15/18 = 83%. Легко убедиться, что имея коды Хаффмана, можно однозначно восстановить первоначальный текст

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

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

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

Вариантами дерева Хаффмана следует также считать деревья, полученные для монотонных источников. Эти источники имеют два важных для наших целей свойства: нет необходимости вычислять частоты появления символов входного текста - как следствие, однопроходный алгоритм; дерево Хаффмана для таких источников может быть представлено в виде вектора из нескольких байтов, каждый из которых обозначает количество кодов дерева определенной длины, например: запись 1,1,0,2,4 говорит о том, что в дереве имеется по одному коду длин 1 и 2 бита, 0 кодов длиной 3 бита, 2 кода длиной 4 бита и 4 кода длиной 5 бит. Сумма всех чисел в записи даст количество символов в алфавите.

Основное применение: универсальный, сжатие текстов и бинарной информации. Динамический алгоритм построения кода Хаффмана используется в архиваторе ICE, статический - в LHA, ARJ. Статический алгоритм Шеннона-Фано используется архиватором PKZIP. Применяется для сжатия изображений (формат JPEG).

Метод «стопки книг» (MTF).

Сравнительно недавно появилась еще одна разновидность адаптивного алгоритма Хаффмана, описанная Рябко, а затем Бентли и названная, соответственно, алгоритмом стопки книг или «двигай вверх» («MTF-MoveToFront»). Каждому символу (букве) присваивается код в зависимости от его положения в алфавите - чем ближе символ к началу алфавита - тем короче код (в качестве кода можно использовать, например, код дерева для монотонных источников). После кодирования очередного символа мы помещаем его в начало алфавита, сдвигая все остальные буквы на одну позицию вглубь. Через некоторое время наиболее часто встречаемые символы сгруппируются в начале, что и требуется для успешного кодирования. Работа алгоритма, действительно, напоминает перекладывание наиболее нужных книг из глубин библиотеки ближе к верху, вследствие чего потом их будет легче найти (аналогия с обыденной жизнью).



Таблица 2. Вывод по методу «стопки книг»

Алгоритм	Степень сжатия	Скорость	Память	Сжатие без потерь	Проходы	РО	ВИ
Стопка книг	3-5	7	8	Да	1	Да	Возм.

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

Арифметическое кодирование является методом, позволяющим упаковывать символы входного алфавита без потерь при условии, что известно распределение частот этих символов. Арифметическое кодирование является оптимальным, достигая теоретической границы степени сжатия H0. Однако, коды Хаффмана в предыдущем разделе мы тоже называли оптимальными. Как объяснить этот парадокс? Ответ заключается в следующем: коды Хаффмана являются неблочными, т.е. каждой букве входного алфавита ставится в соответствие определенный выходной код. Арифметическое кодирование-блочное и выходной код является уникальным для каждого из возможных входных сообщений; его нельзя разбить на коды отдельных символов.

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

Поясним работу метода на примере.

Пусть алфавит состоит из двух символов: «a» и «b» с вероятностями соответственно 3/4 и 1/4.

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

Построение интервала для сообщения «АВГ…».

Выполним алгоритм для цепочки «aaba»

Таблица 3. Построение арифметического кода

Просмотренная цепочка	Интервал
«»	(0, 1) = (0, 1)
«a»	(0, 3/4) = (0, 0.11)
«aa»	(0, 9/16) = (0, 0.1001)
«aab»	(27/64, 36/64) = (0.011011, 0.100100)
«aaba»	(108/256, 135/256) = (0.01101100, 0.10000111)

На первом шаге мы берем первые 3/4 интервала, соответствующие символу «а», затем оставляем от него еще только 3/4. После третьего шага от предыдущего интервала останется его правая четверть в соответствии с положением и вероятностью символа «b». И, наконец, на четвертом шаге мы оставляем лишь первые 3/4 от результата. Это и есть интервал, которому принадлежит исходное сообщение.

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

Арифметический декодер работает синхронно с кодером: начав с интервала (0, 1), он последовательно определяет символы входной цепочки. В частности, в нашем случае он вначале разделит (пропорционально частотам символов) интервал (0, 1) на (0, 0.11) и (0.11, 1). Поскольку число 0.1 (переданный кодером код цепочки «aaba») находится в первом из них, можно получить первый символ: «a». Затем делим первый подинтервал (0, 0.11) на (0, 0.1001) и (0.1001, 0.1100) (пропорционально частотам символов). Опять выбираем первый, так как 0 < 0.1 < 0.1001. Продолжая этот процесс, мы однозначно декодируем все четыре символа.

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

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

Работа: в реальном масштабе времени и в потоке (кроме статического).

Основное применение: универсальный, сжатие текстов. Используется в архиваторе LZARI, для сжатия изображений (JPEG).



Заключение

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

Сжатие данных используется очень широко. Можно сказать, почти везде. Например, документы PDF, как правило, содержат сжатую информацию. Довольно много исполняемых файлов EXE сжаты специальными упаковщиками. Всевозможные мультимедийные файлы (GIF, JPG, MP3, MPG) являются своеобразными архивами.

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

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

Список использованных источников

1. Ахметов А.Н., Борзенко А.В. Современный персональный компьютер. - М.: Компьютер Пресс, 2003. - 317 с.

2. Банк В.Р., Зверев В.С. Информационные системы в экономике: Учебник. - 2003 г.

3. Борзенко А.В. IBMPC: устройство, ремонт, модернизация. - М., Компьютер Пресс, 1996. - 344 с.

4. Зверев В.С. Информатика: Учебное пособие для студентов вузов. Астрахань, 2003.

5. Компьютер Пресс // М.: Компьютер Пресс - 2002.

6. Компьютерра // М.: ООО «Пресса» - 2001.

7. Кузнецов Е.Ю., Осман В.М. Персональные компьютеры и программируемые микрокалькуляторы: Учеб. пособие для ВТУЗов - М.: Высш. шк. -1991 г. 160 с.

8. Фигурнов А.Э. IBM-РС для пользователя. М., 1998.

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

...