Изменения

*''' ''' Итак, кодировщик заносит первую «а» <tex>а</tex> в строку, ищет и находит "<tex>а" </tex> в словаре. Добавляет в строку следующую "<tex>а"</tex>, находит, что "<tex>аа" </tex> нет в словаре. Тогда он добавляет запись <5>: "<tex>аа" </tex> в словарь и выводит метку <0> ("<tex>а"</tex>) в выходной поток. *''' '''Далее строка инициализируется второй «а»<tex>а</tex>, то есть принимает вид "<tex>a?" </tex> вводится третья «а»<tex>а</tex>, строка вновь равна "<tex>аа"</tex>, которая теперь имеется в словаре. *''' '''Если появляется четвертая «а»<tex>а</tex>, то строка "<tex>aa?" </tex> равна "<tex>ааа"</tex>, которой нет в словаре. Словарь пополняется этой строкой, а на выход идет метка <5> ("<tex>aa"</tex>). *''' '''После этого строка инициализируется третьей «а»<tex>а</tex>, и т.д. и т.п. Дальнейший процесс вполне ясен.

Можно показать, что такая последовательность будет корректно восстановлена. Декодировщик сначала читает первый код – это <0>, которому соответствует символ "<tex>a"</tex>. Затем читает код <5>, но этого кода в его таблице нет. Но мы уже знаем, что такая ситуация возможна только в том случае, когда добавляемый символ равен первому символу только что считанной последовательности, то есть "<tex>a"</tex>. Поэтому он добавит в свою таблицу строку "<tex>aa" </tex> с кодом <5>, а в выходной поток поместит "<tex>aa"</tex>. И так может быть раскодирована вся цепочка кодов.