PAQ1: Описание модели (c) 2002, Matt Mahoney http://www.cs.fit.edu/~mmahoney/compression v1.02 Эффективность сжатия зависит от качества предсказания. Предиктор (предсказатель) смешивает оценки некоторого набора моделей и выдает вероятность того, будет следующий бит (s[i]) нулем или единицей, учитывая предыдущие данные (s[1] s[2] ... s[i-1]). Оценка вероятности представляется в виде функции от счетчиков нулей и единиц (n0 и n1) - _p(1) = n1/(n0+n1)_ с весом (достоверностью) _n0+n1_. Модели комбинируются путем сложения соответствующих счетчиков, что эквивалентно смешиванию с указанными весами. PAQ1 использует предсказания пяти моделей: m0 - Базовая модель; p(1) = 1/2 с достоверностью 2, т.е. n0=1, n1=1. Сама по себе, эта модель не дает никакого сжатия. Используется для обеспечения корректности кодирования в вырожденных случаях. m1 - Нестационарная контекстная модель. Это комбинация N=8 субмоделей порядка n - от 1 до N. В субмодели порядка n очередной бит оценивается в контексте предыдущих (n-1) байтов, плюс от 0 до 7 битов текущего байта. Каждый раз, когда 0 или 1 встречается в некотором контексте, ассоциированный с ним (контекстом) счетчик n0 или n1 инкрементируется. Если "противоположный" счетчик превышает 2, то "излишек" делится пополам. Это является компромиссом между стационарной моделью, где все события в одном контексте одинаково значимы, и "инверсно-временной" моделью, в которой вероятность события обратно пропорциональна времени с момента его последнего появления, вне зависимости от того, что происходило перед этим. Для примера, предположим, что контекст встречался десять раз и последовательность битов в контексте - 1111111000. Если "символы" независимы, тогда n0=7, n1=3, и p(1)=7/10 с достоверностью 10. В "инверсно- временной" модели последняя единица была четыре события назад, а последний ноль - одно событие назад, т.о. ноль в четыре раза вероятней единицы, из чего следует, что p(1)=1/5. 1111111 n0 = 0 n1 = 7 p(1) = 1 с достоверностью 7 11111110 n0 = 1 n1 = 4 p(1) = 4/5 с достоверностью 5 111111100 n0 = 2 n1 = 3 p(1) = 3/5 с достоверностью 5 1111111000 n0 = 3 n1 = 2 p(1) = 2/5 с достоверностью 5 Счетчики берутся с весом n^2 (порядок в квадрате). Смысл этого в том, что если последние n байтов контекстов совпадают, то следующий байт совпадет с вероятностью (n-1)/n (в "инверсно-временной" модели), из чего следует вес n. Также, ожидаемое число совпадений длины n пропорционально 1/n, поэтому мы домножаем веса еще на n. Для хранения счетчиков используется хэш-таблица из 16M элементов. Каждый элемент занимает два байта (т.о., требуется 32Mb памяти) - восьмибитовая контрольная сумма для обнаружения коллизий и восьмибитовое же значение, описывающее состояние счетчиков n0 и n1. Контекст хэшируется в 32 бита, 24 бита используются для индексирования хэш-таблицы и 8 - для нахождения коллизий. Если случается коллизия, то проверяются следующие два элемента таблицы. В ситуации, когда все три заняты, элемент с минимальным n0+n1 удаляется. Восьмибитное "состояние" представляет значения от 0 до 10 непосредственно, а прочие до 512 - приближенно, с эмпирическими инкрементами. Т.к. n0 и n1 не могут быть большими одновременно, то отдельные "состояния" для таких пар не требуются. m2 - Модель совпадений. Это аппроксимация нестационарной контекстной модели для порядков, больших n=8. Она ищет совпадение длиной 8 или более байт (плюс текущие 0..7 бит) в предыдущих 4M входных данных, и, если таковое найдено, то предсказывает появление следующего бита оттуда с весом 3*n^2 (вместо n^2, т.к. контекст мог повторяться и неоднократно, но используется только последнее встречание). Для этого применена хэш-таблица из 1M трехбайтных указателей (предыдущий элемент всегда перезаписывается) на буфер размером 4M, т.е. всего 7Mb памяти. m3 - Словарная модель. Это оптимизация для английского текста. На самом деле, есть две субмодели - порядка 1 и порядка 2, работающие со словами. В первой, контекстом является последнее слово или часть слова, плюс предыдущие и текущие биты (от 8 до 15). Слово определяется, как последовательность букв (a-z) без учета регистра. Вторая субмодель включает в контекст предыдущее слово. Вес равен (n+w)^2, где w - это длина слова или слов (т.е. квадрат длины контекста в байтах, как в m1). Счетчики содержатся в хэш-таблице из 4M элементов (8Mb памяти) аналогично модели m1. m4 - Табличная модель. Это оптимизация для данных с записями или строками фиксированной длины, таких, как базы данных, таблицы и массивы чисел в двоичной форме. Если длина записи может быть определена, то используются две субмодели. Первая - битовая модель порядка 1 (без контекста) с весом 4, в которой "предысторией" являются все биты в той же "колонке". Вторая - битовая модель порядка 9 с весом 16, где контекстом являются предыдущие восемь бит (пересекающие границу байта), то есть предыстория - это все биты, имеющие такой же 8-мибитный контекст, что и текущий. Битовые счетчики хранятся в 32K-элементной хэш-таблице (64Kb). Длина записи определяется путем нахождения паттерна из четырех последовательных восьмибитовых "строк" на равных интервалах минимум в 9 бит. (Это не обязательно должно быть целое число байт). Если паттерн из n "строк" с равными промежутками найден в блоке размером r, то предполагается встречание еще n записей. Новый цикл длиной r может заменить старый, если новое произведение r*n превысит старое (в расчете на появление еще n записей). РЕЗУЛЬТАТЫ Следующие результаты были получены при помощи PAQ1 и различных популярных и известных своей высокой эффективностью программ на Calgary Corpus. С каждой программой производились два теста. В первом сжимались 14 файлов (сообщается суммарный размер, или размер архива, в зависимости от программы). Во втором тесте эти 14 файлов были "склеены" в один, размером 3,141,622 и сжаты. Показаны полученные размеры. Времена работы приводятся для первого теста, т.к. были примерно одинаковы в обоих. Тестирование производилось на машине с процессором Duron-750, 256Mb памяти и L2-кэшем 128k под Windows Me. PAQ1 компилировался при помощи DJGPP (g++) 2.95.2 с оптимизацией (gxx -O). Для остальных программ были выбраны наборы опций, приводящие к максимальному сжатию в рамках 64M памяти. Program Options 14 files Seconds Concatenated ------- ------- -------- ------- ------------ compress 1,272,772 1.5 1,318,269 pkzip 2.04e 1,032,290 1.5 1,033,217 gzip 1.2.4 -9 1,017,624 2 1,021,863 P5 992,902 31.8 то же P6 841,717 38.4 то же P12 831,341 38.8 то же bzip2 1.0.0 -9 828,347 5 859,448 acb u 766,322 110 769,363 boa 0.58b -m15 751,413 44 769,196 ppmd H e -m64 -o16 744,057 5 759,674 sbc 0.910 c -m3 740,161 4.1 819,016 ppmonstr H e -m64 -o1 719,922 13 736,899 rk 1.04 -mx3 -M64 -ts 712,188 36 755,872 rk 1.02 b5 -mx3 707,144 64 750,740 PAQ1 m1, 1 MB 843,819 46.3 то же m1, 8 MB 768,463 45.9 m1, 16 MB 758,456 45.6 m1, 32 MB 751,734 45.3 m1-m2, 32+7 MB 731,637 48.5 m1-m3, 32+7+8 MB 723,092 62.1 m1-m4, 16+7+8 MB 720,310 71.2 m1-m4, 32+7+4 MB 717,766 68.0 m1-m4, 32+7+8 MB (as coded) 716,704 68.1 compress, pkzip и gzip используют алгоритмы класса LZ, т.е. кодируют строки, как указатели на предыдущие вхождения или элементы словаря. В bzip2 и sbc применяется преобразование Берроуза-Уилера (BWT). P5,P6 и P12 основаны на нейросетевом предсказании и арифметическом кодировании. Acb, boa, ppmd, ppmonstr и rk используют стационарный PPM. Rk - лучший из 157 компрессоров, согласно статистике ACT от 6/24/2001 (Gilchrist, см. http://compression.ca/act-calgary.html), за ним следуют sbc, boa и acb. На Canterbury Corpus лучшие три - это ppmonstr, ppmd и rk. (см. http://www.geocities.com/SiliconValley/Bay/1995/texts22.html). PAQ1 превосходит все остальные компрессоры в случае, если Calgary Corpus "склеен" в один файл. Его эффективность не зависит от этого, т.к. PAQ1 (и P5,P6,P12) всегда объединяет файлы, чтобы воспользоваться общей статистикой. Объединение часто вредит таким стационарным моделям, как PPM или BWT, т.к. Calgary Corpus содержит смесь текстовых и бинарных файлов с различной статистикой и модели не адаптируются. Результаты для RK -mx3 и PAQ1. RK - это основанный на PPMZ архиватор, который подбирает порядок файлов для оптимизации сжатия. Для корректности, сравнение с PAQ1 производилось с использованием того же порядка файлов, с которым работал RK, а не алфавитного. File Size RK -mx3 Ratio PAQ1 Ratio ------ ------ ------- ----- ------ ----- PAPER2 82199 22111 26.8 22323 27.16 PAPER1 53161 13085 24.6 12783 24.05 BOOK1 768771 201950 26.2 206539 26.87 BOOK2 610856 139591 22.8 132151 21.63 OBJ1 21504 9397 43.6 10027 46.63 GEO 102400 47960 46.8 52244 51.02 OBJ2 246814 63754 25.8 66416 26.91 PIC 513216 30595 5.9 46975 9.15 BIB 111261 24146 21.7 23011 20.68 PROGL 71646 13692 19.1 12661 17.67 PROGC 39611 11614 29.3 10571 26.69 PROGP 49379 10207 20.6 9048 18.32 TRANS 93695 14273 15.2 13465 14.37 NEWS 377109 104435 27.6 97917 25.97 ------ ------ ------- ----- ------ ----- 14 3141622 706810 22.4 716386 22.80 Rk превосходит PAQ1 на бинарных файлах, таких как GEO (сейсмические данные, 32-хбитные числа), PIC (монохромное изображение с разрешением 200 dpi, страница из книги), OBJ1 (программа для VAX) и OBJ2 (программа для Macintosh). Тем не менее, PAQ1 лучше RK на большинстве текстовых файлов, особенно ближе к концу списка, по мере увеличения объема статистики. Rk также превосходит PAQ1 на случайных данных, т.к. практически не увеличивает их объем, в отличие от 6.6% (8.5bpc) увеличения, получаемого PAQ1. Замедление "старения" статистики (применение "более стационарной" модели) уменьшит эту разницу, но и ухудшит компрессию практически для всех остальных файлов. Оказалось удивительно сложно обнаруживать случайные данные среди вполне сжимаемых, не жертвуя способностью адаптироваться к изменяющейся статистике.