Pregunta sobre la definición de "Prefijo libre"

Question

Estoy tratando de entender la definición de "Prefijo" gratis", pero no entiendo la definición ni el ejemplo de que wikipedia ofrece. Yo estaba esperando una aclaración. A continuación es un extracto de la wikipedia (http://en.wikipedia.org/wiki/Prefix_code):

"Un prefijo de código es un tipo de sistema de código (normalmente una longitud variable de código) que se distinguen por su posesión de la "prefijo de la propiedad"; el cual indica que no es válida la palabra de código en el sistema que es un prefijo (inicio) de cualquier otra palabra de código válida en el conjunto. Por ejemplo, un código con el código de palabras {9, 59, 55} tiene el prefijo de la propiedad; un código que consta de {9, 5, 59, 55} no, porque "5" es un prefijo de ambos "59" y "55". Con un prefijo de código, un receptor puede identificar cada palabra sin necesidad de un marcador especial entre las palabras."

No entiendo el prefijo de la propiedad, ni entiendo por qué el primer set satisface el prefijo de la propiedad y la segunda falla, ya que ambos conjuntos tienen "59" y "55" como elementos en el conjunto.

Podría alguien explicar el prefijo de la propiedad, explicar el ejemplo que estoy confundido acerca y proporcionar otro ejemplo?

Answer 1

Supongamos que tenemos un código simple que consta de las tres palabras cat, catapulta, y el camello.

Este conjunto de codewords no es de prefijo libre, porque a (toda) la palabra, a saber, gato, es también un prefijo de otra palabra.

Aquí es un (falso) ilustración del problema que esto puede causar. Supongamos que el gato codifica "ejecutar como h***", catapulta codifica tener "un buen momento", y "catenaria" codifica "cuando la cena?".

Imagine ahora que codewords vienen en tipo de lentamente, letra por letra. Si usted consigue las letras $$\text{c$\qquad$ a$\qquad$ t}$$ usted no sabe qué hacer, este podría ser el mensaje completo, así que es mejor dejar de mirar a la pantalla del ordenador y salir de allí rápido, o tal vez es el comienzo de otra palabra, y es mejor esperar.

Supongamos por el contrario que la única codewords son capturas, la catapulta, la catenaria, y catamount. Esta colección de codewords es de prefijo libre, ya que ninguna de (toda) la palabra es la parte inicial de otra palabra. Si $$\text{c$\qquad$ a$\qquad$ t} \qquad\qquad \text{or even} \qquad\qquad \text{c$\qquad$ a$\qquad$ t$\qquad$a}$$ viene en, usted sabe que tiene que esperar para que llegue el mensaje.

En un mayor nivel de programación, supongamos que las letras vienen en un flujo continuo, no se separan en codewords. Usted quiere ser capaz de separar esta secuencia de letras en codewords "sobre la marcha".

Si ambos gato y la catapulta se codewords, si ves que el gato no se puede tomar la decisión hasta ver la siguiente carta. Es por eso que el primer ejemplo no es de prefijo libre.

En el segundo ejemplo, no hay ningún problema, si ves un gato, ya sé que no es en la palabra clave de la lista, así que esperar a que el resto.

Comentario: Hay algunas buenas razones para usar la variable longitud de los códigos. Por ejemplo, supongamos que nuestros mensajes abrumadora mayoría consisten en información numérica, con muy breves fragmentos de texto. A continuación, puede aumentar el rendimiento de un lote para codificar los dígitos como muy corto de cadenas de bits, y las letras del alfabeto como el tiempo de cadenas de bits.

En un lenguaje que debe ser interpretado por un ordenador, es a menudo conveniente tener el prefijo libre de la propiedad, porque puede significar que podamos utilizar un simple analizador. Un analizador que tiene que hacer una buena cantidad de "mirar hacia adelante" con el fin de interpretar una cadena disminuye la eficiencia.

Answer 2

Un ejemplo de un no-prefix-free conjunto de codewords para el que la frontera entre palabras no se puede determinar es el conjunto $\{\text{cat}, \text{catsup}, \text{supply}, \text{ply}\}$. Si recibimos el mensaje de $\text{catsupply}$ no podemos saber si esto significa que el $\text{cat supply}$ o $\text{catsup ply}$.

Los problemas con André Nicolás ejemplos son causadas por el conjunto de algunos mensajes formado por la concatenación de codewords no se prefix-free, que es diferente de si o no el conjunto de codewords sí es. Es posible para cualquiera de las propiedades para sostener sin el otro, o ambos, o ninguno, dependiendo de la concatenaciones de codewords se consideran válidos los mensajes. Por ejemplo, podríamos añadir una palabra clave $\text{endoftransmission}$ y requieren que cada mensaje final con ella, y con la definición de "mensaje" el conjunto de mensajes construidos a partir de los codewords $\{\text{cat},\text{catapult},\text{endoftransmission}\}$ es de prefijo libre aunque el conjunto de los codewords sí no lo es. Alternativamente, el conjunto de codewords $\{\text{a}, \text{b}\}$ es de prefijo libre, pero necesitamos algunas restricciones en lo que constituye un mensaje para el conjunto de mensajes de prefijo libre, porque $\text{aa}$ $\text{a}$ no pueden ser los mensajes.