Delphi World - Теория сжатия - Часть 4
Delphi World - это проект, являющийся сборником статей и малодокументированных возможностей  по программированию в среде Delphi. Здесь вы найдёте работы по следующим категориям: delphi, delfi, borland, bds, дельфи, делфи, дэльфи, дэлфи, programming, example, программирование, исходные коды, code, исходники, source, sources, сорцы, сорсы, soft, programs, программы, and, how, delphiworld, базы данных, графика, игры, интернет, сети, компоненты, классы, мультимедиа, ос, железо, программа, интерфейс, рабочий стол, синтаксис, технологии, файловая система...
Теория сжатия - Часть 4

Автор: Timothy Bell

4. ВОПРОСЫ ПРАКТИЧЕСКОЙ РЕАЛИЗАЦИИ.

4.1 Ограничения по памяти.

Многие из описанных выше адаптивных схем строят модели, использующие по мере осуществления сжатия все больше и больше памяти. Существует несколько ме- тодов удержания размеров модели в некоторых границах.

Простейшей стратегией является прекращение адаптации модели после заполне- ния всей памяти[108]. Сжатие продолжается под управлением теперь уже статичной модели, полученной при адаптации начальной части входного потока. Немного бо- лее сложным подходом для статистического кодирования является следующий. Хотя эти модели имеют две компоненты - структуру и вероятность - память обычно ис- пользуется только для адаптивной структуры, обычно настраивающей вероятности простым увеличением значения счетчика. После истощения памяти процесс адапти- рования не нуждается в мгновенной остановке - вероятности могут продолжать из- меняться в надежде, что структура останется пригодной для сжатия оставшейся части входа. Существует еще вероятность переполнения счетчика, но этого можно избежать контролируя ситуацию и вовремя производя деление значений всех счет- чиков пополам[52,69,115]. Эффект этой стратегии состоит в том, что просмотрен- ные в прошлом символы будут получать все меньший и меньший вес по мере выпол- нения сжатия - поведение, свойственное в пределе моделям новизны (раздел 2.3).

Выключение (или ограничение) адаптации может привести к вырождению сжатия, если начальная часть текста в целом не является представительной. Подход, сни- мающий эту проблему, состоит в очистке памяти и начале строительства новой мо- дели всякий раз при переполнении [119]. Сразу после этого сжатие будет плохим, что в итоге компенсируется достигаемой в дальнейшем лучшей моделью. Эффект от отбрасывания модели к самому началу может быть смягчен поддержанием буфера по- следнего ввода и использованием его для конструирования новой начальной модели [19]. Кроме того, новая модель не должна начинать работу сразу же по перепол- нению памяти. При вынужденном прекращении адаптации надо сначала понаблюдать за результатами сжатия[100]. Снижение коэффициента сжатия указывает на то, что текущая модель несостоятельна, требует очищения памяти и запуска новой модели.

Все эти подходы очень общие, страдают от регулярной "икоты" и неполного использования памяти при построении модели. Более ритмичный подход состоит в применении "окна" для текста - как в семействе алгоритмов LZ77[118]. Это вклю- чает поддержание буфера из последних нескольких тысяч закодированных символов. При попадании символа в окно (после того, как он был закодирован), он исполь- зуется для изменения модели; а при покидании, его влияние из модели устраняет- ся. Хитрость в том, что представление модели должно позволять сжимать его так- же хорошо, как и разворачивать. Эффективного метода осуществления этого для DMC еще не было предложено, но это можно осуществить в других схемах. Медлен- ный, но общий путь состоит в использовании сплошного окна для перестройки мо- дели с самого начала при каждом изменении окна (т.е. при кодировании очеpедно- го символа). Ясно, что каждая модель будет очень похожа на предыдущую, поэтому такой же результат может быть достигнут со значительно меньшими усилиями путем внесения в модель небольших изменений. Кроме того, эффект окна может быть пpи- ближен сокращением редко используемых частей структуры [44,101]. Кнут [52] в своем адаптивном кодировании Хаффмана использовал окно.

4.2 Подсчет.

Во время конструирования статистических моделей необходимо производить оценку вероятностей. Обычно это осуществляется подсчетом количества появлений символа в образце, т.е. нахождением относительной частоты символа, которая ис- пользуется для оценки его вероятности. Храненение счетчиков требует значитель- ных объемов памяти из пространства, выделенного модели, однако, ее можно со- кратить.

Если n есть максимальное количество наблюдений, то счетчикам требуется log n битов памяти. Однако, можно применять меньшие регистры, если при угрозе переполнения делить значения счетчиков пополам. Понижение точности частот на- носит небольшой ущерб, поскольку возникновение небольших ошибок в их предска- зании почти не оказывает влияния на среднюю длину кода. На самом деле, масшта- бирование счетчиков часто улучшает сжатие, поскольку дает более старым счетчи- кам меньший вес, чем текущим, а последние статистики часто являются лучшей ос- новой для предсказания следующего символа, чем более ранние. Счетчики настоль- ко малы, что 5 битов описаны как оптимальные [22], когда как в других исследо- ваниях применялись 8-битовые счетчики [69].

Для двоичного алфавита необходимо хранить только два счетчика. Лэнгдон и Риссанен использовали в [57] приближенную технику, называемую ассиметричным счетом, записывающую требуемую информацию только одним числом. Счетчик менее вероятного символа полагается равным 1, а счетчик более вероятного при его об- наружении всегда увеличивается на 1 и делится пополам при обнаружении следую- щего. Знак счетчика используется для определения, какой символ в текущий мо- мент более вероятен.

Моррис в [70] предложил технику, при которой счетчики, достигшие значения n, помещаются в log(log(n)) битовый регистр. Принцип состоит в хранении лога- рифма счетчика и увеличении счетчика с вероятностью 2^-c, где c есть текущее значение регистра. Этот вероятностный подход гарантирует увеличение значения счетчика так часто, как следует, т.е. в среднем. Для анализа этой техники смо- три Флажолета [29].

5. СРАВHЕHИЕ.

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

5.1. Ха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. Экспериментельно оцениваемые схемы сжатия.
------T--------------------------T--------------------------------------------¬
¦Схема¦  Авторы                  ¦ Заданные параметры                         ¦
+-----+--------------------------+--------------------------------------------+
¦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        [1987] ¦Contexts  Количество контекстов в модели    ¦
¦     ¦Rissanen                  ¦  = 32    1-го порядка.                     ¦
¦     ¦                          ¦Threshold Количество появлений символа, пре-¦
¦     ¦                          ¦  = 50    жде, чем он станет контекстом.    ¦
+-----+--------------------------+--------------------------------------------+
¦ADSM ¦Abramson           [1989] ¦  -       Без параметров.                   ¦
+-----+--------------------------+--------------------------------------------+
¦PPMC ¦Moffat             [1988b]¦m = 3     Максимальный размер контекста.    ¦
¦     ¦                          ¦          Неограниченная память.            ¦
+-----+--------------------------+--------------------------------------------+
¦WORD ¦Moffat             [1987] ¦  -       Без параметров.                   ¦
+-----+--------------------------+--------------------------------------------+
¦DMC  ¦Cormack and        [1987] ¦t = 1     Предпосылка изменений на текущем  ¦
¦     ¦Horspool                  ¦          пути для клонирования.            ¦
¦     ¦                          ¦T = 8     Предпосылка изменений на остель-  ¦
¦     ¦                          ¦          ных путях для клонирования.       ¦
+-----+--------------------------+--------------------------------------------+
¦MTF  ¦Moffat             [1987] ¦size = 2500   Количество слов в списке.     ¦
L-----+--------------------------+---------------------------------------------

Рисунок 7 характеризует образцы текстов, которые обрабатывались вышеука- занными методами. Они включают книги, статьи, черно-белые изобpажения и прочие виды файлов, распространенные в системах ЭВМ. Таблица 4 содержит полученные результаты, выраженные в битах на символ. Лучшее для каждого файла сжатие от- мечено звездочкой.


-------T--------T---------T-------------------T-------¬
¦ Text ¦ Type   ¦ Format  ¦      Content      ¦ Size  ¦
+------+--------+---------+-------------------+-------+
¦bib   ¦biblio- ¦UNIX     ¦725 references     ¦111.261¦
¦      ¦graphy  ¦"refer"  ¦for books and      ¦chars  ¦
¦      ¦        ¦format,  ¦papers on          ¦       ¦
¦      ¦        ¦ASCII    ¦Computer Science   ¦       ¦
¦      ¦        ¦         ¦                   ¦       ¦
+------+--------+---------+-------------------+-------+
¦book1 ¦fiction ¦Unfor-   ¦Thomas Hardy:      ¦768.771¦
¦      ¦book    ¦matted   ¦"Far from the      ¦chars  ¦
¦      ¦        ¦ASCII    ¦ Madding Crowd"    ¦       ¦
¦      ¦        ¦         ¦                   ¦       ¦
¦      ¦        ¦         ¦                   ¦       ¦
+------+--------+---------+-------------------+-------+
¦book2 ¦non-    ¦UNIX     ¦Witten:            ¦610.856¦
¦      ¦fiction ¦"troff"  ¦"Principles        ¦chars  ¦
¦      ¦book    ¦format,  ¦ of computer       ¦       ¦
¦      ¦        ¦ASCII    ¦ speech"           ¦       ¦
¦      ¦        ¦         ¦                   ¦       ¦
+------+--------+---------+-------------------+-------+
¦geo   ¦geophy- ¦32 bit   ¦Seismic data       ¦102.400¦
¦      ¦sical   ¦numbers  ¦                   ¦chars  ¦
¦      ¦data    ¦         ¦                   ¦       ¦
¦      ¦        ¦         ¦                   ¦       ¦
¦      ¦        ¦         ¦                   ¦       ¦
+------+--------+---------+-------------------+-------+
¦news  ¦elec-   ¦USENET   ¦A variety of       ¦377.109¦
¦      ¦tronic  ¦batch    ¦topics             ¦chars  ¦
¦      ¦news    ¦file     ¦                   ¦       ¦
¦      ¦        ¦         ¦                   ¦       ¦
¦      ¦        ¦         ¦                   ¦       ¦
+------+--------+---------+-------------------+-------+
¦obj1  ¦object  ¦Execu-   ¦Compilation        ¦21.504 ¦
¦      ¦code    ¦table    ¦of                 ¦chars  ¦
¦      ¦        ¦file     ¦"progp"            ¦       ¦
¦      ¦        ¦for      ¦                   ¦       ¦
¦      ¦        ¦VAX      ¦                   ¦       ¦
+------+--------+---------+-------------------+-------+
¦obj2  ¦object  ¦Execu-   ¦"Knowledge         ¦246.814¦
¦      ¦code    ¦table    ¦ Support System"   ¦chars  ¦
¦      ¦        ¦file     ¦program            ¦       ¦
¦      ¦        ¦for      ¦                   ¦       ¦
¦      ¦        ¦Apple    ¦                   ¦       ¦
+------+--------+---------+-------------------+-------+
¦paper1¦tech-   ¦UNIX     ¦Witten,Neal and    ¦53.161 ¦
¦      ¦nical   ¦"troff"  ¦Cleary:"Arithmetic ¦chars  ¦
¦      ¦paper   ¦format,  ¦coding for data    ¦       ¦
¦      ¦        ¦ASCII    ¦compression"       ¦       ¦
¦      ¦        ¦         ¦                   ¦       ¦
+------+--------+---------+-------------------+-------+
¦paper2¦tech-   ¦UNIX     ¦Witten:            ¦82.199 ¦
¦      ¦nical   ¦"troff"  ¦"Computer          ¦chars  ¦
¦      ¦paper   ¦format,  ¦ (In)security"     ¦       ¦
¦      ¦        ¦ASCII    ¦                   ¦       ¦
¦      ¦        ¦         ¦                   ¦       ¦
+------+--------+---------+-------------------+-------+
¦pic   ¦black & ¦1728x2376¦CCITT facsimile    ¦513.216¦
¦      ¦white   ¦bit map  ¦test, picture 5    ¦chars  ¦
¦      ¦facsi-  ¦200      ¦(page of           ¦       ¦
¦      ¦mile    ¦pixels   ¦ textbook)         ¦       ¦
¦      ¦picture ¦per inch ¦                   ¦       ¦
+------+--------+---------+-------------------+-------+
¦progc ¦program ¦Source   ¦Unix utility       ¦39.611 ¦
¦      ¦        ¦code     ¦"compress"         ¦chars  ¦
¦      ¦        ¦in "C",  ¦version 4.0        ¦       ¦
¦      ¦        ¦ASCII    ¦                   ¦       ¦
¦      ¦        ¦         ¦                   ¦       ¦
+------+--------+---------+-------------------+-------+
¦progl ¦program ¦Source   ¦System software    ¦71.646 ¦
¦      ¦        ¦code in  ¦                   ¦chars  ¦
¦      ¦        ¦LISP,    ¦                   ¦       ¦
¦      ¦        ¦ASCII    ¦                   ¦       ¦
¦      ¦        ¦         ¦                   ¦       ¦
+------+--------+---------+-------------------+-------+
¦progp ¦program ¦Source   ¦Program to         ¦49.379 ¦
¦      ¦        ¦code in  ¦evaluate           ¦chars  ¦
¦      ¦        ¦Pascal,  ¦compression        ¦       ¦
¦      ¦        ¦ASCII    ¦performance of     ¦       ¦
¦      ¦        ¦         ¦PPM                ¦       ¦
+------+--------+---------+-------------------+-------+
¦trans ¦tran-   ¦"EMACS"  ¦Mainly screen      ¦93.695 ¦
¦      ¦script  ¦editor   ¦editing, browsing  ¦chars  ¦
¦      ¦of      ¦ctrl-ing ¦and using mail     ¦       ¦
¦      ¦terminal¦terminal ¦                   ¦       ¦
¦      ¦session ¦ASCII    ¦                   ¦       ¦
L------+--------+---------+-------------------+--------
-------T--------------------------------------------------------------------¬
¦ Text ¦   Sample                                                           ¦
+------+--------------------------------------------------------------------+
¦bib   ¦ %A Witten, I.H.                                                    ¦
¦      ¦ %D 1985                                                            ¦
¦      ¦ %T Elements of computer typography                                 ¦
¦      ¦ %J IJMMS                                                           ¦
¦      ¦ %V 23                                                              ¦
+------+--------------------------------------------------------------------+
¦book1 ¦ 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 ¦ 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   ¦ 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  ¦ 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  ¦ 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  ¦ 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¦ 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¦ 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,                                      ¦
+------+--------------------------------------------------------------------+
¦progc ¦ compress() {                                                       ¦
¦      ¦     register long fcode;                                           ¦
¦      ¦     register code_int i = 0;                                       ¦
¦      ¦     register int c;                                                ¦
¦      ¦     register code_int ent;                                         ¦
+------+--------------------------------------------------------------------+
¦progl ¦ (defun draw-aggregate-field (f)                                    ¦
¦      ¦   (draw-field-background f)  ; clear background, if any            ¦
¦      ¦   (draw-field-border f)      ; draw border, if any                 ¦
¦      ¦                              ; draw subfields                      ¦
¦      ¦   (mapc 'draw-field (aggregate-field-subfields f))                 ¦
¦      ¦                              ; flush it out                        ¦
¦      ¦   (w-flush (window-w (zone-window (field-zone f)))) t)             ¦
+------+--------------------------------------------------------------------+
¦progp ¦ if E > Maxexp then {overflow-set to most negative value}           ¦
¦      ¦ begin                                                              ¦
¦      ¦    S:=MinusFiniteS;                                                ¦
¦      ¦    Closed:=false;                                                  ¦
¦      ¦ end                                                                ¦
+------+--------------------------------------------------------------------+
¦trans ¦ 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;4        ¦
¦      ¦ HterFall 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'e     ¦
¦      ¦     Assignment                                                     ¦
L------+---------------------------------------------------------------------

    Рисунок 7. Описание образцов текстов, использованных в экспериментах.

    Таблица 4. Результаты опытов по сжатию ( биты на символ )
----------T-------T-----T-----T-----T-----T-----T-----T-----T-----T-----T-----¬
¦ Текст   ¦ Размер¦ 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¦
L---------+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+------

Опыт показывает, что более изощренные статистические модели достигают луч- шего сжатия, хотя LZFG имеет сравнимую характеристику. Худшую характеристику имеют простейшие схемы - диады и кодирование Хаффмана.

5.2 Требования скорости и памяти.

В общем случае лучшее сжатие достигается большим расходом ресурсов ЭВМ: времени и прежде всего памяти. Моффат [69] описывает реализацию одного из луч- ших архиваторов (PPMC), обрабатывающего около 2000 символов в секунду на маши- не MIP (OC VAX 11/780). DMC выполняется немного медленнее, так как работает с битами. Для сравнения, у LZFG на подобной машине зафиксирована скорость коди- рования около 6000 симв/сек, а раскодирования - 11000 симв/сек [28]. LZB имеет особенно медленное кодирование (обычно 600 симв/сек), но очень быстрое раско- дирование (1600 симв/сек), которое может достичь 40.000.000 симв/сек при ис- пользовании архитектуры RISC [43].

Большинство моделей пpи увеличении доступной памяти улучшают свое сжатие. Пpи использовании лучшей СД скоpость их pаботы повысится. Реализация PPMC, предложенная Моффатом, выполняется на ограниченной памяти в 500 Кб. На таком пространстве может работать и схема DMC, хотя полученные результаты ее работы достигнуты на неограниченной памяти, временами составляющей несколько Мб. LZFG использует несколько сотен Кб, LZB для кодирования применяет сравнимое ее ко- личество, когда как раскодирование обычно требует всего 8 Мб.

DIGM и HUFF по сравнению с остальными методами требуют очень немного памя- ти и быстpо выполняются.

6. ДАЛЬHЕЙШИЕ ИССЛЕДОВАHИЯ.

Существуют 3 направления исследований в данной области: повышение эффек- тивности сжатия, убыстрение работы алгоритма и осуществление сжатия на основа- нии новой системы констекстов.

Сейчас лучшие схемы достигают сжатия в 2.3 - 2.5 битов/символ для английс- кого текста. Показатель иногда может быть немного улучшен за счет использова- ния больших объемов памяти, но сообщений о преодолении рубежа в 2 бита/символ еще не было. Обычные люди достигали результата в 1.3 бита/символ при предска- зании символов в английском тексте [21]. Хотя обычно это принимается за нижнюю границу, но теоретических причин верить, что хорошо тренированные люди или си- стемы ЭВМ не достигнут большего, не существует. В любом случае, несомненно, существует много возможностей для улучшения алгоритмов сжатия.

Одним направлением для исследований является подгонка схем сжатия к отече- ственным языкам. Сегодняшние системы работают полностью на лексическом уровне. Использование больших словарей с синтаксической и семантической информацией может позволить машинам получить преимущество от имеющейся в тексте высокоуpо- вневой связности. Однако, необходимо иметь в виду, что очень большое количест- во слов обычного английского текста в обычном английском словаpе может быть не найдено. Например, Уолкер и Эмслер[107] проверили 8 миллионов слов из New York Times News Service для Webster's Seventh New Collegiate Dictionary[65] и обна- ружили, что в словаpе отсутствовало почти 2/3 (64%) слов (они подсчитали, что около 1/4 из них - грамматические формы слов, еще 1/4 - собственные существи- тельные, 1/6 - слова, написанные через дефис, 1/12 - напечатаны с орфографи- ческими ошибками, а оставшуюся четверть составляют возникшие уже после выпуска словаря неологизмы). Большинство словарей не содеpжат имен людей, названий мест, институтов, торговых марок и т.д., хотя они составляют основную часть почти всех документов. Поэтому, специальные алгоритмы сжатия, взятые в рассче- те на лингвистическую информацию более высокого уровня, будут несомненно зави- сеть от системной сферы. Вероятно, что поиски методов улучшения характеристик сжатия в данном направлении будут объединяться с исследованиями в области кон- текстуального анализа по таким проблемам как извлечение ключевых слов и авто- матическое абстрагирование.

Второй подход диаметрально противоположен описанному выше наукоемкому на- правлению, и состоит в поддержании полной адаптивности системы и поиске улуч- шений в имеющихся алгоритмах. Необходимы лучшие пути организации контекстов и словарей. Например, еще не обнаружен пригодный метод постстроения моделей со- стояний; показанный метод DMC - лишь форма контекстно-ограниченной модели[8]. Тонкости роста этих СД вероятно значительно влияют на сжатие, но, несмотря на статью Уильямса [110], этот вопрос еще не был исследован систематично. Дpугой стоящей темой для исследований являются методы выделения кодов уходов в час- тично соответствующих контекстуальных моделях. В итоге, пpеобpазование систем, определяемых состояниями, таких как скрытые модели Маркова[77], может вдохнуть новую жизнь в модели состояний сжатия текстов. Например, алгоритм Баума-Уэлча определения скрытых моделей Маркова [4] в последнее время был вновь открыт в области распознавания речи [60]. Он может быть успешно применен для сжатия те- кстов, равно как и для техники глобальной оптимизации, такой как моделирование обжига[25]. Недостаток этих методов состоит в их значительных временных затра- тах, что позволяет сейчас эксплуатировать довольно небольшие модели с десятка- ми и сотнями, а не тысячами и более состояний.

Поиски более быстрых алгоритмов, сильно влияющих на развитие методов сжа- тия текстов, будут несомненно продолжены в будущем. Постоянный компромисс меж- ду стоимостями памяти и вычислений будет стимулировать дальнейшую работу над более сложными СД, требующими больших объемов памяти, но ускоряющих доступ к хранимой информации. Применение архитектуры RISC, например в [43], разными пу- тями воздействует на баланс между хранением и выполнением. Будет развиваться аппаратура, например, исследователи экспериментируют с арифметическим кодиро- ванием на микросхеме, когда как Гонзалес-Смит и Сторер [34] разработали для сжатия Зива-Лемпела параллельные алгоритмы поиска. В общем, увеличение вариан- тов аппаратных реализаций будет стимулировать и разнообразить исследования по улучшению использующих их алгоритмов.

Последняя область на будущее - это разработка и реализация новых систем, включающих сжатие текстов. Существует идея объединения в единую систему ряда распространенных пpогpамм pазных областей применения, включая текст-процессор MaxWrite(7)[117], цифровой факсимильный аппаpат [42], сетевую почту и новости (например, UNIX "net-news") и архивацию файлов (например, программы ARC и PKARC для IBM PC(8), которые часто применяются для pаспpеделяемого ПО из элек- тронных бюллютеней). Для увеличения скорости и сокращения стоимости большинст- во этих систем используют удивительно простые методы сжатия. Все они представ- ляют собой потенциальные сферы применения для более сложных методов моделиро- вания.

Люди часто размышляют над объединением адаптированного сжатия с дисковым контроллером для сокращения использования диска. Это поднимает интересные сис- темные проблемы, частично в сглаживании взрывного характера вывода большинства алгоритмов сжатия, но в основном в согласовывании случайного характера доступа к дисковым блокам с требованиями адаптации к разным стилям данных. Сжатие име- ет значительные преимущества для конечного движения - некоторые высокоскорост- ные модемы (например, Racal-Vadic's Scotsman) и конечные эмуляторы (например, [3]) уже имеют адаптивные алгоритмы. В будущем полностью цифровые телефонные сети радикально изменят характер конечного движения и, вообще, сферу локальных сетей. Эффективность сжатия трудно оценить, но эти усовершенствования опреде- ленно будут давать преимущество в скорости реализации.

Еще одной сферой применения является шифрование и защита данных [113]. Сжатие придает хранимым и передаваемым сообщениям некоторую степень секретнос- ти. Во-первых, оно защищает их от случайного наблюдателя. Во-вторых, посредст- вом удаления избыточности оно не дает возможности криптоаналитику установить присущий естественному языку статистичекий порядок. В-третьих, что самое важ- ное, модель действует как очень большой ключ, без которого расшифровка невоз- можна. Применение адаптивной модели означает, что ключ зависит от всего текс- та, переданного системе кодирования/раскодирования во время ее инициализации. Также в качестве ключа может быть использован некоторый префикс сжатых данных, опpеделяющий модель для дальнейшего pаскодиpования[47].

Сжатие текстов является настолько же нужной областью исследований как и 40 лет назад, когда ресурсы ЭВМ были скудны. Его пpименение продолжает изменяться вместе с улучшением технологии, постоянно увеличивая выигрыш за счет машинного времени, скорости передачи данных, первичного и вторичного хранения.

(1) - Везде  в этой статье основание логарифма есть 2, а  единица информации -
      бит.
(2) - Вероятность может  быть менее 100%  в случае иностранных слов, таких как
      "Coq au vin" или "Iraq.".
(3) - Понятие введено Моффатом в [69] для техники, использованной в [16].
(4) - Эта перемена инициалов  в аббревиатуре является увековеченной нами исто-
      рической ошибкой.
(5) - UNIX - торговая марка AT&T Bell Laboratories.
(6) - На самом деле это дерево Patricia [51,71].
(7) - MacWrite - зарегестрированная торговая марка Apple Computer,Inc.
(8) - IBM - зарегестрированная торговая марка International Business Machines.

ADSM                    = adaptive dependency source model.
Arithmetic coding       - арифметическое кодирование.
Bits per character      - биты на символ - единица измерения степени сжатия.
  (bit/char)
Blending strategy       - смешанная стратегия.
Code space              - кодовое пространство.
Compression ratio       - характеристика степени сжатия.
Conditioning classes    - классы условий.
Cross-product           - перекрестное умножение.
Cumulative probability  - накапливаемая вероятность.
DAFC                    = A doubly-adaptive file compression algorithm.
Dictionary coding       - словарное кодирование.
Digram coding           - кодирование диадами.
Entropy                 - энтропия.
Escape probability      - вероятность ухода.
File                    - файл, обозначение сжимаемых данных.
Finite-context modeling - контекстно-ограниченное моделирование.
Finite-context          - вероятностные модели с конечным числом состояний.
  probabilistic model
FSM                     = finite-state machine - конечный автомат.
Greedy parsing          - тщательный разбор.
Hyphenated words        - слова, разделенные дефисом.
Input                   - ввод, обозначение сжимаемых данных.
Lazy exclusion          - ленивое исключение.
Lookahead buffer        - упpеждающий (пpосмотpенный) впеpед буфер.
LFF                     = Longest Fragment First
                        - метод помещения в начало самого длинного фрагмента.
Noiseless compression   - сжатие без помех (обpатимое).
Order-o fixed-context   - контекстно-зависимая модель степени o.
  model
Parsing                 - разбор текста на фразы.
PPMA                    = prediction by partial match, method A.
Proper nouns            - имена собственные.
Recency models          - модели новизны.
Run-length coding       - кодиpование длин тиpажей.
Skew count              - ассиметричный счет.
Source                  - источник, производящий (содержащий) данные для
                          сжатия.
Source coding           - синоним процесса сжатия.
Statistical coding      - статистическое кодирование.
String                  - строка, обозначение сжимаемых данных.
Text                    - текст, обозначение сжимаемых данных.
Trie                    = digital search tree - дерево цифрового поиска.
Update exclusion        - обновляемое исключение.
Vowel-consonant pairs   - пары "гласная-согласная".
Zero frequency problem  - проблема нулевой частоты.
Ziv-Lempel compression  - сжатие Зива-Лемпела.
Проект Delphi World © Выпуск 2002 - 2017
Автор проекта: Эксклюзивные курсы программирования