Хаpактеpистики сжатия.
Таблица 3 представляет сравниваемые методы сжатия. DIGM - простое кодирование с применением диад, основанное на работе Шнайдермана и Ханта[94] и интересное главным образом своей скоростью. LZB в среднем дает лучшее сжатие среди семейства алгоритмов LZ77, а LZFG - среди LZ78. HUFF - это адаптированный кодировщик Хаффмана применяющий модель 0-го порядка. Остальные методы адаптивно создают вероятностные модели, применяемые в сочетании с арифметическим кодиpованием. DAFC применяет модель, переключаемую между 0-м и 1-м порядками. ADSM использует контекст 1-го порядка с рядом кодируемых символов. PPMC [69] основан на методе, предложенном Клири и Уиттеном [16], применяющим более длинные контексты, и является одним из лучших контекстно-ограниченных методов моделирования. WORD - это контекстно-ограниченная модель, в которой вместо символов используются слова. DMC строит модели с ограниченным числом состояний [19], а MTF есть метод новизны, применяющий стратегию move-to-front [67], котоpый является усовершенствованием метода, предложенного Бентли и другими [10]. Почти все методы имеют параметры, обычно воздействующие на скорость работы и требуемые объемы памяти. Мы выбрали значения, которые дают хорошее сжатие без необязательно больших запросах ресурсов ЭВМ.
Таблица 3. Экспериментельно оцениваемые схемы сжатия.
| Схема | Авторы | Заданные параметры |
| DIGM | Snyderman and Hunt [1970] | - Без параметров. |
| LZB | Bell [1987] | N = 8192 Количество символов в окне. p = 4 Минимальная длина соответствия. |
| LZFG | Fiala and Greene [1989] | M = 4096 Максимальное число фраз в словаре. |
| HUFF | Gallager [1978] | - Без параметров. |
| DAFC | Langdon and Rissanen [1987] | Contexts = 32 Количество контекстов в модели 1-го порядка. Threshold =50 Количество появлений символа, прежде, чем он станет контекстом. |
| ADSM | Abramson [1989] | - Без параметров. |
| PPMC | Moffat [1988b] | m = 3 Максимальный размер контекста. Неограниченная память. |
| WORD | Moffat [1987] | - Без параметров. |
| DMC | Cormack and Horspool [1987] | t = 1 Предпосылка изменений на текущем пути для клонирования. T = 8 Предпосылка изменений на остальных путях для клонирования. |
| MTF | Moffat [1987] | size = 2500 Количество слов в списке. |
Рисунок 7 характеризует образцы текстов, которые обрабатывались вышеуказанными методами. Они включают книги, статьи, черно-белые изобpажения и прочие виды файлов, распространенные в системах ЭВМ. Таблица 4 содержит полученные результаты, выраженные в битах на символ. Лучшее для каждого файла сжатие от- мечено звездочкой.
| Text | Type | Format | Content | Size | Sample |
| bib | bibliography | UNIX "refer" format, ASCII | 725 references for books and papers on Computer Science | 111.261 characters | %A Witten, I.H.; %D 1985; %T Elements of computer typography; %J IJMMS; %V 23 |
| book1 | fiction book | Unformatted ASCII | Thomas Hardy: "Far from the Madding Crowd" | 768.771 characters | a caged canary - all probably from the window of the house just vacated. There was also a cat in a willow basket, from the partly-opened lid of which she gazed with half-closed eyes, and affectionately-surveyed the small birds around. |
| book2 | non-fiction book | UNIX "troff" format, ASCII | Witten: "Principles of computer speech" | 610.856 characters | Figure 1.1 shows a calculator that speaks. .FC "Figure 1.1" Whenever a key is pressed the device confirms the action by saing the key's name. The result of any computation is also spoken aloud. |
| geo | geophysical data | 32 bit numbers | Seismic data | 102.400 characters | d3c2 0034 12c3 00c1 3742 007c 1e43 00c3 2543 0071 1543 007f 12c2 0088 eec2 0038 e5c2 00f0 4442 00b8 1b43 00a2 2143 00a2 1143 0039 84c2 0018 12c3 00c1 3fc2 00fc 1143 000a 1843 0032 e142 0050 36c2 004c 10c3 00ed 15c3 0008 10c3 00bb 3941 0040 1143 0081 ad42 0060 e2c2 001c 1fc3 0097 17c3 00d0 2642 001c 1943 00b9 1f43 003a f042 0020 a3c2 00d0 12c3 00be 69c2 00b4 cf42 0058 1843 0020 f442 0080 98c2 0084 |
| news | electronic news | USENET batch file | A variety of topics | 377.109 characters | In article <18533@amdahl.amdahl.com> thon@uts.amdahl.com (Ronald S. Karr) writes: >Some Introduction: >However, we have conflicting ideas concerning what to do with sender >addresses in headers. We do, now, support the idea that a pure !-path >coming it can be left as a !-path, with the current hostname prepended |
| obj1 | object code | Executable file for VAX | Compilation of "progp" | 21.504 characters | 0b3e 0000 efdd 2c2a 0000 8fdd 4353 0000 addd d0f0 518e a1d0 500c 50dd 03fb 51ef 0007 dd00 f0ad 8ed0 d051 0ca1 dd50 9850 7e0a bef4 0904 02fb c7ef 0014 1100 ba09 9003 b150 d604 04a1 efde 235a 0000 f0ad addd d0f0 518e a1d0 500c 50dd 01dd 0bdd 8fdd 4357 0000 04fb d5ef 000a 7000 c5ef 002b 7e00 8bdd 4363 0000 addd d0f0 518e a1d0 500c 50dd 04fb e7ef 0006 6e00 9def 002b 5000 5067 9def 002b 5200 5270 dd7e |
| obj2 | object code | Executable file for Apple Macintosh | "Knowledge Support System" program | 246.814 characters | 0004 019c 0572 410a 7474 6972 7562 6574 0073 0000 0000 00aa 0046 00ba 8882 5706 6e69 6f64 0077 0000 0000 00aa 0091 00ba 06ff 4c03 676f 00c0 0000 0000 01aa 0004 01ba 06ef 0000 0000 0000 00c3 0050 00d3 0687 4e03 7765 00c0 0000 0000 00c3 0091 01d3 90e0 0000 0000 0015 0021 000a 01f0 00f6 0001 0000 0000 0000 0400 004f 0000 e800 0c00 0000 0000 0500 9f01 1900 e501 0204 4b4f 0000 0000 1e00 9f01 3200 e501 |
| paper1 | technical paper | UNIX "troff" format, ASCII | Witten,Neal and Cleary:"Arithmetic coding for data compression" | 53.161 characters | Such a \fIfixed\fR model is communicated in advance to both encoder and decoder, after which it is used for many messages. .pp Alternatively, the probabilities the model assigns may change as each symbol is transmitted, based on the symbol frequencies seen \fIso far\fR in this |
| paper2 | technical paper | UNIX "troff" format, ASCII | Witten: "Computer (In)security" | 82.199 characters | Programs can be written which spread bugs like an epidemic. They hide in binary code, effectively undetectable (because nobody ever examins binaries). They can remain dormant for months or years, perhaps quietly and imperceptibly infiltrating their way into the very depths of a system, then suddenly pounce, |
| pic | black and white facsimile picture | 1728x2376 bit map 200 pixels per inch | CCITT facsimile test, picture 5 (page of textbook) | 513.216 characters | |
| progc | program | Source code in "C", ASCII | Unix utility "compress" version 4.0 | 39.611 characters |
compress() { register long fcode; register code_int i = 0; register int c; register code_int ent; |
| progl | program | Source code in LISP, ASCII | System software | 71.646 characters |
(defun draw-aggregate-field (f) (draw-field-background f) ; clear background, if any (draw-field-border f) ; draw border, if any (mapc 'draw-field (aggregate-field-subfields f)) ; draw subfields (w-flush (window-w (zone-window (field-zone f)))) t) ; flush it out |
| progp | program | Source code in Pascal, ASCII | Program to evaluate compression performance of PPM | 49.379 characters |
if E > Maxexp then {overflow-set to most negative value} begin S:=MinusFiniteS; Closed:=false; end |
| trans | transcript of terminal session | "EMACS" editor controlling terminal with ASCII code | Mainly screen editing, browsing and using mail | 93.695 characters |
WFall Term\033[2'inFall Term\033[4'\033[60;1HAuto-saving...\033[28;4H\033[ 60;15Hdone\033[28;4H\033[60;1H\033[K\0\0\033[28;4HterFall Term\033[7' Term \033[7'\033[12'\t CAssignment\033[18'lAssignment\033[19'aAssignment\033 [20'Sassignment\033[21'sAssignment\033[22'Assignment\033[8@\0t \033[ 23'pAssignment\033[24'reAssignment\033[26'sAssignment\033[27'eAssignment |
Рисунок 7. Описание образцов текстов, использованных в экспериментах.
Таблица 4. Результаты опытов по сжатию ( биты на символ )
| Текст | Размер | DIGM | LZB | LZFG | HUFF | DAFC | ADSM | PPMC | WORD | DMC | MTF |
| bib | 111261 | 6.42 | 3.17 | 2.90 | 5.24 | 3.84 | 3.87 | *2.11 | 2.19 | 2.28 | 3.12 |
| book1 | 768771 | 5.52 | 3.86 | 3.62 | 4.56 | 3.68 | 3.80 | *2.48 | 2.70 | 2.51 | 2.97 |
| book2 | 610856 | 5.61 | 3.28 | 3.05 | 4.83 | 3.92 | 3.95 | 2.26 | 2.51 | *2.25 | 2.66 |
| geo | 102400 | 7.84 | 6.17 | 5.70 | 5.70 | *4.64 | 5.47 | 4.78 | 5.06 | 4.77 | 5.80 |
| news | 377109 | 6.03 | 3.55 | 3.44 | 5.23 | 4.35 | 4.35 | *2.65 | 3.08 | 2.89 | 3.29 |
| obj1 | 21504 | 7.92 | 4.26 | 4.03 | 6.06 | 5.16 | 5.00 | *3.76 | 4.50 | 4.56 | 5.30 |
| obj2 | 246814 | 6.41 | 3.14 | 2.96 | 6.30 | 5.77 | 4.41 | *2.69 | 4.34 | 3.06 | 4.40 |
| paper1 | 53161 | 5.80 | 3.22 | 3.03 | 5.04 | 4.20 | 4.09 | *2.48 | 2.58 | 2.90 | 3.12 |
| paper2 | 82199 | 5.50 | 3.43 | 3.16 | 4.65 | 3.85 | 3.84 | 2.45 | *2.39 | 2.68 | 2.86 |
| pic | 513216 | 8.00 | 1.01 | *0.87 | 1.66 | 0.90 | 1.03 | 1.09 | 0.89 | 0.94 | 1.09 |
| progc | 39611 | 6.25 | 3.08 | 2.89 | 5.26 | 4.43 | 4.20 | *2.49 | 2.71 | 2.98 | 3.17 |
| progl | 71646 | 6.30 | 2.11 | 1.97 | 4.81 | 3.61 | 3.67 | *1.90 | 1.90 | 2.17 | 2.31 |
| progp | 49379 | 6.10 | 2.08 | 1.90 | 4.92 | 3.85 | 3.73 | *1.84 | 1.92 | 2.22 | 2.34 |
| trans | 93695 | 6.78 | 2.12 | *1.76 | 5.58 | 4.11 | 3.88 | 1.77 | 1.91 | 2.11 | 2.87 |
| В среднем | 224402 | 6.46 | 3.18 | 2.95 | 4.99 | 4.02 | 3.95 | *2.48 | 2.76 | 2.74 | 3.24 |
