#algorithm #encoding #binary #scheme
#алгоритм #кодирование #двоичный #схема
Вопрос:
У меня есть схема кодирования, но я не знаю ее названия. Я знаю, что должен быть алгоритм для кодирования / декодирования целых чисел в эту двоичную схему. Схема выглядит следующим образом:
1 2 3 4 5 6 7 8 9 etc.
0 - 0 0 00 00 00 00 000 000
1 1 10 01 01 01 010 001 001
2 11 10 10 100 011 010 010
3 11 110 101 100 011 011
4 111 110 101 100 100
5 111 110 101 101
6 111 110 110
7 111 1110
8 1111
etc.
Пример:
Когда у вас есть диапазон из 6 целых чисел (от 0 до 5), вы можете использовать столбец 6. При этом вы можете немного сэкономить на числах 0 и 1. При использовании столбца 9 вы сэкономите немного на каждом числе, кроме 7 и 8.
«Вы сэкономите немного» противоречит использованию 2, 3, 4 или N битовых слов.
Я попытался погуглить это, но не могу найти правильные ключевые слова для поиска. Может ли кто-нибудь указать мне правильное направление?
Спасибо!
Ответ №1:
Похоже, что это кодирование Хаффмана с предполагаемым равномерным распределением по всем значениям в любом заданном диапазоне.
Так, например, 5-й столбец — это просто кодировка Хаффмана для набора символов [0-5] (включительно), которая предполагает, что все 6 чисел имеют равную вероятность появления.
Комментарии:
1. Привет, Диллон Дэвис, кодирование Хаффмана пришло мне в голову. Но я думаю, что вы правы. Использование набора 0-5 с равными частотами действительно приведет к получению битов на запись в столбце.
2. Знаете ли вы, существует ли алгоритм, который не требует построения дерева для каждого диапазона (0-N), но вычисляет их напрямую? Для этого должен быть шаблон. Я искал De Bruijn и некоторые другие последовательности, но не смог найти ту, которая подходит для этой проблемы. Я хочу поблагодарить вас за ваше предложение, это дало мне идею. Я мог бы предварительно загрузить все таблицы Хаффмана для каждых 0-N диапазонов, которые у меня есть.
3. @Willempie изучите адаптивное кодирование Хаффмана. В качестве бонуса он также адаптируется к частоте каждой цифры / символа, чтобы стать более эффективным.