Изменения
→Описание
Процесс сжатия выглядит следующим образом: последовательно считываются символы входного потока и происходит проверка, существует ли в созданной таблице строк такая строка. Если такая строка существует, считывается следующий символ, а если строка не существует, в поток заносится код для предыдущей найденной строки, строка заносится в таблицу, а поиск начинается снова.
Например, если сжимают байтовые данные (текст), то строк в таблице окажется <tex>256</tex> (от <tex>"0"</tex> до <tex>"255"</tex>). Если используется <tex>10</tex>-битный код, то под коды для строк остаются значения в диапазоне от <tex>256</tex> до <tex>1023</<tex>. Новые строки формируют таблицу последовательно, т. е. можно считать индекс строки ее кодом.
Для декодирования на вход подается только закодированный текст, поскольку алгоритм LZW может воссоздать соответствующую таблицу преобразования непосредственно по закодированному тексту.
=== Кодирование ===
* Начало.
* ''' Шаг <tex>1</tex>. ''' Все возможные символы заносятся в словарь. Во входную фразу <tex>X</tex> заносится первый символ сообщения.* ''' Шаг <tex>2</tex>. ''' Считать очередной символ <tex>Y</tex> из сообщения.* ''' Шаг <tex>3</tex>. ''' Если <tex>Y</tex> {{---}} это символ конца сообщения, то выдать код для <tex>X</tex>, иначе: ** Если фраза <tex>XY</tex> уже имеется в словаре, то присвоить входной фразе значение <tex>XY</tex> и перейти к Шагу <tex>2</tex>, ** Иначе выдать код для входной фразы <tex>X</tex>, добавить <tex>XY</tex> в словарь и присвоить входной фразе значение <tex>Y</tex>. Перейти к Шагу <tex>2</tex>.
* Конец.
=== Декодирование ===
* Начало.
* ''' Шаг <tex>1</tex>. ''' Все возможные символы заносятся в словарь. Во входную фразу <tex>X</tex> заносится первый код декодируемого сообщения.* ''' Шаг <tex>2</tex>. ''' Считать очередной код <tex>Y</tex> из сообщения.* ''' Шаг <tex>3</tex>. ''' Если <tex>Y</tex> {{---}} это конец сообщения, то выдать символ, соответствующий коду <tex>X</tex>, иначе:
** Если фразы под кодом <tex>XY</tex> нет в словаре, вывести фразу, соответствующую коду <tex>X</tex>, а фразу с кодом <tex>XY</tex> занести в словарь.
** Иначе присвоить входной фразе код <tex>XY</tex> и перейти к Шагу <tex>2</tex>.
* Конец.
