tecnicas de diccionario

27
1 1. Técnicas de diccionario 1.1. Generalidades Se miran técnicas que incorporan la estructura de los datos para incrementar la cantidad de compresión. Estas técnicas construyen una lista de patrones que ocurren frecuentemente y las codifican para transmitir su índice en la lista. Más útiles con fuentes que generan un número relativamente pequeño de patrones muy frecuentemente. 1.2. Introducción Muchas aplicaciones en las que las fuentes generan patrones recurrentes (Ej.: texto). Hay otros patrones que casi nunca ocurren. Aproximación: conservar una lista o diccionario de patrones recurrentes y cuando estos aparecen se codifican con referencia al diccionario. Si el patrón no está en el diccionario entonces puede ser codificado usando algún otro método menos eficiente. Para que esta lista sea efectiva la clase de patrones que ocurren frecuentemente y por tanto el tamaño del diccionario debe ser mucho más pequeño que el número 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 minúsculas del alfabeto inglés seguidas de una marca de puntuación (coma, punto, exclamación, interrogación, punto y coma y dos puntos). En otras palabras, el tamaño del alfabeto de entrada es 32. Si fuéramos a codificar el texto fuente un carácter al tiempo, tratando cada carácter como un evento igualmente probable, necesitaríamos á. Tratando todos los 32 4 = 1048576 patrones de cuatro caracteres como igualmente probables, tendríamos un código que asignaría 20 a cada patrón de cuatro caracteres. Pongamos ahora los 256 patrones de cuatro caracteres más probables en un diccionario. El esquema de transmisión funciona como sigue: siempre que deseemos enviar un patrón 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 patrón no se encuentra en el diccionario enviaremos un 1 seguido de que codifican el patrón. Si el patrón que encontramos no está en el diccionario, nosotros enviaremos realmente más 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 número promedio de bits por patrón. Si la probabilidad de encontrar un patrón del diccionario es , entonces el número promedio de esta dado por: = + ( − ) = −

Upload: sebastian-escobar-osorio

Post on 08-Jul-2016

35 views

Category:

Documents


3 download

DESCRIPTION

codificacion por medio de diccionarios, teoria de la informacion

TRANSCRIPT

Page 1: tecnicas de diccionario

1

1. Técnicas de diccionario

1.1. Generalidades

Se miran técnicas que incorporan la estructura de los datos para incrementar

la cantidad de compresión.

Estas técnicas construyen una lista de patrones que ocurren frecuentemente

y las codifican para transmitir su índice en la lista.

Más útiles con fuentes que generan un número relativamente pequeño de

patrones muy frecuentemente.

1.2. Introducción

Muchas aplicaciones en las que las fuentes generan patrones recurrentes

(Ej.: texto).

Hay otros patrones que casi nunca ocurren.

Aproximación: conservar una lista o diccionario de patrones recurrentes y

cuando estos aparecen se codifican con referencia al diccionario. Si el patrón

no está en el diccionario entonces puede ser codificado usando algún otro

método menos eficiente. Para que esta lista sea efectiva la clase de patrones

que ocurren frecuentemente y por tanto el tamaño del diccionario debe ser

mucho más pequeño que el número 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 minúsculas del alfabeto inglés seguidas de una

marca de puntuación (coma, punto, exclamación, interrogación, punto y coma y dos

puntos). En otras palabras, el tamaño del alfabeto de entrada es 32. Si fuéramos a

codificar el texto fuente un carácter al tiempo, tratando cada carácter como un evento

igualmente probable, necesitaríamos 𝟓 𝒃𝒊𝒕𝒔 𝒑𝒐𝒓 𝒄𝒂𝒓á𝒄𝒕𝒆𝒓. Tratando todos los 324 =1048576 patrones de cuatro caracteres como igualmente probables, tendríamos un

código que asignaría 20 𝑏𝑖𝑡𝑠 a cada patrón de cuatro caracteres.

Pongamos ahora los 256 patrones de cuatro caracteres más probables en un

diccionario. El esquema de transmisión funciona como sigue: siempre que deseemos

enviar un patrón 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 patrón

no se encuentra en el diccionario enviaremos un 1 seguido de 𝟐𝟎 𝒃𝒊𝒕𝒔 que codifican el

patrón. Si el patrón que encontramos no está en el diccionario, nosotros enviaremos

realmente más 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 número promedio de bits por

patrón.

Si la probabilidad de encontrar un patrón del diccionario es 𝑷, entonces el número

promedio de 𝒃𝒊𝒕𝒔/𝒑𝒂𝒕𝒓ó𝒏 𝑹 esta dado por:

𝑹 = 𝟗𝑷 + 𝟐𝟏(𝟏 − 𝑷) = 𝟐𝟏 − 𝟏𝟐𝑷

Page 2: tecnicas de diccionario

2

Para que nuestro esquema sea útil, 𝑹 debería tener un valor inferior a 𝟐𝟎. Esto sucede

cuando 𝑷 ≥ 𝟎. 𝟎𝟖𝟑𝟑. Esto no parece como un número muy grande. Sin embargo observe

que si todos los patrones ocurrieran en una manera igualmente probable, la probabilidad

de encontrar un patrón del diccionario sería menor que 𝟎. 𝟎𝟎𝟎𝟐𝟒𝟒

De acuerdo con este ejemplo si se quiere mejorar mucho el desempeño 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 información 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 estático y de lo contrario se pude construir un diccionario

adaptativo.

1.3. Diccionario estático

Construir un diccionario estático es más apropiado cuando se tiene un conocimiento a

priori del comportamiento de la fuente. Este método es especialmente apropiado de usar

en aplicaciones específicas.

Ejemplo:

Compresión de los datos de estudiantes de la universidad.

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

las fichas. Dependiendo de la ubicación geográfica ciertos dígitos de la tarjeta de

seguridad social son más probables.

Los diccionarios generados para esta aplicación no trabajaran bien en otros casos y por el

contrario podrían causar una expansión en vez de una compresión.

1.3.1. Codificación digrama

Es una técnica que es menos específica a una aplicación. Esta técnica 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:

Construcción de un diccionario de 𝟐𝟓𝟔 𝒆𝒏𝒕𝒓𝒂𝒅𝒂𝒔 de todos los caracteres 𝑨𝑺𝑪𝑰𝑰

imprimibles. Las primeras 𝟗𝟓 𝒆𝒏𝒕𝒓𝒂𝒅𝒂𝒔 son los caracteres 𝑨𝑺𝑪𝑰𝑰 imprimibles y el resto

seria los 𝟏𝟔𝟏 𝒑𝒂𝒓𝒆𝒔 más 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 envía,

si no está se codifica el primer carácter del par. El segundo carácter se convierte en el

primer carácter del siguiente digrama. El codificador lee el siguiente carácter para

completar un digrama y se repite el procedimiento.

Page 3: tecnicas de diccionario

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:

Código Entrada Código Entrada

𝟎𝟎𝟎 𝒂 𝟏𝟎𝟎 𝒓

𝟎𝟎𝟏 𝒃 𝟏𝟎𝟏 𝒂𝒃

𝟎𝟏𝟎 𝒄 𝟏𝟏𝟎 𝒂𝒄

𝟎𝟏𝟏 𝒅 𝟏𝟏𝟏 𝒂𝒅

Tabla 1: Un diccionario de muestra

Supongamos que deseamos codificar la secuencia 𝒂𝒃𝒓𝒂𝒄𝒂𝒅𝒂𝒃𝒓𝒂.

En las tablas 𝟐 𝒚 𝟑 se muestran los treinta pares de caracteres más frecuentes en un texto

en 𝑳𝒂𝒕𝒆𝒙 y en un programa en 𝑪.

Par Conteo Par Conteo

𝒆𝒃 𝟏𝟏𝟐𝟖 𝒂𝒓 𝟑𝟏𝟒

𝒃𝒕 𝟖𝟑𝟖 𝒂𝒕 𝟑𝟏𝟑

𝒃𝒃 𝟖𝟐𝟑 𝒃𝒘 𝟑𝟎𝟗

𝒕𝒉 𝟖𝟏𝟕 𝒕𝒆 𝟐𝟗𝟔

𝒉𝒆 𝟕𝟏𝟐 𝒃𝒔 𝟐𝟗𝟓

𝒊𝒏 𝟓𝟏𝟐 𝒅𝒃 𝟐𝟕𝟐

𝒔𝒃 𝟒𝟗𝟒 𝒃𝒐 𝟐𝟔𝟔

𝒆𝒓 𝟒𝟑𝟑 𝒊𝒐 𝟐𝟓𝟕

𝒃𝒂 𝟒𝟐𝟓 𝒄𝒐 𝟐𝟓𝟔

𝒕𝒃 𝟒𝟎𝟏 𝒓𝒆 𝟐𝟒𝟕

𝒆𝒏 𝟑𝟗𝟐 𝒃𝒔 𝟐𝟒𝟔

𝒐𝒏 𝟑𝟖𝟓 𝒓𝒃 𝟐𝟑𝟗

𝒏𝒃 𝟑𝟓𝟑 𝒅𝒊 𝟐𝟑𝟎

𝒕𝒊 𝟑𝟐𝟐 𝒊𝒄 𝟐𝟐𝟗

𝒃𝒊 𝟑𝟏𝟕 𝒄𝒕 𝟐𝟐𝟔

Tabla 2: 𝟑𝟎 pares de caracteres que ocurren más frecuentemente en un documento en

𝒍á𝒕𝒆𝒙 de 𝟒𝟏𝟑𝟔𝟒 caracteres

Par Conteo Par Conteo

𝒃𝒃 𝟓𝟕𝟐𝟖 𝒔𝒕 𝟒𝟒𝟐

𝒏𝒍𝒃 𝟏𝟒𝟕𝟏 𝒍𝒆 𝟒𝟒𝟎

: 𝒏𝒍 𝟏𝟏𝟑𝟑 𝒖𝒕 𝟒𝟒𝟎

𝒊𝒏 𝟗𝟖𝟓 𝒇( 𝟒𝟏𝟔

𝒏𝒕 𝟕𝟑𝟗 𝒂𝒓 𝟑𝟖𝟏

= 𝒃 𝟔𝟖𝟕 𝒐𝒓 𝟑𝟕𝟒

𝒃𝒊 𝟔𝟔𝟐 𝒓𝒃 𝟑𝟕𝟑

𝒕𝒃 𝟔𝟏𝟓 𝒆𝒏 𝟑𝟕𝟏

𝒃 = 𝟔𝟏𝟐 𝒆𝒓 𝟑𝟓𝟖

Page 4: tecnicas de diccionario

4

): 𝟓𝟓𝟖 𝒓𝒊 𝟑𝟓𝟕

. 𝒃 𝟓𝟓𝟒 𝒂𝒕 𝟑𝟓𝟐

𝒏𝒍𝒏𝒍 𝟓𝟎𝟔 𝒑𝒓 𝟑𝟓𝟏

𝒃𝒇 𝟓𝟎𝟓 𝒕𝒆 𝟑𝟒𝟗

𝒆𝒃 𝟓𝟎𝟎 𝒂𝒏 𝟑𝟒𝟖

𝒃 ∗ 𝟒𝟒𝟒 𝒍𝒐 𝟑𝟒𝟕

Tabla 3: 30 pares de caracteres en una colección de programas en 𝑪 que contienen

𝟔𝟒𝟗𝟖𝟑 caracteres

1.4. Diccionario adaptativo

𝐽𝑎𝑐𝑜𝑏 𝑍𝑖𝑣 y 𝐴𝑏𝑟𝑎ℎ𝑎𝑚 𝐿𝑒𝑚𝑝𝑒𝑙 en 𝟏𝟗𝟕𝟕 y 𝟏𝟗𝟕𝟖 propusieron técnicas de construcción

de diccionarios adaptativos llamadas 𝑳𝒁𝟕𝟕 y 𝑳𝒁𝟕𝟖.

1.4.1. La aproximación 𝑳𝒁𝟕𝟕

En este caso el diccionario es una porción de la secuencia previamente codificada. Se

utiliza una ventana deslizante (ilustración 1) que contiene dos partes:

El buffer de búsqueda que contiene una porción de la secuencia previamente

codificada

El buffer de 𝒍𝒐𝒐𝒌 − 𝒂𝒉𝒆𝒂𝒅 que contiene la próxima porción de la secuencia a ser

codificada.

Ilustración 1: ventana deslizante en 𝑳𝒁𝟕𝟕

Se codifica enviando una tripleta ⟨𝒐, 𝒍, 𝒄⟩ en donde:

𝒐 Se denomina el offset y es la distancia más larga entre los caracteres que concuerdan

entre los dos búferes.

𝒍 Es el número de caracteres que coinciden en los dos búferes.

𝒄 Es el código del siguiente carácter luego del acople. Este se envía por si la longitud

de la secuencia es cero o sea que no coincide en la comparación, es decir si es un carácter

nuevo.

Si el tamaño del búfer de búsqueda es 𝑺, el tamaño de la ventana completa es 𝑾 y el

tamaño del alfabeto de la fuente es 𝑨, entonces el tamaño para codificar la tripleta es

⌈𝒍𝒐𝒈𝟐𝑺⌉ + ⌈𝒍𝒐𝒈𝟐𝑾⌉ + ⌈𝒍𝒐𝒈𝟐𝑨⌉

Page 5: tecnicas de diccionario

5

Esto se debe a que la longitud del acople puede ser superior a la ventana de búsqueda.

Ejemplo:

Suponga que se quiere codificar la secuencia

… 𝑐𝑎𝑏𝑟𝑎𝑐𝑎𝑑𝑎𝑏𝑟𝑎𝑟𝑟𝑎𝑟𝑟𝑎𝑑 …

Suponga además que la longitud de la ventana es 𝟏𝟑, el tamaño del buffer de búsqueda

es 𝟕 y que la condición corriente es como sigue:

𝑐𝑎𝑏𝑟𝑎𝑐𝑎 𝑑𝑎𝑏𝑟𝑎𝑟

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

⟨𝟎, 𝟎, 𝑪(𝒅)⟩

Ilustración 2: codificación del ejemplo

La siguiente a tiene 𝟑 acoples de longitudes 𝟐, 𝟒 𝒚 𝟕 respectivamente. La longitud del

acople en este último caso es 𝟒 y por tanto se envía la tripleta ⟨𝟕, 𝟒, 𝑪(𝒓)⟩ , desplazando

la ventana queda así:

𝑎𝑑𝑎𝑏𝑟𝑎𝑟 𝑟𝑎𝑟𝑟𝑎𝑑

La tripleta en este caso toma la forma ⟨𝟑, 𝟓, 𝑪(𝒅)⟩ .

La decodificación:

Para ver cómo funciona la decodificación, asumamos que se ha decodificado la secuencia

𝒄𝒂𝒃𝒓𝒂𝒄𝒂 y que se recibe las tripletas ⟨𝟎, 𝟎, 𝑪(𝒅)⟩, ⟨𝟕, 𝟒, 𝑪(𝒓)⟩ 𝒚 ⟨𝟑, 𝟓, 𝑪(𝒅)⟩. La

primera tripleta es fácil de decodificar; no hubo acople con la tira previamente

decodificada y el próximo símbolo es 𝒅. La tira decodificada ahora es 𝒄𝒂𝒃𝒓𝒂𝒄𝒂𝒅. El

primer elemento de la siguiente tripleta le dice al decodificador que mueva hacia atrás el

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

decodificación trabaja como se muestra en la ilustración 3:

Page 6: tecnicas de diccionario

6

Ilustración 3: decodificación de la tripleta ⟨𝟕, 𝟒, 𝑪(𝒓)⟩

Finalmente, veamos cómo se decodifica la tripleta ⟨𝟑, 𝟓, 𝑪(𝒅)⟩. Nos movemos atrás tres

caracteres y arrancamos a copiar. Los primeros tres caracteres que copiamos son 𝒓𝒂𝒓, el

apuntador se mueve una vez más como se muestra en la ilustración 4, para copiar el

carácter 𝒓 recientemente copiado. Similarmente, copiamos el siguiente carácter 𝒂.

Aunque arrancamos copiando solamente tres caracteres, terminamos copiando cinco

caracteres. Observe que el acople solo tiene que arrancar en el buffer de búsqueda, y

puede extenderse en el 𝒃𝒖𝒇𝒇𝒆𝒓 𝒍𝒐𝒐𝒌 𝒂𝒉𝒆𝒂𝒅. En efecto, si el ultimo carácter en el

𝒃𝒖𝒇𝒇𝒆𝒓 𝒍𝒐𝒐𝒌 𝒂𝒉𝒆𝒂𝒅 hubiera sido 𝒓 en lugar de 𝒅 seguido por varias repeticiones

adicionales de 𝒓𝒂𝒓, la secuencia entera de 𝒓𝒂𝒓 repetidas podrían haber sido codificadas

con una sola tripleta

Ilustración 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 implícitamente

es que los patrones recurrentes ocurren muy cercanamente.

Variaciones

Para mejorar el algoritmo de codificación se puede

Page 7: tecnicas de diccionario

7

Codificar la tripleta con longitud variable (𝑷𝑲𝒁𝑰𝑷, 𝒁𝑰𝑷, 𝑨𝑹𝑱, etc.)

Variar el tamaño de los búferes.

Eliminar la tripleta cuando se codifica un solo carácter usando una bandera de un bit

para indicar que lo que sigue es el código de un solo carácter.

Con el uso de la bandera no se necesita seguir enviando el tercer miembro de la

tripleta.

1.4.2. La aproximación 𝑳𝒁𝟕𝟖

En el algoritmo 𝑳𝒁𝟕𝟕 se pierde eficiencia si los patrones recurrentes no ocurren muy

cercanos, por ejemplo en este caso:

Ilustración 5: Ejemplo de secuencia codificada ineficientemente en 𝑳𝒁𝟕𝟕

En el algoritmo 𝑳𝒁𝟕𝟖 se elimina la necesidad del búfer de búsqueda construyendo

explícitamente un diccionario tanto en el transmisor como en el receptor.

Las entradas se codifican como una dupleta ⟨𝒊, 𝒄⟩ en donde:

𝒊 Es un índice correspondiente a la entrada del diccionario que fue el acople más largo a

la entrada, si no hay acople se envía cero.

𝒄 Es el código del carácter de la entrada que sigue la porción acoplada de la entrada.

Esta dupleta se convierte en la entrada más nueva del diccionario.

Ejemplo:

Codifiquemos la secuencia

𝒘𝒂𝒃𝒃𝒂𝒃 𝒘𝒂𝒃𝒃𝒂𝒃𝒘𝒂𝒃𝒃𝒂𝒃𝒘𝒂𝒃𝒃𝒂𝒃𝒘𝒐𝒐𝒃𝒘𝒐𝒐𝒃𝒘𝒐𝒐

En donde el espacio se representa por la 𝒃 rayada. Inicialmente el diccionario está vacío,

tal que los primeros tres símbolos encontrados son codificados con el índice puesto en 0.

Las tres primeras salidas del codificador son ⟨𝟎, 𝑪(𝒘)⟩, ⟨𝟎, 𝑪(𝒂)⟩, ⟨𝟎, 𝑪(𝒃)⟩ y el

diccionario luce como en la tabla 4:

Índice Entrada

𝟏 𝒘

𝟐 𝒂

𝟑 𝒃

Tabla 4: Diccionario inicial

Page 8: tecnicas de diccionario

8

El cuarto símbolo es una b, la cual es la tercer entrada en el diccionario. Si le añadimos

el siguiente símbolo, obtenemos el patrón 𝒃𝒂 el cual no está en el diccionario, luego

codificamos estos dos símbolos como ⟨𝟑, 𝟐⟩, y agregamos el patrón 𝒃𝒂 como la cuarta

entrada en el diccionario.

Diccionario

Salida del codificador Índice Entrada

⟨𝟎, 𝑪(𝒘)⟩ 𝟏 𝒘

⟨𝟎, 𝑪(𝒂)⟩ 𝟐 𝒂

⟨𝟎, 𝑪(𝒃)⟩ 𝟑 𝒃

⟨𝟑, 𝟐⟩ 𝟒 𝒃𝒂

⟨𝟎, 𝑪(𝒃)⟩ 𝟓 𝒃

⟨𝟏, 𝟐⟩ 𝟔 𝒘𝒂

⟨𝟑, 𝟑⟩ 𝟕 𝒃𝒃

⟨𝟐, 𝟓⟩ 𝟖 𝒂𝒃

⟨𝟔, 𝟑⟩ 𝟗 𝒘𝒂𝒃

⟨𝟒, 𝟓⟩ 𝟏𝟎 𝒃𝒂𝒃

⟨𝟗, 𝟑⟩ 𝟏𝟏 𝒘𝒂𝒃𝒃

⟨𝟖, 𝟏⟩ 𝟏𝟐 𝒂𝒃𝒘

⟨𝟎, 𝑪(𝒐)⟩ 𝟏𝟑 𝒐

⟨𝟏𝟑, 𝟓⟩ 𝟏𝟒 𝒐𝒃

⟨𝟏, 𝟏𝟑⟩ 𝟏𝟓 𝒘𝒐

⟨𝟏𝟒, 𝟏⟩ 𝟏𝟔 𝒐𝒃𝒘

⟨𝟏𝟑, 𝟏𝟑⟩ 𝟏𝟕 𝒐𝒐

Tabla 5: Desarrollo del diccionario

El principal problema que aparece aquí es que el diccionario crece indefinidamente.

1.4.3. El algoritmo 𝑳𝒁𝑾

𝑳𝒁𝑾 Es una modificación de 𝑳𝒁𝟕𝟖 hecha por Terry Welch en donde se elimina la

necesidad de codificar el segundo elemento de la dupleta y por lo tanto se requiere enviar

solo el índice del diccionario inicializando este con todas las letras del alfabeto de la

fuente.

La entrada del codificador es acumulada en el patrón 𝒑 a medida que este es contenido

en el diccionario. Si la adición de otra letra 𝒂 resulta en otro patrón 𝒑 ∗ 𝒂 que no está en

el diccionario, entonces el índice de 𝒑 es transmitido al receptor y se adiciona el patrón

𝒑 ∗ 𝒂 al diccionario.

Ejemplo:

Codifiquemos la secuencia previa usando el algoritmo 𝑳𝒁𝑾

𝒘𝒂𝒃𝒃𝒂𝒃 𝒘𝒂𝒃𝒃𝒂𝒃𝒘𝒂𝒃𝒃𝒂𝒃𝒘𝒂𝒃𝒃𝒂𝒃𝒘𝒐𝒐𝒃𝒘𝒐𝒐𝒃𝒘𝒐𝒐

Asumiendo que el alfabeto de la fuente es: {𝒃, 𝒂, 𝒃, 𝒐, 𝒘} el diccionario 𝑳𝒁𝑾 luce

inicialmente como se muestra en la tabla 6:

Page 9: tecnicas de diccionario

9

Índice Entrada

𝟏 𝒃

𝟐 𝒂

𝟑 𝒃

𝟒 𝒐

𝟓 𝒘

Tabla 6: diccionario 𝑳𝒁𝑾 inicial

El codificador encuentra de primera la letra 𝒘. Este patrón está en el diccionario, por lo

tanto concatenamos la siguiente letra con ella, formando el patrón 𝒘𝒂. Este patrón no está

en el diccionario, así codificamos 𝒘 con su índice 𝟓, adicionamos el patrón 𝒘𝒂 como el

sexto elemento del diccionario, y comenzamos un nuevo patrón que arranca con el

carácter 𝒂. Como 𝒂 está en el diccionario, concatenamos el siguiente elemento 𝒃 para

formar el patrón 𝒂𝒃. Este patrón no está en el diccionario, así que codificamos el patrón

𝒂 con su índice 𝟐, adicionamos el patrón 𝒂𝒃 al diccionario como la séptima entrada del

diccionario y arrancamos construyendo un nuevo patrón con el carácter 𝒃. Continuamos

de esta manera, construyendo los patrones de 𝟐 letras hasta que encontramos el carácter

𝒘 en el segundo 𝒘𝒂𝒃𝒃𝒂. En este punto la salida del codificador consiste enteramente de

índices del diccionario inicial, o sea 𝟓𝟐𝟑𝟑𝟐𝟏. El diccionario en este punto luce como se

muestra en la tabla 7 (la entrada 𝟏𝟐 en el diccionario está aún bajo construcción).

Índice Entrada

𝟏 𝒃

2 𝒂

3 𝒃

4 𝒐

5 𝒘

6 𝒘𝒂

7 𝒂𝒃

8 𝒃𝒃

9 𝒃𝒂

10 𝒂𝒃

11 𝒃𝒘

12 𝒘 …

Tabla 7: construyendo el elemento 𝟏𝟐 del diccionario LZW

𝒘𝒂𝒃𝒃𝒂𝒃 𝒘𝒂𝒃𝒃𝒂𝒃𝒘𝒂𝒃𝒃𝒂𝒃𝒘𝒂𝒃𝒃𝒂𝒃𝒘𝒐𝒐𝒃𝒘𝒐𝒐𝒃𝒘𝒐𝒐

El siguiente símbolo en la secuencia es 𝒂. Concatenando este a 𝒘, obtenemos el patrón

𝒘𝒂. Este patrón ya existe en el diccionario (ítem 6), así nosotros leemos el siguiente

símbolo, el cual es 𝒃. Concatenando este carácter a 𝒘𝒂, obtenemos el patrón 𝒘𝒂𝒃. Este

patrón no existe en el diccionario, entonces lo incluimos como la 𝟏𝟐𝒂𝒗𝒂 entrada al

diccionario, y arrancamos un nuevo patrón con el símbolo 𝒃. También codificamos 𝒘𝒂

con su valor de índice 𝟔. Observe que después de una serie de entradas de dos letras,

ahora tenemos una entrada de tres letras. A medida que la codificación progresa, la

longitud de las entradas continúa incrementándose. Mientras más largas sean las entradas

indica que el diccionario está capturando más de la estructura de la secuencia. El

Page 10: tecnicas de diccionario

10

diccionario al final del proceso de codificación se muestra en la tabla 8. Observe que la

todas las entradas de la doce a la 𝟏𝟗 tienen una longitud de 𝟑 o de cuatro letras. Luego

encontramos el patrón 𝒘𝒐𝒐 por primera vez y caemos a un patrón de dos letras por tres

entradas más, después de lo cual regresamos a entradas de longitud en incremento.

La secuencia de salida del codificador es

𝟓 𝟐 𝟑 𝟑 𝟐 𝟏 𝟔 𝟖 𝟏𝟎 𝟏𝟐 𝟗 𝟏𝟏 𝟕 𝟏𝟔 𝟓 𝟒 𝟒 𝟏𝟏 𝟐𝟏 𝟐𝟑 𝟒

𝑤𝑎𝑏𝑏𝑎𝑏 𝑤𝑎𝑏𝑏𝑎𝑏𝑤𝑎𝑏𝑏𝑎𝑏𝑤𝑎𝑏𝑏𝑎𝑏𝑤𝑜𝑜𝑏𝑤𝑜𝑜𝑏𝑤𝑜𝑜

Índice Entrada Índice Entrada

𝟏 𝒃 𝟏𝟒 𝒂𝒃𝒘

𝟐 𝒂 𝟏𝟓 𝒘𝒂𝒃𝒃

𝟑 𝒃 𝟏𝟔 𝒃𝒂𝒃

𝟒 𝒐 𝟏𝟕 𝒃𝒘𝒂

𝟓 𝒘 𝟏𝟖 𝒂𝒃𝒃

𝟔 𝒘𝒂 𝟏𝟗 𝒃𝒂𝒃𝒘

𝟕 𝒂𝒃 𝟐𝟎 𝒘𝒐

𝟖 𝒃𝒃 𝟐𝟏 𝒐𝒐

𝟗 𝒃𝒂 𝟐𝟐 𝒐𝒃

𝟏𝟎 𝒂𝒃 𝟐𝟑 𝒃𝒘𝒐

𝟏𝟏 𝒃𝒘 𝟐𝟒 𝒐𝒐𝒃

𝟏𝟐 𝒘𝒂𝒃 𝟐𝟓 𝒃𝒘𝒐𝒐

𝟏𝟑 𝒃𝒃𝒂

Tabla 8: Ejemplo de Codificación 𝑳𝒁𝑾

A medida que el diccionario crece o sea que las entradas son más largas indica que el

diccionario está capturando más de la estructura en la secuencia.

Ejemplo: El algoritmo de decodificación 𝑳𝒁𝑾

En este ejemplo tomaremos la salida del codificador del ejemplo previo y lo

decodificaremos usando el algoritmo 𝐿𝑍𝑊. La secuencia de salida del codificador en el

ejemplo previo fue 𝟓 𝟐 𝟑 𝟑 𝟐 𝟏 𝟔 𝟖 𝟏𝟎 𝟏𝟐 𝟗 𝟏𝟏 𝟕 𝟏𝟔 𝟓 𝟒 𝟒 𝟏𝟏 𝟐𝟏 𝟐𝟑 𝟒.

Esta es la entrada a la entrada del decodificador. El decodificador arranca con el mismo

diccionario inicial de la tabla 𝟔. El valor del índice 𝟓 corresponde a la letra 𝒘, así

decodificamos 𝒘 como el primer elemento de nuestra secuencia. Al mismo tiempo, para

replicar el procedimiento de construcción del diccionario en el codificador, comenzamos

la construcción del siguiente elemento del diccionario. Arrancamos con la letra 𝒘. Este

patrón existe en el diccionario así no lo adicionamos al diccionario, y continuamos con el

proceso de decodificación. La siguiente entrada del decodificador es el 𝟐, el cual es el

índice de la letra correspondiente 𝒂. Decodificamos una 𝒂 y la concatenamos con nuestro

patrón corriente para forma el patrón 𝒘𝒂. Como este patrón no está en el diccionario, lo

adicionamos como el sexto elemento del diccionario y arrancamos un nuevo patrón

comenzando con la letra 𝒂. Las siguientes cuatro entradas 𝟑 𝟑 𝟐 𝟏 corresponden con las

letras 𝒃𝒃𝒂𝒃, y generan las entradas al diccionario 𝒂𝒃, 𝒃𝒃, 𝒃𝒂 𝒚 𝒂𝒃. El diccionario luce

como se muestra en la tabla 9, donde la entrada 𝟏𝟏 está bajo construcción.

Page 11: tecnicas de diccionario

11

Índice Entrada

𝟏 𝒃

𝟐 𝒂

𝟑 𝒃

𝟒 𝒐

𝟓 𝒘

𝟔 𝒘𝒂

𝟕 𝒂𝒃

𝟖 𝒃𝒃

𝟗 𝒃𝒂

𝟏𝟎 𝒂𝒃

𝟏𝟏 𝒃 …

Tabla 9: Construyendo la entrada 𝟏𝟏 del diccionario 𝑳𝒁𝑾 mientras se decodifica.

La siguiente entrada es 𝟔, el cual es el índice correspondiente al patrón 𝒘𝒂. Luego,

decodificamos una 𝒘 y una 𝒂. Primero concatenamos 𝒘 al patrón existente, el cual es 𝒃,

y formamos el patrón 𝒃𝒘. Como este patrón no existe en el diccionario se convierte en la

entrada 𝟏𝟏. El nuevo patrón ahora arranca con la letra 𝒘. Habíamos decodificado

previamente la letra 𝒂, la cual concatenamos ahora con 𝒘 para obtener el patrón 𝒘𝒂. Este

patrón está contenido en el diccionario, luego decodificamos la siguiente entrada, la cual

es 𝟖. Esta corresponde a la entrada 𝒃𝒃 en el diccionario. Decodificamos la primera 𝒃 y la

concatenamos con el patrón 𝒘𝒂 para obtener el patrón 𝒘𝒂𝒃. Este patrón no existe en el

diccionario, así lo adicionamos con la entrada 𝟏𝟐 en el diccionario y arrancamos un nuevo

patrón con la letra 𝒃 . Decodificando la segunda 𝒃 y concatenándola al nuevo patrón

conseguimos el patrón 𝒃𝒃. Este patrón existe en diccionario…El problema que resulta

acá es cuando aparecen secuencias que se repiten permanentemente.

Hay una situación particular donde el método de decodificación del algoritmo 𝑳𝒁𝑾

descrito antes no funciona. Suponga que tenemos una fuente con un alfabeto 𝑨 = {𝒂, 𝒃},

y que queremos codificar la secuencia que comienza en 𝒂𝒃𝒂𝒃𝒂𝒃𝒂𝒃𝒂𝒃 … El

procedimiento de codificación es aun el mismo. Comenzamos con el diccionario inicial

mostrado en la tabla 10:

Índice Entrada

𝟏 𝒂

𝟐 𝒃

Tabla 10: Diccionario inicial para la secuencia 𝒂𝒃𝒂𝒃𝒂𝒃𝒂𝒃𝒂𝒃 ⋯

El proceso termina con el diccionario final de la tabla 11:

Índice Entrada

𝟏 𝒂

𝟐 𝒃

𝟑 𝒂𝒃

𝟒 𝒃𝒂

𝟓 𝒂𝒃𝒂

𝟔 𝒂𝒃𝒂𝒃

𝟕 𝒃 …

Page 12: tecnicas de diccionario

12

Tabla 11: Diccionario final para la secuencia 𝒂𝒃𝒂𝒃𝒂𝒃𝒂𝒃𝒂𝒃 ⋯

En este caso en el proceso de decodificación hay que usar entradas del diccionario que

aún no han sido construidas y por lo tanto es imposible decodificar.

El proceso de compresión en 𝒔𝒆𝒖𝒅𝒐𝒄ó𝒅𝒊𝒈𝒐 es el siguiente:

El proceso de descompresión es el siguiente:

Un algoritmo en 𝑪:

/**********************************************************************

** Copyright (c) 1989 Mark R. Nelson

**

** LZW data compression/expansion demonstration program.

**

Page 13: tecnicas de diccionario

13

** April 13, 1989

**

** Minor mods made 7/19/2006 to conform with ANSI-C - prototypes, casting,

** and argument agreement.

**********************************************************************

*********/

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <conio.h>

#define BITS 12 /* Setting the number of bits to 12, 13*/

#define HASHING_SHIFT (BITS-8) /* or 14 affects several constants. */

#define MAX_VALUE (1 << BITS) - 1 /* Note that MS-DOS machines need to */

#define MAX_CODE MAX_VALUE - 1 /* compile their code in large model if*/

/* 14 bits are selected. */

#if BITS == 14

#define TABLE_SIZE 18041 /* The string table size needs to be a */

#endif /* prime number that is somewhat larger*/

#if BITS == 13 /* than 2**BITS. */

#define TABLE_SIZE 9029

#endif

#if BITS <= 12

#define TABLE_SIZE 5021

#endif

void *malloc();

int *code_value; /* This is the code value array */

Page 14: tecnicas de diccionario

14

unsigned int *prefix_code; /* This array holds the prefix codes */

unsigned char *append_character; /* This array holds the appended chars */

unsigned char decode_stack[4000]; /* This array holds the decoded string */

/*

* Forward declarations

*/

void compress(FILE *input,FILE *output);

void expand(FILE *input,FILE *output);

int find_match(int hash_prefix,unsigned int hash_character);

void output_code(FILE *output,unsigned int code);

unsigned int input_code(FILE *input);

unsigned char *decode_string(unsigned char *buffer,unsigned int code);

/**********************************************************************

** This program gets a file name from the command line. It compresses the

** file, placing its output in a file named test.lzw. It then expands

** test.lzw into test.out. Test.out should then be an exact duplicate of

** the input file.

**********************************************************************

***/

main (int argc, char *argv[])

{

FILE *input_file;

FILE *output_file;

FILE *lzw_file;

char input_file_name[81];

clrscr();

Page 15: tecnicas de diccionario

15

/*

** The three buffers are needed for the compression phase.

*/

code_value=(int*)malloc(TABLE_SIZE*sizeof(int));

prefix_code=(unsigned int *)malloc(TABLE_SIZE*sizeof(unsigned int));

append_character=(unsigned char *)malloc(TABLE_SIZE*sizeof(unsigned char));

if (code_value==NULL || prefix_code==NULL || append_character==NULL)

{

printf("Fatal error allocating table space!\n");

getch();

exit(-1);

}

/*

** Get the file name, open it up, and open up the lzw output file.

*/

if (argc>1)

strcpy(input_file_name,argv[1]);

else

{

gotoxy(10,10);

printf("Por favor ingrese el nombre del archivo: ");

scanf("%s",input_file_name);

}

input_file=fopen(input_file_name,"rb");

lzw_file=fopen("comp.txt","wb");

Page 16: tecnicas de diccionario

16

if (input_file==NULL || lzw_file==NULL)

{

printf("Fatal error opening files.\n");

getch();

exit(-1);

};

/*

** Compress the file.

*/

compress(input_file,lzw_file);

fclose(input_file);

fclose(lzw_file);

free(code_value);

/*

** Now open the files for the expansion.

*/

lzw_file=fopen("comp.txt","rb");

output_file=fopen("out.txt","wb");

if (lzw_file==NULL || output_file==NULL)

{

printf("Fatal error opening files.\n");

getch();

exit(-2);

};

/*

Page 17: tecnicas de diccionario

17

** Expand the file.

*/

expand(lzw_file,output_file);

fclose(lzw_file);

fclose(output_file);

free(prefix_code);

free(append_character);

getch();

}

/*

** This is the compression routine. The code should be a fairly close

** match to the algorithm accompanying the article.

**

*/

void compress(FILE *input,FILE *output)

{

unsigned int next_code;

unsigned int character;

unsigned int string_code;

unsigned int index;

int i;

next_code=256; /* Next code is the next available string code*/

for (i=0;i<TABLE_SIZE;i++) /* Clear out the string table before starting */

code_value[i]=-1;

i=0;

Page 18: tecnicas de diccionario

18

gotoxy(10,13);

printf("Comprimiendo...\n");

getch();

string_code=getc(input); /* Get the first code */

/*

** This is the main loop where it all happens. This loop runs util all of

** the input has been exhausted. Note that it stops adding codes to the

** table after all of the possible codes have been defined.

*/

while ((character=getc(input)) != (unsigned)EOF)

{

if (++i==1000) /* Print a * every 1000 */

{ /* input characters. This */

i=0; /* is just a pacifier. */

printf("*");

}

index=find_match(string_code,character);/* See if the string is in */

if (code_value[index] != -1) /* the table. If it is, */

string_code=code_value[index]; /* get the code value. If */

else /* the string is not in the*/

{ /* table, try to add it. */

if (next_code <= MAX_CODE)

{

code_value[index]=next_code++;

prefix_code[index]=string_code;

Page 19: tecnicas de diccionario

19

append_character[index]=character;

}

output_code(output,string_code); /* When a string is found */

string_code=character; /* that is not in the table*/

} /* I output the last string*/

} /* after adding the new one*/

/*

** End of the main loop.

*/

output_code(output,string_code); /* Output the last code */

output_code(output,MAX_VALUE); /* Output the end of buffer code */

output_code(output,0); /* This code flushes the output buffer*/

printf("\n");

}

/*

** This is the hashing routine. It tries to find a match for the prefix+char

** string in the string table. If it finds it, the index is returned. If

** the string is not found, the first available index in the string table is

** returned instead.

*/

int find_match(int hash_prefix,unsigned int hash_character)

{

int index;

int offset;

index = (hash_character << HASHING_SHIFT) ^ hash_prefix;

Page 20: tecnicas de diccionario

20

if (index == 0)

offset = 1;

else

offset = TABLE_SIZE - index;

while (1)

{

if (code_value[index] == -1)

return(index);

if (prefix_code[index] == hash_prefix &&

append_character[index] == hash_character)

return(index);

index -= offset;

if (index < 0)

index += TABLE_SIZE;

}

}

/*

** This is the expansion routine. It takes an LZW format file, and expands

** it to an output file. The code here should be a fairly close match to

** the algorithm in the accompanying article.

*/

void expand(FILE *input,FILE *output)

{

unsigned int next_code;

unsigned int new_code;

Page 21: tecnicas de diccionario

21

unsigned int old_code;

int character;

int counter;

unsigned char *string;

next_code=256; /* This is the next available code to define */

counter=0; /* Counter is used as a pacifier. */

gotoxy(10,16);

printf("Descomprimiendo...\n");

old_code=input_code(input); /* Read in the first code, initialize the */

character=old_code; /* character variable, and send the first */

putc(old_code,output); /* code to the output file */

/*

** This is the main expansion loop. It reads in characters from the LZW file

** until it sees the special code used to inidicate the end of the data.

*/

while ((new_code=input_code(input)) != (MAX_VALUE))

{

if (++counter==1000) /* This section of code prints out */

{ /* an asterisk every 1000 characters */

counter=0; /* It is just a pacifier. */

printf("*");

}

/*

** This code checks for the special

STRING+CHARACTER+STRING+CHARACTER+STRING

** case which generates an undefined code. It handles it by decoding

Page 22: tecnicas de diccionario

22

** the last code, and adding a single character to the end of the decode string.

*/

if (new_code>=next_code)

{

*decode_stack=character;

string=decode_string(decode_stack+1,old_code);

}

/*

** Otherwise we do a straight decode of the new code.

*/

else

string=decode_string(decode_stack,new_code);

/*

** Now we output the decoded string in reverse order.

*/

character=*string;

while (string >= decode_stack)

putc(*string--,output);

/*

** Finally, if possible, add a new code to the string table.

*/

if (next_code <= MAX_CODE)

{

prefix_code[next_code]=old_code;

append_character[next_code]=character;

Page 23: tecnicas de diccionario

23

next_code++;

}

old_code=new_code;

}

printf("\n");

}

/*

** This routine simply decodes a string from the string table, storing

** it in a buffer. The buffer can then be output in reverse order by

** the expansion program.

*/

unsigned char *decode_string(unsigned char *buffer,unsigned int code)

{

int i;

i=0;

while (code > 255)

{

*buffer++ = append_character[code];

code=prefix_code[code];

if (i++>=MAX_CODE)

{

printf("Fatal error during code expansion.\n");

exit(-3);

}

}

Page 24: tecnicas de diccionario

24

*buffer=code;

return(buffer);

}

/*

** The following two routines are used to output variable length

** codes. They are written strictly for clarity, and are not

** particularyl efficient.

*/

unsigned int input_code(FILE *input)

{

unsigned int return_value;

static int input_bit_count=0;

static unsigned long input_bit_buffer=0L;

while (input_bit_count <= 24)

{

input_bit_buffer |=

(unsigned long) getc(input) << (24-input_bit_count);

input_bit_count += 8;

}

return_value=input_bit_buffer >> (32-BITS);

input_bit_buffer <<= BITS;

input_bit_count -= BITS;

return(return_value);

}

void output_code(FILE *output,unsigned int code)

Page 25: tecnicas de diccionario

25

{

static int output_bit_count=0;

static unsigned long output_bit_buffer=0L;

output_bit_buffer |= (unsigned long) code << (32-BITS-output_bit_count);

output_bit_count += BITS;

while (output_bit_count >= 8)

{

putc(output_bit_buffer >> 24,output);

output_bit_buffer <<= 8;

output_bit_count -= 8;

}

}

Aplicaciones:

a. Compresor de archivos 𝒄𝒐𝒎𝒑𝒓𝒆𝒔𝒔 de 𝒖𝒏𝒊𝒙

En este caso el tamaño del diccionario es adaptativo y se arranca con 𝟓𝟏𝟐. Una vez que

el diccionario se llena se dobla el tamaño del diccionario de manera recursiva hasta que

se logra un tamaño dado por 𝒃𝒎𝒂𝒙 siendo 𝒃 el tamaño del código de palabra que puede

estar entre 𝟗 𝒚 𝟏𝟔.

Cuando se alcanza el tope del diccionario 𝒄𝒐𝒎𝒑𝒓𝒆𝒔𝒔 se vuelve una técnica de

diccionario estático. En este punto se monitorea la rata de compresión y si esta cae por

debajo de un umbral el diccionario es borrado y se recomienza la construcción.

b. Compresión de imágenes formato de intercambio de gráficos (𝑮𝑰𝑭)

Fue desarrollado por la empresa 𝒄𝒐𝒎𝒑𝒖𝒔𝒆𝒓𝒗𝒆 𝒊𝒏𝒇𝒐𝒓𝒎𝒂𝒕𝒊𝒐𝒏 𝒔𝒆𝒓𝒗𝒊𝒄𝒆 para codificar

imágenes gráficas.

La imagen comprimida se almacena con un primer byte que indica el mínimo número de

𝑏𝑖𝑡𝑠 𝑏 𝑝𝑜𝑟 𝑝𝑖𝑥𝑒𝑙 de la imagen original.

El número binario 𝟐𝒃 se define como el código claro (𝑐𝑙𝑒𝑎𝑟 𝑐𝑜𝑑𝑒) para resetear todos

los parámetros de compresión y descomprensión.

Page 26: tecnicas de diccionario

26

El tamaño inicial del diccionario es 𝟐𝒃−𝟏. Cuando este se llena se dobla el tamaño hasta

que se logra un tamaño máximo de 𝟒𝟎𝟗𝟔 y luego de esto el algoritmo se comporta como

un algoritmo de diccionario estático.

Las palabras de código se almacenan en bloques de caracteres de 𝟖 𝒃𝒊𝒕𝒔 cada uno y el

tamaño máximo es de 𝟐𝟓𝟓.

Cada bloque es precedido por un encabezado que contiene el tamaño del bloque.

El bloque es terminado con un terminador de bloque que consiste de 𝟖 𝒄𝒆𝒓𝒐𝒔.

El fin de la imagen comprimida es denotado por un código de fin de información con

valor 2𝑏 +1. Esta palabra de código debe aparecer antes del terminador de bloque

Ilustración 6: imágenes de prueba para el algoritmo 𝑮𝑰𝑭

Imagen 𝐺𝑰𝑭 Codificación aritmética de los

valores de los pixeles

Codificación aritmética de las

diferencias entre pixeles

𝑆𝑒𝑛𝑎 𝟓𝟏𝟎𝟖𝟓 𝟓𝟑𝟒𝟑𝟏 𝟑𝟏𝟖𝟒𝟕

𝑆𝑒𝑛𝑠𝑖𝑛 𝟔𝟎𝟔𝟒𝟗 𝟓𝟖𝟑𝟎𝟔 𝟑𝟕𝟏𝟐𝟔

Tierra 𝟑𝟒𝟐𝟕𝟔 𝟑𝟖𝟐𝟒𝟖 𝟑𝟐𝟏𝟑𝟕

Omaha 𝟔𝟏𝟓𝟖𝟎 𝟓𝟔𝟎𝟔𝟏 𝟓𝟏𝟑𝟗𝟑

Tabla 11: comparación de 𝑮𝑰𝑭 con la codificación aritmética

Se observa que en imágenes que no presentan muchos patrones repetitivos la rata de

compresión no es muy alta y pueden ser preferibles otros métodos.

Page 27: tecnicas de diccionario

27

c. Compresión sobre módems 𝑽. 𝟒𝟐 𝒃𝒊𝒔

Esta recomendación está hecha para transmisión a través de una red telefónica junto con

procedimientos de corrección de errores. Se usa en conexión de computadores con

usuarios remotos a través de módems. Tiene dos modos: modo transparente y modo

comprimido.

En el modo transparente se transmite sin comprimir en el caso de que no haya secuencias

repetitivas y por lo tanto se presente expansión en vez de compresión. Esto implica que

la recomendación sugiera que se chequee periódicamente para observar si se da tal

situación.

En el modo comprimido se usa un diccionario de tamaño variable con un tamaño inicial

que se negocia al momento de establecer el enlace entre el transmisor y el receptor.

La recomendación 𝑽. 𝟒𝟐 𝒃𝒊𝒔 sugiere un tamaño de 𝟐𝟎𝟒𝟖 y un mínimo de 𝟓𝟏𝟐.

Se reservan tres entradas del diccionario para caracteres de control

Código Nombre Descripción

𝟎 𝑬𝑻𝑴 𝐸𝑛𝑡𝑒𝑟 𝑡𝑟𝑎𝑛𝑠𝑝𝑎𝑟𝑒𝑛𝑡 𝑚𝑜𝑑𝑒

𝟏 𝑭𝑳𝑼𝑺𝑯 𝐹𝑙𝑢𝑠ℎ 𝑑𝑎𝑡𝑎

𝟐 𝑺𝑻𝑬𝑷𝑼𝑷 𝐼𝑛𝑐𝑟𝑒𝑚𝑒𝑛𝑡 𝑐𝑜𝑑𝑒𝑤𝑜𝑟𝑑 𝑠𝑖𝑧𝑒

Tabla 12: palabras de control en modo comprimido

Cuando el número de entradas supera un umbral pre acordado 𝑪𝟑 el codificador envía el

𝑺𝑻𝑬𝑷𝑼𝑷 y el tamaño de la palabra se incrementa en 𝟏 𝒃𝒊𝒕, al mismo tiempo se dobla el

valor de 𝑪𝟑.

Cuando todas las entradas se llenan el algoritmo inicia un procedimiento de 𝑟𝑒𝑢𝑠𝑜. La

localización de la primera entrada del diccionario se mantiene en una variable 𝑵𝟓.

Arrancando de 𝑵𝟓 Un contador 𝑪𝟏 se incrementa hasta que el algoritmo encuentra una

entrada del diccionario que no es prefijo de cualquier otra entrada del diccionario, lo que

significa que este patrón no se ha vuelto a encontrar desde que se creó, además debido a

la manera como fue localizado, entre patrones de esta clase este patrón ha estado alrededor

del más largo. Este procedimiento de 𝑟𝑒𝑢𝑠𝑜 habilita al algoritmo para podar (𝑝𝑟𝑢𝑛𝑒) el

diccionario de tiras que pueden haber sido encontradas en el pasado pero no han sido

encontradas recientemente en una base continua. De esta manera el diccionario se acopla

siempre a las estadísticas corrientes de la fuente.