Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

Алгоритм

LZW

Это весьма популярный вариант алгоритма LZ78, который был разработан Терри Уэлчем (Terry Welch) в 1984 ([Welch 84] и [Phillips 92]). Его главной особенностью является удаление второго поля из метки. Метка LZW состоит только из указателя на место в словаре. Для лучшего понимания алгоритма LZW мы временно забудем, что словарь является деревом и будем предполагать, что словарь - это просто массив, состоящий из строк разной длины. Метод LZW начинается инициализацией словаря всеми символами исходного алфавита. В общем случае 8-битного алфавита, первые 256 записей (отдельные символы с ...

Две характерные черты арифметического кодирования позволяют легко расширить этот метод сжатия.

1. Основной шаг кодирования состоит из двух операций

Low := Low+(High-Low+l)*LowCmnFreq[X]/10; High := Low+(High-Low+l)*HighCumFreq[X]/10-l;

Это означает, что для кодирования символа X необходимо сообщить кодеру накопленные частоты этого символа и символа, расположенного над ним (см. табл. 1.24 с примером накопленных частот). Но тогда частота X (или ее вероятность) может изменяться каждый раз после кодирования, при условии, что кодер и ...

В табл. 1.35 даны шаги кодирования строки а^а^а^а^а^. Она похожа на табл. 1.34 и иллюстрирует проблему потери значащих разрядов. Переменные Low и High сближаются, и поскольку в этом примере Low всегда равна 0, переменная High теряет свои значащие цифры при приближении к Low.

Потеря значащих цифр происходит не только в этом случае, но всегда, когда Low и High должны близко сходиться. Из-за своего конечного размера переменные Low и High могут достигнуть значений, скажем 499996 и 500003, а затем, вместо того, чтобы получить значения с одинаковыми старшими цифрами, они ...

Этот вариант адаптивного кодирования Хаффмана очень прост, но менее эффективен. Его идея заключается в построении множества из п кодов переменной длины на основе равных вероятностей и случайном присвоении этих кодов п символам. После чего смена кодов делается «на лету» по мере считывания и сжатия символов. Метод не слишком производителен, поскольку коды не основаны на реальных вероятностях символов входного файла. Однако его проще реализовать, и он будет работать быстрее описанного выше алгоритма, поскольку переставляет строки таблицы быстрее, чем первый алгоритм ...

Классический вариант алгоритма

Сжатие по методу Хаффмана постепенно вытесняется арифметическим сжатием. Свою роль в этом сыграло то, что закончились сроки действия па­тентов, ограничивающих использование арифметического сжатия. Кроме того, алгоритм Хаффмана приближает относительные частоты появления символов в потоке частотами, кратными степени двойки (например, для символов а, Ъ, с, d с вероятностями 1/2, 1/4, 1/8, 1/8 будут использованы ко­ды О, 10, 110, 111), а арифметическое сжатие дает лучшую степень прибли­жения частоты. По теореме Шеннона наилучшее сжатие в ...

Один из классических алгоритмов, известных с 60-х гг. Использует только частоту появления одинаковых байтов во входном блоке данных. Ставит в соответствие символам входного потока, которые встречаются ча­ще, цепочку битов меньшей длины. И напротив, встречающимся редко -цепочку большей длины. Для сбора статистики требует двух проходов по входному блоку (также существуют однопроходные адаптивные варианты алгоритма).

Для начала введем несколько определений.

Определение. Пусть задан алфавит *Ґ={ai,.... ar}, состоящий из конечно­го числа букв. Конечную ...

В ЧЕМ РАЗНИЦА МЕЖДУ МЕТОДОМ И АЛГОРИТМОМ?

Метод - это совокупность действий, а алгоритм - конкретная последо­вательность действий.

1. Алгоритм более подробен, чем метод. Иллюстрация алгоритма - блок-схема, а иллюстрация метода - устройство, компоненты которого рабо­тают одновременно.

2. Один и тот же метод могут реализовывать несколько алгоритмов. И чем сложнее метод, тем больше возможно реализаций в виде алгоритмов.

3. По описанию алгоритма можно понять метод, но описание метода даст более полное представление об идеях, реализованных в ...

Решение задачи сравнения алгоритмов по достигаемой ими степени сжа­тия требует введения некоторого критерия, так как нельзя сравнивать про­изводительность реализаций на каком-то абстрактном файле. Следует осто­рожно относиться к теоретическим оценкам, так как они вычисляются с точностью до констант. Величины этих констант на практике могут коле­баться в очень больших пределах, особенно при сжатии небольших файлов.

В 1989 г. группа исследователей предложила оценивать коэффициент сжатия с помощью набора файлов, получившего название Calgary Compres­sion Corpus2 (CalgCC). ...

Кодирование Хаффмана является простым алгоритмом для построения кодов переменной длины, имеющих минимальную среднюю длину. Этот весьма популярный алгоритм служит основой многих компьютерных программ сжатия текстовой и графической информации. Некоторые из них используют непосредственно алгоритм Хаффмана, а другие берут его в качестве одной из ступеней многоуровневого процесса сжатия. Метод Хаффмана [Huffman 52] производит идеальное сжатие (то есть, сжимает данные до их энтропии), если вероятности символов точно равны отрицательным степеням числа 2. Алгоритм начинает строить кодовое ...