Моделирование при сжатии текстовых данных - Ха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]. Почти все методы имеют параметры, обычно воздействующие на скорость работы и требуемые объемы памяти. Мы выбрали значения, которые дают хорошее сжатие без необязательно больших запросах ресурсов ЭВМ.
Схема | Авторы | Заданные параметры |
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 Количество слов в списке. |