§ Принцип работы

По правде говоря, я раньше думал, что этот алгоритм компрессии и декомпрессии крайне сложен и я никогда не смогу его понять. На деле же все оказалось наоборот, довольно-таки просто. Я не скажу, что LZW-компрессор хорошо сжимает данные, но он довольно простой в реализации, конкретно декомпрессор (да и компрессор тоже не сильно сложный). Это его достоинство. Недостатков же довольно много — и не очень хорошая компрессия, и наличие довольно крупного словаря.
Суть любого компрессора — это находить повторяющиеся последовательности ранее и вставлять вместо них более короткие ссылки. Простой пример CAT CAT CAT. Здесь вместо двух других CAT можно поставить номера, например CAT $1 $1.
Но это пример, на самом деле, алгоритм работает немного иначе. Он оперирует словарем всегда. Буду разбирать на примере строки "LALATLAT" — специально сделал так, чтобы было и покороче и более-менее понятно.

§ Объяснение по шагам

Шаг 1: Словарь у нас пустой, и первая буква "L". Её же и выдаем, и в словарь добавляется первая последовательность "LA" — потому что в словарь можно добавить только минимум 2х символьные последовательности. Почему добавляется "LA" все просто, поскольку после буквы L идет буква A — следующая за буквой L. В словаре есть 256-й код под названием "LA". Первые 0..255 кодов обозначают одиночную букву.
Шаг 2: Теперь добавляется символ "A", также, ранее в словаре не было похожих последовательностей, там только "LA", и потому добавляется еще раз в словарь, уже под номером 257, и это будет "AL".
Шаг 3: А вот теперь надо добавить "LA" — поскольку ранее в словаре такая последовательность была, потому вместо L пишем код 256 - потому что под этим кодом находится "LA". Его и добавляем. Но это еще не все! В словарь теперь добавляется трехбуквенный код "LAT", потому что если, начиная с 3-й позиции взять 3 буквы, то получится "LAT". Это крайне важно! В словарь добавляется всякий раз, либо после одиночной буквы, либо после добавления последовательности. Так что теперь под номером 258 находится слово "LAT".
Шаг 4: Буква "T" выводится в поток, и в словарь под номером 259 добавляется последовательность "TL".
Шаг 5: Далее идет "LAT", который в словаре у нас уже есть под номером 258. Это число выдается на выход. Поскольку более нечего сжимать далее, то декомпрессия заканчивается. Конечно, под номером 260 добавляется "LAT" и еще 4-й символ будет пустой, ибо конец потока.

§ Примеры декомпрессии

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

01234567
LALATLAT
^------- Выдается "L", в словаре 256: "LA"   (позиция 0, длина 2)
 ^------ Выдается "A,  в словаре 257: "AL"   (позиция 1, длина 2)
  ^----- Выдается 256, в словаре 258: "LAT"  (2, 3)
    ^--- Выдается "T", в словаре 259: "TL"   (4, 2)
     ^-- Выдается 258, в словаре 270: "LAT " (5, 4)

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

0123456
AAAAAAA
^------ Выдать "A", в словарь 256: "AA"   (0, 2)
 ^----- Выдать 256, в словарь 257: "AAA"  (1, 3)
   ^--- Выдать 257, в словарь 258: "AAAA" (3, 4)
      ^ Выдать "A", потому что последний символ

Вот что интересно в этом примере. Дело в том, что здесь представлен случай, когда выдаются символы, которых еще нет, но которые появляются по мере выгрузки в поток. К примеру, когда выдается символ 256 на экран, то второго "А" из "АА" еще нет, но он появляется как только копируется первый "А". Также и с остальными. Так что тут тоже не лишено все особой хитрости при сжатии.
На самом деле, это все получается естественным образом, так что ничего удивительного.
Примеров много не бывает:

0123456789
BATBATBATB
^--------- Выдать "B", 256: "BA" (0,2)
 ^-------- Выдать "A", 257: "AT" (1,2)
  ^------- Выдать "T", 258: "TB" (2,2)
   ^------ Выдать 256, 259: "BAT" (3,3)
     ^---- Выдать 258, 260: "TBA" (5,3)
       ^-- Выдать 257, 261: "ATB" (7,3)
         ^ Выдать "B", закончить

Как это реализовать? Я уже написал код на ассемблере ранее для этой цели. Здесь я думаю, что применение кода на асме совершенно нецелесообразно. Да и вообще лучше избежать лишний раз использование кода в этой статье.

§ Битовый поток

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

0 1 2 3 4 5 6 7 8 9 - номер бита
0 1 1 1 0 1 0 1 1 0 - значение бита

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

7 6 5 4 3 2 1 0 | 15 14 13 12 11 10 9 8 | -- номера битов
1 0 1 0 1 1 1 0 | x  x  x  x  x  x  0 1 | -- значение битов

Это лишь вопрос наглядности. Если развернуть последовательность байтов в битовую "ленту", как сверху, то будет вполне себе наглядно.
Теперь вопрос? Как например, извлечь 3 бита, начиная с бита 6? Ответ был бы простой — сначала надо отсчитать 6 бит, и получить 3 бита. Для компьютера это не так просто.
Дело в том, что биты 6,7 и 8 находятся в разных байтах. Значит, надо прочесть аж 2 байта за один раз и сдвинуть на 6 битов вправо, чтобы бит 6,7 и 8 оказались в позициях 0,1 и 2. Следующий шаг это срезание всех остальных битов, что делается просто командой AND, и поскольку надо 3 бита, то будет AND 7 или AND 111b в двоичном виде.
Что делать, если надо прочесть 4 бита, начиная с 11?
Для того, чтобы это сделать, для начала, надо прочитать байт номер 1, а не 0. Потом сдвинуть на 3 бита вправо, чтобы выровнять биты на начало и оставить через команду AND 1111b значащие биты.
В общем-то, на этом и всё, получается.