Файл: Методы кодирования данных (Общая информации о сжатии данных).pdf
Добавлен: 31.03.2023
Просмотров: 240
Скачиваний: 3
Введение
При обработке сигналов данных или кодирования источника данных предполагает кодирование с использованием меньшего количества бит, чем исходное представление. Сжатие может быть либо с потерями, либо без потерь. Сжатие без потерь сокращает биты путем выявления и устранения статистической избыточности. Никакая информация не теряется при сжатии без потерь. Сжатие уменьшает количество битов, удаляя ненужную или менее важную информацию.
Процесс уменьшения размера файла данных часто называют сжатием данных. В контексте передачи данных он называется кодированием источника; кодирование, выполняемое в источнике данных, до того, как оно будет сохранено или передано. Исходное кодирование не следует путать с канальным кодированием, для обнаружения ошибок и коррекции или линейного кодирования, средством для преобразования данных в сигнал.
Сжатие полезно, поскольку оно уменьшает ресурсы, необходимые для хранения и передачи данных. Вычислительные ресурсы потребляются в процессе сжатия и, как правило, при обращении процесса (декомпрессии). Сжатие данных подвержено компромиссу в пространстве-времени. Например, для схемы сжатия для видео может потребоваться дорогостоящее аппаратное обеспечение для того, чтобы видео было декомпрессировано достаточно быстро, чтобы его можно было разглядеть по мере его распаковки, а также возможность полностью распаковать видео, прежде чем смотреть его, может оказаться неудобным или потребовать дополнительного хранения. Конструкция схем сжатия данных включает компромиссы между различными факторами, включая степень сжатия, количество искажений, введенных (при использовании сжатия с потерями), и вычислительные ресурсы, необходимые для сжатия и распаковки данных.
Объектом исследования в данной работе является кодирование информации.
Предмет исследования – особенности методов кодирования данных.
Целью данной работы является анализ особенностей и методов кодирования информации.
Для достижения данной цели необходимо решить следующие задачи:
- изучить основы и сущность кодирования информации;
- изучить методологию и особенности методов кодирования информации;
- проанализировать эффективность методов кодирования информации.
Методологическую основу данного исследования составили такие методы как анализ, синтез, сравнение, обобщение, выделение, классификация, интерпретация и другие методы научного познания.
Структура работы. Данная работа состоит из введения, двух глав, заключения и списка использованной литературы.
Глава 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, этот алгоритм анализирует входные данные и генерирует статический словарь, а не генерирует его динамически.