Как сжать данные с помощью кодирования Хаффмана: 10 шагов

Оглавление:

Как сжать данные с помощью кодирования Хаффмана: 10 шагов
Как сжать данные с помощью кодирования Хаффмана: 10 шагов

Видео: Как сжать данные с помощью кодирования Хаффмана: 10 шагов

Видео: Как сжать данные с помощью кодирования Хаффмана: 10 шагов
Видео: Как Избавиться от Социофобии 2024, Марш
Anonim

Алгоритм Хаффмана используется для сжатия или кодирования данных. Обычно каждый символ в текстовом файле хранится в виде восьми битов (цифр, 0 или 1), которые отображаются на этот символ с использованием кодировки, называемой ASCII. Файл с кодировкой Хаффмана разрушает жесткую 8-битную структуру, поэтому наиболее часто используемые символы хранятся всего в нескольких битах ('a' может быть "10" или "1000", а не ASCII, который равен "01100001"). Таким образом, наименее распространенные символы часто занимают намного больше, чем 8 бит ('z' может быть "00100011010"), но поскольку они встречаются так редко, кодирование Хаффмана в целом создает файл гораздо меньшего размера, чем исходный.

Шаги

Часть 1 из 2: Кодирование

Сжатие данных с использованием кодирования Хаффмана, шаг 1
Сжатие данных с использованием кодирования Хаффмана, шаг 1

Шаг 1. Подсчитайте частоту каждого символа в кодируемом файле

Включите фиктивный символ, чтобы отметить конец файла - это будет важно позже. А пока назовите его EOF (конец файла) и отметьте его как имеющий частоту 1.

Например, если вы хотите закодировать текстовый файл, читающий "ab ab cab", у вас будет 'a' с частотой 3, 'b' с частотой 3, '' (пробел) с частотой 2, 'c' с частотой 1, и EOF с частотой 1

Сжатие данных с использованием кодирования Хаффмана, шаг 2
Сжатие данных с использованием кодирования Хаффмана, шаг 2

Шаг 2. Сохраните символы в виде узлов дерева и поместите их в приоритетную очередь

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

  • Двоичное дерево - это формат данных, в котором каждая часть данных представляет собой узел, который может иметь до одного родителя и двух дочерних элементов. Его часто рисуют как ветвящееся дерево, отсюда и название.
  • Очередь - это точно названный набор данных, в котором первое, что попадает в очередь, также и первое, что выходит (например, ожидание в очереди). В очереди с приоритетом данные хранятся в порядке их приоритета, так что первое, что выходит, - это самое срочное дело, вещь с наименьшим приоритетом, а не первое, что ставится в очередь.
  • В примере "ab ab cab" ваша очередь приоритетов будет выглядеть так: {'c': 1, EOF: 1, '': 2, 'a': 3, 'b': 3}
Сжатие данных с использованием кодирования Хаффмана, шаг 3
Сжатие данных с использованием кодирования Хаффмана, шаг 3

Шаг 3. Начните строить свое дерево

Удалите (или удалите из очереди) два наиболее важных дела из очереди приоритетов. Создайте новый узел дерева, который будет родителем этих двух узлов, сохраняя первый узел как его левый дочерний элемент, а второй как его правый дочерний элемент. Приоритет нового узла должен быть суммой приоритетов его дочернего узла. Затем поместите этот новый узел в очередь приоритета.

Очередь с приоритетом теперь выглядит так: {'': 2, новый узел: 2, 'a': 3, 'b': 3}

Сжатие данных с использованием кодирования Хаффмана, шаг 4
Сжатие данных с использованием кодирования Хаффмана, шаг 4

Шаг 4. Завершите построение вашего дерева:

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

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

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

  • Например, начните с корня. Посетите левый дочерний элемент корня, а затем посетите левый дочерний элемент этого узла. Поскольку узел, в котором вы сейчас находитесь, не имеет потомков, вы достигли персонажа. Это ' '. Поскольку вы дважды шли налево, чтобы попасть сюда, кодировка '' - «00».
  • Для этого дерева карта будет выглядеть так: {'': "00", 'a': "10", 'b': "11", 'c': "010", EOF: "011"}.
Сжатие данных с использованием кодирования Хаффмана, шаг 6
Сжатие данных с использованием кодирования Хаффмана, шаг 6

Шаг 6. В выходной файл включите карту кодирования в качестве заголовка

Это позволит декодировать файл.

Сжатие данных с использованием кодирования Хаффмана, шаг 7
Сжатие данных с использованием кодирования Хаффмана, шаг 7

Шаг 7. Закодируйте файл

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

  • Для файла «ab ab cab» закодированный файл будет выглядеть так: «1011001011000101011011».
  • Файлы хранятся в байтах (8 бит или 8 двоичных цифр). Поскольку алгоритм кодирования Хаффмана не использует 8-битный формат, закодированные файлы часто не имеют длины, кратной 8. Остальные цифры будут заполнены нулями. В этом случае два нуля будут добавлены в конец файла, который выглядит как еще один пробел. Это может быть проблемой: как декодер узнает, когда прекратить чтение? Однако, поскольку мы включили символ конца файла, декодер доберется до него, а затем остановится, игнорируя все, что было добавлено после.

Часть 2 из 2: декодирование

Сжатие данных с использованием кодирования Хаффмана, шаг 8
Сжатие данных с использованием кодирования Хаффмана, шаг 8

Шаг 1. Прочтите файл в кодировке Хаффмана

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

Сжатие данных с использованием кодирования Хаффмана, шаг 9
Сжатие данных с использованием кодирования Хаффмана, шаг 9

Шаг 2. Считайте двоичную информацию по одной цифре за раз

Просматривайте дерево по мере чтения: если вы читаете «0», перейдите к левому дочернему элементу узла, в котором вы находитесь, а если вы читаете «1», перейдите к правому дочернему элементу. Достигнув листа (узла без дочерних элементов), вы достигли персонажа. Запишите символ в декодированный файл.

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

Сжатие данных с использованием кодирования Хаффмана, шаг 10
Сжатие данных с использованием кодирования Хаффмана, шаг 10

Шаг 3. Повторяйте, пока не дойдете до EOF

Поздравляю! Вы расшифровали файл.

Рекомендуемые: