Или же он будет пыхтеть, пыхтеть и взрывать твой дом!
Это было совершенно неактуально. Эта проблема на самом деле о кодировании Хаффмана . Суть в том, что частота символов в данном тексте используется, чтобы сделать его представление короче. Другими словами, скажем, что наш алфавит a
сквозной z
и пробел. Это 27 символов. Каждый из них может быть уникально закодирован всего в 5 битах, потому что 5 битам достаточно места для 32 символов. Однако во многих ситуациях (например, в английском или в других языках) некоторые символы встречаются чаще, чем другие. Мы можем использовать меньше битов для более частых символов и (возможно) больше битов для менее частых символов. Если все сделано правильно, то количество битов в целом уменьшится, а исходный текст все равно можно будет восстановить уникальным образом.
Давайте возьмем «этот вопрос о кодировании Хаффмана» в качестве примера. Этот текст имеет длину 37 символов, что обычно составляет 37 * 8 = 296 бит, хотя только 37 * 5 = 185 бит, если мы используем только 5 бит для каждого символа. Запомни.
Вот таблица (sorta) каждого символа и их частоты в тексте, отсортированная от наиболее частой к наименее (где _ обозначает пробел):
_ 5
i 4
n 3
o 3
s 3
t 3
u 3
a 2
f 2
h 2
b 1
c 1
d 1
e 1
g 1
m 1
q 1
Соответствующее оптимальное кодирование может быть:
_ 101
i 011
n 1100
o 1101
s 1110
t 1111
u 001
a 10011
f 0001
h 0101
b 00000
c 00001
d 01000
e 01001
g 10000
m 10001
q 10010
Должно быть сразу ясно, что это будет лучшая кодировка, чем просто использование 5 битов для каждого символа. Давайте выясним, насколько лучше!
145 бит по сравнению с 185! Это экономия 40 бит или чуть более 20%! (Это, конечно, при условии, что информация о структуре доступна для декодирования.) Это кодирование является оптимальным, поскольку больше битов не может быть отброшено путем изменения представления любого символа.
Задание
- Напишите программу или функцию с одним параметром, который ...
- Принимает входные данные из STDIN (или эквивалентные) или в качестве одного аргумента.
- Выведите оптимальное кодирование Хаффмана, как указано выше, с символами, отсортированными по частоте (порядок в пределах класса частот не имеет значения).
- Вы можете предположить, что символы на входе ограничены диапазоном ASCII
32..126
плюс новая строка. - Вы можете предположить, что ввод не более 10 000 символов (в идеале, теоретически, ввод должен быть неограниченным).
- Ваш код должен закончиться достаточно быстро. Приведенный выше пример в худшем случае должен занять не более минуты. (Это предназначено, чтобы исключить грубую силу.)
- Оценка в байтах.
Примеры
x
---
x 0
xxxxxxxxx
---
x 0
xxxxxxxxy
---
x 0
y 1 (these may be swapped)
xxxxxyyyz
---
x 0
y 10
z 11
uuvvwwxxyyzz
--- (or)
u 000 000
v 001 001
w 100 010
x 101 011
y 01 10
z 11 11
this question is about huffman coding
---
101
i 011
n 1100
o 1101
s 1110
t 1111
u 001
a 10011
f 0001
h 0101
b 00000
c 00001
d 01000
e 01001
g 10000
m 10001
q 10010
Удачного кодирования!
Обратите внимание, что этот похожий вопрос тесно связан даже с тем, что этот вопрос является дубликатом. Тем не менее, единый консенсус в отношении Меты заключается в том, что более старый следует считать его дубликатом.
источник
this question is about huffman coding
я посчитал число битов равным 145 , а не 136.Ответы:
Pyth, 53 байта
демонстрация
Вот версия, которая показывает внутреннее состояние, так что вы можете видеть, как строится кодировка:
демонстрация
Скопируйте вывод в среду с более широкими линиями для более четкого изображения.
источник
Python 2, 299 байт
Вот моя попытка ответа.
Коды Хаффмана отличаются от приведенных примеров, но все же должны быть оптимальными.
источник
Matlab, 116 байт
tabulate
делает таблицу частот.huffmandict
берет список символов и вероятностей для каждого символа и вычисляет код.источник
Рубин,
189180 байтРабота в процессе.
Это анонимная функция; например, назначить его чему-либо
f
и вызватькоторый возвращает хеш как это:
источник
Haskell, 227 байт
Пример использования:
Как это устроено:
p
Вызовы,f
которые строят таблицу Хаффмана в виде списка (символ, кодировка) -пар, например[ ('a',"0"), ('b',"1") ]
, сортируют таблицу по длине кодировок, форматируют каждую пару для вывода и объединяют между ними символами новой строки.f
сначала проверяет регистр одной буквы и возвращает соответствующую таблицу. В противном случае он сортирует входную строку и группирует последовательности одинаковых символов (например,"ababa"
->["aaa","bb"]
) и отображает их в пары(sequence , [(char, "")])
(->[ ("aaa", [('a',"")]), ("bb", [('b', "")])]
. Первый элемент используется для отслеживания частоты, второй элемент представляет собой список пар символа и это кодировка (которая изначально пуста) .Это все таблицы Хаффмана с одним элементом, как ожидается,p
и объединяются с помощьюg
иh
.g
сортирует список пар по длине первого элемента, то есть по частоте и по вызовамh
.h
объединяет таблицы Хаффмана первых двух элементов, объединяя частоты и помещая0
(1
) перед каждым элементом первой (второй) таблицы. Объединить обе таблицы. Вызовитеg
снова, остановитесь, когда останется один элемент, отбросьте частотную часть и верните полную таблицу Хаффмана.источник
К (нгн / к) , 78 байт
Попробуйте онлайн!
возвращает список строк для печати
h::0#'x
создает пустой список для каждого символа (технически он изменяет каждый символ до длины 0). мы будем хранить обратные коды Хаффмана там. мы используем::
вместо:
присвоения, чтобы сделатьh
глобальным, чтобы это было видно в подфункциях..=x
список списков - индексы строки, сгруппированные по значению символа(#1_)
это функция, которая возвращает истину, если длина аргумента> 1 (технически "длина 1 капли ...")(#1_){
...}/
означает: пока аргумент имеет длину> 1, продолжайте применять функцию фигурных скобокx@<#'x
отсортировать аргумент по длине0 2_
разрезать его на 2-х элементную голову и хвост{h[x],:!2;y,,,/x}
обновитьh
, добавив 0 и 1 к индексам, содержащимся в заголовке; вернуть хвост с головой в качестве единого элемента(?,/'x,'" ",'|'$h)(?x)?>#'=x
поменять местами всеh
, отсортировать, уникальные, добавить соответствующие символы и отформатироватьисточник
JavaScript (ES6) 279
По сути, основной алгоритм из Википедии. Я, наверное, могу сделать лучше.
Более читаемый внутри фрагмента ниже
источник