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