Autor Tema: compresion - cifrado con huffman - duda (Leído 4219 veces)

ryan parker · « **en:** Martes 10 de Julio de 2012, 14:01 »

Hola a todos estoy analizando un codigo que consegui sobre este algoritmo de huffman, me intereso el tema de compresion, y despues de seguir esta lectura pues observe que tambien era posible el cifrado de datos, asi que los puse en marcha y algunas pequeñas modificaciones que realize, aunque sigue siendo el mismo code.

Código: C++

#include <iostream>
#include <cstdio>
 
using namespace std;
 
typedef struct _nodo{
   char letra;
   int frecuencia;
 
   _nodo *sig;
   _nodo *cero;
   _nodo *uno;
} tipoNodo;
 
 
typedef struct _tabla{
   char letra;
   unsigned long int bits;
   char nbits;
   _tabla *sig;
} tipoTabla;
 
tipoTabla *Tabla;
 
void Cuenta(tipoNodo* &Lista, char c);
void Ordenar(tipoNodo* &Lista);
void InsertarOrden(tipoNodo* &Cabeza, tipoNodo *e);
void BorrarArbol(tipoNodo *n);
void CrearTabla(tipoNodo *n, int l, int v);
void InsertarTabla(char c, int l, int v);
tipoTabla *BuscaCaracter(tipoTabla *Tabla, char c);
 
int main(int argc, char *argv[]){
   tipoNodo *Lista;
   tipoNodo *Arbol;
 
   FILE *fe, *fs;
   char c;
   tipoNodo *p;
   tipoTabla *t;
   int nElementos;
   long int Longitud = 0;
 
   unsigned long int dWORD;
   int nBits;
 
   if(argc < 3)
   {
      cout<<"\n\tUsar:\n\t"<<argv[0]<<" <fichero_entrada> <fichero_salida>\n";
      return 1;
   }
 
   Lista = NULL;
 
   fe = fopen(argv[1], "r");
   while((c = fgetc(fe)) != EOF){
      Longitud++;
      Cuenta(Lista, c);
   }
   fclose(fe);
 
   Ordenar(Lista);
 
   Arbol = Lista;
   while(Arbol && Arbol->sig){
      p = new(tipoNodo);
      p->letra = 0;
      p->uno = Arbol;
      Arbol = Arbol->sig;
      p->cero = Arbol;
      Arbol = Arbol->sig;
      p->frecuencia = p->uno->frecuencia + p->cero->frecuencia;
      InsertarOrden(Arbol, p);
   }
 
   Tabla = NULL;
   CrearTabla(Arbol, 0, 0);
 
   fs = fopen(argv[2], "wb");
 
   fwrite(&Longitud, sizeof(long int), 1, fs);
 
   nElementos = 0;
   t = Tabla;
   while(t){
      nElementos++;
      t = t->sig;
   }
 
   fwrite(&nElementos, sizeof(int), 1, fs);
 
   t = Tabla;
   while(t)
   {
      fwrite(&t->letra, sizeof(char), 1, fs);
      fwrite(&t->bits, sizeof(unsigned long int), 1, fs);
      fwrite(&t->nbits, sizeof(char), 1, fs);
      t = t->sig;
   }
 
 
   fe = fopen(argv[1], "r");
   dWORD = 0;
   nBits = 0;
   while((c = fgetc(fe)) != EOF)
   {
 
      t = BuscaCaracter(Tabla, c);
 
      while(nBits + t->nbits > 32){
         c = dWORD >> (nBits-8);
         fwrite(&c, sizeof(char), 1, fs);
         nBits -= 8;
      }
      dWORD <<= t->nbits;
      dWORD |= t->bits;
      nBits += t->nbits;
   }
 
   while(nBits>0){
      if(nBits>=8) c = dWORD >> (nBits-8);
      else c = dWORD << (8-nBits);
      fwrite(&c, sizeof(char), 1, fs);
      nBits -= 8;
   }
 
   fclose(fe);
   fclose(fs);
 
 
   BorrarArbol(Arbol);
 
   while(Tabla){
      t = Tabla;
      Tabla = t->sig;
      delete(t);
   }
 
   return 0;
}
 
void Cuenta(tipoNodo* &Lista, char c){
   tipoNodo *p, *a, *q;
 
   if(!Lista){
      Lista = new(tipoNodo);
      Lista->letra = c;
      Lista->frecuencia = 1;
      Lista->sig = Lista->cero = Lista->uno = NULL;
   }
   else{
      p = Lista;
      a = NULL;
      while(p && p->letra < c){
         a = p;
         p = p->sig;
      }
 
      if(p && p->letra == c) p->frecuencia++;
      else{
         q = new(tipoNodo);
         q->letra = c;
         q->frecuencia = 1;
         q->cero = q->uno = NULL;
         q->sig = p;
         if(a) a->sig = q;
         else Lista = q;
      }
   }
}
 
void Ordenar(tipoNodo* &Lista){
   tipoNodo *Lista2, *a;
 
   if(!Lista) return;
   Lista2 = Lista;
   Lista = NULL;
   while(Lista2){
      a = Lista2;
      Lista2 = a->sig;
      InsertarOrden(Lista, a);
   }
}
 
void InsertarOrden(tipoNodo* &Cabeza, tipoNodo *e)
{
   tipoNodo *p, *a;
 
   if(!Cabeza){
      Cabeza = e;
      Cabeza->sig = NULL;
   }
   else{
       p = Cabeza;
       a = NULL;
       while(p && p->frecuencia < e->frecuencia){
          a = p;
          p = p->sig;
       }
 
       e->sig = p;
       if(a) a->sig = e;
       else Cabeza = e;
    }
}
 
void CrearTabla(tipoNodo *n, int l, int v){
   if(n->uno)  CrearTabla(n->uno, l+1, (v<<1)|1);
   if(n->cero) CrearTabla(n->cero, l+1, v<<1);
   if(!n->uno && !n->cero) InsertarTabla(n->letra, l, v);
}
 
void InsertarTabla(char c, int l, int v){
   tipoTabla *t, *p, *a;
 
   t = new(tipoTabla);
   t->letra = c;
   t->bits = v;
   t->nbits = l;
 
   if(!Tabla){
      Tabla = t;
      Tabla->sig = NULL;
   }
   else{
       p = Tabla;
       a = NULL;
       while(p && p->letra < t->letra){
          a = p;
          p = p->sig;
       }
 
       t->sig = p;
       if(a) a->sig = t;
       else Tabla = t;
    }
}
 
tipoTabla *BuscaCaracter(tipoTabla *Tabla, char c){
   tipoTabla *t;
 
   t = Tabla;
   while(t && t->letra != c) t = t->sig;
   return t;
}
 
void BorrarArbol(tipoNodo *n){
   if(n->cero) BorrarArbol(n->cero);
   if(n->uno)  BorrarArbol(n->uno);
   delete(n);
}

Ahora estuve viendo que la logica era comprimir por que coge solo un digito y si se repite a esta le aumenta la cantidad de veces en un apartado de frecuencias, entonces seguido seria pasarle al arbol, para que reduzca el tamanño en Bits.

Pero note que en una frase de 15 bits, esta llegaba a 72 Bits. (nom comprime ...)
Luego observe que el texto guardado ya no es legible, no se si esto se deba a las funciones archivos:

Código: C++

   fs = fopen(argv[2], "wb");

Lo asumi que tal vez este cifrado pero recorde que en archivos la escritura tambien se puede hacer en binario, cosa que aun no me queda, si deberia cifrar comprimir ?

Me da entender que con este algoritmo puedo comprimir el tamaño de la frase en texto plano y dicho sea de paso pueda comprimir/cifrar la informacion.

Ahora luego de encriptarlo vi que si era posible leer al supuesto archivo cifrado asi que decidi usar una forma de leer el archivo asi que use hexdump

Código: Bash

hexdump -C cifrado

y pude ver en el siquiete resultado:

Código: Bash

00000000  0f 00 00 00 0c 00 00 00  0a 02 00 00 00 04 31 03  |..............1.|
00000010  00 00 00 04 61 00 00 00  00 04 62 01 00 00 00 04  |....a.....b.....|
00000020  64 06 00 00 00 04 65 03  00 00 00 02 6f 07 00 00  |d.....e.....o...|
00000030  00 04 70 04 00 00 00 04  72 05 00 00 00 04 74 04  |..p.....r.....t.|
00000040  00 00 00 03 75 0a 00 00  00 04 78 0b 00 00 00 04  |....u.....x.....|
00000050  9d c7 6d 16 b1 03 20                              |..m... |
00000057

como se puede ver es posible la lectura de los caracteres usados en la supuesta encriptacion.
la frase usada fue: pruebadetexto1

la duda es:
. en realidad esto esta cifrado?
. por que puedo el texto si la idea de huffman es convertilo a binario?

lo digo por que con usando archivos en C, los textos usados para guardarlos en texto plano se guardan en binario y son ilegibles al leerlo.

Saludos.

ProfesorX

Me parece que estas un poco confundido respecto a como funcionan estos algoritmos.

Para empezar, tenemos dos tipos de algoritmo de compresion, con perdida y sin perdida.

En la compresion con perdida se reduce el tamaño de los datos de tal manera que si descomprimimos los datos se obtiene una secuencia de datos que es muy parecida a la secuencia original, pero no es exactamente igual a la secuencia original. Un ejemplo de este tipo de compresion son los archivos de imagenes jpg, los de musica mp3 y los de video mpg. Es por esta razon que por ejemplo cuando comprimes y descomprimes por ejemplo un archivo de musica, no suena como el original, ya que siempre habra perdida de informacion.

En la compresion sin perdida se reduce el tamaño de los datos de tal manera que si descomprimimos los datos obtenemos EXACTAMENTE la secuencia de datos original. Un ejemplo de este tipo de compresion son los archivos ZIP y RAR.

Acalarado esto vamos a los puntos.

Citar

Pero note que en una frase de 15 bits, esta llegaba a 72 Bits. (nom comprime ...)

Respecto a esto, parece que crees que cuando comprimes informacion, siempre deberia disminuir su tamaño. Pero esto no funciona asi. Este tipo de algoritmo es un algoritmo sin perdida, o sea que debes ser capaz de obtener la secuencia original de datos.

Supongamos que de 15 bits se reduce a 1 bit. Ahora un bit solo representa 0 y 1, entonces piensalo, solo tengo 2 valores a elegir, es imposible que de esos 2 valores pueda "reconstuir" la secuencia original de 15 bits. Recuerda que en realidad el algoritmo funciona elaborando una tabla de frecuencias con los valores contenidos en la secuencia de datos, y cuantas veces se repite cada dato. Entonces el tamaño "adicional" que aparece cuando comprimes una frase pequeña es donde esta contenida esta tabla de frecuencias.

Esto significa en realidad que el algoritmo es mas eficiente (o sea, comprime mas) entre mas grande sea la secuencia de datos, y tenga mayor cantidad de datos "repetidos", o sea mayor sera su porcentaje de compresion. Esta es la razon por la que por ejemplo un archvo de mapa de bits (BMP) se comprime en un porcentaje mayor que un archivo de imagen JPG cuando las comprimes en un archivo zip. (nota que hablo de porcentajes de compresion y no de tamaño en si).

Citar

como se puede ver es posible la lectura de los caracteres usados en la supuesta encriptacion.
la frase usada fue: pruebadetexto1

la duda es:
. en realidad esto esta cifrado?
. por que puedo el texto si la idea de huffman es convertilo a binario?

Ahora, recuerda que todo caracter tiene una representacion en codigo ASCII, y este codigo en realidad es un numero en binario y viceversa. Esto significa tambien que CUALQUIER numero en binario se puede representar como un caracter ASCII.

Por ejemplo, la letra A mayuscula se representa con el numero 01000001 en binario, 41 en hexadecimal y 65 en decimal, esto tambien significa que si tu guardaras el numero 65 en binario en un archivo, y lo ves con el Hexdump, tu lo verias como si fuera la A mayuscula y no como el numero 65.

Entonces lo que tu ves en el hexdump es la representacion en ASCII de los numeros en binario, y pareciera que puedes ver el texto original, pero no es asi, si te fijas bien tambien aparecen la letra m y x, que no estan en tu texto original, ademas que las letras no aparecen en el orden de tu frase, recuerda tambien que este no es un algoritimo de cifrado, es un algoritmo de compresion, y aunque pareciera que cifrar y comprimir es lo mismo no es asi.

Espero que con esto te haya aclarado un poco las dudas.

Saludos

SoloCodigo

Autor Tema: compresion - cifrado con huffman - duda (Leído 4219 veces)

ryan parker

compresion - cifrado con huffman - duda

ProfesorX

Re:compresion - cifrado con huffman - duda