Siguiente: Códigos de Huffman Arriba: Codificación Anterior: Decodificación única

Algoritmo de Sardinas-Patterson

Sea $\gamma:A\to C^+$ una función de codificación. Recordamos que confundiremos voluntariamente $\gamma^*:A^*\to C^*$ con $\gamma$. La función $\gamma$ es de decodificación única si rige la implicación siguiente:

$$\gamma(\alpha_0)\cdots\gamma(\alpha_{\mu-1}) = \gamma(\beta_... ... \mu=\nu\ \&\ \left[\forall i<\mu:\ \alpha_i = \beta_i\right]$$ (3)

cualesquiera que sean los símbolos $\alpha_0,\ldots,\alpha_{\mu-1}\,;\,\beta_0,\ldots,\beta_{\nu-1}\in A$.

Sea $\Gamma = \gamma(A)\subset C^+$ la imagen bajo la función de codificación $\gamma$ del alfabeto $A$. Recursivamente, se define $\Gamma^0 = \{\mbox{\rm nil}\}$ y $\Gamma^{k+1} = \Gamma^k\Gamma$. Para cada $k\in\mathbb{N}$, $\Gamma^k$ es pues la familia de palabras en $C^+$ consistente de códigos de palabras de longitud $k$ en $A$.

Si $\gamma$ es de decodificación única, entonces la relación (3) implica que toda palabra en $\Gamma^k$ se expresa de manera única como la concatenación de $k$ palabras en $\Gamma$. Sintetizaremos esta última propiedad, diciendo que $\Gamma^k$ es de factorización única sobre $\Gamma$.

Proposición 2.1   Si $\gamma$ es de decodificación única, entonces para cualesquiera $n,k\in\mathbb{Z}^+$, $\Gamma^{kn}$ es de factorización única sobre $\Gamma^k$.

Se define también $\Gamma^* = \bigcup_{k\in\mathbb{N}}\Gamma^k$.

Proposición 2.2 (Criterio de Schützenberger)   Considérese las siguientes tres condiciones:

1. $\gamma$ es de decodificación única.
2. $\Gamma\cap\left[\bigcup_{k\geq 2}\Gamma^k\right]=\emptyset$
3. $\left[\left(\sigma\Gamma^*\right)\cap\Gamma^*\not=\emptyset\mbox{ o }\left(\Gam... ...sigma\right)\cap\Gamma^*\not=\emptyset\right]\ \Longrightarrow\ \sigma\in\Gamma$.

Entonces vale la equivalencia:

$$\mbox{ 1. } \Longleftrightarrow\mbox{ 2. \& 3.}$$ (4)

En efecto, veamos cada una de las implicaciones requeridas. Por un lado:

1. $\Longrightarrow$ 2. Es claro que si hubiera una palabra $\rho\in\Gamma\cap\left[\bigcup_{k\geq 2}\Gamma^k\right]$, ella tendría más de una factorización y en consecuencia $\gamma$ no podría ser de decodificación única.

1. $\Longrightarrow$ 3. Supongamos que hubiese una palabra $\tau\in\left(\sigma\Gamma^*\right)\cap\Gamma^*$. Existen entonces $k_0,k_1\in\mathbb{N}$ tales que $\rho\in\sigma\Gamma^{k_0}\cap\Gamma^{k_1}$. Por la descomposición única a fortiori $k_1=k_0+1$ y $\sigma\in\Gamma$.

Por otro lado:

2. & 3. $\Longrightarrow$ 1. Si acaso $\gamma(\alpha_0)\cdots\gamma(\alpha_{k_0-1}) = \gamma(\beta_0)\cdots\gamma(\beta_{k_1-1}),$ entonces bien $\gamma(\alpha_0)$ es un prefijo de $\gamma(\beta_0)$ o al revés. Supongamos lo primero, entonces $\gamma(\beta_0)=\gamma(\alpha_0)\sigma$, para alguna palabra $\sigma$. Por la condición 3. $\sigma$ debe estar en $\Gamma$. Por la condición 2. se ha de tener $\gamma(\alpha_0)= \gamma(\beta_0)$ y $\alpha_0=\beta_0$. Continuando de la misma forma para el resto de la palabra resulta la condición 1. $\Box$

Sea $\gamma:A\to C^+$ una función de codificación y $\Gamma = \gamma(A)\subset C^+$ su imagen. Definimos, iterativamente

$$\begin{eqnarray*} \Gamma_1 &=& \{\sigma\in A^+\vert\ \exists \tau\in\Gamma:\ \ta... ...}\left[\exists \tau\in\Gamma^k:\ \tau\sigma\in\Gamma^j\right]\} \end{eqnarray*}$$

El conjunto $\Gamma_1$ consiste pues de los restos que le hacen falta a palabras en el código $\Gamma$ para convertirse en otras palabras en el código. Similarmente, $\Gamma_k$ consiste de restos para que palabras previas se conviertan en códigos de palabras de longitud $k-1$, o bien de restos para que códigos de palabras de longitud $k-1$ se conviertan en palabras previas.

Proposición 2.3   Existen $i,j\in\mathbb{N}$, $i<j$, tales que $\Gamma_i = \Gamma_j$. Es decir, a la larga, la sucesión de conjuntos de restos $\left(\Gamma_k\right)_k$ ha de ser periódica.

En efecto, veamos primero que las longitudes de los restos están acotadas. Sea $n$ la longitud mayor de las palabras de código: $n=\max\{\mbox{long}(\gamma(\alpha))\vert\ \alpha\in A\}$. Por inducción en $k$ se ve de manera directa:

$$\forall k\in\mathbb{Z}^+\ \forall\sigma\in\Gamma_k:\ \mbox{long}(\sigma)\leq n.$$

Así, cada $\Gamma_i$ sólo tiene un número finito de posibilidades de ser formado. De donde resulta la proposición. $\Box$

Naturalmente:

Proposición 2.4   El código $\gamma$ es de decodificación única si y sólo si

$$\forall k\in\mathbb{Z}^+:\ \Gamma\cap\Gamma_k = \emptyset.$$ (5)

Ahora bien, la condición $\Gamma\cap\Gamma_k \not= \emptyset$ es claramente equivalente a que $\mbox{\rm nil}\in\Gamma_{k+1}$. Por tanto, si acaso $\mbox{\rm nil}\in\Gamma_k$ para algún $k$ entonces $\gamma$ no puede ser de decodificación única.

Esto proporciona el algoritmo de Sardinas-Patterson para decidir si un código $\gamma$ es de decodificación única:

1. $\Gamma := \gamma(A)\subset C^+$ ;
2. $i:=1$ ; calcúlese $\Gamma_i$ ;
3. mientras que $\mbox{\rm nil}\not\in\Gamma_i$ hágase
   1. $i++$ ;
   2. calcúlese $\Gamma_i$ ;
   3. si $\left(\exists j<i:\ \Gamma_j==\Gamma_i\right)$ entonces

      decídase '$\gamma$ es de decodificación única'

4. decídase '$\gamma$ no es de decodificación única'

(si ocurre que en alguna iteración $\mbox{\rm nil}\in\Gamma_i$, entonces la palabra $\tau$ en $\Gamma_j\cap\Gamma_i$, con $j<i$, que mostrara tal hecho ha de poseer más de una factorización).
Siguiente: Códigos de Huffman Arriba: Codificación Anterior: Decodificación única