Архиватор

Табл. 1.2. Кодирование LZVV для «alf_eats_alfalfa»

 1.3.5 Декодирование LZW

Для того, чтобы понять как работает декодер метода LZW, прежде всего еще раз напомним основные три шага, которые выполняет кодер каждый раз, делая очередную запись в выходной файл: (1) он заносит туда словарный указатель на строку I, (2) сохраняет строку Iх в следующей свободной позиции словаря и (3) инициализирует строку I символом x.

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

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

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

 1.3.6 Структура словаря LZW

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

Поэтому для  наших целей хорошим выбором  будет структура дерева, которая  уже использовалось в LZ78, при построении которого добавление новых строк  Iх делается добавлением всего одного нового символа х. Основная проблема состоит в том, что каждый узел дерева LZW может иметь много потомков (дерево не двоичное, а -ичное, где  - это объем алфавита). Представим себе узел буквы а с номером 97. В начале у него нет потомков, но если к дереву добавится строка ab, то у а появится один потомок. Если позже добавится новая строка, скажем, ае, то потомков станет два, и так далее. Значит, дерево следует сконструировать так, чтобы каждый узел в нем мог бы иметь любое число потомков, причем без резервирования дополнительной памяти для них заранее.

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

Разработка  программы ArchivatorLZW

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

 

2.1 Блок-схема алгоритма сжатия файла

 

 
2.2 Алгоритм

    Предполагается, что мы имеем словарь, в который  можем добавлять слова, и осуществлять их поиск (в словаре). При добавлении нового слова оно получает свой порядковый номер. Каждое слово уникально, т.е. в словаре не может быть двух одинаковых слов.

    Переменная  NewByte является символом (байтом), а переменная SrcWord – словом (в нашем случае это ANSIString) 

2.2.1Алгоритм сжатия файла.

    1. Очистим словарь; очистим SrcWord

2. Если исходный  файл полностью считан, то к  п. 6

3. Считать  в NewByte очередной символ из исходного файла

4. Если в  словаре есть слово SrcWord+NewByte

      тогда: присвоим SrcWord=SrcWord+NewByte.

Иначе:  запишем в выходной файл номер слова SrcWord;

      добавим в словарь слово SrcWord+NewByte;

      присвоим  SrcWord=NewByte.

5. Перейти  к п .2

6. Найдем в  словаре слово SrcWord и сохраним его номер в выходном файле

7. Конец

2.2.2Алгоритм распаковки файла

Примечание: NewCode – это не байт (в данном случае это тип Word)

    1. Очистим словарь; очистим SrcWord

2. Если исходный  файл полностью считан, то к  п. 16

3. Считаем  в NewCode данные из сжатого файла

4. Если NewCode – это просто символ

      тогда: перейдем к п. 5

      иначе: перейдем к п. 8

5. Запишем  NewCode в выходной файл

6. Если в  словаре есть слово SrcWord+NewByte

      тогда: присвоим SrcWord=SrcWord+NewByte.

      Иначе: добавим в словарь слово SrcWord+NewByte;

      присвоим  SrcWord=NewByte.

7. Перейдем  к п. 2

8. //NewCode – это номер слова в словаре

    Если  NewCode больше, чем слов в словаре //т.е. слова с таким номером в словаре еще вообще нет

    тогда: присвоим N=2;

      присвоим  NewByte=SrcWord[1];

      Если  в словаре есть слово SrcWord+NewByte

      тогда: присвоим SrcWord=SrcWord+NewByte.

      Иначе: добавим в словарь слово SrcWord+NewByte;

      присвоим  SrcWord=NewByte.

      Иначе: присвоим N=1

     9. Присвоим SaveWord=слово_из_словаря_с_номером(NewCode)

    10. Сохраним SaveWord в выходной файл

11. Запустим  цикл для i от N до длины слова SaveWord

12. Присвоим  NewByte=SaveWord[i]

13. Если в  словаре есть слово SrcWord+NewByte

      тогда: присвоим SrcWord=SrcWord+NewByte.

      Иначе: добавим в словарь слово SrcWord+NewByte;

      присвоим  SrcWord=NewByte.

14. Конец цикла

15. Перейдем  к п. 2

16. Конец

 

2.3 Создание интерфейса

Рис.2.1 Вид  окна работающей программы 

• На рис.2.1. Показан вид окна работающей программы.

 
 

    Программная форма имеет две кнопки:

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

2.4Программная реализация алгоритмов

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

    Перед вызовом функции сжатия необходимо создать два битовых файловых потока: для чтения – исходный файл; для записи – создаваемый (выходной) файл. Также перед непосредственным сжатием необходимо в выходном файле  сохранить имя и размер исходного  файла в прямом виде (не сжатом). Это  необходимо для последующей распаковки файла.

    Теперь  необходимо установить правила для  формата данных в сжатом файле. Выделим  для номера словаря 12 бит – получим 4096 возможных номеров (от 0 до 4095). Это  значит, что словарь может содержать  не больше 4096 слов. Для хранения же просто одного символа требуется 8 бит.

    Установим следующие правила:

    если  мы записываем в выходной файл просто один символ, то сначала запишем  один бит, равный нулю (“0”). Затем записываем сам символ (т.е. 8 его бит);

    если  мы записываем в выходной файл номер  слова из словаря, то сначала запишем  один байт, равный единице (“1”). Затем записываем номер слова из словаря (т.е. 12 его бит).

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

    Ниже  приведен листинг файла, в котором  выполняются основные функции по сжатию и распаковке файлов. 
 
 
 
 
 
 

2.5Пример

    Продемонстрируем  работу архиватора сжав произведение Гончарова И.А., “Обломов”.

    

      
 
 
 
 
 
 
 
 

2.6Листинг программы

    Файл Compressor.pas

unit Compressor;

interface

Function CompressFile(SrcFile, DestFile:String):Integer;

Function DeCompressFile(SrcFile, DestDir:String):Integer;

implementation

Uses  SysUtils, FileStreams, Dictionaries;

Var

  ReadStream:TFileReadStream;

  WriteStream:TFileWriteStream;

  Dic:TDictionary;

  NowBitsForDic:Byte;

Procedure WriteFileName(FileName:String; FSize:Integer);

Var

  i:Word;

Begin

  FileName:=ExtractFileName(FileName);

  WriteStream.Write(Length(FileName), 16);

  For i:=1 To Length(FileName) Do

    WriteStream.Write(Ord(FileName[i]), 8);

  WriteStream.Write(0, 8);

  i:=FSize And $FFFF;

  WriteStream.Write(i, 16);

  i:=FSize ShR 16;

  WriteStream.Write(i, 16);

  WriteStream.Write(0, 16);

End;

Procedure WriteSingleByte(Ch:Byte);

Begin

  WriteStream.WriteBit(0);

  WriteStream.Write(Ch, 8);

End;

Procedure WriteDoubleByte(Ch:Word; Cnt:Byte);

Begin

  WriteStream.WriteBit(1);

  WriteStream.Write(Ch, Cnt);

End;

Procedure WriteByDic(N:Integer);

Var

  Data:Word;

Begin

  If N<-256 Then Exit;

  Data:=Abs(N);

  If N<0 Then

  Begin

    Dec(Data);

    WriteSingleByte(Data);

  End

  Else Begin

    WriteDoubleByte(Data, NowBitsForDic);

  End;

End;

Function FindInDic(SingleWord:TSingleWord):Integer;

Begin

  If GetWordLength(SingleWord)=1 Then

  Begin

    Result:=-(Integer(SingleWord[1])+1);

    Exit;

  End;

  Result:=Dic.Find(SingleWord);