Алгоритм Хаффмана за O(n)

Задача:

Пусть у нас есть отсортированный по возрастанию алфавит [math]\Sigma = \{a_1, a_2, \cdots, a_n\}[/math], [math]|\Sigma| = n[/math]. Где [math]a_i[/math] — число вхождений символа в строку. Требуется построить код Хаффмана за [math]O(n)[/math].

Описание алгоритма

Eсли массив не отсортирован, то это можно сделать, например, цифровой сортировкой за [math] O(n) [/math], что не ухудшит асимптотику.

Идея алгоритма заключается в том, чтобы создать такую очередь с приоритетами, из которой можно было бы доставать два минимума за [math] O(1) [/math], после чего в эту же очередь с приоритетами положить их сумму за [math] O(1) [/math]. У нас уже есть массив с отсортированными частотами, теперь заведем второй массив, в котором мы будем хранить суммы. На каждой итерации мы будем выбирать два минимума из четырех элементов (первые 2 элемента первого массива и первые 2 элемента второго массива). Теперь рассмотрим одну итерацию подробнее.

У нас есть три варианта возможных пар минимумов :

1. Оба элемента из первого массива.
2. Первый элемент первого массива и первый элемент второго массива.
3. Два первых элемента второго массива.

Во всех случаях мы дописываем сумму в конец второго массива и передвигаем указатели в массивах на еще не использованные элементы.

Несложно заметить, что в этом массиве элементы тоже будут идти по неубыванию. Допустим, что на каком-то шаге сумма получилась меньше чем предыдущая, но это противоречит тому, что на каждом шаге мы выбираем два минимальных (т.е. на каждом последующем шаге мы выбираем два минимума из элементов не меньших, чем на предыдущем шаге).

На каждом шаге количество элементов уменьшается ровно на один, а минимум из 4-х элементов мы выбираем за константное время, поэтому асимптотика программы составляет [math]O(n)[/math].

Пример

Для примера возьмем строку "абракадабра". [math]i, j[/math] — указатели на первые неиспользованные элементы в массиве 1 и 2, соответственно.

[math]i = 0, j = 0[/math]

Буква	д	к	б	р	а
Массив 1	1	1	2	2	5

Массив 2	[math]\infty[/math]	[math]\infty[/math]	[math]\infty[/math]	[math]\infty[/math]	[math]\infty[/math]

На первом шаге два минимальных элемента — это первые две ячейки первого массива. Их сумму сохраняем во второй массив.

[math]i = 2, j = 0[/math]

Буква	д	к	б	р	а
Массив 1	1	1	2	2	5

	дк
Массив 2	2	[math]\infty[/math]	[math]\infty[/math]	[math]\infty[/math]	[math]\infty[/math]

На втором шаге снова суммируются первые две ячейки первого массива (нам все равно что взять, первый элемент второго массива или второй элемент первого).

[math]i = 4, j = 0[/math]

Буква	д	к	б	р	а
Массив 1	1	1	2	2	5

	дк	бр
Массив 2	2	4	[math]\infty[/math]	[math]\infty[/math]	[math]\infty[/math]

На третьем шаге два минимальных элемента — это первые две ячейки второго массива.

[math]i = 4, j = 2[/math]

Буква	д	к	б	р	а
Массив 1	1	1	2	2	5

	дк	бр	дкбр
Массив 2	2	4	6	[math]\infty[/math]	[math]\infty[/math]

На четвертом шаге складываются две оставшиеся ячейки.

[math] i = 5, j = 3[/math]

Буква	д	к	б	р	а
Массив 1	1	1	2	2	5

	дк	бр	дкбр	адкбр
Массив 2	2	4	6	11	[math]\infty[/math]

Псевдокод

Код возвращает число бит, необходимых для кодирования текста с заданным количеством вхождений каждого символа.

int HuffmanCoding(a: int[0..n]):
   b: int[0..n]
   i, j, ans: int // i, j — указатели в массивах
   for k = 0 to n
      b[k] = [math]\infty[/math]
   for k = 0 to n - 1
      if a[i] + a[i + 1] <= a[i] + b[j] and a[i] + a[i + 1] <= b[j] + b[j + 1]
         b[k] = a[i] + a[i + 1]
         ans += b[k]
         i += 2
         continue
      if a[i] + b[j] <= a[i] + a[i + 1] and a[i] + b[j] <= b[j] + b[j + 1]
         b[k] = a[i] + b[j]
         ans += b[k]
         i++
         j++
         continue
      if b[j] + b[j + 1] <= a[i] + a[i + 1] and b[j] + b[j + 1] <= a[i] + b[j]
         b[k] = b[j] + b[j + 1]
         ans += b[k]
         j += 2
   return ans

См. также

• Оптимальное хранение словаря в алгоритме Хаффмана