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

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:41:26Z

rollbackEdits.php mass rollback

185.244.195.157 в 03:28, 1 сентября 2022

2022-09-01T03:28:24Z

188.227.78.59 в 12:14, 27 марта 2016

2016-03-27T12:14:30Z

Shersh: /* Определение */

2015-11-22T13:24:46Z

‎Определение

Ozymandias в 13:22, 22 ноября 2015

2015-11-22T13:22:49Z

Ozymandias в 13:18, 22 ноября 2015

2015-11-22T13:18:26Z

Ozymandias: Выполнен тикет 5.1 + загружена новая картинка и приведен новый пример + приведены английские термины

2015-11-21T20:46:26Z

Выполнен тикет 5.1 + загружена новая картинка и приведен новый пример + приведены английские термины

Внесённые изменения

Dgerasimov: немного изменил структуру

2014-01-06T18:51:21Z

немного изменил структуру

KirillKutirev: /* Время работы */

2013-12-29T13:34:06Z

‎Время работы

KirillKutirev: /* Пример */

2013-12-29T13:25:02Z

‎Пример

← Предыдущая		Версия 16:41, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	'''Алгоритм Хаффмана''' (англ. ''Huffman's algorithm'') — алгоритм [[Задача_об_оптимальном_префиксном_коде_с_сохранением_порядка._Монотонность_точки_разреза \| оптимального префиксного кодирования]] алфавита. Был разработан в 1952 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им курсовой работы. Используется во многих программах сжатия данных, например, PKZIP 2, LZH и др.		'''Алгоритм Хаффмана''' (англ. ''Huffman's algorithm'') — алгоритм [[Задача_об_оптимальном_префиксном_коде_с_сохранением_порядка._Монотонность_точки_разреза \| оптимального префиксного кодирования]] алфавита. Был разработан в 1952 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им курсовой работы. Используется во многих программах сжатия данных, например, PKZIP 2, LZH и др.

← Предыдущая		Версия 03:28, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	'''Алгоритм Хаффмана''' (англ. ''Huffman's algorithm'') — алгоритм [[Задача_об_оптимальном_префиксном_коде_с_сохранением_порядка._Монотонность_точки_разреза \| оптимального префиксного кодирования]] алфавита. Был разработан в 1952 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им курсовой работы. Используется во многих программах сжатия данных, например, PKZIP 2, LZH и др.		'''Алгоритм Хаффмана''' (англ. ''Huffman's algorithm'') — алгоритм [[Задача_об_оптимальном_префиксном_коде_с_сохранением_порядка._Монотонность_точки_разреза \| оптимального префиксного кодирования]] алфавита. Был разработан в 1952 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им курсовой работы. Используется во многих программах сжатия данных, например, PKZIP 2, LZH и др.

← Предыдущая		Версия 12:14, 27 марта 2016
Строка 150:		Строка 150:
	[[Категория: Дискретная математика и алгоритмы]]		[[Категория: Дискретная математика и алгоритмы]]

−	[[Категория: Алгоритмы сжатия ]]	+	[[Категория:Алгоритмы сжатия]]

@@ Строка 9: / Строка 9: @@
 :* <tex>c_{i}</tex> не является префиксом для <tex>c_{j}</tex>, при <tex>i \ne j</tex>,
-:* cумма <tex>\sum\limits_{i \in [1, n]} w_{i}\cdot |c_{i}|</tex> минимальна (<tex>|c_{i}|</tex> — длина кода <tex>c_{i}</tex>)
+:* cумма <tex>\sum\limits_{i \in [1, n]} w_{i}\cdot |c_{i}|</tex> минимальна (<tex>|c_{i}|</tex> — длина кода <tex>c_{i}</tex>),
 называется '''кодом Хаффмана'''.
 }}
 == Алгоритм построения бинарного кода Хаффмана ==

@@ Строка 7: / Строка 7: @@
 Пусть <tex>A=\{a_{1},a_{2}, \ldots ,a_{n}\}</tex> — алфавит из <tex>n</tex> различных символов, <tex>W=\{w_{1},w_{2}, \ldots ,w_{n}\}</tex> — соответствующий ему набор положительных целых весов. Тогда набор бинарных кодов <tex>C=\{c_{1},c_{2}, \ldots ,c_{n}\}</tex>, где <tex>c_{i}</tex> является кодом для символа <tex>a_{i}</tex>, такой, что:
-* <tex>c_{i}</tex> не является префиксом для <tex>c_{j}</tex>, при <tex>i \ne j</tex>,
+:* <tex>c_{i}</tex> не является префиксом для <tex>c_{j}</tex>, при <tex>i \ne j</tex>,
-* cумма <tex>\sum\limits_{i \in [1, n]} w_{i}\cdot |c_{i}|</tex> минимальна (<tex>|c_{i}|</tex> — длина кода <tex>c_{i}</tex>)
+:* cумма <tex>\sum\limits_{i \in [1, n]} w_{i}\cdot |c_{i}|</tex> минимальна (<tex>|c_{i}|</tex> — длина кода <tex>c_{i}</tex>)
 называется '''кодом Хаффмана'''.
@@ Строка 64: / Строка 64: @@
 |}
-На последнем шаге объединим два узла <tex>brcd</tex> и <tex>a</tex>:
+На последнем шаге объединим два узла {{---}} <tex>brcd</tex> и <tex>a</tex>:
 {| class="wikitable"

@@ Строка 5: / Строка 5: @@
 {{Определение
 |definition=
-Пусть <tex>A=\{a_{1},a_{2},...,a_{n}\}</tex> — алфавит из n различных символов, <tex>W=\{w_{1},w_{2},...,w_{n}\}</tex> — соответствующий ему набор положительных целых весов. Тогда набор бинарных кодов <tex>C=\{c_{1},c_{2},...,c_{n}\}</tex>, где <tex>c_{i}</tex> является кодом для символа <tex>a_{i}</tex>, такой, что:
+Пусть <tex>A=\{a_{1},a_{2}, \ldots ,a_{n}\}</tex> — алфавит из <tex>n</tex> различных символов, <tex>W=\{w_{1},w_{2}, \ldots ,w_{n}\}</tex> — соответствующий ему набор положительных целых весов. Тогда набор бинарных кодов <tex>C=\{c_{1},c_{2}, \ldots ,c_{n}\}</tex>, где <tex>c_{i}</tex> является кодом для символа <tex>a_{i}</tex>, такой, что:
-. <tex>c_{i}</tex> не является префиксом для <tex>c_{j}</tex>, при <tex>i \ne j</tex>
+* <tex>c_{i}</tex> не является префиксом для <tex>c_{j}</tex>, при <tex>i \ne j</tex>,
-. Сумма <tex>\sum\limits_{i \in [1, n]} w_{i}\cdot c_{i}</tex> минимальна. (<tex>|c_{i}|</tex> — длина кода <tex>c_{i}</tex>)
+* cумма <tex>\sum\limits_{i \in [1, n]} w_{i}\cdot |c_{i}|</tex> минимальна (<tex>|c_{i}|</tex> — длина кода <tex>c_{i}</tex>)
 называется '''кодом Хаффмана'''.
@@ Строка 15: / Строка 15: @@
 == Алгоритм построения бинарного кода Хаффмана ==
-Построение кода Хаффмана сводится к построению соответствующего бинарного дерева по следующему алгоритму:
+Построение кода Хаффмана сводится к построению соответствующего [[ Двоичная_куча | бинарного дерева]] по следующему алгоритму:
-* Составим [[Список | список]] кодируемых символов, при этом будем рассматривать один символ как дерево, состоящее из одного элемента c весом, равным частоте появления символа в строке.
+# Составим [[Список | список]] кодируемых символов, при этом будем рассматривать один символ как дерево, состоящее из одного элемента c весом, равным частоте появления символа в строке.
-* Из списка выберем два узла с наименьшим весом.
+# Из списка выберем два узла с наименьшим весом.
-* Сформируем новый узел с весом, равным сумме весов выбранных узлов, и присоединим к нему два выбранных узла в качестве детей.
+# Сформируем новый узел с весом, равным сумме весов выбранных узлов, и присоединим к нему два выбранных узла в качестве детей.
-* Добавим к списку только что сформированный узел вместо двух объединенных узлов.
+# Добавим к списку только что сформированный узел вместо двух объединенных узлов.
-* Если в списке больше одного узла, то повторим пункты со второго по пятый.
+# Если в списке больше одного узла, то повторим пункты со второго по пятый.
 === Время работы ===
@@ Строка 28: / Строка 28: @@
 === Пример ===
-[[Файл:Huffman_abracadabra.jpg|400px|thumb|right|Дерево Хаффмана для строки "<tex>abracadabra</tex>"]]
+[[Файл:Huffman_abracadabra.jpg|400px|thumb|right|Дерево Хаффмана для слова <tex>abracadabra</tex>]]
-Закодируем слово "<tex>abracadabra</tex>". Тогда алфавит будет <tex>A= \{a, b, r, c, d\} </tex>, а набор весов (частота появления символов алфавита в кодируемой строке) <tex>W=\{5, 2, 2, 1, 1\}</tex>:
+Закодируем слово <tex>abracadabra</tex>. Тогда алфавит будет <tex>A= \{a, b, r, c, d\} </tex>, а набор весов (частота появления символов алфавита в кодируемом слове) <tex>W=\{5, 2, 2, 1, 1\}</tex>:
 В дереве Хаффмана будет <tex>5</tex> узлов:
@@ Строка 48: / Строка 48: @@
 |}
-Затем опять объединим в один узел два минимальных по весу узла: <tex>r</tex> и <tex>cd</tex>:
+Затем опять объединим в один узел два минимальных по весу узла {{---}} <tex>r</tex> и <tex>cd</tex>:
 {| class="wikitable"
@@ Строка 64: / Строка 64: @@
 |}
-На последнем шаге объединим два узла <tex>brcd</tex> и <tex>a</tex>.
+На последнем шаге объединим два узла <tex>brcd</tex> и <tex>a</tex>:
 {| class="wikitable"
@@ Строка 72: / Строка 72: @@
 |}
-Остался один узел, значит, мы пришли к корню дерева Хаффмана (смотри рисунок). Теперь для каждого символа выберем кодовое слово: бинарную последовательность, обозначающую путь по дереву к этому символу от корня :
+Остался один узел, значит, мы пришли к корню дерева Хаффмана (смотри рисунок). Теперь для каждого символа выберем кодовое слово (бинарная последовательность, обозначающая путь по дереву к этому символу от корня):
 {| class="wikitable"
@@ Строка 80: / Строка 80: @@
 |}
-Таким образом, закодированное слово "<tex>abracadabra</tex>" будет выглядеть как <tex>01110101000010010111010</tex>. Длина закодированного слова {{---}} <tex>23</tex> бита. Стоит заметить, что если бы мы использовали алгоритм кодирования с одинаковой длиной всех кодовых слов (англ. ''Constant length coding''), то закодированная строка заняла бы <tex>33</tex> бита, что существенно больше.
+Таким образом, закодированное слово <tex>abracadabra</tex> будет выглядеть как <tex>01110101000010010111010</tex>. Длина закодированного слова {{---}} <tex>23</tex> бита. Стоит заметить, что если бы мы использовали алгоритм кодирования с одинаковой длиной всех кодовых слов, то закодированное слово заняло бы <tex>33</tex> бита, что существенно больше.
 == Корректность алгоритма Хаффмана ==
@@ Строка 136: / Строка 136: @@
 Справедливость теоремы непосредственно следует из лемм (1) и (2)
 }}
 == Источники информации ==

@@ Строка 24: / Строка 24: @@
 == Время работы ==
-Если сортировать элементы после каждого суммирования или использовать очередь с приоритетами, то алгоритм будет работать за время <tex>O(NlogN)</tex>.Такую асимптотику можно улучшить до <tex>O(N)</tex>, используя обычные массивы.
+Если сортировать элементы после каждого суммирования или использовать очередь с приоритетами, то алгоритм будет работать за время <tex>O(N \log N)</tex>.Такую асимптотику можно улучшить до <tex>O(N)</tex>, используя обычные массивы.
 == Пример ==

@@ Строка 28: / Строка 28: @@
 == Пример ==
-[[Файл:Mississippi.png|400px|thumb|right|Дерево Хаффмана для слова ''"Миссисипи"'']]
+[[Файл:Mississippi.png|400px|thumb|right|Дерево Хаффмана для слова ''"миссисипи"'']]
 Для примера возьмём слово ''" миссисипи"''. Тогда алфавит будет <tex>A= \{</tex> ''и, м, п, с'' <tex>\} </tex>, а набор весов <tex>W=\{4, 1, 1, 3\}</tex>: