CODIGOS PREFIJOS

CODIGOS PREFIJOS

Definición. -Un conjunto P de sucesiones binarias (que representa un conjunto de símbolos) es un código prefijo si ninguna de las sucesiones de p es el prefijo de otra sucesión de P.

Ejemplos:

1.-Sea el conjunto E = {000, 001, 011, 10, 11} es un código prefijo

2.- Sea el conjunto F = {1, 00, 01, 000, 0001} no es un código prefijo

3.-Consideremos un subconjunto del alfabeto S = {a, e, n, r, t} y representemos los elementos de S mediante las siguientes sucesiones binarias.

a: 01 e: 0 n: 101 r: 10 t: 1

Si transmitimos el mensaje “ata” se enviará la sucesión binaria 01101 pero también se puede transmitir los mensajes con esta sucesión etn, atet, an en consecuencia no es código prefijo

Si consideramos un segundo esquema de codificación a: 111 e: 0 n: 1100 r: 1101 t: 10, ahora

si transmitimos el mensaje “ata” se enviará [pic 1]

la sucesión binaria 11110111 donde no hay

posibilidades de confusión, en consecuencia

es un código prefijo.

Además, podemos usar el árbol binario completo

etiquetado para decodificar la sucesión 11110111

 de la siguiente forma. 

CODIFICACIÓN DE HUFFMAN

▪ Es una técnica para comprensión de datos. Este algoritmo le asigna secuencias binarias (códigos) a los símbolos del alfabeto de manera de utilizar la menor cantidad de bits posibles.

▪ La idea del algoritmo del “algoritmo de Huffman” es que los datos a ser comprimidos, contienen símbolos que aparecen con mayor frecuencia y otros muy poco, asignándoles el código mas corto a los que más aparecen.

▪ A continuación los pasos a seguir:

• Paso 1.

▪ Se coloca los caracteres en orden creciente de acuerdo a la frecuencia de repetición

• Paso 2.

▪ Fusionar los nodos de menor frecuencia hasta obtener un solo árbol manteniendo el ordenamiento creciente.

• Paso 3.

▪ En el árbol obtenido en el paso 2 las hojas representan los símbolos o caracteres, los caminos o trayectorias de la raíz a las hojas se codifica con 0 a la izquierda y con 1 a la derecha.

• Paso 4.

▪ Finalmente de árbol se obtiene el código prefijo.

Ejemplo

▪ Supongamos que en un cierto archivo con 100 000 caracteres, donde aparecen 6 caracteres diferentes y la frecuencia de aparición de cada uno de ellos es la siguiente:

[pic 2]

Solución:

Fase 1. : Caracteres colocados en orden creciente de frecuencia.

[pic 3]

Fase 2. y posteriores : Fusionar hasta obtener un sólo árbol, Manteniendo la ordenación creciente.

[pic 4][pic 5]

[pic 6][pic 7][pic 8]

Dado finalmente el árbol binario ponderado podemos codificar y decodificar.

▪ Codificación: Basta con concatenar el código de cada uno de los caracteres.

▪ Ejemplo : aabacd=[pic 9]

▪ Descodificación: ningún código es prefijo de otro código.

▪ Ejemplo: 101011101111011100= badadcf , a=0, b=101, c=100, d=111, e=1101, f=1100

ARBOL GENERADOR

Un árbol generador de un grafo G (también llamado árbol recubridor o árbol expandido), es un subgrafo de G que es árbol y contiene a todos los vértices de G.

[pic 10]

Un grafo G, un árbol T generador de G.

ARBOL DE EXPANSIÓN MÍNIMA(RECUBRIDOR)

Dado un grafo G = V, E , no dirigido ponderado. Un árbol de expansión mínima es un árbol compuesto por todos los vértices y cuya suma de los pesos las aristas sea mínimo. El árbol generador mínimo de un grafo, no necesariamente es único.

Ejemplo 1

▪ Para el grafo G de la siguiente figura existen dos árboles generadores mínimos T1 y T2.

[pic 11]

Un grafo ponderado G y dos árboles generadores mínimos de G (T1 y T2).

Ejemplo 2

Una compañía de teléfono móviles da servicio a ciertas áreas geográficas, considerando la

distancia en kilómetros. Dichas áreas se representan por el siguiente grafo.[pic 12]

                                                                                                  Determinar cuál sería la ruta del mensaje                          

...