Просмотр исходного текста страницы Алгоритм Хаффмана за 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 элемента второго массива). Теперь рассмотрим одну итерацию подробнее. 

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

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

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

На каждом шаге количество элементов  уменьшается ровно на один, а минимум из 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 {{---}} указатели в массивах</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

==См. также==
*[[Оптимальное хранение словаря в алгоритме Хаффмана]]

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

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