Тема: «Архивирование файлов алгоритмом Зива-Лемпеля-Велча»

Расчетно-графическая работа №9

1 Теоретическая часть

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

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

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

Алгоритм Зива – Лемпеля - Велча (LZW) относится к алгоритмам сжатия без потерь.

История этого алгоритма начинается с опубликования в мае 1977 г. Дж. Зивом и А. Лемпелем статьи в журнале "Информационные теории". В последствии этот алгоритм был доработан А. Велчем, и в окончательном варианте отражен в статье "IEEE Computer" в июне 1984. В этой статье описывались подробности алгоритма и некоторые общие проблемы, с которыми можно столкнуться при его реализации. Позже этот алгоритм получил название - LZW (Lempel - Ziv - Welch).

Алгоритм:

1. Создать словарь со всеми возможными односимвольными фразами. Принять за входную фразу w первый символ сообщения.

2. Считать очередной символ k из кодируемого сообщения. Если КОНЕЦ_СООБЩЕНИЯ, то выдать код и КОНЕЦ, иначе если фраза wk уже есть в словаре, присвоить входной фразе значение wk и перейти к п. 2, иначе выдать код w, добавить wk в словарь, присвоить входной фразе значение k и перейти к п 2.

Алгоритм LZW представляет собой алгоритм кодирования последовательностей неодинаковых символов. Возьмем для примера строку: "Объект TSortedCollection порожден от TCollection.".В данной строке слово "Collection" повторяется дважды. В этом слове 10 символов = 80 бит. Если мы заменим это слово, в выходном файле, во втором его включении, на ссылку на первое включение, то получим сжатие информации. Если рассматривать входной блок информации размером не более 64К и ограничить длину кодируемой строки в 256 символов, то, учитывая байт "флаг" получим, что строка из 80 бит, заменяется 8+16+8 = 32 бита. (1 байт – флаг, 2 байта – ссылка, 1 байт – длинна кодируемой последовательности). Если существуют повторяющиеся строки в файле, то они будут закодированы в таблицу. Очевидным преимуществом алгоритма является то, что нет необходимости включать таблицу кодировки в сжатый файл. Другой важной особенностью является то, что сжатие по алгоритму LZW является однопроходной операцией в противоположность алгоритму Хаффмана, которому требуется два прохода.

Плюс его: высокая степень сжатия.

Минус: сложность в реализации.

2 Примеры решения задачи сжатия сообщений

Сжать по алгоритму LZW следующие сообщения:

1) ONTOMEMEONTO

2) GOAWAYAWGO

3) EVERYOFEVEOF

3 Задание

Закодировать последовательность Ψ с помощью алгоритма LZW.

Ψ выбирать в соответствии с номером варианта.

Ниже даны варианты задания:

1) GHIOGHIOEBHGIOEJDIBHJGGHIOEBHG#

2) chessvariantisagamechessisVAR#

3) worldleadingsupplierleadsuppl#

4) securEtheofficialMatchsecurof#

5) recormesstansmitamessagerecO#

6) efforttocorrecttoeffortcorre#

7) abouttheFederaltheFedeaboutt#

8) textualandnumericaltextlandn#

9) AnnPustaybecameAnnPustbecam#

10) tookmeonamassivetookonamass#

11) DirectoroftheOfficectoroftherec#

12) shortfilmaboutshorfilmoutfilmAB#

13) whenwesaywhenweshenwsaywwe#

14) AswewillseeORASWESEEWILLORAS#

15) BetterlatethanneverBettthanlate#

16) CallaspadeaspadeCallspadeaCall#

17) EverydoghasitsdayEveryhasdayits#

18) PracticemakesperfectPractmakeper#

19) TwoheadsarebetterheadareTwobet#

20) LookatthebrightsideLooktheatside#

4 Содержание отчета

1) Условие задачи в соответствии с вариантом.

2) Начальный словарь.

3) Таблица кодирования сообщения:

Символ	Битовый код (на выходе)	Новая запись словаря

4) Записать код.

5) Подсчитать общую длину исходного сообщения и общую длину закодированного сообщения.

6) Выводы.

5 Список литературы

1) Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. ― М.: ДИАЛОГ-МИФИ, 2002. ― 384 с.

2) Сэломон Д. Сжатие данных, изображений и звука. ― М.: Техносфера, 2004. ― 368 с.

Дата добавления: 2014-10-31