|
Теория сжатия - Часть 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 - сжатие Зива-Лемпела.
|
Автор проекта: USU Software
Вы можете выкупить этот проект.