Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Кодирование

Итак, пусть мы сжимаем последовательность «abacabadabacabae».

 

· Шаг 1: Тогда, согласно изложенному выше алгоритму, мы добавим к изначально пустой строке “a” и проверим, есть ли строка “a” в таблице. Поскольку мы при инициализации занесли в таблицу все строки из одного символа, то строка “a” есть в таблице.

· Шаг 2: Далее мы читаем следующий символ «b» из входного потока и проверяем, есть ли строка “ab” в таблице. Такой строки в таблице пока нет.

· Добавляем в таблицу <5> “ab”. В выход: <0>;

· Шаг 3: “ba” — нет. В словарь: <6> “ba”. В выход: <1>;

· Шаг 4: “ac” — нет. В словарь: <7> “ac”. В выход: <0>;

· Шаг 5: “ca” — нет. В словарь: <8> “ca”. В выход: <2>;

· Шаг 6: “ab” — есть в словаре; “aba” — нет. В словарь: <9> “aba”. В выход: <5>;

· Шаг 7: “ad” — нет. В словарь: <10> “ad”. В выход: <0>;

· Шаг 8: “da” — нет. В словарь: <11> “da”. В выход: <3>;

· Шаг 9: “aba” — есть в словаре; “abac” — нет. В словарь: <12> “abac”. В выход: <9>;

· Шаг 10: “ca” — есть в таблице; “cab” — нет. В словарь: <13> “cab”. В выход: <8>;

· Шаг 11: “ba” — есть в таблице; “bae” — нет. В словарь: <14> “bae”. В выход: <6>;

· Шаг 12: И, наконец последняя строка “e”, за ней идет конец сообщения, поэтому мы просто выводим <4>.

 

 

Итак, мы получаем закодированное сообщение «0 1 0 2 5 0 3 9 8 6 4», что на 11 бит короче. При этом для расшифровки необходимо дополнительно хранить начальный словарь: 0-a, 1-b, 2-c, 3-d, 4-e.

<== предыдущая лекция | следующая лекция ==>
Описание алгоритма сжатия LZW | Декодирование по LZW
Поделиться с друзьями:


Дата добавления: 2014-01-04; Просмотров: 347; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.009 сек.