Программные методы защиты информации. Часть 1. Крыжановская Ю.А. - 27 стр.

                                      27
      В качестве кода можно взять любое число из интервала, полученного на
шаге 4, например, 0,43.
      Алгоритм декодирования работает аналогично кодирующему: на входе
0,43 и идет разбиение интервала.
      Продолжая этот процесс, можно однозначно декодировать все четыре сим-
вола. Для того чтобы декодирующий алгоритм мог определить конец цепочки,
можно либо передавать ее длину отдельно, либо добавить к алфавиту дополни-
тельный уникальный символ - "конец цепочки".
Алгоритм Лемпеля-Зива-Велча (Lempel-Ziv-Welch - LZW)
      Данный алгоритм отличают высокая скорость работы как при упаковке, так
и при распаковке, достаточно скромные требования к памяти и простая аппарат-
ная реализация.
      Недостаток - низкая степень сжатия по сравнению со схемой двухступен-
чатого кодирования.
      Предположим, что у нас имеется словарь, хранящий строки текста и со-
держащий порядка от 2-х до 8-ми тысяч пронумерованных гнезд. Запишем в пер-
вые 256 гнезд строки, состоящие из одного символа, номер которого равен номе-
ру гнезда.
      Алгоритм просматривает входной поток, разбивая его на подстроки и до-
бавляя новые гнезда в конец словаря. Прочитаем несколько символов в строку s
и найдем в словаре строку t - самый длинный префикс s.
      Пусть он найден в гнезде с номером n. Выведем число n в выходной поток,
переместим указатель входного потока на length(t) символов вперед и добавим в
словарь новое гнездо, содержащее строку t+c, где с - очередной символ на входе
(сразу после t). Алгоритм преобразует поток символов на входе в поток индексов
ячеек словаря на выходе.
      При практической реализации этого алгоритма следует учесть, что любое
гнездо словаря, кроме самых первых, содержащих одно-символьные цепочки,
хранит копию некоторого другого гнезда, к которой в конец приписан один сим-
вол. Потому можно обойтись простой списочной структурой с одной связью.
Пример 23: ABCABCABCABCABCABC - 1 2 3 4 6 5 7 7 7
  1      2       3     4      5     6     7      8       9
  А      В       С    АВ     ВС    СА АВС САВ ВСА
      Применительно к графическим изображениям алгоритм LZW реализован в
форматах GIF и TIFF. Не ориентирован на 8-битные изображения, построенные на
компьютере. Сжимает за счет одинаковых подцепочек в потоке. Ситуация, когда
алгоритм увеличивает изображение, встречается крайне редко. LZW универсален
— именно его варианты используются в обычных архиваторах.
Двухступенчатое кодирование. Алгоритм Лемпеля-Зива
     Гораздо большей степени сжатия можно добиться при выделении из вход-
ного потока повторяющихся цепочек - блоков и кодирования ссылок на эти це-
почки с построением хеш-таблиц от первого до n-го уровня.
     Метод, о котором и пойдет речь, принадлежит Лемпелю и Зиву и обычно
называется LZ-compression или LZ77 (названный так по году своего опубликова-