Методы кодирования данных (Общая информации о сжатии данных)

Содержание:

Введение

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

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

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

Объектом исследования в данной работе является кодирование информации.

Предмет исследования – особенности методов кодирования данных.

Целью данной работы является анализ особенностей и методов кодирования информации.

Для достижения данной цели необходимо решить следующие задачи:

- изучить основы и сущность кодирования информации;

- изучить методологию и особенности методов кодирования информации;

- проанализировать эффективность методов кодирования информации.

Методологическую основу данного исследования составили такие методы как анализ, синтез, сравнение, обобщение, выделение, классификация, интерпретация и другие методы научного познания.

Структура работы. Данная работа состоит из введения, двух глав, заключения и списка использованной литературы.

Глава 1. Теоретические основы кодирования информации

Общая информации о сжатии данных

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

Как и в случае любой формы связи, сжатая передача данных работает только тогда, когда и отправитель, и получатель информации понимают схему кодирования. Например, этот текст имеет смысл только в том случае, если приемник понимает, что он предназначен для интерпретации как символов, представляющих английский язык^[1]. Аналогично, сжатые данные могут быть поняты только в том случае, если метод декодирования известен приемнику. Некоторые алгоритмы сжатия используют это свойство для шифрования данных во время процесса сжатия, так что декомпрессия может быть достигнута только уполномоченной стороной (например, с использованием пароля).

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

Существуют две основные категории алгоритмов сжатия: с потерями и без потерь. Алгоритмы сжатия с потерями включают в себя уменьшение размера файла, обычно путем удаления мелких деталей, требующих большого объема данных для хранения при полной точности.

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

Сжатие данных без потерь – это уменьшение размера файла, так что функция декомпрессии может восстановить исходный файл без потери данных. Сжатие данных без потерь используется повсеместно в вычислениях, от экономии места на вашем персональном компьютере до отправки данных через Интернет, общении по защищенной оболочке или просмотра изображения PNG или GIF.

Основным принципом, на котором работают алгоритмы сжатия без потерь, является то, что любой неслучайный файл будет содержать дублируемую информацию, которая может быть сжата с использованием методов статистического моделирования, которые определяют вероятность появления символа или фразы. Эти статистические модели могут затем использоваться для генерации кодов для конкретных символов или фраз на основе их вероятности возникновения и назначения кратчайших кодов наиболее распространенным данным. Такие методы включают энтропийное кодирование, кодирование по длине и сжатие с использованием словаря. Используя эти методы и другие, 8-битные символы или последовательность таких символов могут быть представлены всего несколькими битами, что приводит к удалению большого количества избыточных данных^[2].

Когда вы хотите отправить сообщение, вам нужно перевести его на язык, который компьютер поймет. Компьютер использует только 0 и 1. Это называется двоичным. Процесс ввода сообщения типа «привет» в 0 и 1 называется кодировкой.

Двоичный способ представляет любое число, используя только 0 и 1. Он называется системой номеров «base 2». Чтобы понять это, нужно сделать шаг назад и подумать о том, как мы обычно представляем числа.

В повседневной жизни мы используем систему номеров «base 10». Это называется «базой 10», потому что мы используем 10 номеров: 0,1,2,3,4,5,6,7,8,9. Если вы хотите представить число выше 9, вам нужно добавить дополнительную цифру. Дополнительная цифра показывает, сколько из них 10. Таким образом, число 27 означает, что у вас есть 2 лота из десяти (представлены первой цифрой) и 7 лотов один (обозначается второй цифрой). Если я хочу представить число выше 99, мне нужно добавить еще одну цифру. Третья цифра представляет собой сумму в 100 единиц в номере. Четвертая цифра показывает, сколько 1000 есть и так далее.

Конечно, мы обычно не делаем этого, потому что это здравый смысл, но нести меня. Каждая дополнительная цифра, которую мы используем в 'base 10', всегда в 10 раз превышает предыдущую цифру. Это не случайность. Если вы решите использовать 10 номеров (0 ... 9), каждая новая цифра должна всегда быть в 10 раз больше предыдущей цифры.

Например, система номеров «базовая 7» использует только 7 номеров 0,1,2,3,4,5,6. Число 8 бессмысленно в базе 7. Это означает, что если я хочу представить число выше 6, мне нужно использовать новую цифру. На этот раз новая цифра показывает, сколько я использую 7. Так, например, число 8 будет написано «11» в базе 7. Первая цифра говорит, что я использую 1 семь, а вторая цифра говорит, что я использую 1. Третья цифра в базе 7 будет в 7 раз больше предыдущей цифры, поэтому она будет представлять собой 49 (7 × 7). Четвертая цифра будет представлять собой 7 × 49 = 343.

По техническим причинам компьютеры говорят в «базе 2», это означает, что используются только 2 числа: 0 и 1. Продолжая логику предыдущих примеров, каждая новая цифра всегда в 2 раза больше, чем предыдущая. Первая цифра представляет 1, вторая цифра представляет 2, третья цифра представляет 4, четвертую 8, пятую 16 и так далее. Как и раньше, мы можем сделать таблицу для перевода двоичного числа в распознаваемое число.

Вычисление числа в двоичном формате очень просто, вы просто добавляете значения цифр, которые имеют «1» под ними. Таким образом, 100110 равно 32 + 4 + 2 = 38. Помните: вы можете представлять любое число в двоичном формате. Попробуйте сами, подумайте о числе от 0 до 63 и узнайте их двоичное представление, используя таблицу выше.

Когда мы говорим о компьютерах и двоичных, немного меняем цифру. Таким образом, двоичное число, составляющее 10 цифр, составляет 10 бит. Сжатие данных предполагает использование как можно большего количества бит.

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

Компьютеры говорят в двоичном формате, но двоичный - это просто способ представления чисел. Предположим, необходимо кодировать алфавит в двоичном формате, чтобы компьютер мог его понять. Алфавит составляет 26 букв в длину, поэтому нужно, чтобы количество бит составляло до 26. С 4 битами наибольшее число - «1111», которое равно 8 + 4 + 2 + 1 = 15, поэтому мы не можем использовать 4 бита. С 5 битами (16, представляющими крайний левый бит) наибольшее число равно «11111», что равно 16 + 8 + 4 + 2 + 1 = 31. Поскольку 26 меньше 31, это означает, что мы можем представлять алфавит с 5 битами. Затем мы можем кодировать алфавит в двоичном виде обычным образом: a = 1, b = 2, c = 3 и т. Д. В двоичном выражении это будет означать a = 00001, b = 00010, c = 00011, d = 00100, e = 00101 и т. Д.

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

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

Однако внутренние файлы системы хранения, потоки Windows NT и метаданные тома не сжимаются.

История алгоритмов сжатия

С 1970-х годов, когда Интернет становился все более популярным, сжатие данных сыграло значительную роль в вычислениях, и были изобретены алгоритмы Lempel-Ziv, но он имеет гораздо более длительную историю за пределами вычислений. Код Морзе, изобретенный в 1838 году, является самым ранним экземпляром сжатия данных, поскольку наиболее распространенным буквам на английском языке, таким как «e» и «t», даются более короткие коды Морзе. Позже, когда компьютеры в мэйнфрейме начали действовать в 1949 году, Клод Шеннон и Роберт Фано изобрели кодировку Шеннон-Фано^[3]. Их алгоритм присваивает коды символам в данном блоке данных на основе вероятности появления символа. Вероятность появления символа обратно пропорциональна длине кода, что приводит к более короткому способу представления данных.

Два года спустя Дэвид Хаффман изучал теорию информации в Массачусетском технологическом институте и имел класс с Робертом Фано. Фано дал классу выбор написания курсовой работы или сдачи экзамена. Хаффман выбрал термин документ, который должен был найти наиболее эффективный метод двоичного кодирования. После нескольких месяцев работы и не придумав ничего, Хаффман собирался выбросить всю свою работу и начать учиться на выпускной экзамен вместо бумаги. Именно в этот момент у него было прозрение, выяснив очень похожий, но более эффективный метод кодирования Шеннон-Фано. Ключевое различие между кодированием Шеннон-Фано и кодированием Хаффмана заключается в том, что в первом случае дерево вероятности построено снизу вверх, создавая субоптимальный результат, а во втором - сверху вниз.

Ранние реализации кодирования Шеннон-Фано и Хаффмана выполнялись с использованием аппаратных и жесткокодированных кодов. Только в 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 года «Метод построения кодов минимальной избыточности»^[5].

Кодирование Хаффмана использует специальный метод для выбора представления для каждого символа, в результате чего получается код без префикса (то есть битовая строка, представляющая некоторый конкретный символ, никогда не является префиксом битовой строки, представляющей любой другой символ), который выражает наиболее распространенные символы, использующие более короткие строки бит, чем используются для менее распространенных исходных символов. Хаффман смог разработать наиболее эффективный метод сжатия этого типа: никакое другое сопоставление отдельных исходных символов с уникальными строками битов не приведет к меньшему среднему размеру выхода, когда фактические частоты символов согласуются с теми, которые используются для создания кода. Позднее было обнаружено, что метод выполняет это в линейном времени, если сортируются входные вероятности (также известные как веса).

Для набора символов с равномерным распределением вероятности и количеством членов, который является степенью двух, кодирование Хаффмана эквивалентно простому двоичному блочному кодированию, например кодированию ASCII. Кодирование Хаффмана - такой распространенный метод создания префикс-свободных кодов, что термин «код Хаффмана» широко используется как синоним «кода без префикса», даже если такой код не создается алгоритмом Хаффмана.

Хотя кодирование Хаффмана является оптимальным для кодирования по символам с известным распределением вероятностей ввода, его оптимальность иногда может быть непредсказуем. Например, арифметическое кодирование и кодирование LZW часто имеют лучшие возможности сжатия. Оба эти метода могут комбинировать произвольное количество символов для более эффективного кодирования и, как правило, адаптироваться к фактической входной статистике, последняя из которых полезна, когда входные вероятности не точно известны.

Адаптивное кодирование Хаффмана - это метод адаптивного кодирования, основанный на кодировании Хаффмана, создающий код при передаче символов, не имеющий первоначальных знаний об источнике распределения, который позволяет однопроходное кодирование и адаптацию к изменяющимся условиям в данных. Преимущество однопроходной процедуры заключается в том, что источник может быть закодирован в реальном времени, хотя он становится более чувствительным к ошибкам передачи, поскольку только одна потеря разрушает весь код.

Арифметическое кодирование - это метод сжатия данных без потерь. Это форма энтропийного кодирования, но в тех случаях, когда другие методы кодирования энтропии разделяют входное сообщение на его компонентные символы и заменяют каждый символ кодовым словом, арифметическое кодирование кодирует все сообщение в единственное число, причем доля n где (0.0 = n <1,0).

Глава 2. Практическая реализация кодирования информации

. Выбор среды разработки

PascalABC.NET - это интегрированная среда разработки на языке программирования Pascal, которая реализует классические функции языка Pascal, большинство языков Delphi, а также ряд собственных расширений. Он реализован на платформе .NET Framework и содержит все современные языковые функции: классы, перегрузку операторов, интерфейсы, обработку исключений, общие классы и подпрограммы, сбор мусора, лямбда-выражения, средства параллельного программирования (OpenMP только с 2016 года).

PascalABC.NET - это также простая и мощная среда разработки с интегрированным отладчиком, системой IntelliSense, дизайнером форм, шаблонами кода и автоматическим форматированием кода. Компилятор командной строки PascalABC.NET также доступен в Linux и MacOS (под Mono).

PascalABC.NET популярен в российских школах и университетах. В Южном федеральном университете он используется в качестве основного языка для обучения студентов информационным технологиям в курсе «Основы программирования» и для обучения детей в одной из крупнейших компьютерных школ России.

Справочник по программированию, разработанный профессором М. Э. Абрамяном, входит в состав PascalABC.NET. Эта книга содержит 1100 учебных заданий и охватывает почти все разделы базовой учебной программы.

Структура программы

Необходимо хранить узел шифрования, который бы содержал информацию о шифруемом символе, его вероятности и коде. Такую задачу с легкостью реализует следующая структура данных:

type Node = record

Letter: char;

Pi: double;

Code: string;

constructor Create(Letter: char; Pi: double; Code: string);

begin

Self.Letter := Letter;

Self.Pi := Pi;

Self.Code := Code;

end;

end;

Как можно видеть, запись содержит в себе следующие поля:

• символ;
• вероятность;
• код.

Также у структуры есть конструктор, который позволяет инициализировать поля записи.

Далее необходимо создать класс, который бы содержал в себе список таковых узлов, и, таким образом, имплементировал бы логику сжатия данных.

Собственно, в таковом классе необходимо реализовать следующее:

• список узлов;
• список слов;
• чтение файла;
• построение кода;
• нахождение медианы;
• печать построенного кода.

Алгоритм построения частотных вероятностей

Данный алгоритм может быть представлен в следующем виде:

1. Загрузить входной файл в оперативную память;
2. Читать все слова из входного файла;
3. Для каждого слова:
4. Для каждого символа в слове произвести поиск в списке узлов:
   1. Если в списке узлов присутствует данный символ – увеличить количество его на единицу;
   2. Иначе – добавить символ в список узлов с количеством равным единице.
5. Для каждого узла в списке узлов разделить вероятность на количество считанных символов из файла, получив таким образом вероятность каждого символа.

Алгоритм сжатия Метода-Фано

Данный алгоритм может быть представлен в следующем виде:

1. Если поданный входной список узлов содержит количество элементов меньше либо равного единице – досрочно прекратить процедуру;
2. Найти медиану для поданного на вход списка узлов;
3. Для каждого узла в входном списке узлов:
   1. если индекс итерации меньше медианы – добавить узел в левую ветку, иначе в правую.
4. Если левая или правая ветка пусты – досрочно прекратить процедуру;
5. Для каждого узла в входном списке узлов:
   1. если итерируемый узел есть в левой ветке – добавить к коду узла ‘0';
   2. если итерируемый узел есть в правой ветке – добавить к коду узла ‘1'.
6. Вызвать процедуру кодирования для левой и правой веток рекурсивно.

Процедура кодирования Шеннона-Фано доступна в процедуре code.

Построение вероятностей происходит во время чтения файла в процедуре readFile.

Полный код доступен далее:

type Node = record

Letter: char;

Pi: double;

Code: string;

constructor Create(Letter: char; Pi: double; Code: string);

begin

Self.Letter := Letter;

Self.Pi := Pi;

Self.Code := Code;

end;

end;

type SF = class

private

_nodes: List<Node>;

_words: List<string>;

procedure sortNodes;

begin

for var i:= 0 to _nodes.Count - 2 do

begin

for var j:= 0 to _nodes.Count - i - 2 do

begin

if (_nodes[j].Pi < _nodes[j + 1].Pi) then

begin

var temp := _nodes[j];

_nodes[j] := _nodes[j + 1];

_nodes[j + 1] := temp;

end;

end;

end;

end;

function contains(c: char; nodes: List<Node>): boolean;

begin

for var i:= 0 to nodes.Count - 1 do

begin

if (nodes[i].Letter = c) then

begin

Result := true;

exit;

end;

end;

Result := false;

end;

function getIndex(c: char): integer;

begin

for var i:= 0 to _nodes.Count do

begin

if (_nodes[i].Letter = c) then

begin

Result := i;

exit;

end;

end;

Result := -1;

end;

procedure readFile(filename: string);

var input: text;

fileword: string;

allSize: integer;

begin

Assign(input, filename);

Reset(input);

while not eof (input) do

begin

read (input, fileword);

_words.Add(fileword);

allSize := allSize + fileword.Length;

for var i := 1 to fileword.Length do

begin

if (contains(fileword[i], _nodes) = false) then

begin

var newNode: Node := (Letter: fileword[i]; Pi: 1; Code: '');

_nodes.Add(newNode);

end

else

begin

var newNode: Node := (Letter: _nodes[getIndex(fileword[i])].Letter; Pi: _nodes[getIndex(fileword[i])].Pi + 1; Code: '');

_nodes[getIndex(fileword[i])] := newNode;

end;

end;

end;

close(input);

for var i:= 0 to _nodes.Count - 1 do

begin

var newNode: Node := (Letter: _nodes[i].Letter; Pi: _nodes[i].Pi / allSize; Code: '');

_nodes[i] := newNode;

end;

sortNodes;

end;

function getMedian(nodes: List<Node>): integer;

var accumulate, sum: double;

begin

sum := 0;

for var i:= 0 to nodes.Count - 1 do sum := sum + _nodes[i].Pi;

accumulate := 0;

for var i:= 0 to nodes.Count - 1 do

begin

accumulate := accumulate + _nodes[i].Pi;

if (accumulate > (sum / 2)) then begin Result := i; exit; end;

end;

Result := 0;

end;

procedure code(nodes: List<Node>; debug: boolean);

begin

if (nodes.Count <= 1) then exit;

var m := getMedian(nodes);

var leftBranch := new List<Node>;

var rightBranch := new List<Node>;

for var i:= 0 to nodes.Count - 1 do

begin

if (i <= m) then leftBranch.Add(nodes[i])

else rightBranch.Add(nodes[i]);

end;

if ((leftBranch.Count = 0) or (rightBranch.Count = 0)) then exit;

for var i:= 0 to _nodes.Count - 1 do

begin

if (contains(_nodes[i].Letter, leftBranch) = true) then

begin

var newNode: Node := (Letter: _nodes[i].Letter; Pi: _nodes[i].Pi; Code: _nodes[i].Code + '0');

_nodes[i] := newNode;

end;

if (contains(_nodes[i].Letter, rightBranch) = true) then

begin

var newNode: Node := (Letter: _nodes[i].Letter; Pi: _nodes[i].Pi; Code: _nodes[i].Code + '1');

_nodes[i] := newNode;

end;

end;

if (debug = true) then begin PrintNodes; readln(); end;

code(leftBranch, debug);

code(rightBranch, debug);

end;

public

constructor Create(filename: string);

begin

_nodes := new List<Node>;

_words := new List<string>;

readFile(filename);

end;

procedure PrintNodes;

begin

for var i:= 0 to _nodes.Count - 1 do

begin

writeFormat('Letter: {0, 3: s}', _nodes[i].Letter);

writeFormat(' Pi: {0, 10}', _nodes[i].Pi);

writeFormat(' Code: {0, 3: s}', _nodes[i].Code);

writeln;

end;

end;

procedure Code(debug: boolean);

begin

code(_nodes, debug);

end;

end;

begin

var s_f := new SF('data.txt');

s_f.code(false);

s_f.PrintNodes;

end.

Заключение

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

• чтение данных из внешнего файла;
• построение вероятностей встречаемости символов;
• кодирование;
• отображение данных.

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

Реализованная программа на языке Pascal ABC позволяет не только в наглядном виде посмотреть, как происходит процедура кодирования, но, благодаря объектно-ориентированной парадигме и продуманной детализированности – понять, как должны строится и функционировать программы.

Список использованных источников

1. Инженерная и технологическая свободная энциклопедия. Сжатие данных. [Электронный ресурс] Режим доступа: http://ethw.org/History_of_Lossless_Data_Compression_Algorithms
2. Лемпель А. “Универсальные алгоритмы сжатия данных”. IEEE Transactions on Information Theory, Vol. 23, No. 3 (1977), pp. 337-343.
3. Свободная энциклопедия. Pascal ABC. [Электронный ресурс]. Режим доступа: https://en.wikipedia.org/wiki/PascalABC.NET
4. Теоретическая информация о сжатии данных. [Электронный ресурс]. Режим доступа: https://www.maximumcompression.com/algoritms.php
5. Сжатие данных: Джесси Рассел — Санкт-Петербург, Книга по Требованию, 2012 г.- 62 с.
6. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео: Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин — Москва, Диалог-МИФИ, 2003 г.- 384 с.
7. Сжатие данных, речи, звука и изображений в телекоммуникационных системах: B. C. Сергеенко, В. В. Баринов — Москва, РадиоСофт, 2009 г.- 360 с.
8. Сжатие данных: Джесси Рассел — Санкт-Петербург, Книга по Требованию, 2012 г.- 62 с.
9. Brandenburg, Heinz K., Stoll G. (1994) "ISO-MPEG-1 Audio: A Generic Standard for Coding of High-Quality Digital Audio," Journal of the Audio Engineering Society, 42(10):780-792, October.
10. Feig E.N., Linzer E. (1990) "Discrete Cosine Transform Algorithms for Image Data Compression," in Proceedings Electronic Imaging '90 East, pp. 84-87, Boston, MA.

1. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео: Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин — Москва, Диалог-МИФИ, 2003 г.- с. 57 ↑

2. Сжатие данных: Джесси Рассел — Санкт-Петербург, Книга по Требованию, 2012 г.- с.38 ↑

3. Теоретическая информация о сжатии данных. [Электронный ресурс]. Режим доступа: https://www.maximumcompression.com/algoritms.php ↑

4. Инженерная и технологическая свободная энциклопедия. Сжатие данных. [Электронный ресурс] Режим доступа: http://ethw.org/History_of_Lossless_Data_Compression_Algorithms ↑

5. Теоретическая информация о сжатии данных. [Электронный ресурс]. Режим доступа: https://www.maximumcompression.com/algoritms.php ↑