Vladimir Dashevsky а по степени сжатия по предварительным данным он не уступает RAR'у Сравнение некорректное.
Можно рассмотреть 3 типа сжатия:
1) Энтропийное. Пусть сообщение над алфовитом S={a1,a2,...,aM}. Сообщение длиной N симвоолов. i-й симовол встречается qi раз. Тогда вероятностью символа ai в сообщении назовём величину qi/N (частоту).
Рассмотрим величину R=сумма по i [-pi * log (pi)]. Это количество бит на символ в среднем.
Пример: сжатие Хаффмана пусть есть алфавит S={a,b,c} с вероятностями 0.5 0.25 0.25
Делим на две кучи с равными вероятностями: {a},{b,c}
Первой куче даём ведущий бит 0, другой 1.
Делим вторую кучу дальше (первую дальше делит ненадо - там 1 симовол): {b},{c}
Первой подкуче даём второй бит 0, другой 1.
Итого:
a=0
b=10
c=11
Величина R=log(2)/2+log(4)/4+log(4)/4=3/2.
Т.е. в среднем при таких вероятностях на храниение одного символа уйдёт полтора бита.
Сообщение "abac" будет закодировано как "010011" т.е. 4 симола закодируются 6 битами (так и есть - полтора бита на символ).
Идея сжатия: часто появляющимся символам даём короткие кодовые последовательности и на этом экономим.
А если бы мы от балды начали кодировать как a=00,b=01,c=10. Тогда ушлобы не 6 бит, а 8.
Сжатие Хаффмана очень простое (надо лишь рекурретно делить на 2 группы с равными вероятностями),
даёт неплохое сжатие, но когда неудаётся разложить в дерево Хаффмана симолы,
чтобы всегда вероятность делилась поровну - не получается в точности достичь
степени сжатия по формуле для R (количество бит на символ).
В арифметическом сжатии возможно в точности достичь величины R, для любого сообщения
(например если алфавит из 2-х символов {a,b} с вероятностями в сообщении 0.8 и 0.2),
то Хаффман не сможет сжать в отличии от арифметического.
Для определения на сколько сожмёт арифметичкое сжатие, можно сказать заранее:
достаточно подсчитать частоту встеречи каждого символа, рассчитать R и умножить на длину сообщения.
Размер алфавита (количество симолов) зависит от того, по сколько бит будем брать за раз:
если брать по 1 биту, то 2-х буквенный алфавит
Если по байту - то 256 различных символов
А можно брать и по 2 байта за раз, тогла алфовит будет состоять из 65536 символов.
В алгоритме JPEG после Дискретного Косинусного Преобразование (DCT) и после квантизации, коэффициенты запаковываются Хаффманом.
В алгоритме JPEG2000 после Вейвлет Преобразование (Wavelet) и после квантизации, коэффициенты запаковываются алгоритмическим сжатием.
Ну про MPEG AVC сам знаешь.
Подробнее про арифметичекое можно найти тута:
http://www.sdteam.com/texts/23/717.zip вроде расписано понятно вплоть до кода
2) Словарное
Ищем повторяющиеся участки, заносим их в словарь и при следующей встрече не пишем этот участок,
а ссылаемся на словарь. Идея проста, но в отличии от Энтропийного сжатия нет математически доказанных
алгоритмов выбора словаря и гарантий на сжатие. При Энтропийном можно заранее сказать на сколько сожмётся
сообщение. В словарном в зависимости от удачности выбора сжатия словаря в конкретном случае.
Очевидно можно придумать тест (напрмер взять алфавит и повторять его без конца: abcabcabc...)
Энтропийное сжатие его не сможет сжать (вероятности встечи всех символов равны, так как их одинаковое количество)
А вот словарное сжатие такой тест сожмёт очень сильно.
На другом тесте соотношение сжатий словарного/энтропийного может быть в точности наоборот.
Потому сравнивать их неразумно. (WinRAR VS арифметическое)
3) Антисловарное
Предположим мы просмотрели всё сообщение и заметили, что оно не содержит подстроки (например aaabba). Но если уменьшить это антислово на 1 символ, то то оно уже будет сожержаться в сообщениии (т.е. aaabb в сообщении есть).
А ну ещё предположим, что алфовит состоит из 2-х символов (рассматриваем биты). Если встретили "aaabb", то следующий символ точно будет "b" т.к. всего два символа, но "a" быть не может, т.к. вначале было замечено, что
сообщение не сожержит "aaabba". А раз точно знаем, что будет "b", то можно его и не писать. Таким образом вместо
"aaabbb" везде в сообщении пишем "aaabb". Таким образом 1 антислово экономит 1 бит для каждого подслова полученного из антислова без последней буквы. Если количество таким образом сыкономленых бит больше, чем требуется на включение антислова в антисловарь (антисловарь ведь тоже надо хранить и передавать с урезанным сообщением), тогда использование данного антислова сжимает сообщение и его надо использовать.
На данный момент алгоритмы антисловарного сжатия не дотягивают до словарного сжатия (по степени сжатия) в среднем (хотя конечно можно придумать пример (последовательность Туе-Морса) при котором антисловарное лучше сожмёт, чем словарное)
- user online
- user offline