Исследование кода Голомба
- Реализовать кодер и декодер кода Голомба.
- Реализовать источник, на выходе которого наблюдаются случайные величины, полученные из геометрического распределения.
- Сжать выход источника кодом Голомба, выполнить декодирование и сравнить декодированный поток со входом кодера.
- Найти оптимальный параметр кода Голомба.
- Сравнить полученную скорость кода Голомба с оценкой энтропии.
- Сделать вывод о влиянии параметра кода Хаффмана на скорость кода.
Исследование кода Хаффмана
- Реализовать кодер и декодер кода Хаффмана.
- Реализовать Марковский источник.
- Сжать выход Марковского источника в предположении, что символы получены из дискретного стационарного источника без памяти. Сжатие выполнить за два прохода. На первом проходе оценить распределение вероятностей и построить таблицу кода. На втором проходе выполнить сжатие.
- Выполнить декодирование, сравнить декодированный поток со входом кодера.
- Сжать выход Марковского источника, оценив матрицу переходных вероятностей по выходу источника. Сжатие выполнить за два прохода. На первом проходе оценить матрицу переходных вероятностей и построить таблицы для кода Хаффмана. На втором проходе выполнить сжатие.
- Выполнить декодирование, сравнить декодированный поток со входом кодера.
- Сжать выход Марковского источника, используя истинную матрицу переходных вероятностей.
- Выполнить декодирование, сравнить декодированный поток со входом кодера.
- Сделать вывод.
Исследование арифметического кодирования
- Реализовать дискретный стационарный источник без памяти.
- Реализовать арифметический кодер и декодер.
- Сжать выход дискретного стационарного источника без памяти, используя истинное распределение вероятностей и оцененное по потоку распределение вероятностей.
- Проанализировать скорость арифметического кода при использовании неправильного распределения вероятностей.
- Выполнить задания предыдущего пункта (исследование кода Хаффмана), используя арифметическое кодирование.
Исследование алгоритма сжатия PPM
- Реализовать арифметические кодер и декодер, использующие контекстное моделирование на основе PPM.
- Скачать данные для сжатия с сайта и проанализировать эффективность кодирования для различных параметров PPM.
Исследование словарных методов сжатия
- Реализовать кодер и декодер в соответствии с алгоритмами LZ77 и LZ78.
- Проанализировать эффективность кодирования на данных из предыдущего задания.
Исследование эффективности сжатия на реальных данных
Выполнить анализ всех реализованных алгоритмов при сжатии данных с соревнования на приз Хаттера. Данные для сжатия можно скачать с официальной страницы соревнования (enwik8).