Алгоритм Хаффмана за O(n) - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:05:51Z

rollbackEdits.php mass rollback

141.98.9.47 в 06:34, 1 сентября 2022

2022-09-01T06:34:15Z

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

2020-04-27T14:02:35Z

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

188.242.29.236: /* Описание алгоритма */

2017-12-27T22:59:15Z

‎Описание алгоритма

Ильнар: /* Псевдокод */

2015-01-12T17:08:30Z

‎Псевдокод

Ильнар в 17:02, 12 января 2015

2015-01-12T17:02:45Z

Ильнар в 16:11, 12 января 2015

2015-01-12T16:11:00Z

Shersh: /* Описание алгоритма */

2015-01-12T15:57:29Z

‎Описание алгоритма

Ильнар в 15:56, 12 января 2015

2015-01-12T15:56:07Z

Ильнар в 15:54, 12 января 2015

2015-01-12T15:54:08Z

@@ Строка 1: / Строка 1: @@
 {{Задача
 |definition =
@@ Строка 55: / Строка 34: @@
 |}
 {| class="wikitable"
 !   || || || || ||
 |-
 | Массив 2 || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex>

@@ Строка 1: / Строка 1: @@
 {{Задача
 |definition =
@@ Строка 34: / Строка 55: @@
 |}
 {| class="wikitable"
 !   || || || || ||
 |-
 | Массив 2 || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex>

@@ Строка 103: / Строка 103: @@
         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]
+        '''if''' a[i] + a[i + 1] <= a[i] + b[j] '''and''' a[i] + a[i + 1] <= b[j] + b[j + 1]//уже на 3-ей итерации выход за границу массива
            b[k] = a[i] + a[i + 1]
            ans += b[k]

@@ Строка 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>.

@@ Строка 99: / Строка 99: @@
   '''int''' HuffmanCoding(a: '''int[0..n]'''):
      b: '''int[0..n]'''
-     i, j, ans: '''int''' ''<font color=green>// i, j {{---}} указатели в массивах, inf {{---}} большое число</font>''
+     i, j, ans: '''int''' ''<font color=green>// i, j {{---}} указатели в массивах</font>''
      '''for''' k = 0 '''to''' n
         b[k] = <tex>\infty</tex>
@@ Строка 119: / Строка 119: @@
            j += 2
      '''return''' ans
 ==См. также==
 *[[Оптимальное хранение словаря в алгоритме Хаффмана]]

@@ Строка 21: / Строка 21: @@
 Несложно заметить, что в этом массиве элементы тоже будут идти по неубыванию. Допустим, что на каком-то шаге сумма получилась меньше чем предыдущая, но это противоречит тому, что на каждом шаге мы выбираем два минимальных.
-На каждом шаге количество элементов  уменьшается ровно на один, а минимум из 4-х элементов мы выбираем за константное время, следовательно, программа делает ровно <tex>n</tex> итераций.
+На каждом шаге количество элементов  уменьшается ровно на один, а минимум из 4-х элементов мы выбираем за константное время, поэтому асимптотика программы составляет <tex>O(n)</tex>.
 ==Пример==
@@ Строка 39: / Строка 39: @@
 |}
-На первом шаге два минимальных элемента - это первые две ячейки первого массива. Их сумму сохраняем во второй массив.
+На первом шаге два минимальных элемента {{---}} это первые две ячейки первого массива. Их сумму сохраняем во второй массив.
 <tex>i = 2, j = 0</tex>
@@ Строка 53: / Строка 53: @@
 |}
-На втором шаге снова суммируются первые две ячейки первого массива(нам все равно что взять, первый элемент второго массива или второй элемент первого).
+На втором шаге снова суммируются первые две ячейки первого массива (нам все равно что взять, первый элемент второго массива или второй элемент первого).
 <tex>i = 4, j = 0</tex>
@@ Строка 67: / Строка 67: @@
 |}
-На третьем шаге два минимальных элемента - это первые две ячейки второго массива.
+На третьем шаге два минимальных элемента {{---}} это первые две ячейки второго массива.
 <tex>i = 4, j = 2</tex>
@@ Строка 102: / Строка 102: @@
         b[k] = <tex>\infty</tex>
      '''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]
            b[k] = a[i] + a[i + 1]
            ans += b[k]
            i += 2
            '''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]
            ans += b[k]
@@ Строка 113: / Строка 113: @@
            j++
            '''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]
            ans += b[k]
@@ Строка 119: / Строка 119: @@
      '''return''' ans
 ==См. также==
 *[[Оптимальное хранение словаря в алгоритме Хаффмана]]

@@ Строка 9: / Строка 9: @@
 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 элемента второго массива). Теперь рассмотрим одну итерацию подробнее.

← Предыдущая		Версия 15:56, 12 января 2015
Строка 121:		Строка 121:
	*[[Алгоритм Хаффмана]]		*[[Алгоритм Хаффмана]]
	*[[Оптимальное хранение словаря в алгоритме Хаффмана]]		*[[Оптимальное хранение словаря в алгоритме Хаффмана]]
		+
		+	[[Категория: Дискретная математика и алгоритмы]]
		+
		+	[[Категория: Алгоритмы сжатия ]]