Если нам дан двоичный файл длины n, где каждый бит независимо равен единице с вероятностью 1/3 и нулем в остальном. Мы хотим построить метод, согласно которому ожидаемая длина сжатой последовательности будет менее чем на 10 процентов больше, чем нижняя граница Шеннона (для всех достаточно больших n). У меня есть нижняя граница 0,918. Я пытался использовать кортежи размера 2, но это дает мне ожидаемую длину 1,88 по кодированию Хаффмана. Я иду в правильном направлении?
Энтропийная граница Шеннона равна 0,918 выходных бит на входной бит.
Если вы просто запишите заданные вами биты, вы потратите 1 выходной бит на входной бит.
Это уже меньше, чем на 10% границы, поэтому сжатие не требуется.
Вы можете использовать Arithmeti c компрессор или Rangecoder .
Существует объяснение с кодом для Arithmeti c компрессор и реализация с открытым исходным кодом Rangecoder .
Я лично рекомендую использовать Rangecoder, потому что он работает быстрее всего и никогда не был запатентован (срок действия патента на арифметику c компрессор уже истек).