 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Алгоритм LZW
|
|
Кодирование
Процесс сжатия выглядит достаточно просто. Мы последовательно считываем символы входного потока (строку) и проверяем, есть ли в уже созданной нами таблице такая строка.
Если строка есть, то считываем следующий символ, а если такой строки нет, - заносим в выходной поток код для предыдущей найденной строки, заносим ее в таблицу и начинаем поиск снова.
Пусть на вход кодера поступает последовательность символов вида / WED / WE / WEE / WEB, при этом размер алфавита входных символов dim A = 255. Схема сжатия выглядит следующим образом:Входные символы Выходной код Новые символы словаря /W / 256 = /W E W 257 = WE D E 258 = ED / D 259 = D/ WE 256 260 = /WE / E 261 = E/ WEE 260 262 = /WEE /W 261 263 = E/W EB 257 264 = WEB<END> B В результате получим выходной код /WED<256>E<260><261><257>B. /WED/WE/WEE/WEB Как при этом изменилась длина выходного кода в сравнении со входным? Если для двоичного кодирования строки / WED / WE / WEE / WEB длиной в 15 букв и размером алфавита dim A = 255 нам понадобилось бы 15 • log2 255 = 15х8 = 120 бит, то для двоичного кодирования выходной строки кодера / WED <256> E <260> <261> <257> B длиной в 10 новых символов с алфавитом в 264 буквы – 10 • 9 = 90 бит.LZW-кодер начинает работу со словаря размером в 4 K, который содержит по адресам от 0 до 255 ссылки на отдельные буквы и от 256 до 4095 – ссылки на подстроки. В процессе кодирования текст подвергается разбору на подстроки, где каждая новая подстрока есть самая длинная из уже просмотренных плюс один символ. Она кодируется как индекс ее префикса плюс дополнительный символ, после чего новая подстрока добавляется в словарь и на нее в дальнейшем можно будет ссылаться.
Декодирование
Дата публикования: 2015-09-17; Прочитано: 544 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
