#python #python-3.x #algorithm #binary #huffman-code
#питон #python-3.x #алгоритм #двоичный #хаффман-код
Вопрос:
Итак, я пытаюсь решить проблему, связанную с декодированием некоторого сжатого сообщения Хаффмана, не зная дерева кода, используемого для сжатия.
Однако я знаю алфавит, который использовался в сообщении.
Поэтому моя идея состояла в том, чтобы попытаться применить силу, но мне немного не хватает навыков работы с алгоритмами.
Я представил, что попытаюсь сгенерировать коды для букв во всех возможных комбинациях. Проблема, однако, в том, что коды (в двоичном формате) никогда не смогут скрыть друг друга.
Таким образом, примером может быть:
| Письмо | Код |
|---|---|
| A | 0100 |
| B | 1111 |
| C | 1011 |
Но тогда не могло быть никаких других кодов, которые начинались бы с любого из вышеперечисленных, так как в конечном итоге они скрывали бы друг друга.
Итак, для алфавита из 40 символов я хотел бы создать уникальные, не скрывающие битовые коды.
Хотя я понятия не имею, с чего начать. Любые советы будут оценены по достоинству.
- Существуют ли какие-либо умные алгоритмы, о которых я не знаю (очень вероятно)?
- Это называется чем-то, чего я не знаю, что могло бы помочь мне в поиске?
- Есть какие-нибудь советы о том, как на самом деле это создать, в любом случае?
Комментарии:
1. Не хочу отвечать на ваш вопрос, но термин, который вы ищете, — это «префиксный код», кодирование, в котором никакое кодирование не является префиксом другого.
2. Кодирование Хаффмана не является обратимым без дополнительной информации. Например, с 3-символьным алфавитом существует только одно допустимое дерево Хаффмана: { 0, 10, 11}, но существует шесть способов присвоения символов кодам. С 40-символьным алфавитом существует примерно 2 миллиарда допустимых деревьев и 40! (это 40 факториальных) способов присвоения символов.
3. Знаете ли вы сообщение, а затем вас просят придумать код? Невозможно найти сообщение с помощью только алфавита и битов сообщения. Существует огромное количество возможных допустимых решений.
4. Да, я понимаю, что это множество комбинаций и, возможно, в конце концов это невозможно. Однако это просто забавный вызов между некоторыми коллегами. Никаких ставок, никаких крайних сроков. Просто хотел попробовать подход брутфорса 🙂
Ответ №1:
Я не думаю, что вы сможете просто перечислить все возможные кодировки. Я легко могу придумать схему для генерации более 2^39 различных кодировок, и в каждой из этих кодировок будет 40! различные способы присвоения кодов буквам.
Пусть x это случайная 40-битная строка. Смотреть на
~x[0] x[0:1] ~x[1] x[0:2] ~x[2] x[0:3] ~x[3] .... x[0:39] ~x[39] x[0:40] Это префиксный код для любого значения x .
Ответ №2:
Пожалуйста, дайте мне знать, если я неправильно понял ваш вопрос.
Двоичные числа сопоставляются один к одному с десятичными числами, поэтому вы можете покрыть двухсимвольный алфавит двоичными числами длиной 1, четырехсимвольными числами длиной 2 и т. Д.
Таким образом, для 40-символьного алфавита вам понадобятся двоичные коды длиной 6. Тогда, если они у вас есть в списке:
alphabet = ['A', 'B', 'C', ...] Вы могли бы получить свое отображение с помощью
mapping = {alphabet[i]: format(i, "b").zfill(6) for i in range(len(alphabet))} {'A': '000000', 'B': '000001', 'C': '000010', ...} Комментарии:
1. Я не думаю, что это генерирует префиксный код, такой как код Хаффмана.
2. Да, это не настоящий двоичный код буквы, который мне нужен. Вместо этого это уникальный код переменной длины. В основном это алгоритм сжатия, который я пытаюсь повернуть вспять с помощью грубой силы. Таким образом, коды-это способ заставить каждый байт занимать меньше битов, поэтому они генерируются таким образом, а не просто являются их фактическим двоичным значением.