elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Rompecabezas de Bitcoin, Medio millón USD en premios


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  compresion - encriptacion con huffman - duda
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: compresion - encriptacion con huffman - duda  (Leído 2,454 veces)
ryan parker

Desconectado Desconectado

Mensajes: 81



Ver Perfil
compresion - encriptacion con huffman - duda
« en: 10 Julio 2012, 04:31 am »

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
  1. #include <iostream>
  2. #include <cstdio>
  3.  
  4. using namespace std;
  5.  
  6. typedef struct _nodo{
  7.   char letra;
  8.   int frecuencia;
  9.  
  10.   _nodo *sig;
  11.   _nodo *cero;
  12.   _nodo *uno;
  13. } tipoNodo;
  14.  
  15.  
  16. typedef struct _tabla{
  17.   char letra;
  18.   unsigned long int bits;
  19.   char nbits;
  20.   _tabla *sig;
  21. } tipoTabla;
  22.  
  23. tipoTabla *Tabla;
  24.  
  25. void Cuenta(tipoNodo* &Lista, char c);
  26. void Ordenar(tipoNodo* &Lista);
  27. void InsertarOrden(tipoNodo* &Cabeza, tipoNodo *e);
  28. void BorrarArbol(tipoNodo *n);
  29. void CrearTabla(tipoNodo *n, int l, int v);
  30. void InsertarTabla(char c, int l, int v);
  31. tipoTabla *BuscaCaracter(tipoTabla *Tabla, char c);
  32.  
  33. int main(int argc, char *argv[]){
  34.   tipoNodo *Lista;
  35.   tipoNodo *Arbol;
  36.  
  37.   FILE *fe, *fs;
  38.   char c;
  39.   tipoNodo *p;
  40.   tipoTabla *t;
  41.   int nElementos;
  42.   long int Longitud = 0;
  43.  
  44.   unsigned long int dWORD;
  45.   int nBits;
  46.  
  47.   if(argc < 3)
  48.   {
  49.      cout<<"\n\tUsar:\n\t"<<argv[0]<<" <fichero_entrada> <fichero_salida>\n";
  50.      return 1;
  51.   }
  52.  
  53.   Lista = NULL;
  54.  
  55.   fe = fopen(argv[1], "r");
  56.   while((c = fgetc(fe)) != EOF){
  57.      Longitud++;
  58.      Cuenta(Lista, c);
  59.   }
  60.   fclose(fe);
  61.  
  62.   Ordenar(Lista);
  63.  
  64.   Arbol = Lista;
  65.   while(Arbol && Arbol->sig){
  66.      p = new(tipoNodo);
  67.      p->letra = 0;
  68.      p->uno = Arbol;
  69.      Arbol = Arbol->sig;
  70.      p->cero = Arbol;
  71.      Arbol = Arbol->sig;
  72.      p->frecuencia = p->uno->frecuencia + p->cero->frecuencia;
  73.      InsertarOrden(Arbol, p);
  74.   }
  75.  
  76.   Tabla = NULL;
  77.   CrearTabla(Arbol, 0, 0);
  78.  
  79.   fs = fopen(argv[2], "wb");
  80.  
  81.   fwrite(&Longitud, sizeof(long int), 1, fs);
  82.  
  83.   nElementos = 0;
  84.   t = Tabla;
  85.   while(t){
  86.      nElementos++;
  87.      t = t->sig;
  88.   }
  89.  
  90.   fwrite(&nElementos, sizeof(int), 1, fs);
  91.  
  92.   t = Tabla;
  93.   while(t)
  94.   {
  95.      fwrite(&t->letra, sizeof(char), 1, fs);
  96.      fwrite(&t->bits, sizeof(unsigned long int), 1, fs);
  97.      fwrite(&t->nbits, sizeof(char), 1, fs);
  98.      t = t->sig;
  99.   }
  100.  
  101.  
  102.   fe = fopen(argv[1], "r");
  103.   dWORD = 0;
  104.   nBits = 0;
  105.   while((c = fgetc(fe)) != EOF)
  106.   {
  107.  
  108.      t = BuscaCaracter(Tabla, c);
  109.  
  110.      while(nBits + t->nbits > 32){
  111.         c = dWORD >> (nBits-8);
  112.         fwrite(&c, sizeof(char), 1, fs);
  113.         nBits -= 8;
  114.      }
  115.      dWORD <<= t->nbits;
  116.      dWORD |= t->bits;
  117.      nBits += t->nbits;
  118.   }
  119.  
  120.   while(nBits>0){
  121.      if(nBits>=8) c = dWORD >> (nBits-8);
  122.      else c = dWORD << (8-nBits);
  123.      fwrite(&c, sizeof(char), 1, fs);
  124.      nBits -= 8;
  125.   }
  126.  
  127.   fclose(fe);
  128.   fclose(fs);
  129.  
  130.  
  131.   BorrarArbol(Arbol);
  132.  
  133.   while(Tabla){
  134.      t = Tabla;
  135.      Tabla = t->sig;
  136.      delete(t);
  137.   }
  138.  
  139.   return 0;
  140. }
  141.  
  142. void Cuenta(tipoNodo* &Lista, char c){
  143.   tipoNodo *p, *a, *q;
  144.  
  145.   if(!Lista){
  146.      Lista = new(tipoNodo);
  147.      Lista->letra = c;
  148.      Lista->frecuencia = 1;
  149.      Lista->sig = Lista->cero = Lista->uno = NULL;
  150.   }
  151.   else{
  152.      p = Lista;
  153.      a = NULL;
  154.      while(p && p->letra < c){
  155.         a = p;
  156.         p = p->sig;
  157.      }
  158.  
  159.      if(p && p->letra == c) p->frecuencia++;
  160.      else{
  161.         q = new(tipoNodo);
  162.         q->letra = c;
  163.         q->frecuencia = 1;
  164.         q->cero = q->uno = NULL;
  165.         q->sig = p;
  166.         if(a) a->sig = q;
  167.         else Lista = q;
  168.      }
  169.   }
  170. }
  171.  
  172. void Ordenar(tipoNodo* &Lista){
  173.   tipoNodo *Lista2, *a;
  174.  
  175.   if(!Lista) return;
  176.   Lista2 = Lista;
  177.   Lista = NULL;
  178.   while(Lista2){
  179.      a = Lista2;
  180.      Lista2 = a->sig;
  181.      InsertarOrden(Lista, a);
  182.   }
  183. }
  184.  
  185. void InsertarOrden(tipoNodo* &Cabeza, tipoNodo *e)
  186. {
  187.   tipoNodo *p, *a;
  188.  
  189.   if(!Cabeza){
  190.      Cabeza = e;
  191.      Cabeza->sig = NULL;
  192.   }
  193.   else{
  194.       p = Cabeza;
  195.       a = NULL;
  196.       while(p && p->frecuencia < e->frecuencia){
  197.          a = p;
  198.          p = p->sig;
  199.       }
  200.  
  201.       e->sig = p;
  202.       if(a) a->sig = e;
  203.       else Cabeza = e;
  204.    }
  205. }
  206.  
  207. void CrearTabla(tipoNodo *n, int l, int v){
  208.   if(n->uno)  CrearTabla(n->uno, l+1, (v<<1)|1);
  209.   if(n->cero) CrearTabla(n->cero, l+1, v<<1);
  210.   if(!n->uno && !n->cero) InsertarTabla(n->letra, l, v);
  211. }
  212.  
  213. void InsertarTabla(char c, int l, int v){
  214.   tipoTabla *t, *p, *a;
  215.  
  216.   t = new(tipoTabla);
  217.   t->letra = c;
  218.   t->bits = v;
  219.   t->nbits = l;
  220.  
  221.   if(!Tabla){
  222.      Tabla = t;
  223.      Tabla->sig = NULL;
  224.   }
  225.   else{
  226.       p = Tabla;
  227.       a = NULL;
  228.       while(p && p->letra < t->letra){
  229.          a = p;
  230.          p = p->sig;
  231.       }
  232.  
  233.       t->sig = p;
  234.       if(a) a->sig = t;
  235.       else Tabla = t;
  236.    }
  237. }
  238.  
  239. tipoTabla *BuscaCaracter(tipoTabla *Tabla, char c){
  240.   tipoTabla *t;
  241.  
  242.   t = Tabla;
  243.   while(t && t->letra != c) t = t->sig;
  244.   return t;
  245. }
  246.  
  247. void BorrarArbol(tipoNodo *n){
  248.   if(n->cero) BorrarArbol(n->cero);
  249.   if(n->uno)  BorrarArbol(n->uno);
  250.   delete(n);
  251. }

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
  1.   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 ?

A bueno puse algunas pruebas como resultados en este topic: Cifrando con Huffman - Duda

Saludos.


« Última modificación: 10 Julio 2012, 13:27 pm por ryan parker » En línea

Your kung-fu is not strong!
ryan parker

Desconectado Desconectado

Mensajes: 81



Ver Perfil
Re: compresion - encriptacion con huffman - duda
« Respuesta #1 en: 10 Julio 2012, 13:28 pm »

estoy cometiendo alguna falta a las reglas ....
o no esta habiendo actividad en el foro ... creo nadie me responde  :o


En línea

Your kung-fu is not strong!
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Duda :Codificación Y Compresión De Un MP3
Multimedia
00000000000 3 2,247 Último mensaje 11 Noviembre 2005, 07:56 am
por Sourraund
[MOD] Compresion de video y audio, cual es la mejor compresion?
Multimedia
robinsv 4 4,961 Último mensaje 29 Diciembre 2005, 21:01 pm
por Songoku
cifrando con huffman - duda
Hacking
ryan parker 0 2,627 Último mensaje 9 Julio 2012, 01:55 am
por ryan parker
que talco? duda bytes necesarios para contener un pixel RGB de sin compresión.
Diseño Gráfico
rub'n 5 12,063 Último mensaje 7 Agosto 2016, 12:20 pm
por 4rm4ndo
Duda encriptacion en imagen .png
Criptografía
kingcreek 0 2,779 Último mensaje 7 Diciembre 2016, 22:55 pm
por kingcreek
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines