Кодирование полиномом (polynom coding)

Дан алфавит \(A\) из \(k\) символов и строка \(s\) длины \(n\) над этим алфавитом. Нас интересуют способы кодирования этой строки. Если про строку кроме ее длины и алфавита больше ничего неизвестно, то можно воспользоваться следующим способом. Для этого зададим нумерацию на алфавите – каждому символу сопоставим число от \(0\) до \(k - 1\). Теперь строка \(s\) является последовательностью чисел от \(0\) до \(k - 1\). А теперь представим эту строку как запись (цифры) некоторого натурального числа \(X\) в системе счисления по основанию \(k\). При такой интерпретации

\[X = \displaystyle\sum_{i=0}^{n-1}{s[i]k^i}, \text{ причем } 0 \leq X < k^n.\]

Очевидно, разным строкам будут соответствовать разные \(X\) и наоборот. Получается, что каждой строке длины \(n\) над алфавитом \(A\) сопоставлено число. Теперь вместо строк можно оперировать этими числами. Например, если потребуется передать строку \(s\) по каналу связи, то достаточно передать ее номер \(X\). По современным каналам связи информация передается в двоичном представлении, поэтому \(X\) нужно перевести в систему счисления по основанию \(2\). Количество бит для представления \(X\) равно \(\log_2{k^n} = n\log_2{k}\), точнее \(\lceil n\log_2{k} \rceil\), потому что используется целое число бит.

Еще раз обратим внимание на то, что получилось. Каждой строке длины \(n\) над алфавитом \(A\) было сопоставлено натуральное число в диапазоне \([0, k^n)\). Это число можно записывать в разных системах счисления. Если взять систему счисления по основанию \(k\), то получится исходная строка. Если взять двоичную систему, то получится набор бит, готовый для передачи по каналам связи. Описанный вариант кодирования будем называть кодированием полиномом, потому что для получения \(X\) нужно вычислить полином.

Теперь определимся, когда такое кодирование выгодно. Минимально возможное число бит для представления строки \(s\) будет \(n \cdot H\), где \(H\) – энтропия. Энтропия вычисляется исходя из распределения символов алфавита в строке и означает минимальное среднее количество бит, для кодирования одного символа в строке. При кодировании полиномом среднее число бит для кодирования одного символа равно в точности \(log_2{k}\) вне зависимости от распределения. Энтропия же меняется в зависимости от распределения и достигает максимума при равномерном распределении. Этот максимум равен как раз \(log_2{k}\). Данный факт говорит о том, что кодирование полином является оптимальным для равномерного распределения.

Пример:

Пусть \(A=\{a, b, c\}\), \(s = aabaccb\). В данном случае \(k = 3\) и \(n = 7\). Нумерация следующая: \(a \rightarrow 0\), \(b \rightarrow 1\), \(c \rightarrow 2\). Тогда \(s = 0010221\). Для нахождения \(X\) вычислим полином:

\[X = 1 + 2 \cdot 3 + 2 \cdot 3^2 + 0 \cdot 3^3 + 1 \cdot 3^4 + 0 \cdot 3^5 + 0 \cdot 3^6 = 106.\]

Двоичное представлении для \(X\) : \(1101010\). Для представления \(X\) требуется \(\lceil 7 \cdot \log_2{3} \rceil = 12\) бит. Поэтому битовый код для строки \(s\) будет 000001101010.