Канторово множество, аксиомы отделимости Хаусдорфа и проза жизни.

Иногда думаю, зачем провел годы в университете. Учили там много,  исключительно математике. Прошло семь лет после выпуска, и голова ощущается совсем пустой, абсолютно. И все чаще приходит мысль, что учили зазря… Но из туманного студенческого математического прошлого иногда выплывают идеи. Очень редко.

Есть такой способ энтропийного кодирования – арифметическое кодирование. Если кратко, то смысл его такой. Пусть есть n символов суммарной вероятности 1, как водится. Выберем n + 1 точку на отрезке от 0 до 1: 0 = a_0 < a_1 < … < a_n = 1. Пусть длина интервала  [a_i, a_{i+1} ) совпадает с вероятностью i-того символа. Разобьем полученные интервалы в тех же пропорциях и так далее, рекурсивно.

Любой последовательности символов соответствует система вложенных интервалов, бесконечной последовательности соответствует действительное число. Реализации арифметического кодирования борятся с единственной проблемой – тем, что точки с разными начальными символами могут быть произвольно близки как действительные числа. Возникает желание – а давайте  заменим интервал [a_i, a_{i+1} )  на  [a_i + \epsilon, a_{i+1}  - \epsilon ]. В эпсилон-окрестностях контрольных точек будет ничто. пустота. нихиль.

В этом случае любому коду соответствует не просто точка отрезка, а точка канторова множества. Мера такого канторова множества совсем незначительно отличается от полной меры отрезка, то есть мы теряем в коэффициенте сжатия не так и много. Что приобретаем – отделимость закодированных точек.

Решил заимплементировать сходу: http://arith-coder.googlecode.com/svn/trunk/arith.cpp Забавным образом работает, я не анализировал специально правильные эпсилоны и не использовал well defined 16.16 fixed point формат.

Сказать, что декодер простой – это значит ничего не сказать. Вот главная функция  http://www.everfall.com/paste/id.php?5cv1qp7gdp9b.

Скорость декодировки и степень сжатия сильно лучше Хаффмана, куда денется. Сразу хочется перенести на cell, где нет целочисленного деления, с которым обычно работают арифметические кодировщики.

  • shodan

    > Скорость декодировки и степень сжатия сильно лучше Хаффмана, куда денется.

    А что по сравнению с классической арифметикой и прочим range coder?

  • IronPeter

    Степень сжатия хуже на епсилон. Доли процента. Скорость – ну наверное такая же. Там то же самое целочисленное деление, только замененное на float (или fixed) point умножение.

  • IronPeter

    ну еще ввод-вывод побайтовый, а не битовый, оно все веселее.