Код Хаффмана с длиной кодового слова не более L бит — различия между версиями
283820 (обсуждение | вклад) м (Было: пусть дан алфавит из 5 символов <tex>A=\{A,B,C,C,D\}</tex> ; Стало: пусть дан алфавит из 5 символов <tex>A=\{A,B,C,D,E\}</tex>,) |
|||
Строка 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 Майкл Наки]. | ||
+ | |} | ||
+ | |||
'''Оптимальный префиксный код с длиной кодового слова не более L бит''' — это код, в котором длина каждого кодового слова не должна превышать заданной константы. Здесь будет приведен алгоритм, решающий эту задачу за время <tex> O(nL) </tex>, где <tex>L</tex> — максимальная длина кодового слова, <tex>n</tex> — размер алфавита, c помощью сведения задачи к [[Задача_о_рюкзаке | задаче о рюкзаке]]. | '''Оптимальный префиксный код с длиной кодового слова не более L бит''' — это код, в котором длина каждого кодового слова не должна превышать заданной константы. Здесь будет приведен алгоритм, решающий эту задачу за время <tex> O(nL) </tex>, где <tex>L</tex> — максимальная длина кодового слова, <tex>n</tex> — размер алфавита, c помощью сведения задачи к [[Задача_о_рюкзаке | задаче о рюкзаке]]. | ||
Версия 08:50, 1 сентября 2022
НЕТ ВОЙНЕ |
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России |
Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению. |
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки. |
Оптимальный префиксный код с длиной кодового слова не более L бит — это код, в котором длина каждого кодового слова не должна превышать заданной константы. Здесь будет приведен алгоритм, решающий эту задачу за время задаче о рюкзаке.
, где — максимальная длина кодового слова, — размер алфавита, c помощью сведения задачи кДанный алгоритм бывает полезен, когда нам нужно ограничить максимальную длину кодового слова, а при использовании алгоритма Хаффмана самому редко встречающемуся символу соответствует слишком длинное кодовое слово. Например, пусть дан алфавит из 5 символов
, а частоты символов являются степенями двойки: . Тогда классический код Хоффмана будет выглядеть следующим образом:
Самое длинное кодовое слово здесь имеет длину 4. Пусть мы хотим, чтобы слова в нашем коде были не длиннее трех бит. Тогда алгоритм, который будет описан ниже, генерирует такой код:
Важно заметить следующий факт. В худшем случае все кодовые слова будут иметь длину L бит. Тогда мы можем закодировать
символов. Таким образом, нельзя получить описанный выше код, если .Содержание
- 1 Сведение задачи о рюкзаке к генерации оптимального префиксного кода с длиной кодового слова не более L бит.
- 2 Восстановление ответа.
- 3 Пример работы алгоритма генерации оптимального префиксного кода с длиной кодового слова не более L бит
- 4 Пример восстановления ответа.
- 5 См. также
- 6 Источники информации
Сведение задачи о рюкзаке к генерации оптимального префиксного кода с длиной кодового слова не более L бит.
Пусть
— ограничение на длину кодового слова, а — частоты символов алфавита. Алгоритм генерации кода будет следующим:- Отсортируем символы алфавита в порядке возрастания их частот.
- Для каждого символа создадим предметов ценностью , каждый из которых имеет вес .
- С помощью задачи о рюкзаке выберем набор предметов суммарной ценностью ( — размер алфавита) с минимальным суммарным весом.
- Посчитаем массив , где — количество предметов ценностью , которые попали в наш набор.
При этом
— это длина кодового слова для -го символа.Зная длины кодовых слов, легко восстановить и сам код.Восстановление ответа.
- Отсортируем все символы по возрастанию длины кодового слова, которое им соответствует, а при равенстве длин — в алфавитном порядке.
- Первому символу сопоставим код, состоящий из нулей, соответствующей длины.
- Каждому следующему символу сопоставим следующее двоичное число. При этом если его длина меньше необходимой, то допишем нули справа.
Заметим, что при генерации каждого следующего кодового слова, в качестве его префикса выступает последовательность, лексикографически большая, чем предыдущее кодовое слово (т.к. мы берем следующее двоичное число), а значит ни для каких двух кодовых слов одно не может быть префиксом другого. Т.е. код, сгенерированный таким образом является префиксным.
Пример работы алгоритма генерации оптимального префиксного кода с длиной кодового слова не более L бит
Пусть
— алфавит из трех различных символов, — соответствующий ему набор частот. Пусть — ограничение на длину кодового слова.Сначала создадим необходимый набор предметов;
Символ | Частота | Предметы |
---|---|---|
A | 1 | |
B | 2 | |
C | 3 |
Решим задачу о рюкзаке для заданного набора и выберем предметы суммарной ценностью
с минимальным суммарным весом. В нашем случае в оптимальный набор попадут следующие предметы:
Посчитаем массив
:
Итак, мы получили длины кодовых слов для символов. Осталось восстановить ответ.
Пример восстановления ответа.
Итак, у нас есть
— алфавит из n различных символов, а также — соответсвующие длины кодовых слов. Отсортируем символы в соответсвии с этими длинами.Сопоставим первому символу код, состоящий из 1 нуля:
Сопоставим следующему символу следующее двоичное число. Т.к. длина кода увеличилась на один, то припишем справа ноль:
Сопоставим следующему символу следующее двоичное число.