Кодирование Хаффмана — это алгоритм сжатия данных без потерь, который используется для сжатия данных таким образом, чтобы свести к минимуму количество битов, используемых для представления данных. Это широко используемый алгоритм, который считается одним из наиболее эффективных способов сжатия данных.
В этом сообщении в блоге я объясню, как работает кодирование Хаффмана и почему оно так полезно.
Алгоритм кодирования Хаффмана обычно используется во многих приложениях, включая передачу и хранение данных.
Символ в компьютере обычно представляется с помощью 8 битов, которые известны как байты. Это означает, что один символ можно сохранить, используя 8 бит или 1 байт памяти.
Схема кодирования ASCII использует 7 бит для представления символа, в то время как схема Unicode использует 16 бит на символ.
A имеет код ascii 65 и может быть представлен в битах как 01000001.
Предположим, у нас есть строка из 20 символов:
let str = "BACABABCCACDIAIDACAB";
Общее количество используемых битов: 20 X 8 бит = 160 бит.
нам нужно 160 бит для хранения строки длиной 20.
Он использует двоичное дерево для представления частоты символов в данном тексте. Первым шагом в процессе кодирования Хаффмана является вычисление частоты каждого символа в тексте. Двоичное дерево построено таким образом, что наиболее часто встречающиеся символы представляются более короткими битовыми строками, а менее часто встречающиеся символы представляются более длинными битовыми строками.
В нашей строке «BACABABCCACDIAIDACAB» у нас есть 5 повторяющихся символов, поэтому нам нужно максимум 3 бита для их хранения.
Как видите, мы можем представить каждый символ, используя 3 бита, и каждый символ имеет свой битовый код.
Теперь, если мы подсчитаем, сколько бит нам нужно, то это будет 20 X 3 бита = 60 бит.
Уменьшение размера со 160 до 60 бит.
у нас есть собственное битовое представление исходного сообщения.
Но вопрос в том, как другой человек узнает, просто взглянув на битовое представление сообщения, что именно оно означает?
Ответ таков: другой человек должен знать таблицу, которую мы использовали для сопоставления, чтобы сообщение было преобразовано обратно в исходный текст.
Итак, нам нужно отправить таблицу вместе с сообщением, чтобы ее было легко преобразовать. нам также нужно рассчитать размер таблицы.
- у нас есть 5 символов, которые нужно отправить в кодах ASCII, поэтому потребуется 5 X 8 = 40 бит.
- Для каждого пользовательского битового представления символа нам нужно: 5 X 3 бита = 15 бит.
- поэтому общее количество битов, необходимых для отправки сжатого сообщения с таблицей, составляет 60 + 40 + 15 = 115 бит.
Это также называется кодом фиксированного размера.
Кодирование Хаффмана использует оптимальный шаблон слияния. В нем говорится, что каждый алфавит должен быть расположен в порядке возрастания их появления. и объедините 2 самых маленьких, чтобы сделать узел.
- мы перечислили наши уникальные символы на основе их появления в порядке возрастания. Предположим, что каждый символ в базе является узлом.
- нам нужно объединить два самых маленьких узла, а затем создать узел.
- вот так выглядит наше дерево:
Теперь на основе этого дерева можно создать новую таблицу с динамическим размером кода. давай сделаем это:
Давайте разберемся, как мы создали коды:
мы начнем сверху, а затем будем двигаться вниз, чтобы добраться до нашего персонажа, и мы также будем отслеживать наш код.
- Чтобы получить код для символа А, давайте начнем сверху, чтобы добраться до А, нам нужно двигаться вниз. поэтому наш путь равен 1 и 1, поэтому наш код для A равен 11.
- Чтобы добраться до персонажа B сверху, нам нужно переместить 0 и 1.
- Аналогично для C:
- Для Д:
- Для меня:
если мы посчитаем сейчас, нам нужно:
2 бита для хранения A, B и C. 3 бита для хранения D и I.
Таким образом, общий размер сообщения составляет (7*2)+(4*2)+(5*2)+(2*3)+(2*3) = 44 бита.
И 40 бит для 5 символов плюс 12 бит для отправки новых кодов.
Общий размер нового сообщения вместе с таблицей составляет 96 бит.
Это также называется кодом динамического размера.
Заключение:
Кодирование Хаффмана — это метод сжатия данных, который включает в себя создание двоичного дерева символов и их частот для назначения более коротких кодовых слов более частым символам и более длинных кодовых слов менее частым символам. Это приводит к более эффективному способу кодирования данных, что приводит к уменьшению размера файла и сокращению времени передачи.
В целом кодирование Хаффмана является полезным методом сжатия данных и может применяться в широком диапазоне приложений.
