Современные методы хранения информации в сжатом виде(методы неискажающего сжатия и восстановления информации)

 

Министерство транспорта Российской Федерации

Омский государственный  университет путей сообщения 

Кафедра «Автоматика и  Системы управления»

 

 

 

 

 

 

 

 

 

Тематический реферат

по дисциплине «ИСВВТ»

 

 

Современные методы хранения информации в сжатом виде(методы неискажающего сжатия и восстановления информации)

ИНМВ.801000.000 Д

 

 

 

 

 

 

 

                                               Студент гр. 29 З

____________К.А. Аненков

                                                        «__»________2012 г.

 

 

                                                                     Руководитель – преподаватель

                                            кафедры АиСУ

____________Н.Ю.Афоничев

                                                      «__»________2012 г.

 

 

 

 

 

 

 

Омск  2012 

Содержание

Введение 4

1 Классификация  методов сжатия 5

2 Критерии  оценки методов сжатия 6

3 Надежность  программ и сложность алгоритмов 7

4 Современные  методы сжатия 8

4.1 Алгоритмы  статистического моделирования 8

4.2 Алгоритмы  словарного сжатия 8

4.3 Алгоритмы  сжатия сортировкой блоков 9

4.4 Методы  энтропийного кодирования 9

4.5 Префиксные  коды 9

4.6 Арифметические  коды 10

5 Обзор алгоритмов  сжатия без потерь 11

5.1 RLE 11

5.2 Алгоритмы  семейства LZ 12

5.3 Алгоритм LZ77 13

5.4 Алгоритм  LZSS 15

5.5 Алгоритм LZ78 17

5.6 Алгоритм  LZW 19

5.7 Алгоритм  LZM 25

5.8 Алгоритм  LZB 27

5.9 Алгоритм  LZH 28

5.10 Алгоритм  LZC 28

5.11 Алгоритм  LZT 28

5.12 Алгоритм  LZMV 29

5.13 Алгоритм  LZJ 29

5.14 Алгоритм  LZFG 29

5.15 Унарное  кодирование 30

5.16 Метод  Хафмана 31

5.16.1 Идея  метода 31

5.16.2 Алгоритм 31

5.16.3 Кодирование  Хаффмана 32

5.16.4 Адаптивное  сжатие Хаффмана 33

5.16.5 Адаптивное  кодирование Хаффмана 34

5.16.6 Проблемы  адаптивного кодирования 35

5.16.7 Фиксированный  алгоритм Хаффмана 36

5.16.8 Алгоритм  стопки книг 36

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

5.18 Вероятностное  сжатие 39

Заключение 40

Библиографический список 41

 

 

Введение

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

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

 

1 Классификация методов сжатия

Методы сжатия данных можно разделить  на два типа:

1. неискажающие (loseless) методы сжатия (называемые также методами сжатия без потерь) гарантируют, что декодированные данные будут в точности совпадать с исходными;
2. искажающие (lossy) методы сжатия (называемые также методами сжатия с потерями) могут искажать исходные данные, например за счет удаления несущественной части данных, после чего полное восстановление невозможно.

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

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

Кроме того, можно выделить:

• методы сжатия общего назначения (general-purpose), которые не зависят от физической природы входных данных и, как правило, ориентированы на сжатие текстов, исполняемых программ, объектных модулей и библиотек и т. д., т. е. данных, которые в основном и хранятся в ЭВМ;
• специальные (special) методы сжатия, которые ориентированы на сжатие данных известной природы, например, звука, изображений и т. д. И за счет знания специфических особенностей сжимаемых данных достигают существенно лучшего качества и/или скорости сжатия, чем при использовании методов общего назначения.

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

 

     

 

2 Критерии оценки методов сжатия

Основными свойствами какого-либо алгоритма  сжатия данных являются:

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

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

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

Понятно, что критерии оценки методов  сжатия с практической точки зрения сильно зависят от предполагаемой области  применения. Например, при использовании  сжатия в системах реального времени  необходимо обеспечить высокую скорость кодирования и декодирования; для  встроенных систем критический параметр – объем требуемой памяти; для  систем долговременного хранения данных – качество сжатия и/или скорость декодирования и т. д.

 

3 Надежность программ и сложность алгоритмов

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4 Современные методы сжатия

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

4.1 Алгоритмы статистического моделирования

Наилучшие по качеству сжатия алгоритмы статистического моделирования источников Маркова семейств PPM (от англ. Prediction by Partial Matching), DMC (от англ. Dynamic Markov Compression), ACB (от англ. Associative Coding by Buyanovski) предсказывают вероятность появления следующего символа на основе анализа частоты появления различных последовательностей символов в ранее закодированной части сообщения.

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

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

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

4.2 Алгоритмы словарного сжатия

Алгоритмы словарного сжатия заменяют подстроки кодируемой последовательности символов ссылками в словарь на идентичные подстроки. С практической точки  зрения наилучшими представляются алгоритмы  семейства LZ (впервые предложенные Лемпелом и Зивом в 1977г.), которые заменяют начало не просмотренной части кодируемого сообщения ссылкой на самое длинное вхождение идентичной подстроки в уже закодированной части.

Обычно для ускорения поиска совпадающих подстрок и ограничения  объема требуемой памяти область  поиска ограничивается определенным количеством  последних символов закодированной части: такая модификация LZ77 называется LZ77 со скользящим окном (LZ77 with sliding window).

Алгоритмы семейства LZ в 1.3-1.7 раза уступают методам статистического моделирования по качеству сжатия, однако обладают очень высокой скоростью кодирования при сравнительно небольшом объеме требуемой памяти.

Огромное преимущество алгоритмов семейства LZ – чрезвычайно высокая скорость декодирования. Это позволяет применять их в тех случаях, когда декодирование осуществляется гораздо чаще кодирования или скорость декодирования очень важна (например, при хранении данных на CD-ROM, в файловых системах со сжатием и т. д.).

Большая часть современных промышленных систем сжатия данных построено на основе различных вариантов алгоритма LZ77, в течение многих лет заслуженно считавшихся наилучшими по соотношению скорости и качества сжатия.

4.3 Алгоритмы сжатия сортировкой блоков

Алгоритмы сжатия сортировкой блоков семейства BWT/BS, разработанные в 1994г. Барроузом и Уилером, разбивают кодируемую последовательность на блоки символов, представляют (обратимым образом) символы каждого блока так, что появляется много повторений одного и того же символа, а затем сжимают преобразованные данные каким-либо достаточно простым способом.

По качеству сжатия они приближаются к методам статистического моделирования (уступая им в 1.2-1.3 раза), а по скорости – к алгоритмам семейства LZ, при меньшем по сравнению с методами статистического моделирования объеме требуемой памяти; скорость декодирования также достаточно высока.

4.4 Методы энтропийного кодирования

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

Такие методы кодирования известны с конца 40-х гг. и хорошо изучены. Их можно разбить на два больших  класса: префиксные (методы Хаффмана, Шеннона, Шеннона-Фано) и арифметические.

4.5 Префиксные коды

Префиксные коды называются так  потому, что ни одно кодовое слово  не является полным началом (т. е. префиксом) никакого другого слова, что гарантирует  однозначность декодирования.

Известно много способов построения префиксных кодов: коды Шеннона и  Шеннона-Фано почти идеальны, а код Хаффмана – оптимален среди префиксных кодов.

Так как длина каждого кодового слова выражается целым числом битов, то префиксные коды неэффективны на алфавитах  малой мощности (2-8 символов) или  при наличии символов с очень  большой (более 30-50%) вероятностью появления  и по качеству сжатия могут уступать арифметическим.

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

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

4.6 Арифметические  коды

Арифметические коды не ставят явного соответствия между символами и  кодовыми словами, они основаны на других принципах.

Качество арифметического кодирования лучше, чем у посимвольного префиксного кодирования, и близко к теоретическому минимуму и при малой мощности алфавита, и при очень неравномерном распределении вероятностей появления символов.

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

Арифметические коды обычно применяются  в сочетании с методами статистического моделирования для кодирования символов в соответствии с предсказанными вероятностями.

 

5 Обзор алгоритмов сжатия без потерь

5.1 RLE

Групповое кодирование – Run Length Encoding (RLE) – один из самых старых и самых простых алгоритмов архивации. Сжатие в RLE происходит за счет замены цепочек одинаковых байт на пары "счетчик, значение". Лучший, средний и худший коэффициенты сжатия – 1/32, 1/2, 2/1.

Одна из реализаций алгоритма такова: ищут наименее часто встречающийся  байт, называют его префиксом и  делают замены цепочек одинаковых символов на тройки "префикс, счетчик, значение". Если же этот байт встретичается в исходном файле один или два раза подряд, то его заменяют на пару "префикс, 1" или "префикс, 2". Остается одна неиспользованная пара "префикс, 0", которую можно использовать как признак конца упакованных данных.

При кодировании *.exe-файлов можно искать и упаковывать последовательности вида AxAyAzAwAt..., которые часто встречаются в ресурсах (строки в кодировке Unicode).

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

Кодер RLE

ТекущийСимвол := ДайОчереднойСимвол()

ТекущееСостояние := НЕТ_ПОВТОРОВ

ТекущаяДлина := 0

Пока ТекущийСимвол <> EOF

  Буфер := ДайОчереднойСимвол()

  Если Буфер = ТекущийСимвол

    Если ТекущееСостояние = НЕТ_ПОВТОРОВ

      Выдать  ( НЕТ_ПОВТОРОВ )

      Выдать  ( ТекущаяДлина )

      Выдать  ( ТекущаяДлина предыдущих символов сообщения )

      ТекущаяДлина := 2

      ТекущееСостояние := ПОВТОРЫ

    Иначе

      ТекущаяДлина := ТекущаяДлина + 1

    Конец если 

  Иначе

    Если ТекущееСостояние = НЕТ_ПОВТОРОВ

      ТекущаяДлина := ТекущаяДлина + 1 Иначе

      Выдать  ( ПОВТОРЫ )

      Выдать  ( ТекущаяДлина )

      Выдать  ( ТекущийСимвол )

      ТекущаяДлина := 1

      ТекущееСостояние := НЕТ_ПОВТОРОВ

    Конец если 

  Конец если

  ТекущийСимвол := Буфер

Конец пока

Декодер RLE

ТекущийКод := ДайКодФрагмента()

Пока ТекущийКод <> EOF

  ТекущаяДлина := ДайДлинуФрагмента()

  Если ТекущийКод = НЕТ_ПОВТОРОВ

    Выдать ( ТекущаяДлина, следующих символов сообщения )

  Иначе

    Выдать ( ТекущаяДлина, ДайОчереднойСимвол() )

  Конец если

  ТекущийКод := ДайКодФрагмента()

Конец пока

К положительным сторонам алгоритма, можно отнести то, что он не требует  дополнительной памяти при работе, и быстро выполняется. Алгоритм применяется  в форматах РСХ, TIFF, ВМР. Интересная особенность группового кодирования  в PCX заключается в том, что степень архивации для некоторых изображений может быть существенно повышена всего лишь за счет изменения порядка цветов в палитре изображения.

5.2 Алгоритмы семейства  LZ

Алгоритм LZ лежит в основе таких  известных программ-архиваторов, как PKZIP, LHA, ARJ, Stacker, Dblspace и многих других. Своим появлением он обязан двум исследователям из Израиля: Якобу Зиву и Абрахаму Лемпелу (Jacob Ziv & Abraham Lempel). В 1977 году они опубликовали работу. Ее появление ознаменовало начало новой эры в сжатии информации. Практически все современные компьютерные программы-архиваторы используют ту или иную модификацию алгоритма LZ. Одной из причин широкого распространения алгоритма LZ стала его исключительная простота.

Основная идея алгоритма

Вспомним первое четверостишье  бессмертного “Евгения Онегина”:

Мой дядя, самых честных  правил,  Когда не в шутку занемог,  Он уважать себя заставил  И лучше выдумать не мог.  Его пример...

Обратите внимание на то, что Пушкин избегает повторного использования  подстроки “Мой дядя”. Сначала вместо нее используется местоимение “он”, затем — “его”. При этом информативность  всего сообщения нисколько не снижается, а его объем уменьшается. Очевидно, что нет смысла полностью  повторять однажды сказанную  в разговоре фразу несколько  раз. То же самое относится и к  компьютерной информации.

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

5.3 Алгоритм LZ77

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

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

Рассмотрим работу LZ77 на примере  сообщения, приведенного в таблице:

Скользящее окно в алгоритме LZ77
for (i=0; i<MAX-1; i++)\r for (j=i+l; j	<MAX; j++)\    r
Обработанная часть сообщения (словарь)	Буфер

Алгоритм LZ77 выдает коды, состоящие  из трех элементов:

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

В нашем примере, просматривая словарь, алгоритм обнаружит, что совпадающей  подстрокой будет “<МАХ”, в словаре она расположена по смещению 14, имеет длину 4 символа, а следующим символом в буфере является ';'. Таким образом, выходной код будет представлять собой тройку <14, 4, ';'>.

После этого алгоритм сдвигает все  содержимое окна на длину совпадающей  подстроки +1 символ влево и одновременно втягивает соответствующее количество очередных символов сообщения.

Если совпадение не обнаружено, то алгоритм выдает код <0, 0, первый символ в буфере> и продолжает свою работу. Хотя такое решение неэффективно, оно гарантирует, что алгоритм сможет закодировать любое сообщение.

УПРОЩЕННЫЙ АЛГОРИТМ LZ77

пока (буфер не пуст)

  найти наиболее длинное  соответствие (позиция_начала, длина)

  в обработанной_части_сообщения и в буфере;

  если (длина > минимальной_длины ), то

    вывести в кодированные  данные пару (позиция _начала, длина);

  иначе

    вывести в кодированные  данные первый символ буфера;

  изменить указатель  на начало буфера и продолжить.

Декодирование в LZ77 еще проще, так  как не нужно осуществлять поиск в словаре.

Проблемы LZ77

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

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

Помимо проблем с быстродействием, у алгоритма LZ77 возникают проблемы с самим сжатием. Они появляются, когда кодер не может найти совпадающую подстроку в словаре и выдает стандартный 3-компонентный код, пытаясь закодировать один символ. Если словарь имеет длину 4Кб, а буфер — 16 байтов, то код <0, 0, символ> будет занимать 3 байта. Кодирование одного байта в три имеет мало общего со сжатием и существенно понижает производительность алгоритма.

5.4 Алгоритм LZSS

Алгоритм LZSS получил свое название по именам своих разработчиков: Lempel, Ziv, Storer, Szimansky. Существенный вклад в развитие алгоритма внес Т. С. Bell. LZSS является развитием LZ77 и стремится избавиться от недостатков своего предшественника. LZSS отличается от LZ77 тем, как поддерживается скользящее окно и какие коды выдает компрессор.

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

Кодер LZSS использует однобитовый префикс, для того чтобы отличать незакодированные символы от пар <смещение, длина>. Такие коды позволяют получить существенный выигрыш в размере сжатого сообщения

Модель данных

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

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

Кодер LZSS

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

Основной цикл работы

Алгоритм последовательно выполняет  следующие действия:

1. кодирует содержимое буфера;
2. считывает очередные символы в буфер, удаляя при необходимости наиболее “старые” строки из словаря;
3. вставляет в дерево новые строки, соответствующие считанным символам.

Завершение работы 
Для того чтобы декодер смог вовремя остановиться, декодируя сжатое сообщение, кодер помещает в сжатый файл специальный символ “КОНЕЦ ФАЙЛА” после того, как он обработал все символы сообщения.