Расшифровка букв ('a' .. 'z') из битовой последовательности без потерь

Question

Я ищу алгоритм, который позволил бы мне представлять входящую последовательность битов в виде букв ('a' .. 'z'), в минимальном размере, так что поток битов может быть восстановлен из букв, даже не удерживая вся последовательность в памяти.

То есть, учитывая внешний источник битов (каждое чтение возвращает практически случайный бит) и пользовательский ввод числа битов, я хотел бы распечатать минимальное количество символов, которые могут представлять эти биты.

В идеале должна быть параметризация - сколько памяти и максимум битов, прежде чем потребуются некоторые потери.

Цель эффективности - то же количество символов, что и в представлении битов в base-26.

Non-решения:

1. Если было достаточно места, сохраните всю последовательность и используйте операцию MOD 26 с большим целым числом.

2. Преобразование каждых 9 битов в 2 символа - это кажется неоптимальным, тратя 25% информационной емкости выводимых букв.

Answer 1

Если вы назначите разное количество битов на букву, вы сможете точно закодировать биты из двадцати шести разрешенных букв без потери битов. (Это очень похоже на код Хаффмана, только с предварительно построенным сбалансированным деревом.)

Чтобы закодировать биты в буквы: накапливайте биты, пока не совпадете точно с одним из битовых кодов в таблице поиска. Выведите эту букву, очистите буфер битов и продолжайте.

Чтобы декодировать буквы в биты: для каждой буквы выведите последовательность битов в таблице.

Внедрение в коде оставлено читателю в качестве упражнения. (Или мне, если мне будет скучно позже.)

a 0000
b 0001
c 0010
d 0011
e 0100
f 0101
g 01100
h 01101
i 01110
j 01111
k 10000
l 10001
m 10010
n 10011
o 10100
p 10101
q 10110
r 10111
s 11000
t 11001
u 11010
v 11011
w 11100
x 11101
y 11110
z 11111

Answer 2

Преобразование каждого блока из 47 битов в число из 26 основных цифр из 10 цифр. Это дает эффективность более 99,99%.

Этот метод, как и другие, такие как Хаффман, нуждается в механизме заполнения для поддержки ввода переменной длины. Это приводит к некоторой неэффективности, которая менее значима при более длинных входах.

В конце потока битов добавьте дополнительный бит 1. Это должно быть сделано во всех случаях, даже когда длина потока битов кратна 47. Любые буквы старшего разряда с нулевым значением могут быть пропущены в последнем блоке кодированного вывода.

При декодировании букв усеченный конечный блок может быть заполнен "нулевыми" буквами и преобразован в 47-битовое представление с основанием 2. Последний бит 1 не является данными, но отмечает конец потока битов.

Answer 3

Ноль отходов будет log_2 (26) бит на букву. Как указывалось ранее, вы можете получить 4,7, прочитав 47 бит и преобразовав их в 10 букв. Тем не менее, вы можете получить 4,67, преобразовав каждые 14 бит в 3 символа. Это имеет то преимущество, что оно вписывается в целое число. Если у вас есть место для хранения и время выполнения важно, вы можете создать таблицу поиска с 17 576 записями, отображающими возможные 14 бит в 3 буквы. В противном случае вы можете выполнять операции mod и div для вычисления 3 букв.

number of letters    number of bits    bits/letter
 1                    4                4
 2                    9                4.5
 3                   14                4.67
 4                   18                4.5
 5                   23                4.6
 6                   28                4.67
 7                   32                4.57
 8                   37                4.63
 9                   42                4.67
10                   47                4.7

Answer 4

Может ли кодирование Хаффмана быть тем, что вы ищете? Это алгоритм сжатия, который в значительной степени представляет любую информацию с минимумом потерянных битов.

Answer 5

Если вы хотите, чтобы двоичный элемент каждой буквы имел одинаковый размер, оптимальное решение будет дано Арифметическое кодирование . Тем не менее, он не достигнет вашей цели среднего представления 4,5 бит / символ. Учитывая 26 различных символов (не включая пробел и т. Д.), 4.7 будет лучшим, что вы можете достичь, не используя кодирование переменной длины (например, Хаффмана. См. Ответ Джегерса) или другие алгоритмы сжатия.

Неоптимальным, хотя и более простым, решением может быть нахождение допустимого количества символов, которые можно поместить в большое целое число. Например, если вы формируете 32-разрядное целое число из каждых 6 блоков символов (что возможно как 26 ^ 6 <2 ^ 32), вы используете 5,33 бит / символ. Вы можете даже вставить 13 букв в 64-битное целое число (4,92 бит / символ). Это довольно близко к оптимальному решению и все же довольно легко реализовать. Использование больших 64-битных целых может быть непростым делом из-за отсутствия встроенной поддержки во многих языках программирования. </p>

Если вы хотите получить еще более высокие коэффициенты сжатия для текста, вам определенно следует обратить внимание на алгоритмы сжатия на основе словаря, такие как LZW или Deflate.

Answer 6

Любое решение, которое вы используете, будет неэффективным в пространстве, потому что 26 не является степенью 2. Что касается алгоритма, я бы предпочел использовать таблицу поиска, а не вычисления на лету для каждой серии 9 бит Ваша таблица поиска будет содержать 512 записей.