Какой самый компактный способ кодирования списков символов из конечного множества?

Question

Мне интересно представить последовательность символов из конечного набора с наименьшим числом байтов.

Например, допустим, у вас есть текстовая строка, которая содержит только символы a-z. Вы можете закодировать их как ascii, так что 1 байт на символ (символ). Однако при этом вы используете только 26 из 256 возможных значений на байт.

Я кодировал решение, которое, кажется, работает хорошо, но я хотел бы знать, если кто-нибудь знает или может придумать лучший способ.

Мой метод заключается в обработке последовательности как целого числа в основании n, где n равно the size of the set of symbols + 1. Например, если ваш набор или символы, или «алфавит» был {a, b, c} (длина 3), то мы использовали бы основание 4. Символам присваиваются числовые значения, поэтому {a => 1, b => 2, c => 3}. Следовательно, последовательность [b, a, c] рассматривается как число 213 в основании 4, так что 39 в десятичном виде. Это целое число может быть закодировано в двоичном виде и декодировано обратно в его базовое представление 4 для получения последовательности 2, 1, 3 => [b, a, c].

Моя реализация Python выше: radixcodec.py

Итак, мой вопрос: есть ли более эффективный способ кодирования списков элементов из конечного набора, чем тот, который я описал?

Answer 1

Используйте основание n , где n - количество символов (например, {a => 0, b => 1, c => 2}). Этот метод оптимален, если каждый символ одинаково вероятен. (Конечно, вам также придется хранить длину строки. Кстати, ваша реализация использует строки Python; это определенно не самая экономичная структура данных, которую вы можете найти.)

Если частоты символов различаются и вы их знаете, вы можете использовать кодирование Хаффмана . Если вы не знаете частоты, есть адаптивное кодирование Хаффмана .

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