3622
правки
Изменения
Нет описания правки
* '''Шаг 1: '''Тогда, согласно изложенному выше алгоритму, мы добавим к изначально пустой строке <tex>a</tex> и проверим, есть ли строка <tex>a</tex> в таблице. Поскольку мы при инициализации занесли в таблицу все строки из одного символа, то строка <tex>a</tex> есть в таблице.
* '''Шаг 2: '''Далее мы читаем следующий символ <tex>b</tex> из входного потока и проверяем, есть ли строка <tex>ab</tex> в таблице. Такой строки в таблице пока нет.
Добавляем в таблицу <5tex>\langle5\rangle</tex> <tex>ab</tex>. В поток: <0tex>\langle0\rangle</tex>;* '''Шаг 3: '''<tex>ba</tex> — нет. В таблицу: <6tex>\langle6\rangle</tex> <tex>ba</tex>. В поток: <1tex>\langle1\rangle</tex>;* '''Шаг 4: '''<tex>ac</tex> — нет. В таблицу: <7tex>\langle7\rangle</tex> <tex>ac</tex>. В поток: <0tex>\langle0\rangle</tex>;* '''Шаг 5: '''<tex>ca</tex> — нет. В таблицу: <8tex>\langle8\rangle</tex> <tex>ca</tex>. В поток: <2tex>\langle2\rangle</tex>;* '''Шаг 6: '''<tex>ab</tex> — есть в таблице; <tex>aba</tex> — нет. В таблицу: <9tex>\langle9\rangle</tex> <tex>aba</tex>. В поток: <5tex>\langle5\rangle</tex>;* '''Шаг 7: '''<tex>ad</tex> — нет. В таблицу: <10tex>\langle10\rangle</tex> <tex>ad</tex>. В поток: <0tex>\langle0\rangle</tex>;* '''Шаг 8: '''<tex>da</tex> — нет. В таблицу: <11tex>\langle11\rangle</tex> <tex>da</tex>. В поток: <3tex>\langle3\rangle</tex>;* '''Шаг 9: '''<tex>aba</tex> — есть в таблице; <tex>abac</tex> — нет. В таблицу: <12tex>\langle12\rangle</tex> <tex>abac</tex>. В поток: <9tex>\langle9\rangle</tex>;* '''Шаг 10: '''<tex>ca</tex> — есть в таблице; <tex>cab</tex> — нет. В таблицу: <13tex>\langle13\rangle</tex> <tex>cab</tex>. В поток: <8tex>\langle8\rangle</tex>;* '''Шаг 11: '''<tex>ba</tex> — есть в таблице; <tex>bae</tex> — нет. В таблицу: <14tex>\langle14\rangle</tex> <tex>bae</tex>. В поток: <6tex>\langle6\rangle</tex>;* '''Шаг 12: '''И, наконец последняя строка <tex>e</tex>, за ней идет конец сообщения, поэтому мы просто выводим в поток <4tex>\langle4\rangle</tex>.
{| class="wikitable" border =1, style="text-align: center; margin-left: auto; margin-right: auto;"
Мы знаем, что для каждого кода надо добавлять в таблицу строку, состоящую из уже присутствующей там строки и символа, с которого начинается следующая строка в потоке.
*''' ''' Итак, кодировщик заносит первую <tex>a</tex> в строку, ищет и находит <tex>a</tex> в словаре. Добавляет в строку следующую <tex>a</tex>, находит, что <tex>aa</tex> нет в словаре. Тогда он добавляет запись <5tex>\langle5\rangle</tex>: <tex>aa</tex> в словарь и выводит метку <0tex>\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>, которой нет в словаре. Словарь пополняется этой строкой, а на выход идет метка <5tex>\langle5\rangle</tex> (<tex>aa</tex>).
*''' '''После этого строка инициализируется третьей <tex>a</tex>, и т.д. и т.п. Дальнейший процесс вполне ясен.
{| class="wikitable" border =1, style="text-align: center; margin-left: auto; margin-right: auto;"
В результате на выходе получаем последовательность <tex>056 </tex>..., которая короче прямого кодирования стандартным методом LZW.
Можно показать, что такая последовательность будет корректно восстановлена. Декодировщик сначала читает первый код – это <0tex>\langle0\rangle</tex>, которому соответствует символ <tex>a</tex>. Затем читает код <5tex>\langle5\rangle</tex>, но этого кода в его таблице нет. Но мы уже знаем, что такая ситуация возможна только в том случае, когда добавляемый символ равен первому символу только что считанной последовательности, то есть <tex>a</tex>. Поэтому он добавит в свою таблицу строку <tex>aa</tex> с кодом <5tex>\langle5\rangle</tex>, а в выходной поток поместит <tex>aa</tex>. И так может быть раскодирована вся цепочка кодов.
Мало того, описанное выше правило кодирования мы можем применять в общем случае не только к подряд идущим одинаковым символам, но и к последовательностям, у которых очередной добавляемый символ равен первому символу цепочки.
