Это эффективная проблема кодирования.
Входные данные - это битовый массив переменной длины с максимальной длиной 63. Например:
[0, 0, 0, 1, 0, 0, 1]
0 s намного большеобщее в этом массиве, чем 1 с. Допустим, 1 s встречаются примерно в 5% случаев.
Мой формат вывода также ограничен. Я могу вывести строку, состоящую только из 36 символов az и 0-9. Вывод переменной длины в порядке.
Я хочу алгоритм кодирования без потерь, который минимизирует мою среднюю длину выходной строки.
Простое кодирование без потерь будет состоять в назначении каждой из первых 32 букв в моем выходном алфавитев уникальную 5-битную последовательность, разделите мой вход на 5-битные выходы и выведите одну букву на 5 бит. Это дает мне ожидаемую длину строки: размер входного массива / 5.
Однако это не использует ни малую вероятность 0 с на входе, ни оставшиеся 4 буквы в моем алфавите.
Можете ли вы предложить лучшую схему кодирования?