Арифметическое кодирование, символ завершения и пустая строка

Question

Предположим, что исходным алфавитом является a, b, c с a в качестве символа завершения, и поэтому единичный интервал соответственно делится на [0, P (a), P (a) + P (b), 1].

Строки, состоящие из группы b и c, оканчивающихся на a (символ завершения), действительны для кодирования.Строки с a в середине считаются недопустимыми для кодирования.

Таким образом, легко создавать строки с кодировками, лежащими в интервале [P (a), 1).Но назначает ли арифметическое кодирование какой-либо строке кодировку в интервале [0, P (a))?Будет ли пустая строка считаться закодированной в цепочку битов, лежащую в [0, P (a))?Поскольку пустая строка может рассматриваться как строка «a» или как просто символ завершения.

Поскольку выделение места для кодирования пустой строки может показаться бессмысленным, почему бы не сделать первое деление единичного интервала следующим образом [0, (P (b) -P (a)) / (1-P (a)), 1], что соответствует отображению [P (a), P (a) + P (b), 1] для заполненияединичный интервал.Тогда последующие уточняющие деления будут использовать [0, P (a), P (a) + P (b), 1] как обычно.

Answer 1

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