Бинарные коды переменной длины

Определение link

Пусть $\Sigma$ конечный исходный алфавит. Бинарным кодом переменной длины называется инъективное отображение

$$ f\colon \Sigma \longrightarrow \lbrace 0,1 \rbrace ^ * $$

такое, что разным символам $\sigma \in \Sigma$ могут соответствовать кодовые слова разной длины. Эквивалентно код часто отождествляют с его множеством кодовых слов

$$ C = \lbrace f(\sigma)\mid \sigma \in \Sigma \rbrace \subseteq \lbrace 0,1 \rbrace^*, $$

при этом длины $l(c)$ для $c \in C$ могут различаться.

• Для обеспечения однозначного декодирования необходимо, чтобы любая конкатенация кодовых слов разбиралась единственным образом.
• Часто достаточным условием служит беспрефиксность кода:

$$ \forall x,y \in C, ~ x \neq y \implies x \text{ не является префиксом } y. $$

В этом случае декодирование мгновенно: считывайте биты до тех пор, пока не достигнете листа в соответствующем бинарном дереве.