Динамическое марковское сжатие
-
Основы динамического марковского сжатия (DMC)
- DMC — алгоритм сжатия без потерь, разработанный Кормаком и Хорспулом.
- Используется прогнозирующее арифметическое кодирование для предсказания битов.
- Сжатие схоже с PPM, но требует больше памяти и не получило широкого распространения.
-
Реализация и применение
- Некоторые недавние реализации включают программы от Nania Francesco Antonio и Frank Schwellinger.
- Основаны на реализации Кормака на языке Си 1993 года.
-
Алгоритм сжатия
- DMC предсказывает и кодирует биты по одному за раз.
- Отличается от PPM тем, что кодирует биты, а не байты.
- Арифметическое кодирование использует два двоичных числа для предсказания вероятности битов.
-
Модель DMC
- Предсказатель — таблица, отображающая контексты в пары вероятностей.
- Модель обновляется после каждого бита и используется для предсказания следующего.
- Добавление новых контекстов возможно путем клонирования существующих.
-
Рекомендации
- Ссылки на YouTube-канал Google Developers для дополнительной информации.
Полный текст статьи: