Алгоритм Хаффмана за O(n)

2020-04-27T14:02:35Z

Aabb: ошибка в алгоритме: выход за границу массива

{{Задача
|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]//уже на 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

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

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

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

Викиконспекты - Вклад участника [ru]

Алгоритм Хаффмана за O(n)