Алгоритм Хаффмана за 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 — указатели в массивах, inf — большое число
   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

См. также

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