- •Ассемблер
- •Фортран
- •Пролог и Пролог
- •Теория искусственного интеллекта
- •Тест Тьюринга
- •2. Классификация эвм по этапам создания.
- •3. Классификация эвм по назначению
- •4 . Классификация эвм по размерам и функциональным возможностям
- •СуперЭвм
- •4.2.Большие эвм
- •.МикроЭвм
- •4.4.1.Универсальные
- •4.4.2.Специализированные
- •4.4.2.1.Серверы
- •1 Принцип модульности
- •2 Принцип функциональной избирательности
- •3 Принцип генерируемости ос
- •4 Принцип функциональной избыточности
- •5 Принцип виртуализации
- •6 Принцип независимости программ от внешних устройств
- •7 Принцип совместимости
- •8 Принцип открытой и наращиваемой ос
- •9 Принцип мобильности (переносимости)
- •10 Принцип обеспечения безопасности вычислений
- •Тема 5. Память в реальном режиме
- •Тема 6. Память в защищенном режиме
- •Тема 7. Аппаратные irq
- •Тема 8 Видеопамять, видеокарты, мониторы
- •4)Основные характеристики мониторов
- •5)Виды мониторов
- •8)Перспективные конструкции и технологии мониторов Технология e-Ink
- •Технология Electro Wetting
- •Технология микродисплеев
- •Электромеханические панели
- •Тема 9 Модемы
- •1. Типовая система передачи данных
- •2) Каналы связи
- •1. 2. 1. Аналоговые и цифровые каналы
- •1. 2. 2. Коммутируемые и выделенные каналы
- •1. 2. 3. Двух- и четырехпроводные каналы
- •3) 3. Семиуровневая модель osi
- •1. 3. 1. Физический уровень
- •1. 3. 2. Канальный уровень
- •4) Факсимильная связь
- •1. 4. 1. Передача факсимильного изображения
- •1. 4. 2. Стандарты факсимильной связи
- •5) Классификация модемов
- •1. 6. 1. По области применения
- •1. 6. 2. По методу передачи
- •1. 6. 3. По интеллектуальным возможностям
- •1. 6. 4. По конструкции
- •1. 6. 5. По поддержке международных и фирменных протоколов
- •6)Устройство современных модемов
- •2. 1. Общие сведения
- •2. 2. Состав модема для ктсоп
- •2. 3. Скремблирование
- •2. 5. Устройство цифрового модема
- •2. 6. Линейное кодирование
- •1) Аналоговая модуляция
- •2) Дискретная модуляция аналоговых сигналов
- •8.2. Методы Шеннона-фано и Хаффмена
- •8.3. Алгоритм lzw
- •8.4. Сжатие данных в протоколах mnp
- •8.4.1. Протокол mnp5
- •8.4.2. Протокол mnp7
- •8.5. Сжатие данных по стандарту V.42bis
- •9.1 Протокол xModem
- •9.2. Протокол xModem-crc
- •9.3. Протокол xModem-ik
- •9.4. Протокол yModem
- •9.5. Протокол yModem-g
- •9.6. Протокол zModem
- •9.6.1. Требования протокола zModem
- •9.6.2. Формат кадров протокола zModem
- •9.6.3. Типы кадров zModem
- •9.6.4. Информация о файле в кадре zfile
- •9.6.5. Работа протокола zModem
- •Тема 10. Назначение чипсетов
- •Тема 11. Современные процессоры. Их архитектура
- •Характерные особенности risc-процессоров
- •3) Классы процессоров
- •4) Структура базового микропроцессора
- •Характеристики микропроцессоров фирмы Intel
- •Тема 12. Современные виды памяти. Их характеристики
- •1) Классификация ram(Random Access Memory):
- •2) Разновидности ram:
- •3)Виды ram и их характеристики:
- •Fpm ram (Быстрая страничная память)
- •Edo ram (память с усовершенствованным выходом)
- •Bedo dram (Пакетная edo ram)
- •Sdr sdram — синхронная dram
- •4)Новые перспективные виды памяти будущих компьютеров
- •Тема 13. Объединение компьютеров между собой
- •Естественные среды
- •Искусственные среды
- •Тема 14. Интернет
- •[Править]Каталоги
- •Тема 15. Жесткие диски и типы файловых систем
- •Название «Винчестер»
- •[Править]Характеристики
- •[Править]Уровень шума
- •[Править]Производители
- •[Править]Устройство
- •[Править]Гермозона
- •[Править]Устройство позиционирования
- •[Править]Блок электроники
- •[Править]Низкоуровневое форматирование
- •[Править]Геометрия магнитного диска
- •[Править]Особенности геометрии жёстких дисков со встроенными контроллерами [править]Зонирование
- •[Править]Резервные секторы
- •[Править]Логическая геометрия
- •[Править]Адресация данных
- •[Править]chs
- •[Править]lba
- •[Править]Технологии записи данных
- •[Править]Метод продольной записи
- •[Править]Метод перпендикулярной записи
- •[Править]Метод тепловой магнитной записи
- •[Править]Структурированные носители данных
- •[Править]Сравнение интерфейсов
- •[Править]raid 1
- •[Править]raid 2
- •[Править]raid 3
- •[Править]raid 4
- •[Править]raid 5
- •[Править]raid 5ee
- •[Править]raid 6
- •[Править]raid 7
- •[Править]raid 10
- •[Править]Комбинированные уровни
- •[Править]Сравнение стандартных уровней
- •[Править]Matrix raid
- •[Править]Программный (англ. Software) raid
- •[Править]Дальнейшее развитие идеи raid
- •Иерархия каталогов в Microsoft Windows
- •Классификация файловых систем
- •[Править]Задачи файловой системы
8.3. Алгоритм lzw
Непосредственным предшественником алгоритма LZW явился алгоритм LZ78, опубликованный в 1978 г. Этот алгоритм воспринимался как математическая абстракция до 1984 г., когда Терри Уэлч (Terry A. Welch) опубликовал свою работу с модифицированным алгоритмом, получившим в дальнейшем название LZW (Lempel-Ziv-Welch).
Алгоритм LZW построен вокруг так называемой таблицы фраз (словаря), которая отображает строки символов сжимаемого сообщения в коды фиксированной длины, равные 12 бит. Таблица обладает свойством предшествования, то есть для каждой фразы словаря, состоящей из некоторой фразы w и символа К, фраза w тоже содержится в словаре.
Алгоритм работы кодера LZW следующий:
Проинициализировать словарь односимвольными фразами, соответствующими символам входного алфавита;
Прочитать первый символ сообщения в текущую фразу *г;
Шаг алгоритма:
Прочитать очередной символ сообщения К:
Если КОНЕЦ_СООВЩЕНИЯ
Выдать ход »;
ВЫХОД;
Конец Коли Коли фрааа »К уже есть в словаре,
Заменить х на код фравы wK;
Повторить Шаг алгоритма;
Иначе
Выдать ход w;
Добавить wK в словарь ;
Повторить Шаг алгоритма;
Конец Если;
Пример работы кодера LZW при преобразовании трехсимвольного алфавита приведен в табл. 8.6 и 8.7.
Описанный алгоритм кодера не оптимизирует выбор фразы для добавления в словарь или разбор сообщения. Однако в силу его простоты он может быть эффективно использован.
Таблица 8.6. Работа кодера LZW на примере трехсимвольного алфавита (а, б, в)
Символ |
wK |
Выход |
Добавление в словарь (фраза — позиция) |
а |
1 |
|
|
6 |
6 |
1 |
16(4) |
а |
2а |
2 |
2а(5) |
6 |
16 |
|
|
в |
4в |
4 |
4в(6) |
б |
36 |
3 |
36(7) |
а |
2а |
|
|
6 |
56 |
5 |
56(8) |
а |
2а |
|
|
6 |
56 |
|
|
а |
8а |
8 |
8а(9) |
а |
1а |
1 |
1а(10) |
а |
1a |
|
|
а |
10a |
10 |
10a (11) |
а |
1a |
|
|
а |
10a |
|
'• |
а |
11a |
11 |
11a (12) |
|
|
1 |
|
Декодер LZW должен использовать тот же словарь, что и кодер, строя его по аналогичным правилам при восстановлении сжатых данных. Каждый считываемый код разбирается с помощью словаря на предшествующую фразу w и символК. Затем рекурсия продолжается для предшествующей фразы w до тех пор, пока она не окажется кодом одного символа.
Таблица 8.7. Словарь, построенный кодером LZW, для примера из табл. 8.6
Фразы, добавленные в словарь при инициализации |
|
а |
1 |
6 |
2 |
в |
3 |
Фразы, добавленные пр |
и разборе сообщения |
16 |
4 |
2а |
5 |
4в |
6 |
36 |
7 |
56 |
8 |
8а |
9 |
la |
10 |
10a |
11 |
11a |
12 |
При этом завершается декомпрессия этого кода. Обновление словаря происходит для каждого декодируемого кода, кроме первого. После завершения декодирования кода его последний символ, соединенный с предыдущей фразой, добавляется в словарь. Новая фраза получает то же значение кода (позицию в словаре), что присвоил ей кодер. В результате такого процесса, шаг за шагом декодер восстанавливает тот словарь, который построил кодер.
Алгоритм декодирования LZW описывается следующим образом:
КОД 8 Прочитать первый ход сообщения( );
ПредмдущийКОД = КОД;
Выдать символ К, у которого код(К) == КОД;
Последний символ = К;
Следующий ход:
КОД = Прочитать очередной код сообщения( );
ВходнойКОД = КОД ;
Если КОНЕЦ_СООБЩЕНИЯ ВЫХОД;
Конец Если;
Если Неизвестен(КОД) // Обработка исключительной //ситуации
Видать(ПоследнийСимаол) КОД = ПредыдущийКОД
ВходнойКОД = код(ПредыдущийКОД, ПоследнийСимвол) Конец Если;
Следующий символ:
Если КОД == ход(wK) В СТЕК (К);
КОД = код(к) ;
Повторить Следующий символ;
Иначе если КОД == код(К) Выдать К;
По еле днийСимвол в JC;
Пока стек не пуст
Выдать (ИЗ_СТЕКА( )) ;
Конец Пока;
Добавить в словарь (ПредыдущийКОД, К);
Предыдущий КОД а Входной КОД;
Повторить СледующийКОД;
Конец Если;
Обычно декодирование LZW намного быстрее процесса кодирования. Автор LZW Терри Уэлч в свое время сумел запатентовать свой алгоритм в США. В настоящее время патент принадлежит компании Unisys. Алгоритм LZW определяется как часть стандарта ITU-T V.42bis, но Unisis установила жесткие условия лицензирования алгоритма для производителей модемов.