Просмотр исходного текста страницы Алгоритм Хаффмана за O(n)

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

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

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

Идея алгоритма заключается в том, чтобы создать такую [[Дискретная_математика,_алгоритмы_и_структуры_данных#.D0.9F.D1.80.D0.B8.D0.BE.D1.80.D0.B8.D1.82.D0.B5.D1.82.D0.BD.D1.8B.D0.B5_.D0.BE.D1.87.D0.B5.D1.80.D0.B5.D0.B4.D0.B8 | очередь с приоритетами]], из которой можно было бы доставать два минимума за <tex> O(1) </tex>, после чего в эту же очередь с приоритетами положить их сумму за <tex> O(1) </tex>. У нас уже есть массив с отсортированными частотами, теперь заведем второй массив, в котором мы будем хранить суммы. 
На каждой итерации мы будем выбирать два минимума из четырех элементов (первые 2 элемента первого массива и первые 2 элемента второго массива). Теперь рассмотрим одну итерацию подробнее. 

У нас есть три варианта возможных пар минимумов :
# Оба элемента из первого массива.
# Первый элемент первого массива и первый элемент второго массива.
# Два первых элемента второго массива.

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

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

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

==Пример==
Для примера возьмем строку "абракадабра".
<tex>i, j</tex> {{---}} указатели на первые неиспользованные элементы в массиве 1 и 2, соответственно.
 
<tex>i = 0, j = 0</tex>
{| class="wikitable"
! Буква || д || к || б || р || а
|-
| Массив 1 || 1 || 1 || 2 || 2 || 5
|}
{| class="wikitable"
!   || || || || ||
|-
| Массив 2 || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex>
|}

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

<tex>i = 2, j = 0</tex>
{| class="wikitable"
! Буква || д || к || б || р || а
|-
| Массив 1 || 1|| 1 || 2 || 2 || 5
|}
{| class="wikitable"
!  || дк || || || ||
|-
| Массив 2 || 2 || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex>
|}

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

<tex>i = 4, j = 0</tex>
{| class="wikitable"
! Буква || д || к || б || р || а
|-
| Массив 1 || 1|| 1 || 2 || 2 || 5
|}
{| class="wikitable"
!  || дк || бр || || ||
|-
| Массив 2 || 2 || 4 || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex>
|}

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

<tex>i = 4, j = 2</tex>
{| class="wikitable"
! Буква || д || к || б || р || а
|-
| Массив 1 || 1 || 1|| 2|| 2|| 5
|}
{| class="wikitable"
!  || дк || бр || дкбр || ||
|-
| Массив 2 || 2|| 4|| 6 || <tex>\infty</tex> || <tex>\infty</tex>
|}

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

<tex> i = 5, j = 3</tex>
{| class="wikitable"
! Буква || д || к || б || р || а
|-
| Массив 1 || 1 || 1 || 2 || 2 || 5
|}
{| class="wikitable"
!  || дк || бр || дкбр || адкбр ||
|-
| Массив 2 || 2 || 4 || 6 || 11 || <tex>\infty</tex>
|}

==Псевдокод==
 '''int''' HuffmanCoding(a: '''int[0..n]'''):
    b: '''int[0..n]'''
    i, j, ans: '''int''' ''<font color=green>// i, j {{---}} указатели в массивах, inf {{---}} большое число</font>''
    '''for''' k = 0 '''to''' n
       b[k] = <tex>\infty</tex>
    '''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
==См. также==
*[[Оптимальное хранение словаря в алгоритме Хаффмана]]

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Алгоритмы сжатия ]]