Метод Хаффмана

История алгоритмов сжатия
С 1970-х годов, когда Интернет становился все более популярным, сжатие данных сыграло значительную роль в вычислениях, и были изобретены алгоритмы Lempel-Ziv, но он имеет гораздо более длительную историю за пределами вычислений. Код Морзе, изобретенный в 1838 году, является самым ранним экземпляром сжатия данных, поскольку наиболее распространенным буквам на английском языке, таким как «e» и «t», даются более короткие коды Морзе. Позже, когда компьютеры в мэйнфрейме начали действовать в 1949 году, Клод Шеннон и Роберт Фано изобрели кодировку Шеннон-Фано. Их алгоритм присваивает коды символам в данном блоке данных на основе вероятности появления символа. Вероятность появления символа обратно пропорциональна длине кода, что приводит к более короткому способу представления данных.
Два года спустя Дэвид Хаффман изучал теорию информации в Массачусетском технологическом институте и имел класс с Робертом Фано. Фано дал классу выбор написания курсовой работы или сдачи экзамена. Хаффман выбрал термин документ, который должен был найти наиболее эффективный метод двоичного кодирования. После нескольких месяцев работы и не придумав ничего, Хаффман собирался выбросить всю свою работу и начать учиться на выпускной экзамен вместо бумаги. Именно в этот момент у него было прозрение, выяснив очень похожий, но более эффективный метод кодирования Шеннон-Фано. Ключевое различие между кодированием Шеннон-Фано и кодированием Хаффмана заключается в том, что в первом случае дерево вероятности построено снизу вверх, создавая субоптимальный результат, а во втором - сверху вниз.
Ранние реализации кодирования Шеннон-Фано и Хаффмана выполнялись с использованием аппаратных и жесткокодированных кодов. Только в 1970-х годах и пришествии Интернета и онлайн-хранилища было реализовано сжатие программного обеспечения, что коды Хаффмана динамически генерировались на основе входных данных. Позже, в 1977 году, Абрахам Лемпель и Якоб Зив опубликовали свой новаторский алгоритм LZ77, первый алгоритм использования словаря для сжатия данных. Более конкретно, LZ77 использовал динамический словарь, часто называемый скользящим окном. В 1978 году тот же дуэт опубликовал свой алгоритм LZ78, который также использует словарь; в отличие от LZ77, этот алгоритм анализирует входные данные и генерирует статический словарь, а не генерирует его динамически.
Теоретический фон сжатия обеспечивается теорией информации (которая тесно связана с алгоритмической теорией информации) и теорией скорости искажения. Эти области исследований были по существу созданы Клодом Шенноном, который опубликовал фундаментальные документы по этой теме в конце 1940-х и начале 1950-х годов. Дойл и Карлсон (Doyle and Carlson, 2000) писали, что сжатие данных «имеет одну из простейших и самых элегантных дизайнерских теорий во всей технике». Теория криптографии и кодирования также тесно связана. Идея сжатия данных глубоко связана со статистическими выводами.
Многие системы сжатия данных без потерь можно рассматривать в терминах четырехступенчатой ​​модели. Системы потери данных с потерями обычно включают еще больше этапов, включая, например, прогнозирование, преобразование частоты и квантование.
Методы сжатия Lempel-Ziv (LZ) являются одними из самых популярных алгоритмов для хранения без потерь. DEFLATE - это вариация на LZ, которая оптимизирована для скорости декомпрессии и степени сжатия, хотя сжатие может быть медленным. DEFLATE используется в PKZIP, gzip и PNG. LZW (Lempel-Ziv-Welch) был запатентован Unisys до июня 2003 года и используется в изображениях GIF. Также следует упомянуть методы LZR (LZ-Renau), которые служат основой метода Zip. В методах LZ используется модель сжатия на основе таблицы, в которой записи таблицы заменяются повторяющимися строками данных. Для большинства методов LZ эта таблица генерируется динамически из более ранних данных на входе. Сама таблица часто кодируется Хаффманом (например, SHRI, LZX). Две действующие схемы кодирования на основе LZ, которые хорошо работают, - LZX, используемые в формате CAB Microsoft, и LZMA, используемые в популярном архиваторе 7-Zip.
Самые лучшие компрессоры используют вероятностные модели, предсказания которых связаны с алгоритмом, называемым арифметическим кодированием. Арифметическое кодирование, изобретенное Йормой Риссаненом и превратившееся в практический метод Виттена, Нила и Клири, обеспечивает превосходное сжатие для более известного алгоритма Хаффмана и особенно хорошо подходит для адаптивных задач сжатия данных, где предсказания сильно зависят от контекста, зависимый. Арифметическое кодирование используется в стандартном стандарте сжатия JBIG, а также стандарте сжатия документа DjVu.
Общий алгоритм Шеннона-Фано
В сегодняшнем мире оцифровки все данные, которые должны быть обработаны, переданы или получены, должны содержать как минимум биты. Таким образом, чтобы уменьшить бит или сжать данные, существует несколько методов, один из которых называется алгоритмом Шеннон-Фано, в котором строится префиксный код на основе набора символов и их вероятностей или частоты.
В алгоритме Шеннон-Фано сортировка символов выполняется в соответствии с их частотой или возникновением. Затем эти отсортированные символы с их появлением делятся на две части по их вероятностям. Первая часть – это наивысший вероятный символ, а вторая часть – остальные символы, и теперь эти оставшиеся символы снова разделяются на две части, одна часть является вторым наивысшим вероятным символом, а вторая часть остается другими символами, таким образом все символы разделяется одним и тем же итерационным процессом и после деления всех символов отдельно, теперь назначаем биты этой последовательности. В ней первая часть, которая разделена на две части, в которых наивысший вероятный символ назначает одним битом «0», а оставшаяся часть назначается бит «1», а аналогично на второй итерации второй наивысший вероятный символ снова присваивается «0», а оставшаяся часть назначается «1» таким образом, биты присваиваются этому дереву.
При кодировании каждого символа мы следуем по пути от вершины к соответствующему символу и принимаем все биты этого пути, чтобы генерировать надлежащие закодированные биты для этого символа. Итак, теперь мы можем заметить, что первый наивысший вероятный символ присваивает «0», второй наивысший вероятный символ, закодированный до «10», третий наивысший вероятный символ, закодированный до «110», четвертый наивысший вероятный символ, закодированный до «1110». Таким образом, мы закодировал весь символ данных, чтобы уменьшить бит, и, наконец, мы можем проверить, подсчитав все биты закодированного символа, что наши результирующие данные сжаты.
Будущее для кодирования информации
Будущее никогда не бывает достоверным, но на основе текущих тенденций могут быть сделаны некоторые прогнозы относительно того, что может произойти в будущем при сжатии данных. Алгоритмы смешивания, такие как PAQ и его варианты, начали привлекать популярность, и они, как правило, достигают наивысших коэффициентов сжатия, но обычно медленны. Благодаря экспоненциальному увеличению аппаратной скорости, следуя закону Мура, алгоритмы смешения контекста, вероятно, будут процветать, поскольку штрафы за скорость преодолеваются за счет более быстрого оборудования из-за их высокой степени сжатия^[4].
Алгоритм, который PAQ стремился улучшить, называемый Prediction by Partial Matching (PPM), также может видеть новые варианты. Наконец, алгоритм цепи Лемпеля-Зива Маркова (LZMA) неизменно показал себя превосходным компромиссом между скоростью и высокой степенью сжатия и, скорее всего, породит больше вариантов в будущем. LZMA может даже быть «победителем», поскольку она еще более развита, уже принятая в многочисленных конкурирующих форматах сжатия, поскольку она была введена в формате 7-Zip. Еще одной потенциальной разработкой является использование сжатия с помощью подстановки подстроки (CSE), которая является восходящей технологией сжатия, которая еще не видела многих программных реализаций. В своей наивной форме он работает аналогично bzip2 и PPM, а исследователи работают над повышением эффективности.
Универсальный метод кодирования
Невозможно создать единый метод сжатия для всех типов данных без какого-либо знания последовательности. Также невозможно подготовить другой алгоритм сжатия для каждой возможной последовательности. Разумный выбор заключается в том, чтобы изобрести алгоритм сжатия данных для некоторого общего источника классов и использовать такой алгоритм для последовательностей, которые можно кодировать с высокой точность, как выходы предполагаемого источника.
Типичные последовательности, появляющиеся в реальном мире, содержат тексты, базы данных, изображения, двоичные данные. Марковские источники, источники FSM конечного порядка, источники FSMX и контекст источников дерева были изобретены для моделирования таких реальных последовательностей. Обычно реальные последовательности могут быть успешно аппроксимированы в соответствии с этими источниками. Следовательно, оправдано называть алгоритмы, предназначенные для эффективной работы с последовательностями, произведеннымитакими источниками универсальными.
Иногда, перед процессом сжатия, полезно транспонировать последовательность в некотором роде, чтобы лучше соответствовать предположению. Например, фото данные часто разлагаются до сжатия. Это означает, что каждый цветной компонент (красный, зеленый и синий) сжимается отдельно. Универсальные алгоритмы сжатия в общем случае не включают такие предварительные транспозиции.
Одним очень простым средством сжатия является кодирование по длине, при котором большие пробеги последовательных идентичных значений данных заменяются простым кодом с указанием значения данных и длины прогона. Это пример сжатия данных без потерь. Он часто используется, чтобы лучше использовать дисковое пространство на офисных компьютерах или лучше использовать пропускную способность соединения в компьютерной сети. Для символических данных, таких как электронные таблицы, тексты, исполняемые программы и т. Д., Без потерь важны, поскольку нельзя переносить даже один бит (за исключением некоторых ограниченных случаев).
Для визуальных и аудиоданных некоторые потери качества можно допускать без потери существенного характера данных. Воспользовавшись ограничениями сенсорной системы человека, можно сэкономить много места, производя вывод, который почти неотличим от оригинала. Эти методы сжатия данных с потерями обычно предлагают трехстороннюю компромисс между скоростью сжатия, сжатым размером данных и потерей качества.
Сжатие изображения с потерями используется в цифровых камерах, что значительно увеличивает их емкость памяти, в то же время ухудшая качество изображения. Аналогично, DVD-диски используют кодек с потерями MPEG-2 для сжатия видео.
При сжатии с потерями звука методы психоакустики используются для удаления не слышимых (или менее слышимых) компонентов сигнала. Сжатие человеческой речи часто выполняется с еще более специализированными методиками, поэтому «речевое сжатие» или «голосовое кодирование» иногда выделяется как отдельная дисциплина, чем «сжатие звука». В аудио кодеках перечислены различные стандарты сжатия звука и речи. Например, сжатие голоса используется в интернет-телефонии, в то время как сжатие аудио используется для копирования CD и декодируется MP3-плеерами.
Кодировка длины пробега (RLE) - это очень простая форма сжатия данных, в которой запуски данных (то есть последовательности, в которых одно и то же значение данных встречается во многих последовательных элементах данных) сохраняются как одно значение и количество данных, а не как оригинальный запуск. Это наиболее полезно для данных, которые содержат много таких прогонов: например, простые графические изображения, такие как значки и линейные чертежи.
Например, рассмотрим экран, содержащий простой черный текст на сплошном белом фоне. В пробеле будет много длинных бегущих пикселей и много коротких прогонов черных пикселей внутри текста. Возьмем гипотетическую линию одиночного сканирования, причем B представляет черный пиксель, а W представляет белый:
WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWB
Если мы применим простой код длины строки к указанной гипотетической строке сканирования, мы получим следующее:
12WB12W3B24WB
Интерпретируйте это как двенадцать W, один B, двенадцать W, три B и т. Д.
Код длины выполнения представляет исходные 53 символа всего 13. Конечно, фактический формат, используемый для хранения изображений, обычно двоичный, а не ASCII-символы, подобные этому, но принцип остается тем же. С помощью этого метода могут быть сжаты даже двоичные файлы данных; спецификации формата файла часто диктуют повторяющиеся байты в файлах как пространство заполнения. Однако более новые методы сжатия, такие как дефляция, часто используют алгоритмы на основе LZ77, обобщение кодирования по длине, которое может использовать прогоны строк символов (таких как BWWBWWBWWWWWW).
Кодировка длины пробега выполняет сжатие данных без потерь и хорошо подходит для знаковых изображений на основе палитры. Он вообще не работает на непрерывных тонах, таких как фотографии, хотя JPEG довольно эффективно использует коэффициенты, которые остаются после преобразования и квантования блоков изображения. RLE используется в факсимильных аппаратах (в сочетании с другими методами в кодировке Modified Huffman). Он относительно эффективен, потому что большинство факсовых документов в основном являются белым пространством, со случайными прерываниями черного.
Данные, имеющие длинные последовательные байты (например, более качественные образцы звука), могут быть сжаты RLE после применения прогностического фильтра, такого как дельта-кодирование.
Кодировщик словаря, также иногда известный как подстановочный кодер, представляет собой любое из нескольких алгоритмов сжатия без потерь, которые работают путем поиска совпадений между сжатым текстом и набором строк, содержащихся в структуре данных (так называемый «словарь», ), поддерживаемый кодером. Когда кодер находит такое совпадение, он заменяет ссылку на позицию строки в структуре данных.
Некоторые словарные кодеры используют «статический словарь», один из которых полный набор строк определяется до начала кодирования и не изменяется во время процесса кодирования. Этот подход чаще всего используется, когда сообщение или набор сообщений, подлежащих кодированию, являются фиксированными и большими; например, многие программные пакеты, которые хранят содержимое Библии в ограниченном пространстве памяти КПК, обычно создают статический словарь с согласованием текста, а затем используют этот словарь для сжатия стихов.
Более распространенными являются методы, в которых словарь запускается в некотором предопределенном состоянии, но содержимое изменяется во время процесса кодирования на основе данных, которые уже были закодированы. Оба алгоритма LZ77 и LZ78 работают по этому принципу. В LZ77 структура данных, называемая «скользящим окном», используется для хранения последних N байтов обрабатываемых данных; это окно служит в качестве словаря, эффективно сохраняя каждую подстроку, которая появилась в прошлых N байтах как словарные записи. Вместо одного индекса, определяющего запись словаря, необходимы два значения: длина, указывающая длину совпадающего текста, и смещение (также называемое расстоянием), указывающее, что совпадение найдено в скользящем окне, начинающем смещение байтов до текущий текст.
PPM - это метод адаптивного статистического сжатия данных, основанный на контекстном моделировании и прогнозировании. Название означает Prediction by Partial Matching. Модели PPM используют набор предыдущих символов в несжатом потоке символов для прогнозирования следующего символа в потоке.
Прогнозы обычно сводятся к ранжированию символов. Число предыдущих символов n определяет порядок модели PPM, который обозначается как PPM (n). Неограниченные варианты, в которых контекст не имеет ограничений по длине, также существуют и обозначаются как PPM *. Если предсказание не может быть сделано на основе всех n контекстных символов, то прогнозируется попытка только с n-1 символами. Этот процесс повторяется до тех пор, пока не будет найдено совпадение, или больше символов не останется в контексте. В этот момент производится фиксированное предсказание. Этот процесс является обратным тому, за которым следуют алгоритмы сжатия DMC (Dynamic Markov Chain), которые формируются из модели нулевого порядка.
Большая часть работы по оптимизации модели PPM - это обработка входных данных, которые еще не встречались во входном потоке. Очевидным способом их обработки является создание «невидимого» символа, который запускает escape-последовательность. Но какую вероятность следует присвоить символу, который никогда не видел? Это называется проблемой с нулевой частотой. Один вариант присваивает «неизведанному» символу фиксированное количество псевдо-хитов. Вариант, называемый PPM-D, увеличивает каждый раз, когда используется символ «невидимый», псевдо-хит «невидимого» символа. (Другими словами, PPM-D оценивает вероятность появления нового символа как отношения числа уникальных символов к общему количеству наблюдаемых символов).
Реализации сжатия PPM сильно различаются в других деталях. Фактический выбор символа обычно записывается с использованием арифметического кодирования, хотя также возможно использовать кодировку Хаффмана или даже какой-либо метод кодирования словаря. Базовая модель, используемая в большинстве алгоритмов PPM, также может быть расширена для прогнозирования нескольких символов. Также возможно использовать немарковское моделирование для замены или дополнения марковского моделирования. Размер символа обычно статичен, как правило, один байт, что упрощает общую обработку любого формата файла.
Опубликованные исследования этого семейства алгоритмов можно найти еще в середине 1980-х годов. Реализация программного обеспечения не пользовалась популярностью до начала 1990-х годов, потому что алгоритмы PPM требуют значительного объема оперативной памяти. Последние реализации PPM являются одними из наиболее эффективных программ сжатия без потерь для текста естественного языка.
Энтропийное кодирование представляет собой схему кодирования, которая присваивает коды символам, чтобы соответствовать длинам кодов с вероятностями символов. Как правило, энтропийные кодеры используются для сжатия данных путем замены символов, представленных кодами равной длины, символами, представленными кодами, где длина каждого кодового слова пропорциональна отрицательному логарифму вероятности. Поэтому в наиболее распространенных символах используются кратчайшие коды.
Согласно исходной кодовой теореме Шеннона, оптимальная длина кода для символа -logbP, где b - количество символов, используемых для создания выходных кодов, а P - вероятность ввода символа.
Двумя из наиболее распространенных методов энтропийного кодирования являются кодирование Хаффмана и арифметическое кодирование. Если приблизительные энтропийные характеристики потока данных известны заранее (особенно для сжатия сигнала), может оказаться полезным более простой статический код, такой как унарное кодирование, гамма-кодирование Elias, кодирование Фибоначчи, кодирование Голомба или кодирование Rice.
В информатике и теории информации кодирование Хаффмана является алгоритмом энтропийного кодирования, используемым для сжатия без потерь данных. Термин относится к использованию таблицы кодов переменной длины для кодирования исходного символа (например, символа в файле), где таблица кодов переменной длины была получена определенным образом на основе предполагаемой вероятности появления для каждого возможного значение символа источника. Он был разработан Дэвидом А. Хаффманом и опубликован в статье 1952 года «Метод построения кодов минимальной избыточности.
Кодирование Хаффмана использует специальный метод для выбора представления для каждого символа, в результате чего получается код без префикса (то есть битовая строка, представляющая некоторый конкретный символ, никогда не является префиксом битовой строки, представляющей любой другой символ), который выражает наиболее распространенные символы, использующие более короткие строки бит, чем используются для менее распространенных исходных символов. Хаффман смог разработать наиболее эффективный метод сжатия этого типа: никакое другое сопоставление отдельных исходных символов с уникальными строками битов не приведет к меньшему среднему размеру выхода, когда фактические частоты символов согласуются с теми, которые используются для создания кода. Позднее было обнаружено, что метод выполняет это в линейном времени, если сортируются входные вероятности (также известные как веса).
Для набора символов с равномерным распределением вероятности и количеством членов, который является степенью двух, кодирование Хаффмана эквивалентно простому двоичному блочному кодированию, например кодированию ASCII. Кодирование Хаффмана - такой распространенный метод создания префикс-свободных кодов, что термин «код Хаффмана» широко используется как синоним «кода без префикса», даже если такой код не создается алгоритмом Хаффмана.
Хотя кодирование Хаффмана является оптимальным для кодирования по символам с известным распределением вероятностей ввода, его оптимальность иногда может быть непредсказуем. Например, арифметическое кодирование и кодирование LZW часто имеют лучшие возможности сжатия. Оба эти метода могут комбинировать произвольное количество символов для более эффективного кодирования и, как правило, адаптироваться к фактической входной статистике, последняя из которых полезна, когда входные вероятности не точно известны.
Адаптивное кодирование Хаффмана - это метод адаптивного кодирования, основанный на кодировании Хаффмана, создающий код при передаче символов, не имеющий первоначальных знаний об источнике распределения, который позволяет однопроходное кодирование и адаптацию к изменяющимся условиям в данных. Преимущество однопроходной процедуры заключается в том, что источник может быть закодирован в реальном времени, хотя он становится более чувствительным к ошибкам передачи, поскольку только одна потеря разрушает весь код.
Арифметическое кодирование - это метод сжатия данных без потерь. Это форма энтропийного кодирования, но в тех случаях, когда другие методы кодирования энтропии разделяют входное сообщение на его компонентные символы и заменяют каждый символ кодовым словом, арифметическое кодирование кодирует все сообщение в единственное число, причем доля n где (0.0 = n <1,0).