brent leimenstoll

Ejemplo de examen sobre ejercicios de compresión (I)

Naruto Uzumaki es un ninja adolescente que tiene encerrado en su interior al «Zorro Demonio de Nueve Colas» Kyūbi (9テイルス悪魔フォックス?). Doce años antes, este demonio atacó a la Aldea Oculta de la Hoja, matando a muchas personas. Como consecuencia, el líder de la aldea (el Cuarto Hokage, Minato Namikaze) sacrificó su vida utilizando el Shiki Fūjin para sellarlo dentro de Naruto cuando era un recién nacido, con lo que esperaba detener la masacre. Por ello, Naruto fue víctima de maltratos por quienes lo consideraban como el propio Kyūbi. A manera de solución, el Tercer Hokage (quien tuvo que reasumir el mando luego del sacrificio del Cuarto Hokage) publicó un decreto
donde prohibía a cualquiera la mención sobre el ataque del Kyūbi, y quien lo hiciera sería severamente castigado. Doce años más tarde, Naruto se gradúa de la Academia Ninja usando su técnica clones de sombra (影分身の術 Kage Bunshin no Jutsu?), proveniente del pergamino prohibido de la aldea, el cual había robado tras ser engañado por el ninja renegado Mizuki, con el supuesto fin de salvar a su maestro Iruka Umino. Este encuentro le permitió a Naruto percatarse de que él era el recipiente contenedor del Kyūbi, y que había alguien que lo estimaba y lo reconocía moralmente como una persona.Los ninjas utilizan otro sistema de comunicación distinto al nuestro. De los papiros de la Aldea Oculta de la Hoja, Naruto ha sacado los siguientes textos de los cuales los tres primeros según Minato Namikaze son una muestra representativa del lenguaje de los Ninjas:

1. 影のんんん影影ん影んッッんんッッッッ影影ッ影ももも影影影影影影影

2. ののもものッッのののッッ影影ののののん影影ッんもも

3. ッッののの影影のののッもももッんのののッッッッ

4. 影影ん影んッッんんッッッッ影影ッ影ももももも

Se pide:

• Tabla de frecuencias.

• Árbol de símbolos y peso del árbol teniendo en cuenta las frecuencias de los símbolos. El árbol deberá de ser el más optimizado.

• Compresión del siguiente mensaje que significa “Naruto es el recipiente contenedor del Kyūbi”:

ッッんんッッッッ影影ッッッんんッッッッ影影ッッんんッッッッ影影ッ影も

• Haya el ratio de compresión.

*****************************************************************************************************
Solución al examen

El primer paso es crear la tabla de frecuencias con solamente los tres primeros textos. Haciendo un recuento de los símbolos de los tres primeros mensajes ( son los tres solamente por la frase “los tres primeros según Minato Namikaze son una muestra representativa del lenguaje de los Ninjas” ) sale lo siguiente:
影影影影影影影影影影影影影影影影影影影影 20 (símbolos)
のののののののののののののののののののの 20 (símbolos)
んんんんんんんんんん 10 (símbolos)
もももももももももも 10 (símbolos)
ッッッッッッッッッッッッッッッッッッッッ 20 (símbolos)

La tabla de frecuencias será la siguiente:

影 – 20 – 25%
の – 20 – 25%
ッ – 20 – 25%
ん – 10 – 12,5%
も – 10 – 12,5%

El árbol será algo parecido al siguiente
arbol

El peso del árbol se obtiene multiplicando la frecuencia de aparición (el %) por el número de bits en el que se codifica cada número.

peso = 25 * 2 + 25 * 2 + 25 * 2 + 12.5 * 3 + 12.5 * 3 = 225

Podría haber otros árboles pero el anterior es el más optimizado.

Pasaremos a codificar el mensaje “Naruto es el recipiente contenedor del Kyūbi” que en el alfabeto anterior es el siguiente:

ッッんんッッッッ影影ッッッんんッッッッ影影ッッんんッッッッ影影ッ影も

Basta con cambiar cada símbolo en el alfabeto 影 por 11, ん por 001 y así sucesivamente. Saldrá el siguiente mensaje:

010100100101010101111101010100100101010101111101010010010101010111110111000

Como se puede observar, ahora el mensaje en vez de ocupar 1 byte por símbolo, al utilizar 2 o 3 bits/símbolo se ha reducido bastante.

Vamos a ver cuál sería el ratio de compresión:
Antes el mensaje ocupaba 34 bytes
Ahora el mensaje comprimido ocupa 75 bits lo que son 9,375 bytes

Si hago una regla de 3 puedo saber el % que ocupa ahora el mensaje:
34 ——- 100
9,375 —- X
X = (9,375 * 100) / 34 = 27,57

El mensaje ahora es un 27,57% del original luego el ratio de compresión es 100-27,57 = 72,43%

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos necesarios están marcados *

Puedes usar las siguientes etiquetas y atributos HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>