1
правка
Изменения
ошибка в алгоритме: выход за границу массива
{{Задача|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 || used 1|| used 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"
! | Массив 1 |дк | used |бр | used || used || used || 5
|-
| Массив 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"
! | Массив 1 |дк | used |бр | used |дкбр | used || used || 5
|-
| Массив 2 || deleted 2|| deleted 4|| 6 || <tex>\infty</tex> || <tex>\infty</tex>
|}
На четвертом шаге складываются две оставшиеся ячейки.
<tex> i = 5, j = 3</tex>
{| class="wikitable"
! Буква | Массив 1 |д | used |к | used |б | used |р | used || usedа
|-
| Массив 2 1 || deleted 1 || deleted 1 || deleted 2 || 11 2 || <tex>\infty</tex>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
==См. также==
*[[Оптимальное хранение словаря в алгоритме Хаффмана]]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы сжатия ]]
