Модифицированное кодирование Хаффмана

Модифицированное кодирование Хаффмана используется в факсах для кодирования черно-белых изображений ( растровых изображений ). Он сочетает в себе коды переменной длины кодирования Хаффмана с кодированием повторяющихся данных в кодировании длин серий .

Базовое кодирование Хаффмана позволяет сжимать файлы, содержащие много повторяющихся данных, например файл, содержащий текст, где буквы алфавита являются повторяющимися объектами. Однако одна строка сканирования содержит только два типа элементов — белые пиксели и черные пиксели — которые могут быть представлены непосредственно как 0 и 1. Этот «алфавит», состоящий всего из двух символов , слишком мал, чтобы напрямую применить кодирование Хаффмана . Но если мы сначала воспользуемся кодированием по длине, у нас будет больше объектов для кодирования. Вот пример, взятый из статьи о кодировании длин серий :

Гипотетическая линия сканирования, где B представляет собой черный пиксель, а W — белый, может выглядеть следующим образом:

WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

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

12W1B12W3B24W1B14W

Здесь мы видим, что имеем, помимо двух предметов «белый» и «черный», еще несколько разных чисел. Эти числа предоставляют множество дополнительных элементов, которые можно использовать, поэтому кодирование Хаффмана можно напрямую применить к приведенной выше последовательности, чтобы еще больше уменьшить ее размер.