55
правок
Изменения
Нет описания правки
# Если фраза ωK уже есть в словаре, присвоить входной фразе значение ωK и перейти к Шагу 2, иначе выдать код ω, добавить ωK в словарь, присвоить входной фразе значение K и перейти к Шагу 2.
Конец
== Пример ==
Данный пример показывает алгоритм LZW в действии, показывая состояние выходных данных и словаря на каждой стадии, как при кодировании, так и при раскодировании сообщения. С тем чтобы сделать изложение проще, мы ограничимся простым алфавитом — только заглавные буквы, без знаков препинания и пробелов.
Сообщение, которое нужно сжать, выглядит следующим образом:
TOBEORNOTTOBEORTOBEORNOT#
Маркер '''#''' используется для обозначения конца сообщения. Тем самым, в нашем алфавите 27 символов (26 заглавных букв от A до Z и #). Компьютер представляет это в виде групп бит, для представления каждого символа алфавита нам достаточно группы из 5 бит на символ. По мере роста словаря, размер групп должен расти, с тем чтобы учесть новые элементы. 5-битные группы дают 2<sup>5</sup> = 32 возможных комбинации бит, поэтому, когда в словаре появится 33-е слово, алгоритм должен перейти к 6-битным группам. Заметим, что, поскольку используется группа из всех нолей 00000, то 33-я группа имеет код '''32'''. Начальный словарь будет содержать:
{| class="wikitable" style="text-align: right; margin-left: auto; margin-right: auto;"
|-
! Символ !! Битовый код !! Номер
|-
| # || 00000 || 0
|-
| A || 00001 || 1
|-
| B || 00010 || 2
|-
| C || 00011 || 3
|-
| D || 00100 || 4
|-
| E || 00101 || 5
|-
| F || 00110 || 6
|-
| G || 00111 || 7
|-
| H || 01000 || 8
|-
| I || 01001 || 9
|-
| J || 01010 || 10
|-
| K || 01011 || 11
|-
| L || 01100 || 12
|-
| M || 01101 || 13
|-
| N || 01110 || 14
|-
| O || 01111 || 15
|-
| P || 10000 || 16
|-
| Q || 10001 || 17
|-
| R || 10010 || 18
|-
| S || 10011 || 19
|-
| T || 10100 || 20
|-
| U || 10101 || 21
|-
| V || 10110 || 22
|-
| W || 10111 || 23
|-
| X || 11000 || 24
|-
| Y || 11001 || 25
|-
| Z || 11010 || 26
|-
|}
