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

Сжатие данных без потерь – это уменьшение размера файла, так что функция декомпрессии может восстановить исходный файл без потери данных. Сжатие данных без потерь используется повсеместно в вычислениях, от экономии места на вашем персональном компьютере до отправки данных через Интернет, общении по защищенной оболочке или просмотра изображения 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 и метаданные тома не сжимаются.