1
правка
Изменения
м
[[Файл:LZW-img.jpg|right|Работа алгоритма LZW]]
*''' ''' Итак, кодировщик заносит первую <tex>a</tex> в строку, ищет и находит <tex>a</tex> в словаре под номером <tex>\langle0\rangle</tex>. Добавляет в строку следующую <tex>a</tex>, находит, что <tex>aa</tex> нет в словаре. Тогда он добавляет запись <tex>\langle5\rangle</tex>: <tex>aa</tex> в словарь и выводит метку <tex>\langle0\rangle</tex> (<tex>a</tex>) в выходной поток. *''' '''Далее строка инициализируется второй <tex>a</tex>, то есть принимает вид <tex>a?</tex> вводится третья <tex>a</tex>, строка вновь равна <tex>aa</tex>, которая теперь имеется в словаре. *''' '''Если появляется четвертая <tex>a</tex>, то строка <tex>aa?</tex> равна <tex>aaa</tex>, которой нет в словаре. Словарь пополняется этой строкой, а на выход идет метка <tex>\langle5\rangle</tex> (<tex>aa</tex>). *''' '''После этого строка инициализируется третьей <tex>a</tex>, и т.д. и т.п. Дальнейший процесс вполне ясен.
Исправлено закодированное сообщение (не хватало закодированной записи второго нуля)
Для декодирования на вход подается только закодированный текст, поскольку алгоритм LZW может воссоздать соответствующую таблицу преобразования непосредственно по закодированному тексту.
Алгоритм генерирует однозначно декодируемый код за счет того, что каждый раз, когда генерируется новый код, новая строка добавляется в таблицу строк. LZW постоянно проверяет, является ли строка уже известной, и, если так, выводит существующий код без генерации нового.
Таким образом, каждая строка будет храниться в единственном экземпляре и иметь свой уникальный номер. Следовательно, при декодировании при получении во время получения нового кода генерируется новая строка, а при получении уже известного, строка извлекается из словаря.
== Алгоритм ==
Больше в таблице не будет других кодов, обладающих этим свойством.<br>
По мере роста словаря, размер групп должен расти, с тем, чтобы учесть новые элементы. <tex>8</tex>-битные группы дают <tex>256</tex> возможных комбинации бит, поэтому, когда в словаре появится <tex>256</tex>-е слово, алгоритм должен перейти к <tex>9</tex>-битным группам. При появлении <tex>512</tex>-ого слова произойдет переход к <tex>10</tex>-битным группам, что дает возможность запоминать уже <tex>1024</tex> слова и т.д.
В нашем примере алгоритму заранее известно о том, что будет использоваться всего <tex>5</tex> различных символов, следовательно, для их хранения будет использоваться минимальное количество бит, позволяющее нам их запомнить, то есть <tex>3</tex> (<tex>8</tex> различных комбинаций).
|}
Итак, мы получаем закодированное сообщение <tex>0 1 0 2 5 0 3 9 8 6 4</tex> и его битовый эквивалент <tex>000 001 000 010 0101 0000 0011 1001 1000 0110 0100</tex>.
Каждый символ исходного сообщения был закодирован группой из трех бит, сообщение содержало <tex>16</tex> символов, следовательно длина сообщения составляла <tex>3 \cdot 16 = 48</tex> бит.
Оказывается, это возможно, если оговорить некоторые действия:
Мы знаем, что для каждого кода надо добавлять в таблицу строку, состоящую из уже присутствующей там строки и символа, с которого начинается следующая строка в потоке.
*''' ''' Пусть словарь состоит из слов : <tex>a, b, c, d, e</tex>. Будем кодировать стоку <tex> aaaaaaaaaa </tex>
*''' ''' Итак, кодировщик заносит первую <tex>a</tex> в строку, ищет и находит <tex>a</tex> в словаре под номером <tex>\langle0\rangle</tex>. Добавляет в строку следующую <tex>a</tex>, находит, что <tex>aa</tex> нет в словаре. Тогда он добавляет запись <tex>\langle5\rangle</tex>: <tex>aa</tex> в словарь и выводит метку <tex>\langle0\rangle</tex> (<tex>a</tex>) в выходной поток.
*''' '''Далее строка инициализируется второй <tex>a</tex>, то есть принимает вид <tex>a?</tex> вводится третья <tex>a</tex>, строка вновь равна <tex>aa</tex>, которая теперь имеется в словаре.
*''' '''Если появляется четвертая <tex>a</tex>, то строка <tex>aa?</tex> равна <tex>aaa</tex>, которой нет в словаре. Словарь пополняется этой строкой, а на выход идет метка <tex>\langle5\rangle</tex> (<tex>aa</tex>).
*''' '''После этого строка инициализируется третьей <tex>a</tex>, и т.д. и т.п. Дальнейший процесс вполне ясен.
[[Файл:LZW-img.jpg|center|Работа алгоритма LZW]]
{| class="wikitable" border = 1, style="float:right; text-align: center; margin-left: 5auto; margin-right: 5auto;"
|- bgcolor=#EEEEEE
! Слово !! Номер в словаре
| e || <tex>\langle4\rangle</tex>
|}
{| class="wikitable" border =1, style="text-align: center; margin-left: auto; margin-right: auto;"
|- bgcolor =#EEEEEE
