Алгоритм Хаффмана за 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]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]