Сети ЭВМ и телекоммуникации. Брейман А.Д. - 41 стр.

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

6.3.1. Алгоритм RLE

      Самый простой из словарных методов – RLE (Run Length Encoding, коди-
рование переменной длины) умеет сжимать данные, в которых есть последова-
тельности повторяющихся байтов. Упакованные RLE данные состоят из управ-
ляющих байтов, за которыми следуют байты данных. Если старший бит управ-
ляющего байта равен 0, то следующие байты (в количестве, записанном в семи
младших битах управляющего байта) при упаковке не изменялись. Если стар-
ший бит равен 1, то следующий байт нужно повторить столько раз, какое число
записано в остальных разрядах управляющего байта.
      Например, исходная последовательность
      00000000 00000000 00000000 00000000 11001100 10111111 10111011
будет закодирована в следующем виде (выделены управляющие байты):
      10000100 00000000 00000011 11001100 10111111 10111011.
      А, например, данные, состоящие из сорока нулевых байтов, будут зако-
дированы всего двумя байтами: 1010 1000 00000000.

6.3.2. Алгоритм Лемпела-Зива

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