 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
LZW-модификация алгоритма Лемпеля-Зива
Эта модификация отличается от рассмотренной ранее Zip–модификации структурой пакета данных. Концепция адреса не используется, наоборот имеются ссылки предшествующие последовательности данных, а также допускаются рекуррентные ссылки на параметр длины. Пакет данных формируется из трех значений: <А, В, С>, первые два из которых указывают на уже закодированную подпоследовательность данных, следующим образом: число А указывает на сколько знаков необходимо отступить назад, чтобы найти начало нужной подпоследовательности, В – длина подпоследовательности которую необходимо считать, С – следующий знак.
Пример. Используя LZW–модификацию алгоритма Лемпеля-Зива, закодировать последовательность
abaababbbbbbbabbbba. (**)
| Пакет данных | <0,0,a> | <0,0,b> | <2,1,a> | <3,2,b> | <1,1,b> | <3,3,b> | <8,5,a> |
| Содер-жимое пакета | A | b | aa | bab | bb | bbbb | bbbb |
| Уже Закоди-рованный текст | a | ab | abaa | Aba abab | Aba ababbb | Abaaba bbbbbbb | AbAa bab bbbbbb |
Для кодирования алгоритмом Лемпеля-Зива установлено, что [1, стр. 83]:
- очень эффективно кодируются повторяющиеся символы и часто появляющиеся цепочки символов;
- редко повторяющиеся символы и последовательности символов с течением времени удаляются из словаря фраз;
- кодирование начальных фраз затрачивается относительно большое количество бит;
- методы теории информации позволяют доказать, что кодирование методом Лемпеля-Зива асимптотически оптимально. Это означает, что для очень длинного текста избыточность исчезает, то есть среднее число бит, необходимое для кодирования текста стремиться к энтропии текста;
- практическая степень сжатия для длинных текстов составляет 50-60%.
Контрольные вопросы
1. Является ли алгоритм Хаффмана примером кодирования без потерь?
2. Существуют ли такие ситуации, когда файл, обработанный алгоритмом сжатия, имеет размер больший размер исходного файла? Если да, то приведите соответствующие примеры.
3. Дайте определение префиксных кодов.
4. В чем заключается принцип создание динамически формируемого словаря в методах сжатия, основанных на алгоритме Лемпеля-Зива?
5. В каких известных программах-архиваторах используются алгоритмы Хаффмана и Лемпеля-Зива?
6. Пусть дан трехсимвольный алфавит со следующими вероятностными соответствиями.
| Xi | А | В | С |
| Р(Xi) | 0,73 | 0,25 | 0,02 |
Для данного алфавита построены следующие шесть вариантов кодов.
| Символ | Код 1 | Код 2 | Код 3 | Код 4 | Код 5 | Код 6 |
| А | ||||||
| В | ||||||
| С |
Изучите предлагаемые коды и определите, какие коды являются практичными.
Поиск по сайту: