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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 9 промежуточных версий 5 участников)
Строка 2: Строка 2:
 
|definition =
 
|definition =
 
Пусть у нас есть отсортированный по возрастанию алфавит <tex>\Sigma = \{a_1, a_2, \cdots, a_n\}</tex>, <tex>|\Sigma| = n</tex>. Где <tex>a_i</tex> {{---}} число вхождений символа в строку.
 
Пусть у нас есть отсортированный по возрастанию алфавит <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>.
 
}}
 
}}
  
Строка 9: Строка 9:
 
Eсли массив не отсортирован, то это можно сделать, например,[[Цифровая_сортировка | цифровой сортировкой]] за  <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>. У нас уже есть массив с отсортированными частотами, теперь давайте заведем второй массив, в котором мы будем хранить суммы. Несложно заметить, что в этом массиве элементы тоже будут идти по неубыванию. Допустим, что на каком-то шаге сумма получилась меньше чем предыдущая, но это противоречит тому, что на каждом шаге мы выбираем два минимальных.  
+
Идея алгоритма заключается в том, чтобы создать такую [[Дискретная_математика,_алгоритмы_и_структуры_данных#.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 элемента второго массива). Теперь рассмотрим одну итерацию подробнее.  
+
На каждой итерации мы будем выбирать два минимума из четырех элементов (первые 2 элемента первого массива и первые 2 элемента второго массива). Теперь рассмотрим одну итерацию подробнее.  
  
 
У нас есть три варианта возможных пар минимумов :
 
У нас есть три варианта возможных пар минимумов :
Строка 17: Строка 17:
 
# Два первых элемента второго массива.
 
# Два первых элемента второго массива.
  
Во всех случаях мы дописываем сумму в конец второго массива и передвигаем указатели в массивах на еще не использованные элементы.  
+
Во всех случаях мы дописываем сумму в конец второго массива и передвигаем указатели в массивах на еще не использованные элементы. Докажем, что второй массив остается отсортированным по возрастанию после каждой итерации.
  
На каждом шаге количество элементов  уменьшается ровно на один, а минимум из 4-х элементов мы выбираем за константное время, следовательно, программа делает ровно <tex>n</tex> итераций.
+
Так как мы выбираем два элемента с наименьшими частотами <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>.
  
 
==Пример==
 
==Пример==
Строка 37: Строка 39:
 
|}
 
|}
  
На первом шаге два минимальных элемента - это первые две ячейки первого массива. Их сумму сохраняем во второй массив.
+
На первом шаге два минимальных элемента {{---}} это первые две ячейки первого массива. Их сумму сохраняем во второй массив.
  
 
<tex>i = 2, j = 0</tex>
 
<tex>i = 2, j = 0</tex>
Строка 51: Строка 53:
 
|}
 
|}
  
На втором шаге снова суммируются первые две ячейки первого массива(нам все равно что взять, первый элемент второго массива или второй элемент первого).
+
На втором шаге снова суммируются первые две ячейки первого массива (нам все равно что взять, первый элемент второго массива или второй элемент первого).
  
 
<tex>i = 4, j = 0</tex>
 
<tex>i = 4, j = 0</tex>
Строка 65: Строка 67:
 
|}
 
|}
  
На третьем шаге два минимальных элемента - это первые две ячейки второго массива.
+
На третьем шаге два минимальных элемента {{---}} это первые две ячейки второго массива.
  
 
<tex>i = 4, j = 2</tex>
 
<tex>i = 4, j = 2</tex>
Строка 94: Строка 96:
  
 
==Псевдокод==
 
==Псевдокод==
 +
Код возвращает число бит, необходимых для кодирования текста с заданным количеством вхождений каждого символа.
 
  '''int''' HuffmanCoding(a: '''int[0..n]'''):
 
  '''int''' HuffmanCoding(a: '''int[0..n]'''):
 
     b: '''int[0..n]'''
 
     b: '''int[0..n]'''
     i, j, inf, ans: '''int''' ''<font color=green>// i, j {{---}} указатели в массивах, inf {{---}} большое число</font>''
+
     i, j, ans: '''int''' ''<font color=green>// i, j {{---}} указатели в массивах</font>''
 
     '''for''' k = 0 '''to''' n
 
     '''for''' k = 0 '''to''' n
       b[k] = inf
+
       b[k] = <tex>\infty</tex>
 
     '''for''' k = 0 '''to''' n - 1
 
     '''for''' k = 0 '''to''' n - 1
       '''if''' a[i] + a[i + 1] <= a[i] + b[j] && a[i] + a[i + 1] <= b[j] + b[j + 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]
 
           b[k] = a[i] + a[i + 1]
 
           ans += b[k]
 
           ans += b[k]
 
           i += 2
 
           i += 2
 
           '''continue'''
 
           '''continue'''
       '''if''' a[i] + b[j] <= a[i] + a[i + 1] && a[i] + b[j] <= b[j] + b[j + 1]
+
       '''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]
 
           b[k] = a[i] + b[j]
 
           ans += b[k]
 
           ans += b[k]
Строка 111: Строка 115:
 
           j++
 
           j++
 
           '''continue'''
 
           '''continue'''
       '''if''' b[j] + b[j + 1] <= a[i] + a[i + 1] && b[j] + b[j + 1] <= a[i] + b[j]
+
       '''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]
 
           b[k] = b[j] + b[j + 1]
 
           ans += b[k]
 
           ans += b[k]
 
           j += 2
 
           j += 2
 
     '''return''' ans
 
     '''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

См. также