Implementación de la compresión Huffman
//main.cpp
#include "HuffmanTree.h"
#include
#include< stdlib.h>
//#include< iostream>
//usando el espacio de nombres std;
int main(){
HuffmanTree huftree;
char Elegir;
while(1){
cout< ;<"\n\n********* *** *************Bienvenido al sistema de codificación/decodificación Huffman************************\n "<< cout<<" Puedes realizar las siguientes operaciones:\n";. cout<<" 1 Construye un árbol de Huffman/n "; cout<<" 2 codificación (el texto fuente ya está en el archivo ToBeTran o escrito en el teclado)/n"; cout<<" (el texto del código ya está en el archivo CodeFile Medium)/n"; p> cout<<" 4 Mostrar código de texto/n"; cout<<" 5 Mostrar Árbol de Huffman/n"; cout<<" 6 Salir/n"; cout<<" Seleccione una operación:"; cin >& & gt;Elegir; cambiar(Elegir) { caso '1': huftree. ruptura; caso '5': huftree.PrintHuffmanTree(); ruptura; caso '6 ': cout <<"\n****************** **** ¡Gracias por usar este sistema!******** ********** *\n\n"; sistema("pausa"); devuelve 0; }/ /switch } //mientras }///main ///Huffmannode.h #ifndef _HuffmanNode_ #define _HuffmanNode_ struct HuffmanNode { int peso; //almacena el peso del nodo, asumiendo que solo se considera para tratar el caso en el que el peso es un número entero int parent; int peso int parent //-1 representa el nodo raíz; de lo contrario, representa el nodo no raíz int lchild,rchild; //almacena el número de la celda donde están los hijos izquierdo y derecho se encuentran respectivamente }; #endif //huffmantree.h" #ifndef _HuffmanTree_ #define _HuffmanTree_ #include "HuffmanNode.h" #include #include< fstream> #include usando el espacio de nombres std; clase HuffmanTree //HuffmanTree { público: estructura HuffmanNode * Node; //Node[] guarda el árbol de Huffman char *Info; //Info[] guarda los caracteres utilizados en el texto fuente - código fuente, por ejemplo: HuffmanTree g.,a',. 'b', 'c', 'd', 'e', estos caracteres se pueden colocar en un nodo en lugar de configurarse individualmente. Almacenamiento de matriz int LeafNum; Árbol de Huffman. La cantidad es también la cantidad de código fuente. public: HuffmanTree() ~HuffmanTree(); > void CreateHuffmanTree() ; /* Crea un árbol Huffman en la memoria y guárdalo en Node[]. Deja que el usuario elija entre dos métodos para crear un árbol Huffman: 1. Leer desde el teclado. número de caracteres del código fuente, cada carácter y el peso de cada carácter, cree un árbol Huffman, y luego escriba el árbol Huffman en el archivo hfmTree.2 Lea la información del árbol Huffman del archivo hfmTree. crear un árbol de Huffman*/ void CreateHuffmanTreeFromKeyboard(); void CreateHuffmanTreeFromFile(); void Encoder() /* Usado Construir el árbol de Huffman ( si no está en la memoria, lea el archivo hfmTree y cree el árbol Huffman en la memoria), codifique el texto del cuerpo en el archivo ToBeTran y escriba el texto del código en el archivo CodeFile El contenido de ToBeTran puede. ser editados y generados a través de programas como el Bloc de notas. */ void Decoder(); /* El texto del código a decodificar se almacena en el archivo CodeFile y utiliza el árbol de Huffman establecido (si no está en la memoria, entonces desde el archivo hfmTree y cree un árbol Huffman en la memoria) para decodificar el texto del código, luego escriba el texto fuente obtenido en el archivo TextFile, escriba el texto fuente generado en el archivo TextFile y envíelo a en la pantalla. */ void PrintCodeFile() /* Muestra el archivo de código CodeFile en la pantalla */ void PrintHuffmanTree() /* Muestra el archivo de código en forma visual en el La pantalla (notación cóncava, tabla generalizada u otra representación de árbol) muestra el árbol de Huffman, y lo escribe en el archivo TreePrint. Escribe el archivo TreePrintFile al mismo tiempo */ void PrintHuffmanTree_aoru(int T,int Layer=1 /* Muestra el árbol de Huffman usando representación cóncava, llamado por PrintHuffmanTree() */ }; # endif //huffmantree.cpp #include "HuffmanTree.h" #include< string #include //#include usando el espacio de nombres std; //********************************************* **** ********* HuffmanTree::HuffmanTree() { LeafNum=0; Nodo= NULL; Información+NULL; } //****************** **** ******** **************************** HuffmanTree:: ~HuffmanTree() { eliminar []Nodo; Nodo=NULL; eliminar []Info; Información=NULL; } //****************************** *********** ******************* void HuffmanTree::CreateHuffmanTree() { char Choose ; cout<< "¿Quieres leer el árbol de Huffman desde un archivo (presiona 1) o ingresar el árbol de Huffman desde el teclado (presiona 2) ?" ; cin> >Choose; if(Choose=='2') { // La entrada del teclado creará un árbol de Huffman CreateHuffmanTreeFromKeyboard( ); }//choose=='2' else { // Construya un árbol de Huffman a partir de la información del archivo del árbol de Huffman hfmTree.dat CreateHuffmanTreeFromFile(); } } //********************* ******** ******* ********************** void HuffmanTree::CreateHuffmanTreeFromKeyboard() { int Num; int i,j,pos1,pos2,max1, max2; cout<<"\ nIngrese el número de juegos de caracteres de origen:"; cin>>Num; if (Num<=1) { cout<< "No se puede construir un árbol de Huffman con h menos de 2 nodos de hoja.\n\n"; return; } LeafNum=Num; Node= nuevo HuffmanNode[2*Num-1]; Info=new char[2*Num-1]; for( i=0; i& lt;Num;i++) { //Lee la información del nodo hoja del árbol de Huffman cout<< "Por favor ingresa el primer "< getchar( ); Info[i]=getchar(); //Los caracteres de origen se almacenan en la matriz de caracteres Info[] getchar() cout<; < "Ingrese el peso o la frecuencia de este carácter"; cin>> Node[i].rchild=-1 //sin hijo correcto } for( i=Num;i<2*Num-1;i++) //el bucle crea nodos del árbol Huffman que indican la necesidad de fusionar Num-1 { pos1 =- 1; pos2=-1; //Se utiliza para almacenar el valor mínimo actual y el siguiente más pequeño en los números de celda respectivamente max1=32767 max2=32767; del número de forma especial, respectivamente Se utiliza para almacenar el valor mínimo encontrado actualmente y el siguiente valor mínimo max1=32767 max2=32767 //32767 es el valor máximo del número de forma especial, se utiliza para almacenar el valor mínimo encontrado actualmente y el siguiente valor mínimo respectivamente Valor mínimo for(j=0;j { if (Node[j].parent==-1) // ¿Es el nodo raíz? if(Node[j].weight< max1) //¿Es menor que el valor mínimo? { max2=max1; //El valor mínimo original se convierte en el siguiente valor mínimo max1= Node[j].weight; //almacena el mínimo pos2=pos1; //modifica el número de la celda donde se encuentra el siguiente más pequeño pos1=j; modificar el número de la celda donde se encuentra el valor mínimo } else if(Node[j].weight { max2=Node[j].weight; pos2=j; } } Nodo [pos1].parent=i; Nodo[pos2].parent=i; Nodo[i].lchild=pos1; Nodo[i ].rchild=pos2; Nodo[i ].parent=-1; Nodo[i].peso=Nodo[pos1].w ocho+Nodo[pos2].weight; }//for LeafNum=Num; cout<< "El árbol de Huffman se ha construido con éxito. \n"; // Escribe el árbol Huffman construido en el archivo hfmTree.dat char ch; cout<< "Si deseas reemplazar el archivo de árbol original de Huffman (Y/N): "; cin>>ch; if (ch!='y ' &&ch!='Y') return ; ofstream fop; fop.open("hfmTree.dat",ios::out|ios::binary|ios::trunc); //abre el archivo if(fop. fail()) { cout<<"\n La apertura del archivo del árbol Huffman no pudo escribir el árbol Huffman en el archivo hfmTree.dat.write((char*)&Info [i] ,sizeof(Info[i])); Flush(cout); } for( i=0;i<2* Num-1 ;i++) { // Finalmente escribe en cada nodo del árbol de Huffman (almacenado en Node[]) fop.write((char*)&Node[i],sizeof(Node[i ])) ; flux(cout); } fop.close() // Cerrar el archivo cout <<" \n El árbol Huffman se ha escrito correctamente en el archivo hfmTree.dat.\n"; } //************ *** ************************************** void HuffmanTree: :CreateHuffmanTreeFromFile() { ifstream fip fip.open("hfmTree.dat",ios::binary|ios:: in); if(fip.fail()) { cout<< "El archivo hfmTree.dat del árbol Huffman no se pudo abrir y no se pudo construir el árbol Huffman. \n"; return; } fip.read((char*)&LeafNum,sizeof(LeafNum)); if (LeafNum<=1) { cout<< "Los datos en el archivo del árbol de Huffman son incorrectos, el número de nodos de hoja es menor que 2 y el árbol de Huffman no se puede construir. read(( char*)&Info[i],sizeof(Info[i])); for(int i=0;i<2*LeafNum-1;i++) fip.read(( char*)&Node[i],sizeof(Node[i])); fip.close(); cout<< "El árbol de Huffman tiene construido exitosamente.\n"; } //*************************** ***** ******************************* void HuffmanTree::Encoder() { if(Node ==NULL) // No hay ningún árbol de Huffman en la memoria, luego use la información en el archivo del árbol de Huffman hfmTree.dat y construya el árbol de Huffman { CreateHuffmanTreeFromFile(); if (LeafNum<=1) { cout< < "Nada en la memoria del árbol de Huffman. Char Choose; cout<< "¿Quieres leer el texto fuente de un archivo (presiona 1) o escribirlo desde el teclado (presiona 2)? " ; cin>>Elegir; if(Choose=='1') { ifstream fip1("ToBeTran .txt"); if(fip1.fail()) { cout<< "¡Error al abrir el archivo de texto fuente! No se puede continuar la ejecución. \n"; return; } char ch; int k=0; while(fip1.get(ch)) k++; //la primera vez que lees el archivo solo cuentas cuántos caracteres hay en el archivo y colocas el número de caracteres en k fip1.close() SourceText=new char[k+1]; //Utiliza el espacio de la matriz de caracteres para almacenar el texto fuente ifstream fip2("ToBeTran.txt"); /Segundo Al leer el archivo fuente por primera vez, escriba el contenido en SourceText[] k=0 while(fip2.get(ch)) SourceText[k++] =ch; p> fip2.close(); SourceText[k]='\0'; cout<< "El El texto fuente a codificar es:"; cout<& & lt;SourceText< } else { // Ingrese la fuente texto del teclado string SourceBuff cin.ignore(); cout<< "Ingrese el texto fuente a codificar (puede ingresar cualquier longitud, presione enter para finalizar):\n"; getline(cin,SourceBuff,'\n'); int k=0; while(SourceBuff[k]!= '\0') k++; SourceText=new char[k+1]; k=0; while(SourceBuff[k]! = '\0') { SourceText[k]=SourceBuff[k]; k++; } SourceText[ k]='\0'; } ofstream fop("CodeFile.dat", ios::trunc ); //abre el archivo donde está almacenado el texto del código char *code; code=new char[LeafNum] //almacena el código de un carácter de texto fuente<; /p> int k=0; int i,j,start; while( TextoFuente[k]! = '\0') //Codifica la cadena de origen una por una comenzando desde el primer carácter de la cadena { start=0; para (i=0;i if(Info[i]==SourceText[k]) //Encuentra el número de la celda donde se encuentra el texto romper; > j=i; while(Node[j].parent!=-1) //el nodo j no es el nodo raíz { j =Node [j].parent; //busca el nodo biparental del nodo j if(Node[j].lchild==i) //Este es el subárbol izquierdo, genera código 0 code[start++]='0'; else code[start++]='1'; //Este es el subárbol derecho, genera código 1 i=j; } code[start]='\0'; //Establece el terminador de cadena for(i = 0;i { j=código[i]; código[i]=código[inicio-1 - i]; code[start-1-i]=j; } i=0; //Escribe el código correspondiente al actual carácter del texto fuente en el archivo de código while(code[i]!= '\0') { fop< i++; } k++; //Mover un carácter hacia atrás en la cadena de origen } fop.close(); cout<<" La codificación se ha completado y el texto del código se ha escrito en el archivo CodeFile.dat.\n\n"; } //*************************************** **** ************* void HuffmanTree::Decoder() { Si está en la memoria Si no hay un árbol de Huffman, construya el árbol de Huffman a partir del archivo del árbol de Huffman hfmTree.dat if (Node==NULL) { CreateHuffmanTreeFromFile(); if (LeafNum<=1) { cout<< "No hay ningún árbol de Huffman en la memoria. Operación deshacer. \n\n"; return; } } } // Desde archivo Lea el texto del código de CodeFile.dat a CodeStr[] ifstream fip1("CodeFile.dat" if(fip1.fail ()) cout<< "No hay texto de código para decodificar.\n"; Retorno; } char * CodeStr; int k=0; char ch; while(fip1.get(ch)) { k++; } fip1.close(); CodeStr=nuevo carácter[k+1]; ifstream fip2("CodeFile.dat"); k=0; while(fip2.get(ch)) CodeStr[k++ ]=ch; fip2.close(); CodeStr[k]='\0'; cout<< "El texto fuente decodificado es: "; ofstream fop("TextFile.dat"); int j=(LeafNum-1)*2; //j apunta a la raíz del árbol de Huffman< / p> int i=0; // El texto del código comienza desde el primer símbolo y desciende por el árbol de Huffman desde la raíz. Dependiendo del símbolo actual del texto del código, se decide si se debe bajar hacia la izquierda. hijo o el hijo correcto. while(CodeStr[i]!= '\0') // Vaya al nodo de hoja del árbol de Huffman y luego traduzca el símbolo del texto fuente correspondiente a la hoja. nodo { if(CodeStr[i]=='0') j=Node[j].lchild //ir a la izquierda else j=Node[j].rchild; //ir a la derecha if(Node[j].close(); cout<<"\n Decodificación exitosa y guardada en el archivo TextFile.dat. \n\n"; } //*************************** *** **************************** void HuffmanTree::PrintCodeFile() { char ch; int i=1; ifstream fip("CodeFile.dat"); ofstream fop; ("CodePrin .dat"); if(fip.fail()) { cout<< "No hay ningún archivo de código, puede' t mostrar el contenido del archivo de código.\n"; return; } while(fip.get(ch)) { p> cout< fop< if(i==50) cout< fop< i=0; } i++; } cout< fop< fip.p> fip.close( ); fop.close(); } //********** ******** ************************************* void HuffmanTree. :PrintHuffmanTree() { // Si no hay ningún árbol de Huffman en la memoria, lea la información del archivo del árbol de Huffman. hfmTree.dat y construye el árbol Huff Man if(Node==NULL) { CreateHuffmanTreeFromFile(); if (LeafNum<=1) { cout<< "No hay ningún árbol de Huffman en la memoria. Operación deshacer. \n\n"; Retorno; } } ofstream fop("TreePrint.dat",ios_base:: trunc); fop.close(); PrintHuffmanTree _aoru(2*LeafNum-1-1); Retorno; } //*************************************** * *************** void HuffmanTree:.PrintHuffmanTree_aoru(int T,int Layer)//representación cóncava { if(Node[T].lchild!=-1) PrintHuffmanTree_aoru(Node[T].lchild,layer+ 1);//subárbol izquierdo for ( int i=1;i<=capa;i++)// raíz cout<<<'\0'<<'\0'<<'\0'; cout< If (Nodo[T].rchild!=-1) PrintHuffmanTree_aoru(Nodo[T].rchild, capa +1); // subárbol derecho }