Популярный метод сжатия данных. Присваивает «наилучшие» коды переменной длины множеству символов в зависимости от их вероятностей. Лежит в основе многих известных программ сжатия файлов на персональных компьютерах. Некоторые из них непосредственно применяют метод Хаффмана, а другие используют его как один из шагов многоступенчатого алгоритма компрессии.

Метод Хаффмана чем-то похож на метод Шеннона-Фано. В общем случае он производит лучшие коды, и подобно методу Шеннона-Фано эти коды являются наилучшими, когда вероятности символов в точности равны отрицательным степеням числа 2. Основное различие между этими двумя методами состоит в том, что метод Шеннона-Фано строит коды сверху вниз (от самого левого к самому правому биту), а метод Хаффмана выстраивает свои коды с помощью дерева, направляясь вверх (то есть, код выписывается справа налево).

Коды. Кодом называется символ, который подставляется на место другого символа. В компьютерных и телекоммуникационных приложениях коды всегда являются двоичными числами. Стандартом де-факто выступает код ASCII. Многие новые приложения поддерживают кодовый стандарт UNICODE, а более старый стандарт EBCDIC все еще применяется в компьютерах IBM.

Коды Грея. Двоичные коды для представления натуральных чисел. Коды любых двух последовательных чисел различаются ровно на 1 бит. Эти коды используются при разделении изображений с градацией серого на битовые слои, каждый из которых становится двухуровневым изображением. Коды переменной длины. Используются в статистических методах сжатия.
Эти коды должны удовлетворять свойству префикса и они присваиваются входным символам в соответствии с их вероятностями. Конференция по сжатию данных (Data Compression Conference, DCC). Конференция для исследователей и разработчиков в области сжатия данных. DCC происходит ежегодно в городе Сноуберд, штат Юта, США. Она происходит в марте и длится три дня.

Корреляция. Статистическая мера линейной зависимости между двумя парными величинами. Эта величина меняется от -1 (совершенная отрицательная зависимость), через 0 (отсутствие зависимости) и до +1 (совершенная положительная зависимость).

Коэффициент сжатия. Важная величина, которая постоянно используется для определения эффективности метода сжатия. Она равна частному размеру выходного файла. Коэффициент сжатия. Коэффициент 0.6 означает, что сжатые данные занимают 60% от исходного размера. Значения большие 1 говорят о том, что вых
одной файл больше входного (отрицательное сжатие). Иногда величина равная 100 х (1 — коэффициент сжатия) используется для определения качества сжатия. Значение, равное 60, означает, что выходной поток занимает 40% от объема исходного потока (то есть, при сжатии освободилось 60% объема).

Коэффициент усиления сжатия. Это число определяется формулой. Контрольный размер - это либо размер входного потока, либо размер сжатого файла, произведенного некоторым эталонным методом сжатия. Методы LZ. Все словарные методы сжатия основаны на работах Я.Зива (J.Ziv) и А.Лемпэла (A.Lempel), опубликованных в 1977 и 1978 гг. С тех пор эти методы принято подразделять на методы LZ77 и LZ78. Эти замечательные идеи вдохновили многих исследователей, которые обобщали, улучшали и комбинировали их, например, с методом RLE или со статистическими алгоритмами. В результате появилось огромное число известных адаптивных методов сжатия текстов, изображений и звука.

Методы LZSS. Это вариант метода LZ77 был разработан Сторером (Storer) и Сжимански (Szymanski) в 1982 [Storer 82]. Базовый алгоритм был улучшен по трем направлениям: (1) буфер упреждения сохранялся в циклической очереди, (2) буфер поиска (словарь) хранился в виде дерева двоичного поиска и (3) метки имели два поля, а не три.

Методы LZW. Это популярная версия алгоритма LZ78 была разработана Терри Уэлчем (Terry Welch) в 1984. Его главной особенностью является удаление второго поля из метки. Метка LZW состоит только из указателя на место в словаре. В результате такая метка всегда кодирует строку из более чем одного символа.

Модель сжатия LZW. Модель является методом предсказания (или прогнозирования вероятности) данных, которые необходимо сжать. Эта концепция весьма важна при статистическом сжатии данных. При использовании статистического сжатия модель необходимо построить до начала процесса сжатия.

В простейшей модели происходит чтение всего входного потока и подсчет частоты появления каждого символа. После этого входной поток считывается повторно, символ за символом, и производится сжатие с учетом информации о вероятностной модели.

Важная особенность арифметического кодирования состоит в возможности отделения статистической модели (таблицы частот и вероятностей) от операций кодирования и декодирования. Например, легко закодировать первую половину потока данных с помощью одной модели, а вторую - с помощью другой модели.