Методы кодирования источников (осень 2016)

Исследование кода Голомба

  1. Реализовать кодер и декодер кода Голомба.
  2. Реализовать источник, на выходе которого наблюдаются случайные величины, полученные из геометрического распределения.
  3. Сжать выход источника кодом Голомба, выполнить декодирование и сравнить декодированный поток со входом кодера.
  4. Найти оптимальный параметр кода Голомба.
  5. Сравнить полученную скорость кода Голомба с оценкой энтропии.
  6. Сделать вывод о влиянии параметра кода Хаффмана на скорость кода.

Исследование кода Хаффмана

  1. Реализовать кодер и декодер кода Хаффмана.
  2. Реализовать Марковский источник.
  3. Сжать выход Марковского источника в предположении, что символы получены из дискретного стационарного источника без памяти. Сжатие выполнить за два прохода. На первом проходе оценить распределение вероятностей и построить таблицу кода. На втором проходе выполнить сжатие.
  4. Выполнить декодирование, сравнить декодированный поток со входом кодера.
  5. Сжать выход Марковского источника, оценив матрицу переходных вероятностей по выходу источника. Сжатие выполнить за два прохода. На первом проходе оценить матрицу переходных вероятностей и построить таблицы для кода Хаффмана. На втором проходе выполнить сжатие.
  6. Выполнить декодирование, сравнить декодированный поток со входом кодера.
  7. Сжать выход Марковского источника, используя истинную матрицу переходных вероятностей.
  8. Выполнить декодирование, сравнить декодированный поток со входом кодера.
  9. Сделать вывод.

Исследование арифметического кодирования

  1. Реализовать дискретный стационарный источник без памяти.
  2. Реализовать арифметический кодер и декодер.
  3. Сжать выход дискретного стационарного источника без памяти, используя истинное распределение вероятностей и оцененное по потоку распределение вероятностей.
  4. Проанализировать скорость арифметического кода при использовании неправильного распределения вероятностей.
  5. Выполнить задания предыдущего пункта (исследование кода Хаффмана), используя арифметическое кодирование.

Исследование алгоритма сжатия PPM

  1. Реализовать арифметические кодер и декодер, использующие контекстное моделирование на основе PPM.
  2. Скачать данные для сжатия с сайта и проанализировать эффективность кодирования для различных параметров PPM.

Исследование словарных методов сжатия

  1. Реализовать кодер и декодер в соответствии с алгоритмами LZ77 и LZ78.
  2. Проанализировать эффективность кодирования на данных из предыдущего задания.

Исследование эффективности сжатия на реальных данных

Выполнить анализ всех реализованных алгоритмов при сжатии данных с соревнования на приз Хаттера. Данные для сжатия можно скачать с официальной страницы соревнования (enwik8).

Результаты