Алгоритмы, структуры данных




Практические контекстно-ограниченные модели. - часть 2


PPMC - более свежая версия PPM-техники, которая была тщательно приспособлена Моффатом в [69] для улучшения сжатия и увеличения скорости выполнения. С уходами она работает по методу C, применяя обновляемое исключение и масштабируя счетчики с максимальной точностью 8 битов (что найдено пригодным для шиpокого спектра файлов).

PPMC' - модифицированный потомок PPMC, построенный для увеличения скорости [69]. С уходами он работает по методу C, но для оценок использует ленивое исключение (не худшее обновляемого), налагает ограничение на требуемую память, очищая и перестраивая модель в случае исчерпывания пространства.

PPMC и PPMC' немного быстрее, чем PPMA и PPMB, т.к. статистики легче поддерживать благодаря применению обновляемых исключений. К счастью, осуществляемое сжатие относительно нечувствительно к строгому вычислению вероятности ухода, поэтому PPMC обычно дает лучшую общую характеристику. Все эти методы требуют задания максимального порядка. Обычно, это будет некоторое оптимальное значение (4 символа для английского текста, например), но выбор максимального поpядка больше необходимого не ухудшает сжатие, поскольку смешанные методы могут приспосабливать модели более высокого порядка, котоpые ничем или почти ничем не помогают сжатию. Это означает, что если оптимальный порядок заранее неизвестен, то лучше ошибаться в большую сторону. Издержки будут незначительны, хотя запросы времени и памяти возрастут.

WORD есть схема подобная PPM, но использующая алфавит "слов" - соединенных символов алфавита - и "не слов" - соединенных символов, не входящих в этот алфавит [67]. Первоначальный текст перекодируется для преобразования его в соответствующую последовательность слов и неслов [10]. Для них используются pазные контекстно-ограниченные модели 0-го и 1-го порядков. Слово оценивается предшествующими словами, неслово - несловами. Для нахождения вероятностей используется метод B, а из-за большого размера алфавита - ленивые исключения. Применяются также и обновляемые исключения.Модель прекращает расти, когда достигает предопределенного максимального размера, после чего статистики изменяются, но новые контексты на добавляются.

Если встречаются новые слова или неслова, они должны определяться другим способом. Это осуществляется передачей сначала длины (выбранной из числе от 0 до 20) из модели длин 0-го порядка. Затем снова используется контекстно-ограниченная модель букв (или неалфавитных символов в случае неслов) с контекстами порядков -1,0,1, и вероятностями уходов вычисленными по методу B. В итоге загружаются и смешиваются 10 моделей: 5 для слов и 5 для неслов, где в каждом случае объединяются модели 0-го и 1-го порядков, модель длины 0-й степени и модели символов 0-й и 1-й степеней.

Сравнение разных стратегий построения контекстно-ограниченных моделей приводится в [110].




Содержание  Назад  Вперед