Редактирование: Алгоритм Хаффмана за O(n)

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 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:
 
# Два первых элемента второго массива.
 
# Два первых элемента второго массива.
  
Во всех случаях мы дописываем сумму в конец второго массива и передвигаем указатели в массивах на еще не использованные элементы. Докажем, что второй массив остается отсортированным по возрастанию после каждой итерации.
+
Во всех случаях мы дописываем сумму в конец второго массива и передвигаем указатели в массивах на еще не использованные элементы.  
  
Так как мы выбираем два элемента с наименьшими частотами <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>.
+
На каждом шаге количество элементов  уменьшается ровно на один, а минимум из 4-х элементов мы выбираем за константное время, следовательно, программа делает ровно <tex>n</tex> итераций.
  
 
==Пример==
 
==Пример==
Строка 39: Строка 39:
 
|}
 
|}
  
На первом шаге два минимальных элемента {{---}} это первые две ячейки первого массива. Их сумму сохраняем во второй массив.
+
На первом шаге два минимальных элемента - это первые две ячейки первого массива. Их сумму сохраняем во второй массив.
  
 
<tex>i = 2, j = 0</tex>
 
<tex>i = 2, j = 0</tex>
Строка 53: Строка 53:
 
|}
 
|}
  
На втором шаге снова суммируются первые две ячейки первого массива (нам все равно что взять, первый элемент второго массива или второй элемент первого).
+
На втором шаге снова суммируются первые две ячейки первого массива(нам все равно что взять, первый элемент второго массива или второй элемент первого).
  
 
<tex>i = 4, j = 0</tex>
 
<tex>i = 4, j = 0</tex>
Строка 67: Строка 67:
 
|}
 
|}
  
На третьем шаге два минимальных элемента {{---}} это первые две ячейки второго массива.
+
На третьем шаге два минимальных элемента - это первые две ячейки второго массива.
  
 
<tex>i = 4, j = 2</tex>
 
<tex>i = 4, j = 2</tex>
Строка 96: Строка 96:
  
 
==Псевдокод==
 
==Псевдокод==
Код возвращает число бит, необходимых для кодирования текста с заданным количеством вхождений каждого символа.
 
 
  '''int''' HuffmanCoding(a: '''int[0..n]'''):
 
  '''int''' HuffmanCoding(a: '''int[0..n]'''):
 
     b: '''int[0..n]'''
 
     b: '''int[0..n]'''
     i, j, ans: '''int''' ''<font color=green>// i, j {{---}} указатели в массивах</font>''
+
     i, j, ans: '''int''' ''<font color=green>// i, j {{---}} указатели в массивах, inf {{---}} большое число</font>''
 
     '''for''' k = 0 '''to''' n
 
     '''for''' k = 0 '''to''' n
 
       b[k] = <tex>\infty</tex>
 
       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] '''and''' a[i] + a[i + 1] <= b[j] + b[j + 1]//уже на 3-ей итерации выход за границу массива
+
       '''if''' a[i] + a[i + 1] <= a[i] + b[j] && a[i] + a[i + 1] <= b[j] + b[j + 1]
                                                                                          //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] '''and''' a[i] + b[j] <= b[j] + b[j + 1]
+
       '''if''' a[i] + b[j] <= a[i] + a[i + 1] && 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]
Строка 115: Строка 113:
 
           j++
 
           j++
 
           '''continue'''
 
           '''continue'''
       '''if''' b[j] + b[j + 1] <= a[i] + a[i + 1] '''and''' b[j] + b[j + 1] <= a[i] + b[j]
+
       '''if''' b[j] + b[j + 1] <= a[i] + a[i + 1] && 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
 
 
==См. также==
 
==См. также==
 +
*[[Алгоритм Хаффмана]]
 
*[[Оптимальное хранение словаря в алгоритме Хаффмана]]
 
*[[Оптимальное хранение словаря в алгоритме Хаффмана]]
  

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: