Click here to load reader

tecnicas de diccionario

  • View
    21

  • Download
    3

Embed Size (px)

DESCRIPTION

codificacion por medio de diccionarios, teoria de la informacion

Text of tecnicas de diccionario

  • 1

    1. Tcnicas de diccionario 1.1. Generalidades

    Se miran tcnicas que incorporan la estructura de los datos para incrementar la cantidad de compresin.

    Estas tcnicas construyen una lista de patrones que ocurren frecuentemente y las codifican para transmitir su ndice en la lista.

    Ms tiles con fuentes que generan un nmero relativamente pequeo de patrones muy frecuentemente.

    1.2. Introduccin

    Muchas aplicaciones en las que las fuentes generan patrones recurrentes (Ej.: texto).

    Hay otros patrones que casi nunca ocurren.

    Aproximacin: conservar una lista o diccionario de patrones recurrentes y cuando estos aparecen se codifican con referencia al diccionario. Si el patrn

    no est en el diccionario entonces puede ser codificado usando algn otro

    mtodo menos eficiente. Para que esta lista sea efectiva la clase de patrones

    que ocurren frecuentemente y por tanto el tamao del diccionario debe ser

    mucho ms pequeo que el nmero de todos los posibles patrones.

    Ejemplo:

    Suponga que tenemos un texto particular que consiste en palabras de cuatro

    caracteres. Tres caracteres de las 26 letras minsculas del alfabeto ingls seguidas de una marca de puntuacin (coma, punto, exclamacin, interrogacin, punto y coma y dos

    puntos). En otras palabras, el tamao del alfabeto de entrada es 32. Si furamos a codificar el texto fuente un carcter al tiempo, tratando cada carcter como un evento

    igualmente probable, necesitaramos . Tratando todos los 324 =1048576 patrones de cuatro caracteres como igualmente probables, tendramos un cdigo que asignara 20 a cada patrn de cuatro caracteres.

    Pongamos ahora los 256 patrones de cuatro caracteres ms probables en un diccionario. El esquema de transmisin funciona como sigue: siempre que deseemos

    enviar un patrn que exista en el diccionario enviaremos un bit bandera, digamos un 0, seguido por un ndice de correspondiente a la entrada en el diccionario. Si el patrn no se encuentra en el diccionario enviaremos un 1 seguido de que codifican el patrn. Si el patrn que encontramos no est en el diccionario, nosotros enviaremos

    realmente ms bits que en el esquema original, en vez de . Pero si est en el diccionario enviaremos solo . La utilidad de nuestro esquema depender del porcentaje de palabras que encontramos que est en el diccionario. Podemos tener una

    idea acerca de la utilidad de nuestro esquema calculando el nmero promedio de bits por

    patrn.

    Si la probabilidad de encontrar un patrn del diccionario es , entonces el nmero promedio de / esta dado por:

    = + ( ) =

  • 2

    Para que nuestro esquema sea til, debera tener un valor inferior a . Esto sucede cuando . . Esto no parece como un nmero muy grande. Sin embargo observe que si todos los patrones ocurrieran en una manera igualmente probable, la probabilidad

    de encontrar un patrn del diccionario sera menor que .

    De acuerdo con este ejemplo si se quiere mejorar mucho el desempeo se debe aumentar

    la probabilidad de que la secuencia est en el diccionario tanto como sea posible, o sea

    que las entradas del diccionario deben ser cuidadosamente escogidas. Para lograr esto

    se debe tener una muy buena idea del comportamiento de la fuente o de lo contrario

    debemos estar en capacidad de obtener esta informacin de alguna manera.

    Dependiendo de si conocemos previamente el comportamiento de la fuente o no, hay dos

    maneras de construir el diccionario: si se conoce dicho comportamiento se puede

    construir un diccionario esttico y de lo contrario se pude construir un diccionario

    adaptativo.

    1.3. Diccionario esttico

    Construir un diccionario esttico es ms apropiado cuando se tiene un conocimiento a

    priori del comportamiento de la fuente. Este mtodo es especialmente apropiado de usar

    en aplicaciones especficas.

    Ejemplo:

    Compresin de los datos de estudiantes de la universidad.

    Se tiene la certeza de que datos como el nombre, la identidad, etc. aparecern en todos

    las fichas. Dependiendo de la ubicacin geogrfica ciertos dgitos de la tarjeta de

    seguridad social son ms probables.

    Los diccionarios generados para esta aplicacin no trabajaran bien en otros casos y por el

    contrario podran causar una expansin en vez de una compresin.

    1.3.1. Codificacin digrama

    Es una tcnica que es menos especfica a una aplicacin. Esta tcnica consiste en un

    diccionario formado por todas las letras del alfabeto de la fuente seguida de tantos pares

    de letras (digramas) como sea posible de acomodar en el diccionario.

    Ejemplo:

    Construccin de un diccionario de de todos los caracteres imprimibles. Las primeras son los caracteres imprimibles y el resto seria los ms frecuentes.

    El codificador digrama lee dos caracteres de entrada y busca el diccionario para ver si

    existe la entrada en el diccionario. Si lo es se codifica el ndice correspondiente y se enva,

    si no est se codifica el primer carcter del par. El segundo carcter se convierte en el

    primer carcter del siguiente digrama. El codificador lee el siguiente carcter para

    completar un digrama y se repite el procedimiento.

  • 3

    Ejemplo:

    Supongamos que tenemos una fuente con un alfabeto de cinco letras = {, , , } , basados en el conocimiento que tenemos acerca de la fuente, construimos el diccionario

    mostrado en la tabla 1:

    Cdigo Entrada Cdigo Entrada

    Tabla 1: Un diccionario de muestra

    Supongamos que deseamos codificar la secuencia .

    En las tablas se muestran los treinta pares de caracteres ms frecuentes en un texto en y en un programa en .

    Par Conteo Par Conteo

    Tabla 2: pares de caracteres que ocurren ms frecuentemente en un documento en de caracteres

    Par Conteo Par Conteo

    : (

    =

    =

  • 4

    ): .

    Tabla 3: 30 pares de caracteres en una coleccin de programas en que contienen caracteres

    1.4. Diccionario adaptativo

    y en y propusieron tcnicas de construccin de diccionarios adaptativos llamadas y .

    1.4.1. La aproximacin

    En este caso el diccionario es una porcin de la secuencia previamente codificada. Se

    utiliza una ventana deslizante (ilustracin 1) que contiene dos partes:

    El buffer de bsqueda que contiene una porcin de la secuencia previamente codificada

    El buffer de que contiene la prxima porcin de la secuencia a ser codificada.

    Ilustracin 1: ventana deslizante en

    Se codifica enviando una tripleta , , en donde:

    Se denomina el offset y es la distancia ms larga entre los caracteres que concuerdan entre los dos bferes.

    Es el nmero de caracteres que coinciden en los dos bferes.

    Es el cdigo del siguiente carcter luego del acople. Este se enva por si la longitud de la secuencia es cero o sea que no coincide en la comparacin, es decir si es un carcter

    nuevo.

    Si el tamao del bfer de bsqueda es , el tamao de la ventana completa es y el tamao del alfabeto de la fuente es , entonces el tamao para codificar la tripleta es

    + +

  • 5

    Esto se debe a que la longitud del acople puede ser superior a la ventana de bsqueda.

    Ejemplo:

    Suponga que se quiere codificar la secuencia

    Suponga adems que la longitud de la ventana es , el tamao del buffer de bsqueda es y que la condicin corriente es como sigue:

    Para codificar la , se puede ver que no hay acople y por lo tanto se transmite la tripleta , , ()

    Ilustracin 2: codificacin del ejemplo

    La siguiente a tiene acoples de longitudes , respectivamente. La longitud del acople en este ltimo caso es y por tanto se enva la tripleta , , () , desplazando la ventana queda as:

    La tripleta en este caso toma la forma , , () .

    La decodificacin:

    Para ver cmo funciona la decodificacin, asumamos que se ha decodificado la secuencia

    y que se recibe las tripletas , , (), , , () , , (). La primera tripleta es fcil de decodificar; no hubo acople con la tira previamente

    decodificada y el prximo smbolo es . La tira decodificada ahora es . El primer elemento de la siguiente tripleta le dice al decodificador que mueva hacia atrs el

    apuntador siete caracteres y copie cuatro caracteres desde aquel punto. El proceso de

    decodificacin trabaja como se muestra en la ilustracin 3:

  • 6

    Ilustracin 3: decodificacin de la tripleta , , ()

    Finalmente, veamos cmo se decodifica la tripleta , , (). Nos movemos atrs tres caracteres y arrancamos a copiar. Los primeros tres caracteres que copiamos son , el apuntador se mueve una vez ms como se muestra en la ilustracin 4, para copiar el

    carcter recientemente copiado. Similarmente, copiamos el siguiente carcter . Aunque arrancamos copiando solamente tres caracteres, terminamos copiando cinco

    caracteres. Observe que el acople solo tiene que arrancar en el buffer de bsqueda, y

    puede extenderse en el . En efecto, si el ultimo carcter en el hubiera sido en lugar de seguido por varias repeticiones adicionales de , la secuencia entera de repetidas podran haber sido codificadas con una sola tripleta

    Ilustracin 4: decodificando la tripleta , , ()

    Como se observa en este ejemplo el esquema es muy simple y no requiere un conocimiento previo de la fuente. Sin embargo lo que se est asumiendo implcitamente

    es que los patrones recurrentes ocurren muy cercanamente.

    Variaciones

    Para mejorar el algoritmo de codificacin se puede

  • 7

    Codificar la tripleta con longitud variable (, , ,

Search related