Кодирование Хаффмана - это метод сжатия данных переменной длины. Он работает путем присвоения наиболее частых значений во входном потоке кодировкам с наименьшей длиной в битах.
Например, вход Seems every eel eeks elegantly. может кодировать букву e в двоичном виде 1, а все остальные буквы - в виде различных других более длинных кодов, все начинающиеся с 0. Таким образом, результирующий поток битов будет меньше, чем если бы каждая буква имела фиксированный размер. В качестве примера давайте рассмотрим количество каждого символа и создадим дерево, которое помещает общие в верхнюю часть.
Letter Count
------ -----
e 10
<SPC> 4
l 3
sy 2
Smvrkgant. 1
<EOF> 1
Маркер конца файла EOF уже есть, так как обычно в вашем файле должно быть кратное восьми битам. Это означает, что любой отступ в конце не будет рассматриваться как реальный символ.
__________#__________
________________/______________ \
________/________ ____\____ e
__/__ __\__ __/__ \
/ \ / \ / \ / \
/ \ / \ / SPC l s
/ \ / \ / \ / \ / \
y S m v / k g \ n t
/\ / \
r . a EOF
Теперь это не обязательно наиболее эффективное дерево, но этого достаточно, чтобы установить, как выполняются кодировки. Давайте сначала посмотрим на несжатые данные. Предполагая восьмибитное кодирование, эти тридцать один символ (нам не нужно EOF для несжатых данных) будут занимать 248 бит.
Но если вы используете дерево выше для определения местоположения символов, выводя нулевой бит, если вы берете левое поддерево, и один бит, если вы выбираете правое, вы получаете следующее:
Section Encoding
---------- --------
Seems<SPC> 00001 1 1 00010 0111 0101 (20 bits)
every<SPC> 1 00011 1 001000 00000 0101 (22 bits)
eel<SPC> 1 1 0110 0101 (10 bits)
eeks<SPC> 1 1 00101 0111 0101 (15 bits)
elegantly 1 0110 1 00110 001110 01000 01001 0110 00000 (36 bits)
.<EOF> 001001 001111 (12 bits)
Это дает в общей сложности 115 битов, округленных до 120, поскольку он должен быть кратным байту, но это все равно примерно половина размера несжатых данных.
Теперь для такого маленького файла это обычно не стоит, так как вы должны добавить пространство, занимаемое самим фактическим деревом (a) , иначе вы не сможете декодировать его на другом конце. Но, конечно, для больших файлов, где распределение символов неравномерно, это может привести к впечатляющей экономии места.
Итак, после всего этого таблицы Хаффмана в JPEG - это просто таблицы, которые позволяют распаковывать поток в полезную информацию.
Процесс кодирования для JPEG состоит из нескольких различных этапов (преобразование цвета, уменьшение цветовой разрешающей способности, дискретное косинусное преобразование на основе блоков и т. Д.), Но последний этап - это кодирование Хаффмана без потерь в каждом блоке, как в этих таблицах. используются для изменения при чтении изображения.
(a) Возможно, случай best для минимального хранения этой таблицы будет выглядеть примерно так:
Size of length section (8-bits) = 3 (longest bit length of 6 takes 3 bits)
Repeated for each byte:
Actual length (3 bits, holding value between 1..6 inclusive)
Encoding (n bits, where n is the actual length)
Byte (8 bits)
End of table marker (3 bits) = 0 to distinguish from actual length above
Для приведенного выше текста это будет:
00000011 8 bits
n bits byte
--- ------ -----
001 1 'e' 12 bits
100 0101 <SPC> 15 bits
101 00001 'S' 16 bits
101 00010 'm' 16 bits
100 0111 's' 15 bits
101 00011 'v' 16 bits
110 001000 'r' 17 bits
101 00000 'y' 16 bits
101 00101 'k' 16 bits
100 0110 'l' 15 bits
101 00110 'g' 16 bits
110 001110 'a' 17 bits
101 01000 'n' 16 bits
101 01001 't' 16 bits
110 001001 '.' 17 bits
110 001111 <EOF> 17 bits
000 3 bits
Это делает таблицу 264 битами, что полностью стирает экономию от сжатия. Однако, как уже говорилось, влияние таблицы становится намного меньше, поскольку размер входного файла увеличивается, и есть способ избежать таблицы в целом.
Этот способ предполагает использование другого варианта Хаффмана, называемого Адаптивный Хаффмана. Это где таблица на самом деле не хранится в сжатых данных.
Вместо этого во время сжатия таблица начинается с EOF и специальной последовательности битов, предназначенной для введения в таблицу нового действительного байта.
При вводе нового байта в таблицу вы должны вывести последовательность битов вводчика, за которой следуют полные восемь битов этого байта.
Затем, после вывода каждого байта и обновления подсчетов, таблица / дерево перебалансируется на основе новых отсчетов, чтобы обеспечить наиболее эффективное использование пространства (хотя перебалансирование может быть отложено для повышения скорости, вам просто нужно убедиться, что та же самая задержка происходит во время декомпрессии, например, каждый раз, когда вы добавляете байт для первого 1К ввода, а затем каждые 10К ввода после этого, при условии, что вы добавили новые байты с момента последнего перебалансирования).
Это означает, что сама таблица может быть построена в точно таким же образом на другом конце (декомпрессия), начиная с той же самой минимальной таблицы только с последовательностью EOF и интродьюсером.
Во время распаковки, когда вы видите последовательность интродуктора, вы можете добавить байт, следующий за ним (следующие восемь битов), в таблицу с нулевым счетчиком, вывести байт, затем отрегулировать счет и перебалансировать (или отложить, как упоминалось ранее).
Таким образом, вам не нужно отправлять таблицу со сжатым файлом. Это, конечно, стоит немного больше времени при сжатии и распаковке, потому что вы периодически перебалансируете таблицу, но, как и в большинстве случаев в жизни, это компромисс.