:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Сжатие и кодирование » Общие алгоритмы
  Общие алгоритмы cжатия и кодирования




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

Метод LZW-сжатия данных
LZW-сжатие выделяется среди прочих, когда встречается с потоком данных, содержащим повторяющиеся строки любой структуры ( текст, сжатие видеоформ и копий экранов). Сжатие однопроходное и может быть осуществлено 'на лету'.

Использование алгоритма расширяющегося префикса для кодирования и схожих пpоцессов
Статья дает описание арифметического кодирования с применением 'splay trees' - расширяющихся деревьев. C исходниками..

Сжатие по алгоритму Хаффмана
Старый, добрый двухпроходной Хаффман. Классика кодирования. Исходник прилагается.

RLE (Групповое кодирование)
Старейший двухпроходной алгоритм сжатия информации. Применяется только как дополнение к другим методам. Легок для освоения и реализации.

UUE-кодирование
Основные алгоритмы UUE-кодирования. Описание используемого при UUE CRC-алгоритма. Исходник прилагается.

Кодирование методом Шеннона-Фано

  Дополнительные материалы:




Модели в компрессии. Различные алгоритмы сжатия z i p
Общий обзор методов компрессии и моделей. Даны основные принципы работы многих известных алгоритмов.

Experiments on the Zero Frequency Problem z i p
The focus of this paper is the problem of transforming the set of counts accumulated for a particular context into a probability distribution. Довольно интересные общие рассуждения без конкретных алгоритмов.

Fast Text Compression Based on Quasi-Arithmetic Code z i p
Описан метод сжатия информации, лишь немного уступающий PPMC в сжатии, но сильно превосходящий по скорости.

Range encoding: an algorithm for removing redundancy z i p
Алгоритм для устранения избыточности сообщения. Больше интересно теоретически, нежели для практики.

Sub-Linear Decoding of Huffman Codes Almost in-place z i p
Сублинейное декодирование Хаффмана, требующее в несколько раз меньше памяти, нежели обычные реализации.

Flexible Parsing for Dynamic Dictionary Based Compression z i p
Улучшение обычного 'жадного' парсинга, заглядывающее назад. Как результат - на 35% улучшение по сравнению с обычным dynamic dictionary compression в gzip и compress.

A Rapid Entropy-Coding Algorithm z i p
Алгоритм entropy coding, сравнимый по быстродействию и скорости с Q- и QM-coder. С исходниками на Си.

Using Neural Networks for Nonlinear Predictive Coding z i p
Использование нейронных сетей для адаптивного сжатия информации. С исходниками.

A Generalization and Improvement to PPM's 'Blending' z i p
Улучшение одного из наиболее мощных методов адаптивной компрессии - PPM blending.