Алгоритм Хаффмана за O(n) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Алгоритм Хаффмана за O(n). == У нас есть массив частот (массив, в котором хранится число вх...»)
 
м (rollbackEdits.php mass rollback)
 
(не показано 12 промежуточных версий 6 участников)
Строка 1: Строка 1:
== Алгоритм Хаффмана за 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>.
 +
}}
  
У нас есть массив частот (массив, в котором хранится число вхождений каждого символа в строку), отсортированный по возрастанию, нужно построить по нему код Хаффмана за <tex> O(n) </tex> (если массив не отсортирован, то это можно сделать, например,[[Цифровая_сортировка | цифровой сортировкой]] за  <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>. У нас уже есть массив с отсортированными частотами, теперь давайте заведем второй массив, в котором мы будем хранить суммы. Несложно заметить, что в этом массиве элементы тоже будут идти по неубыванию. Допустим, что на каком-то шаге сумма получилась меньше чем предыдущая, но это противоречит тому, что на каждом шаге мы выбираем два минимальных (т.е. на каждом последующем шаге мы выбираем два минимума из элементов больших, чем на предыдущем шаге).  
+
Eсли массив не отсортирован, то это можно сделать, например,[[Цифровая_сортировка | цифровой сортировкой]] за  <tex> O(n) </tex>, что не ухудшит асимптотику.
На каждой итерации мы будет выбирать два минимума из четырех элементов (первые 2 элемента первого массива и первые 2 элемента второго массива). Теперь рассмотрим одну итерацию подробнее.  
+
 
 +
Идея алгоритма заключается в том, чтобы создать такую [[Дискретная_математика,_алгоритмы_и_структуры_данных#.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 элемента второго массива). Теперь рассмотрим одну итерацию подробнее.  
  
 
У нас есть три варианта возможных пар минимумов :
 
У нас есть три варианта возможных пар минимумов :
Строка 11: Строка 17:
 
# Два первых элемента второго массива.
 
# Два первых элемента второго массива.
  
В первом варианте мы просто дописываем сумму в конец второго массива. Во втором варианте мы вычеркиваем первый элемент из второго массива и добавляем его сумму с первым элементом первого массива в конец второго. Ну и в третьем варианте, мы вычеркиваем два первых элемента второго массива и добавляем их сумму в конец этого массива.Если в первом массиве элементы закончились, а во втором осталось больше одного элемента, то они меняются ролями.
+
Во всех случаях мы дописываем сумму в конец второго массива и передвигаем указатели в массивах на еще не использованные элементы. Докажем, что второй массив остается отсортированным по возрастанию после каждой итерации.
 +
 
 +
Так как мы выбираем два элемента с наименьшими частотами <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>n</tex> итераций.
+
На каждом шаге количество элементов  уменьшается ровно на один, а минимум из 4-х элементов мы выбираем за константное время, поэтому асимптотика программы составляет <tex>O(n)</tex>.
  
 
==Пример==
 
==Пример==
 
Для примера возьмем строку "абракадабра".
 
Для примера возьмем строку "абракадабра".
 
+
<tex>i, j</tex> {{---}} указатели на первые неиспользованные элементы в массиве 1 и 2, соответственно.
 +
 +
<tex>i = 0, j = 0</tex>
 
{| class="wikitable"
 
{| class="wikitable"
 
! Буква || д || к || б || р || а
 
! Буква || д || к || б || р || а
 
|-
 
|-
 
| Массив 1 || 1 || 1 || 2 || 2 || 5
 
| Массив 1 || 1 || 1 || 2 || 2 || 5
 +
|}
 +
{| class="wikitable"
 +
!   || || || || ||
 
|-
 
|-
 
| Массив 2 || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex>
 
| Массив 2 || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex>
 
|}
 
|}
  
На первом шаге два минимальных элемента - это первые две ячейки первого массива. Их сумму сохраняем во второй массив.
+
На первом шаге два минимальных элемента {{---}} это первые две ячейки первого массива. Их сумму сохраняем во второй массив.
 +
 
 +
<tex>i = 2, j = 0</tex>
 
{| class="wikitable"
 
{| class="wikitable"
| Массив 1 || used || used || 2 || 2 || 5
+
! Буква || д || к || б || р || а
 +
|-
 +
| Массив 1 || 1|| 1 || 2 || 2 || 5
 +
|}
 +
{| class="wikitable"
 +
!  || дк || || || ||
 
|-
 
|-
 
| Массив 2 || 2 || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex>
 
| Массив 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"
 
{| class="wikitable"
| Массив 1 || used || used || used || used || 5
+
|| дк || бр || || ||
 
|-
 
|-
 
| Массив 2 || 2 || 4 || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex>
 
| Массив 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"
 
{| class="wikitable"
| Массив 1 || used || used || used || used || 5
+
|| дк || бр || дкбр || ||
 
|-
 
|-
| Массив 2 || deleted || deleted || 6 || <tex>\infty</tex> || <tex>\infty</tex>
+
| Массив 2 || 2|| 4|| 6 || <tex>\infty</tex> || <tex>\infty</tex>
 
|}
 
|}
  
 
На четвертом шаге складываются две оставшиеся ячейки.
 
На четвертом шаге складываются две оставшиеся ячейки.
 +
 +
<tex> i = 5, j = 3</tex>
 
{| class="wikitable"
 
{| class="wikitable"
| Массив 1 || used || used || used || used || used
+
! Буква || д || к || б || р || а
 
|-
 
|-
| Массив 2 || deleted || deleted || deleted || 11 || <tex>\infty</tex>
+
| Массив 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
 +
 +
==См. также==
 +
*[[Оптимальное хранение словаря в алгоритме Хаффмана]]
 +
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
 +
[[Категория: Алгоритмы сжатия ]]

Текущая версия на 19:05, 4 сентября 2022

Задача:
Пусть у нас есть отсортированный по возрастанию алфавит [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. Два первых элемента второго массива.

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

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

На каждом шаге количество элементов уменьшается ровно на один, а минимум из 4-х элементов мы выбираем за константное время, поэтому асимптотика программы составляет [math]O(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]

Псевдокод

Код возвращает число бит, необходимых для кодирования текста с заданным количеством вхождений каждого символа.

int HuffmanCoding(a: int[0..n]):
   b: int[0..n]
   i, j, ans: int // i, j — указатели в массивах
   for k = 0 to n
      b[k] = [math]\infty[/math]
   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

См. также