49
правок
Изменения
Отмена правки 40463 участника Studenikina (обсуждение)
Рассмотрим пример сжатия и декодирования сообщения.
Сначала создадим начальный словарь единичных символов. В стандартной кодировке ASCII имеется 256 различных символов, поэтому, для того, чтобы все они были корректно закодированы (если нам неизвестно, какие символы будут присутствовать в исходном файле, а какие - нет), начальный размер кода будет равен 8 битам. Если нам заранее известно, что в исходном файле будет меньшее количество различных символов, то вполне разумно уменьшить количество бит. Чтобы инициализировать таблицу, мы установим соответствие кода 0 соответствующему символу с битовым кодом 00000000, тогда 1
соответствует символу с кодом 00000001, и т.д., до кода 255. На самом деле мы указали, что каждый код от 0 до 255 является корневым.
Больше в таблице не будет других кодов, обладающих этим свойством.<br>
По мере роста словаря, размер групп должен расти, с тем, чтобы учесть новые элементы. 8-битные группы дают 256 возможных комбинации бит, поэтому, когда в словаре появится 256-е слово, алгоритм должен перейти к 9-битным группам. При появлении 512-ого слова произойдет переход к 10-битным группам, что дает возможность запоминать уже 1024 слова и т.д.
В нашем примере алгоритму заранее известно о том, что будет использоваться всего 5 различных символов, следовательно, для их хранения будет использоваться минимальное количество бит, позволяющее нам их запомнить, то есть 3 ( 8 различных комбинаций ).
=== Кодирование ===
Мы знаем, что для каждого кода надо добавлять в таблицу строку, состоящую из уже присутствующей там строки и символа, с которого начинается следующая строка в потоке.
*''' ''' Итак, кодировщик заносит первую <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, 5, 6 …, которая короче прямого кодирования стандартным методом LZW.
Можно показать, что такая последовательность будет корректно восстановлена. Декодировщик сначала читает первый код – это <0>, которому соответствует символ <tex>"a</tex>". Затем читает код <5>, но этого кода в его таблице нет. Но мы уже знаем, что такая ситуация возможна только в том случае, когда добавляемый символ равен первому символу только что считанной последовательности, то есть <tex>"a</tex>". Поэтому он добавит в свою таблицу строку <tex>"aa</tex> " с кодом <5>, а в выходной поток поместит <tex>"aa</tex>". И так может быть раскодирована вся цепочка кодов.
Мало того, описанное выше правило кодирования мы можем применять в общем случае не только к подряд идущим одинаковым символам, но и к последовательностям, у которых очередной добавляемый символ равен первому символу цепочки.
