Algoritmo de Sardinas-Patterson

En teoría de la codificación , el algoritmo de Sardinas-Patterson es un algoritmo clásico para determinar en tiempo polinomial si un código de longitud variable dado es decodificable de forma única, y recibe su nombre de August Albert Sardinas y George W. Patterson, quienes lo publicaron en 1953. ^{[ 1 ]} El algoritmo realiza una búsqueda sistemática de una cadena que admita dos descomposiciones diferentes en palabras clave. Como informa Knuth , el algoritmo fue redescubierto unos diez años después, en 1963, por Floyd , a pesar de que en ese momento ya era bien conocido en la teoría de la codificación. ^{[ 2 ]}

Considere el código ${\displaystyle \{\,{\texttt {a}}\mapsto {\texttt {1}},{\texttt {b}}\mapsto {\texttt {011}},{\texttt {c}}\mapsto {\texttt {01110}},{\texttt {d}}\mapsto {\texttt {1110}},{\texttt {e}}\mapsto {\texttt {10011}}\,\}}$. Este código, que se basa en un ejemplo de Berstel, ^{[ 3 ]} es un ejemplo de un código que no es decodificable de forma única, ya que la cadena

011101110011

puede interpretarse como la secuencia de palabras clave

01110 – 1110 – 011 ,

pero también como la secuencia de palabras clave

011 – 1 – 011 – 10011 .

Por lo tanto, cdb y babe ofrecen dos posibles decodificaciones de esta cadena codificada .

En general, se puede encontrar una palabra clave siguiendo esta idea: En la primera ronda, elegimos dos palabras clave.${\displaystyle x_{1}}$y${\displaystyle y_{1}}$de tal manera que${\displaystyle x_{1}}$es un prefijo de${\displaystyle y_{1}}$, eso es, ${\displaystyle x_{1}w=y_{1}}$por algún "sufijo colgante"${\displaystyle w}$Si uno lo intenta primero${\displaystyle x_{1}={\texttt {011}}}$y${\displaystyle y_{1}={\texttt {01110}}}$, el sufijo colgante es${\displaystyle {\texttt {w}}={\texttt {10}}}$. Si logramos encontrar dos secuencias${\displaystyle x_{2},\ldots ,x_{p}}$y${\displaystyle y_{2},\ldots,y_{q}}$de palabras clave tales que ${\displaystyle x_{2}\cdots x_{p}=wy_{2}\cdots y_{q}}$, entonces hemos terminado: Porque entonces la cadena${\displaystyle x=x_{1}x_{2}\cdots x_{p}}$alternativamente se puede descomponer como${\ Displaystyle y_ {1} y_ {2} \ cdots y_ {q}}$y hemos encontrado la cadena deseada que tiene al menos dos descomposiciones diferentes en palabras clave.

En la segunda ronda, probamos dos enfoques diferentes: el primer intento consiste en buscar una palabra clave que tenga w como prefijo. Luego obtenemos un nuevo sufijo colgante w , con el que podemos continuar nuestra búsqueda. Si finalmente encontramos un sufijo colgante que es en sí mismo una palabra clave (o la palabra vacía ), entonces la búsqueda terminará, ya que sabemos que existe una cadena con dos descomposiciones. El segundo intento consiste en buscar una palabra clave que sea en sí misma un prefijo de w . En nuestro ejemplo, tenemos${\displaystyle w={\texttt {10}}}$y la secuencia 1 es una palabra clave. Por lo tanto, también podemos continuar con${\displaystyle w={\texttt {0}}}$como el nuevo sufijo colgante.

El algoritmo se describe de forma más conveniente utilizando cocientes de lenguajes formales . En general, para dos conjuntos de cadenas D y N , el cociente (izquierdo)${\displaystyle N^{-1}D}$se define como las palabras residuales obtenidas de D al eliminar algún prefijo en N. Formalmente,${\displaystyle N^{-1}D=\{\,y\mid xy\in D~{\textrm {y}}~x\in N\,\}}$Ahora dejemos...${\displaystyle C}$denota el conjunto (finito) de palabras clave en el código dado.

El algoritmo procede en rondas, donde en cada ronda mantenemos no solo un sufijo colgante como se describió anteriormente, sino el conjunto (finito) de todos los posibles sufijos colgantes. Comenzando con la ronda${\displaystyle i=1}$, el conjunto de posibles sufijos colgantes se denotará por${\displaystyle S_{i}}$Los conjuntos${\displaystyle S_{i}}$se definen inductivamente de la siguiente manera:

${\displaystyle S_{1}=C^{-1}C\setminus \{\varepsilon \}}$Aquí, el símbolo${\displaystyle \varepsilon }$denota la palabra vacía .

${\displaystyle S_{i+1}=C^{-1}S_{i}\cup S_{i}^{-1}C}$, para todos${\displaystyle i\geq 1}$.

El algoritmo calcula los conjuntos${\displaystyle S_{i}}$en orden creciente de${\displaystyle i}$. Tan pronto como uno de los${\displaystyle S_{i}}$Si contiene una palabra de C o la palabra vacía, el algoritmo termina y responde que el código dado no es decodificable de forma única. De lo contrario, una vez que se haya formado un conjunto${\displaystyle S_{i}}$ es igual a un conjunto encontrado previamente${\displaystyle S_{j}}$con${\displaystyle j<i}$En ese caso, el algoritmo entraría, en principio, en un bucle infinito. En lugar de continuar indefinidamente, responde que el código dado es decodificable de forma única.

Consulte el cuadro de la izquierda para ver un ejemplo de ejecución del algoritmo en el código proporcionado; las letras minúsculas y mayúsculas denotan el código y las cadenas de "sufijo colgante", respectivamente. Durante la construcción de${\displaystyle S_{2}}$Se encuentra la palabra clave b (mostrada en rojo) y el algoritmo se detiene. El recuadro de la derecha indica cómo se puede demostrar que la cadena de ejemplo 1110011 tiene múltiples codificaciones ( db , aae ), utilizando las ecuaciones recopiladas durante la ejecución del algoritmo.

Dado que todos los conjuntos${\displaystyle S_{i}}$son conjuntos de sufijos de un conjunto finito de palabras clave, solo hay un número finito de candidatos diferentes para${\displaystyle S_{i}}$. Since visiting one of the sets for the second time will cause the algorithm to stop, the algorithm cannot continue endlessly and thus must always terminate. More precisely, the total number of dangling suffixes that the algorithm considers is at most equal to the total of the lengths of the codewords in the input, so the algorithm runs in polynomial time as a function of this input length. By using a suffix tree to speed the comparison between each dangling suffix and the codewords, the time for the algorithm can be bounded by O(nk), where n is the total length of the codewords and k is the number of codewords.^[4] The algorithm can be implemented using a pattern matching machine. ^[5] The algorithm can also be implemented to run on a nondeterministic Turing machine that uses only logarithmic space; the problem of testing unique decipherability is NL-complete, so this space bound is optimal.^[6]

A proof that the algorithm is correct, i.e. that it always gives the correct answer, is found in the textbooks by Salomaa^[7] and by Berstel et al.^[8]

• Kraft's inequality in some cases provides a quick way to exclude the possibility that a given code is uniquely decodable.
• Prefix codes and block codes are important classes of codes which are uniquely decodable by definition.
• Timeline of information theory
• Post's correspondence problem is similar, yet undecidable.

• Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe (2010). Códigos y autómatas . Enciclopedia de Matemáticas y sus Aplicaciones. Vol.  129. Cambridge: Cambridge University Press. ISBN 978-0-521-88831-8. Zbl 1187.94001 . 
• Berstel, Jean; Reutenauer, Christophe (2011). Series racionales no conmutativas con aplicaciones . Enciclopedia de Matemáticas y sus Aplicaciones. Vol.  137. Cambridge: Cambridge University Press . ISBN 978-0-521-19022-0. Zbl 1250.68007 . 
• Knuth, Donald E. (diciembre de 2003). "Robert W Floyd, In Memoriam". SIGACT News . 34 (4): 3– 13. doi : 10.1145/954092.954488 . S2CID 35605565 . 
• Rodeh, M. (1982). "Una prueba rápida para la descifrabilidad única basada en árboles de sufijos (Corresp.)". IEEE Transactions on Information Theory . 28 (4): 648– 651. doi : 10.1109/TIT.1982.1056535 ..
• Apostolico, A.; Giancarlo, R. (1984). "Implementación en máquina de coincidencia de patrones de una prueba rápida para la descifrabilidad única". Information Processing Letters . 18 (3): 155– 158. doi : 10.1016/0020-0190(84)90020-6 ..
• Rytter, Wojciech (1986). "La complejidad espacial del problema de descifrabilidad única". Information Processing Letters . 23 (1): 1– 3. doi : 10.1016/0020-0190(86)90121-3 . MR 0853618 . .
• Salomaa, Arto (1981). Joyas de la teoría del lenguaje formal . Pitman Publishing. ISBN 0-273-08522-0. Zbl 0487.68064 . 
• Sardinas, August Albert; Patterson, George W. (1953), "Una condición necesaria y suficiente para la descomposición única de mensajes codificados", Actas de la Convención de la IRE , Convención Nacional de 1953, Parte 8: Teoría de la Información , págs. 104-108 . .

Lecturas adicionales

• Robert G. Gallager : Teoría de la información y comunicación fiable. Wiley, 1968.