Алгоритм Хаффмана за 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. Два первых элемента второго массива.

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

Так как мы выбираем два элемента с наименьшими частотами [math]f_1[/math] и [math]f_2[/math], то в силу выбора элементов их суммарная частота [math]S = f_1 + f_2[/math] будет не больше суммы двух любых других из нерассмотренных частот, следовательно, никакая из последующих сумм не окажется меньше [math]S[/math]. Докажем, что [math]S[/math] не меньше значений, добавленных во второй массив на предыдущих итерациях. Допустим, что это не так и на каком-то шаге мы добавили в массив число [math]S_1[/math] такое, что [math]S_1 \gt S[/math]. Это значит, что на одной из итераций мы выбрали два элемента таким образом, что хотя бы один из них был больше [math]f_1[/math] либо больше [math]f_2[/math]. Но так как первый массив отсортирован по возрастанию, а второй изначально заполнен [math]\infty[/math], это противоречит тому, что на каждой итерации мы выбираем два минимальных значения. Следовательно, наше предположение неверно, сумма [math]S[/math] является наибольшей из рассмотренных ранее сумм и второй массив отсортирован по возрастанию.

На каждом шаге количество элементов уменьшается ровно на один, а минимум из 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]//уже на 3-ей итерации выход за границу массива
                                                                                          //i = 4, i + 1 = 5, a[5] = undefined
         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

См. также

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