Prefix-Free Encoding

출처

숫자가 아닌 임의의 객체를 인코딩하려면 2가지 조건이 필요하다.
하나는 인코딩 함수가 one-to-one 이어야 한다는 것과,
두번째는 Prefix-Free 이어야 한다는 것이다.

One-To-One 이 필요한 이유는 매우 직관적이다.
One-To-One 이 아니라면 Decoding 이 불가능하기 때문이다.

Prefix-Free 가 필요한 이유는 여러개의 객체를 tuple 로 묶어서 인코딩을 하기 위해서이다.
만약 Prefix-Free 하지 않는다면, 여러개의 객체를 하나의 bit string 으로 표현하는 인코딩 함수가
one-to-one 이 아니게 되어서, Decoding 이 불가능할수도 있다.

Definition 2.17 (Prefix free encoding)

$y,y'$: string
$y$ is a prefix of $y'$ if
$|y| \leq |y'|$ and $\forall i<|y|$, $y'_i = y_i$

$\mathcal{O}$ : non-empty set
$E:\mathcal{O} \rightarrow \{0,1\}^*$ : function
E is prefix free if
$E(o) \neq \emptyset, \forall o \in \mathcal{O}$ and
$\nexists$ distinct objects $o,o' \in \mathcal{O}$ s.t $E(o)$ is a prefix of $E(o')$

Theorem 2.18 (Prefix-free implies tuple encoding)

$E:\mathcal{O} \rightarrow \{0,1\}^*$ is prefix-free
Define $\overline{E}:\mathcal{O}^* \rightarrow \{0,1\}^*$ as follows:
$\forall o_0,\ldots,o_{k-1} \in \mathcal{O}^*$

Then, $\overline{E}$ is one to one.

Proof

Suppose $\overline{E}$ is not one to one.
$\Rightarrow \exists$ distinct tuples $(o_0,\ldots,o_{k-1})$, $(o'_0,\ldots,o'_{k'-1})$ s.t

Let $i$ be the first index s.t $o_i \neq o'_i$
Then, $x_j = E(o_j) = E(o'_j)$ for $\forall j \in \{0, 1, 2, \dots i-1\}$.

$\therefore E(o_i) \cdots E(o_{k-1}) = E(o'_i) \cdots E(o'_{k'-1})$
This means that one of $E(o_i)$ and $E(o'_i)$ must be a prefix of the other.
This contradicts to "E is prefix-free".
Proved by contradiction.
QED

Lemma 2.20

$E:\mathcal{O} \rightarrow \{0,1\}^*$ is one-to-one. Then,
$\exists$ one-to-one prefix-free encoding $\overline{E}$ s.t $|\overline{E}(o)| \leq 2|E(o)|+2$ for $\forall o\in \mathcal{O}$.

Proof

Double every bit in the string $x$ ($0 \mapsto 00$, $1 \mapsto 11$)
and mark the end of the string by concatenating to it the pair $01$.
Then, $E(x) \neq E(x')$ for $\forall x \neq x'$

Define a function $PF:\{0,1\}^* \rightarrow \{0,1\}^*$ for $x\in \{0,1\}^*$ as follows:

We want to show $\overline{E}(o)=PF(E(o))$ is an prefix-free encoding.

(1) $\overline{E}$ is encoding

$E$ is one-to-one and $PF$ is one-to-one.
Then, $\overline{E}=PF \circ E$ is also one-to-one
$\therefore$ $\overline{E}$ is encoding.

(2) $\overline{E}$ is prefix-free

$\overline{E}$ is prefix-free
$\Leftrightarrow$ $\overline{E}(o)$ is not a prefix of $\overline{E}(o')$ for
$\forall$ distinct object $o, o' \in \mathcal{O}$

Suppose $\overline{E}(o)$ is a prefix of $\overline{E}(o')$ for some distinct $o, o' \in \mathcal{O}$
$\overline{E}(o)=PF(E(o))$
$\overline{E}(o')=PF(E(o'))$
Let $x = E(o)$, $x'=E(o')$.
Since $E$ is one-to-one, $x \neq x'$.

(i) $|x|<|x'|$
the two bits in positions $2|x|$ in $PF(x)$ will be $01$
but two bits in positions $2|x|$ in $PF(x')$ will be $00$ or $11$
$\Rightarrow$ $PF(x)$ and $PF(x')$ differ in the coordinates $2|x|, 2|x|+1$
$\therefore PF(x)$ cannot be a prefix of $PF(x')$.

(ii) $|x|=|x'|$
Since $x \neq x'$, $\exists$ coordinate $i$ in which they differ.
$\Rightarrow$ $PF(x)$ and $PF(x')$ differ in the coordinates $2i,2i+1$
$\therefore$ $PF(x)$ cannot be a prefix of $PF(x')$.

(iii) $|x|>|x'|$
then $|PF(x)|=2|x|+2>|PF(x')|=2|x'|+2$.
$\Rightarrow$ $PF(x)$ is longer than $PF(x')$.
$\therefore PF(x)$ cannot be a prefix of $PF(x')$.

Therefore, $PF(x)=\overline{E}(o)$ is not a prefix of $PF(x')=\overline{E}(o')$ for $\forall o, o' \in \mathcal{O}$.
Hence, completing the proof.
QED