Краткий обзор основных теорий сжатия. Концепции идей и их реализация. Сжатие данных с использованием преобразования Барроуза-Вилера. Статический алгоритм Хафмана. Локально адаптивный алгоритм сжатия. Алгоритм Зива-Лемпеля (Welch) и метод Шеннона-Фано.
Аннотация к работе
кодов позволяет оптимизировать словарь и поднять эффективность сжатия. Главная алгоритмическая проблема здесь заключается в оптимальном выборе строк, так как это предполагает значительный объем переборов. Данный метод предполагает замену потока символов кодами, записанными в памяти в виде словаря (таблица перекодировки). Этой проблеме посвящено много книг, например, David Salomon, Giovanni Motta, Handbook of Data Compression, Springer, или Khalid Sayood, Introduction to data compression. Пусть сообщения m(1),…,m(n) имеют вероятности P(m(1)),… P(m(n)) и пусть для определенности они упорядочены так, что P(m(1)) і P(m(2)) і … і P(m(N)).