03 - Алгоритмы Хаффмана для кодирования и декодирования данных

Алгоритм Хаффмана (англ. Huffman's algorithm) — алгоритм оптимального префиксного кодирования некоторого алфавита с минимальной избыточностью.

Был разработан в 1952 году аспирантом Массачусетского технологического института Дэвидом Альбертом Хаффманом при написании им курсовой работы^[1].

Используется во многих программах сжатия данных.

Предложенный Хаффманом метод кодирования состоит из двух основных этапов:

Построение оптимального кодового дерева.
Построение «словаря» код-символ на основе построенного дерева.

David Albert Huffman

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

Математическое определение

Пусть $A=\{ {a_1,a_2,{…},a_n}\}$ — алфавит из $n$ различных символов, $W=\{ {w_1,w_2,…,w_n}\}$ — соответствующий ему набор положительных целых весов. Тогда набор бинарных кодов $C=\{ {c_1,c_2,…,c_n}\}$ , где $c_i$ является кодом для символа $a_i$ , такой, что:
$c_i$ не является префиксом для $c_j$ , при ${i}\ne{j}$ ,
сумма $\displaystyle\sum_{ {i}∈[1,n]} {w_i}⋅|c_i|$ минимальна ( $|c_i|$ — длина кода $c_i$ ),
называется кодом Хаффмана.

Алгоритм построения бинарного кода Хаффмана

Построение кода Хаффмана сводится к построению соответствующего бинарного дерева по следующему алгоритму: ^[2]

Составим список кодируемых символов, при этом будем рассматривать один символ как дерево, состоящее из одного элемента c весом, равным частоте появления символа в строке.
Из списка выберем два узла с наименьшим весом по следующему правилу:
- Всегда выбираются два узла с наименьшими весами.
- Если веса равны, предпочтение отдается узлу, который был создан раньше (это важно для воспроизводимости результатов).
Сформируем новый узел с весом, равным сумме весов выбранных узлов, и присоединим к нему два выбранных узла в качестве детей.
Добавим к списку только что сформированный узел вместо двух объединенных узлов.
Если в списке больше одного узла, то повторим пункты со второго по пятый.

Пример построения дерева Хаффмана

Закодируем слово $abracadabra$ . Тогда алфавит будет $A=\{ {a,b,r,c,d}\}$ , а набор весов (частота появления символов алфавита в кодируемом слове) $W=\{ {5,2,2,1,1}\}$ .

В дереве Хаффмана будет $5$ узлов:

Узел	$a$	$b$	$r$	$c$	$d$
Вес	5	2	2	1	1

По алгоритму возьмем два символа с наименьшей частотой — это $c$ и $d$ . Сформируем из них новый узел $cd$ весом $2$ (сумма весов каждого из узлов) и добавим его к списку узлов:

Узел	$a$	$b$	$r$	$cd$
Вес	5	2	2	2

Затем опять объединим в один узел два минимальных по весу узла — $b$ и $r$ :

Узел	$a$	$cd$	$br$
Вес	5	2	4

Еще раз повторим эту же операцию, но для узлов $cd$ и $br$ :

Узел	$a$	$cdbr$
Вес	5	6

На последнем шаге объединим два узла — $a$ и $cdbr$ :

Узел	$acdbr$
Вес	11

Остался один узел, значит, мы пришли к корню дерева Хаффмана.

Теперь для каждого символа определим его код — бинарную последовательность, обозначающую путь по дереву к этому символу от корня:

Символ	$a$	$b$	$r$	$c$	$d$
Код	0	110	111	100	101

Таким образом, закодированное слово $abracadabra$ будет выглядеть как $0111010100001010111010$ . Длина закодированного слова — $23$ бита. Стоит заметить, что если бы мы использовали алгоритм кодирования с одинаковой длиной всех кодовых слов, то закодированное слово заняло бы $33$ бита, что существенно больше.

Реализация алгоритма Хаффмана на языке Fortran 77

Ниже приводится реализация алгоритма Хаффмана на языке программирования Fortran 77. Основой для программы послужил подход, описанный в книге Numerical Recipes in FORTRAN 77: Volume 1, The Art of Scientific Computing^[3]. Однако реализация была адаптирована и упрощена для студентов, чтобы она была представлена как единая программа, понятная для изучения.

C************************************************************************
C     HUFFMAN ENCODING ALGORITHM
C     WRITTEN BY: PAVEL TKACHEV
C     BASED ON METHODS FROM:
C     "NUMERICAL RECIPES IN FORTRAN 77: VOL 1", 1992
C     ADAPTED AND SIMPLIFIED FOR STUDENTS.
C     CONTACT: PHOENIXWEISS@YA.RU
C     DATE: DECEMBER 2024
C************************************************************************

      PROGRAM HUFFMAN
      IMPLICIT NONE

C     Constants for array sizes and large integer value
      INTEGER MAXSYM, MAXNOD, MAXINT
      PARAMETER (MAXSYM = 256, MAXNOD = 512, MAXINT = 999999999)

C     Arrays for frequencies, tree structure, and parent nodes
      INTEGER FREQ(MAXNOD)
      INTEGER LEFT(MAXNOD)
      INTEGER RIGHT(MAXNOD)
      INTEGER PARENT(MAXNOD)

C     Variables for input processing and Huffman tree construction
      INTEGER CHRCOD, LEN, N, NDS
      INTEGER NODE1, NODE2
      CHARACTER*1 SYM(MAXSYM), CH
      CHARACTER*256 INP
      INTEGER I, J
      INTEGER MIN1, MIN2, ROOT
      INTEGER CODLEN
      CHARACTER*256 CODE
      LOGICAL FOUND

      INTEGER LENTR
      EXTERNAL LENTR

      EXTERNAL ENCODE

C     Initialize arrays
      DO I = 1, MAXNOD
         FREQ(I) = 0
         LEFT(I) = 0
         RIGHT(I) = 0
         PARENT(I) = 0
      END DO

C     Get input string
      WRITE(*,*) 'Enter a phrase:'
      READ(*,'(A)') INP

C     Get length of input string without trailing spaces
      LEN = LENTR(INP)
      IF (LEN .EQ. 0) THEN
         WRITE(*,*) 'Empty input. Exiting.'
         STOP
      END IF

C     Count frequency of each unique symbol
      N = 0
      DO I = 1, LEN
         CH = INP(I:I)
         CHRCOD = ICHAR(CH)
         IF (CHRCOD .LT. 32 .OR. CHRCOD .GT. 126) GOTO 100
         FOUND = .FALSE.
         DO J = 1, N
            IF (CH .EQ. SYM(J)) THEN
               FOUND = .TRUE.
               FREQ(J) = FREQ(J) + 1
               GOTO 100
            END IF
         END DO
         N = N + 1
         SYM(N) = CH
         FREQ(N) = 1
  100 CONTINUE
      END DO
      IF (N .EQ. 0) THEN
         WRITE(*,*) 'No symbols to encode. Exiting.'
         STOP
      END IF

C     Build Huffman tree
      NDS = N
      DO WHILE (NDS .LT. 2 * N - 1)
         MIN1 = MAXINT
         MIN2 = MAXINT
         NODE1 = -1
         NODE2 = -1

C        Find two nodes with smallest frequencies
         DO I = 1, NDS
            IF (PARENT(I) .NE. 0) GOTO 200
            IF (FREQ(I) .LT. MIN1) THEN
               MIN2 = MIN1
               NODE2 = NODE1
               MIN1 = FREQ(I)
               NODE1 = I
            ELSE IF (FREQ(I) .LT. MIN2) THEN
               MIN2 = FREQ(I)
               NODE2 = I
            END IF
  200    CONTINUE
         END DO
         IF (NODE2 .EQ. -1) EXIT

C        Create a new parent node for the two smallest nodes
         NDS = NDS + 1
         FREQ(NDS) = FREQ(NODE1) + FREQ(NODE2)
         LEFT(NDS) = NODE1
         RIGHT(NDS) = NODE2
         PARENT(NODE1) = NDS
         PARENT(NODE2) = NDS
      END DO

      ROOT = NDS

C     Generate and display Huffman codes for each symbol
      WRITE(*,*) 'Huffman Codes:'
      DO I = 1, N
         CALL ENCODE(I, PARENT, LEFT, RIGHT, ROOT, CODE, CODLEN)
         WRITE(*,'(A1, A3, A)') SYM(I), ' -> ', CODE(1:CODLEN)
      END DO

      END

C**********************************************************************
C     _Function to compute length of string without trailing spaces
      INTEGER FUNCTION LENTR(STR)
      CHARACTER*(*) STR
      INTEGER J, CHRCOD
      LENTR = LEN(STR)
      DO J = LENTR, 1, -1
         CHRCOD = ICHAR(STR(J:J))
         IF (CHRCOD .NE. 10 .AND. CHRCOD .NE. 13 .AND.
     1       CHRCOD .NE. 32) THEN
            LENTR = J
            RETURN
         END IF
      END DO
      LENTR = 0
      END

C**********************************************************************
C     _Subroutine to generate Huffman code for a given symbol
      SUBROUTINE ENCODE(NODE, PARENT, LEFT, RIGHT, ROOT, CODE, LEN)
      INTEGER NODE
      INTEGER PARENT(*), LEFT(*), RIGHT(*), ROOT, LEN
      CHARACTER*256 CODE
      CHARACTER*1 PATH(256)
      INTEGER POS, CUR, I

C     Initialize variables
      POS = 0
      LEN = 0
      CODE = ''
      CUR = NODE

C     Trace path from node to root to generate the code
  300 CONTINUE
      IF (CUR .EQ. ROOT) GOTO 400
      POS = POS + 1
      IF (LEFT(PARENT(CUR)) .EQ. CUR) THEN
         PATH(POS) = '0'
      ELSE
         PATH(POS) = '1'
      END IF
      CUR = PARENT(CUR)
      GOTO 300
  400 CONTINUE

C     Reverse path to form the final code
      LEN = POS
      DO I = 1, POS
         CODE(I:I) = PATH(POS - I + 1)
      END DO
      RETURN
      END

Программа реализует алгоритм Хаффмана для сжатия текста.

Основные особенности программы

Ввод строки и подсчёт частот символов:
- Пользователь вводит строку.
- Программа автоматически подсчитывает частоту появления каждого символа, используя ASCII-коды. Это позволяет избежать ручного ввода частот.
Построение дерева Хаффмана:
- На основе частот создаётся бинарное дерево.
- Два узла с наименьшими частотами объединяются в новый узел, пока не останется один корневой узел.
Генерация кодов:
- Для каждого символа определяется уникальный код Хаффмана.
- Код строится путём обхода дерева от символа к корню (левый поворот = 0, правый поворот = 1).
Вывод результатов:
- Для каждого символа отображается его уникальный код.
- Кодированная строка создаётся путём замены символов на их коды.
Использование простых структур данных:
- Программа работает с массивами для хранения частот, связей дерева и узлов, что упрощает реализацию и обеспечивает совместимость со стандартом Fortran-77.

Как запустить программу

Сохранение кода:
- Скопируйте программу в текстовый файл и сохраните его с расширением .f, например, huffman.f.
Установка компилятора Fortran:
- Убедитесь, что на вашем компьютере установлен компилятор Fortran (например, gfortran). Если компилятор не установлен, его можно установить:
  - Linux: sudo apt install gfortran
  - MacOS: brew install gfortran
  - Windows: используйте MinGW или WSL (Windows Subsystem for Linux).
Компиляция программы:
- Откройте терминал, перейдите в директорию с файлом программы и выполните:
```
gfortran -ffixed-form -o huffman huffman.f
```
- В результате будет создан исполняемый файл huffman.
Запуск программы:
- Выполните команду:
```
./huffman
```
  На Windows вместо ./huffman используйте huffman.exe.
Проверка на фразе "abracadabra":
- После запуска программа запросит ввод строки. Введите abracadabra и нажмите Enter.
- Программа подсчитает частоты символов, построит дерево Хаффмана и выведет коды для каждого символа.

Пример работы программы

Ввод:

Enter a phrase:
abracadabra

Вывод:

Huffman Codes:
a -> 0
b -> 110
r -> 111
c -> 100
d -> 101

Программа демонстрирует базовые принципы алгоритма Хаффмана и позволяет студентам изучить его реализацию в классическом процедурном стиле благодаря использованию языка Fortran 77, который широко применялся в 1970-1980-х годах для научных и инженерных вычислений, студенты также получают возможность познакомиться с историческим подходом к программированию.

Кодирование Хаффмана, журнал Монитор, номер 7-8, 1993 год