Файл: Методы кодирования данных (Общая информации о сжатии данных).pdf
Добавлен: 31.03.2023
Просмотров: 243
Скачиваний: 3
Теоретический фон сжатия обеспечивается теорией информации (которая тесно связана с алгоритмической теорией информации) и теорией скорости искажения. Эти области исследований были по существу созданы Клодом Шенноном, который опубликовал фундаментальные документы по этой теме в конце 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), которые формируются из модели нулевого порядка.