精华内容
下载资源
问答
  • Java--哈夫曼压缩原理

    2021-07-30 22:56:43
    1. 哈夫曼压缩原理 首先要明确一点,计算机里面所有的文件都是以二进制的方式存储的。 在计算机的存储单元中,一个ASCII码值占一个字节,1个字节等于8位(1Byte = 8bit) 可以参考这个网站: ASCII码在线转换...

    1. 哈夫曼压缩原理

    • 首先要明确一点,计算机里面所有的文件都是以二进制的方式存储的。
    • 在计算机的存储单元中,一个ASCII码值占一个字节,1个字节等于8位(1Byte = 8bit)

    可以参考这个网站:

    ASCII码在线转换计算器
    在这里插入图片描述


    以"JavaJavaJavaJavaJavaJava"这个字符串为例,它在计算机内部是这样存储的(每一个字符的ASCII码转换为二进制存储起来):

    public static void main(String[] args) {
            String beforeStr = "JavaJavaJavaJavaJavaJava";
            StringBuilder afterStr = new StringBuilder("");
    //        把字符串的每一个字符的ASCII码转换为二进制存储起来
            for (int i = 0; i < beforeStr.length(); i++) {
                afterStr.append(binaryToDecimal((int) beforeStr.charAt(i)));
            }
            System.out.println(beforeStr + "\n 在计算内是这样存储的: \n" + afterStr);
            System.out.println("afterStr.length = " + afterStr.length());
        }
    
        //     十进制转换位二进制的算法
        public static String binaryToDecimal(int n) {
            StringBuilder str = new StringBuilder();
            while (n != 0) {
                str.insert(0, n % 2);
                n = n / 2;
            }
    //        不满8位前面补0
            while (str.length() < 8) {
                str.insert(0, '0');
            }
            return str.toString();
        }
    

    在这里插入图片描述
    可以发现现在“JavaJavaJavaJavaJavaJava”转01字符串的长度位192

    验证文件大小:

    1. 首先,我新建了一个文件
      在这里插入图片描述

    2. 填充内容

    在这里插入图片描述

    1. 查看大小

    在这里插入图片描述

    文件大小为24字节 = 24 * 8 = 192bit

    以 “JavaJavaJavaJavaJavaJava” 这个字符串每个字符出现的次数为权值建立最优二叉数

    在这里插入图片描述

    所以“JavaJavaJavaJavaJavaJava”可以表示为:
    001011001011001011001011001011001011  长度为36

    所以压缩率为:
    原来长度是 192,压缩了 (192-36) = 156
    压缩率:156/ 192= 81.25%



    展开全文
  • python实现信息论哈夫曼编码_哈夫曼压缩原理及python3实现(非面向对象结构)-附件资源
  • 哈夫曼压缩与解压缩

    万次阅读 多人点赞 2018-08-13 12:52:01
    哈夫曼压缩与解压缩 目录 哈夫曼压缩与解压缩 一:引言 二:主要技术点 三:过程介绍 1、压缩: 2、解压缩 四:详细分析 一:准备过程 二:压缩 三:解压缩 五:结果演示 六:总结 七:源码地址 一:...

    哈夫曼压缩与解压缩

    目录

    哈夫曼压缩与解压缩

    一:引言

    二:主要技术点

    三:过程介绍

    1、压缩:

    2、解压缩

    四:详细分析

    一:准备过程

    二:压缩

    三:解压缩

    五:结果演示

    六:总结

    七:源码地址


    一:引言

    之前的两个贪吃蛇和巨大数的练习,总体来说难度不大,有好的算法和比较新颖的微译码补码。但是,哈夫曼压缩与解压缩可以说难度比前两个大得多,涉及的知识面更加广。做完这个,是对自己基本功的检测,更能提升自己的编程能力。 

    hffman编码的思想对文件进行压缩,主要原理是通过huffman编码来重新表示字符,使得出现频率高的字符编码短,出现少的字符编码长。整体下来的话,所需的总的bit位是减少的。但是要注意当大部分字符出现的频率都差不多时,huffman压缩的压缩效率会很低。

    编程环境:

    UE(或sublime),TDM-GCC。

    二:主要技术点

    1. 文件的各种操作
    2. 递归思想构造哈夫曼编码。
    3. 位运算思想进行压缩与解压缩。
    4. 自定义目标压缩文件头部元数据。
    5. 主函数带参,命令行参数。

    三:过程介绍

    1、压缩:

    1、统计字符种类及频度:ASCII码值当下标,字符频度当对应下标的值。

    2、构建哈夫曼树:在没有访问过的节点中,找最小字符频度下标来构建哈夫曼树。

    3、构建哈夫曼编码:递归思想构建。

    4、生成压缩文件(.ycyHuf后缀名):把字符的哈夫曼编码以二进制形式写入目标文件中。给压缩文件头部写入元数据,解压缩时需使用这些数据。

    注意事项:给目标文件写二进制数据时,最后一个字节如果不满八位,会产生垃圾数据,如果不进行处理,在解压后,就不能完整的还原。所以,需计算最后一个字节中的有效位数。

    2、解压缩

    1、根据压缩文件的头部元数据,得到字符种类和频度。

    2、构建哈夫曼树:在没有访问过的节点中,找最小字符频度下标来构建哈夫曼树。

    3、构建哈夫曼编码:递归思想构建。

    4、生成解压缩的文件(后缀名和源文件后缀名一样 )即可:一位一位的从压缩文件中读取信息,'1'向左子树走,'0'向右子树走。

    注意事项:压缩文件头部有元数据,所以,解压时需要把文件指针定位到真正的信息处。当碰到最后一字节的垃圾位时,应结束,否则解压出的信息和源文件会不匹配。

    四:详细分析

    一:准备过程

    三个关于位运算的宏

    1、取出index位,若取出的index位为0,则GET_BYTE值为假,否则为真

    #define GET_BYTE(vbyte, index) (((vbyte) & (1 << ((index) ^ 7))) != 0)

    2、把index位设置为‘1’

    #define SET_BYTE(vbyte, index) ((vbyte) |= (1 << ((index) ^ 7)))

    3、把index位设置为‘0’ 

    #define CLR_BYTE(vbyte, index) ((vbyte) &= (~(1 << ((index) ^ 7))))

    二:压缩

    1、统计字符种类和频度

    结构体定义:

    typedef struct ALPHA_FREQ {
    	unsigned char alpha;		//字符,考虑到文件中有汉字,所以定义成unsigned char
    	int freq;					//字符出现的频度
    } ALPHA_FREQ;

    代码分析:

    ALPHA_FREQ *getAlphaFreq(char *sourceFileName, int *alphaVariety) {
    	int freq[256] = {0};
    	int i;
    	int index;
    	ALPHA_FREQ *alphaFreq = NULL;
    	FILE *fpIn;
    	int ch;
    	
    	fpIn = fopen(sourceFileName, "rb");
    	
    	/*统计所有字符的频度*/
    	ch = fgetc(fpIn);
    	while(!feof(fpIn)) {
    		freq[ch]++;
    		ch = fgetc(fpIn);
    	}
    	fclose(fpIn);
    
    	/*统计所有字符的种类*/
    	for(i = 0; i < 256; i++) {
    		if(freq[i]) {
    			(*alphaVariety)++;
    		}
    	}
    
    	alphaFreq = (ALPHA_FREQ *) calloc(sizeof(ALPHA_FREQ), *alphaVariety);
    	for(i = index = 0; i < 256; i++) {
    		if(freq[i]) {
    			alphaFreq[index].alpha = i;
    			alphaFreq[index].freq = freq[i];
    			index++;
    		}
    	}
    
    	return alphaFreq;
    }

    统计字符及其频度,开始想到了一个笨办法。 如下:

    AlPHA_FREQ freq[256]
    count = 0;
    i = 0;
    
    while(str[i]) {
    	index = 0;
    	while(index < count) {
    		if(freq[index].alpha == str[i]) {
    			break;
    		}
    		index++
    	}
    	
    	if(index < count) {
    		freq[count].freq++;
    	} else {
    		freq[count].alpha = str[i];
    		freq[count].freq = 1;
    		count++;
    	}
    }

    但是,这样做有一个很大的缺点:随着字符串的增多,查找次数就会越来越多,极端情况下,没有重复的字符,那么就要执行n-1次,光一个统计字符的函数,其时间复杂度就达到了O(n^2);这显然是不合理的。因此,有一个更好的算法:构建一个大的数组,以字符的ASCII码值当下标,字符频度当对应下标的值,实现用空间,换时间的目的。例如'A'的频度,永远存放在下标为65的元素中。这样做,其时间复杂度达到了O(n)。

    2、初始化哈夫曼表

    结构体定义:

    typedef struct HUFFMAN_TAB {
    	ALPHA_FREQ alphaFreq;
    	int leftChild;
    	int rightChild;
    	boolean visited;
    	char *code;
    } HUFFMAN_TAB;
    HUFFMAN_TAB *initHuffmanTab(ALPHA_FREQ *alphaFreq, int alphaVariety, int *hufIndex) {
    	int i;
    	HUFFMAN_TAB *huffmanTab = NULL;
    
    	huffmanTab = (HUFFMAN_TAB *) calloc(sizeof(HUFFMAN_TAB), 2 * alphaVariety - 1);
    	//huffmanTab申请了 2 * alphaVariety - 1大小的空间,在这只用了 alphaVariety个,还剩alphaVariety - 1个
    	for(i = 0; i < alphaVariety; i++) {
    		hufIndex[alphaFreq[i].alpha] = i;	//把哈夫曼表中的字符和其对应的下标形成键值对,存到hufIndex中
    		huffmanTab[i].alphaFreq = alphaFreq[i];
    		huffmanTab[i].leftChild = huffmanTab[i].rightChild = -1;
    		huffmanTab[i].visited = FALSE;
    		huffmanTab[i].code = (char *) calloc(sizeof(char), alphaVariety);
    	}
    
    	return huffmanTab;
    }

    字符种类个数即为哈夫曼树的叶子结点个数,那么,根据完全二叉树的性质,这个哈夫曼树的总结点数为叶子节点数加度为2的节点数,所以,n总 = 2 * n0 - 1。先构建出哈夫曼表,为后面构建哈夫曼树做准备。注意,需设置一个visited成员来表示结点有没有被访问过。

    例如:字符串为“siytweusitweusitweusitwesitesitesitesieieieeeeee”,那么,统计出的结果为这样:

    根据这个哈夫曼表,可以画出哈夫曼树的结构了,如下:

    3、生成哈夫曼树

    生成哈夫曼树,我们需要把频度大的节点放在离根近的地方,频度小的节点放在离根远的地方。所以,需要进行最小字符频度的查找。

    int getMinFreq(HUFFMAN_TAB *huffmanTab, int count) {
    	int index;
    	int minIndex = NOT_INIT;
    
    	for(index = 0; index < count; index++) {
    		if(FALSE == huffmanTab[index].visited) {
    			if(NOT_INIT == minIndex || huffmanTab[index].alphaFreq.freq < huffmanTab[minIndex].alphaFreq.freq) {
    				minIndex = index;
    			}
    		}
    	}
    	huffmanTab[minIndex].visited = TRUE;
    
    	return minIndex;
    }
    void creatHuffmanTree(HUFFMAN_TAB *huffmanTab, int alphaVariety) {
    	int i;
    	int leftChild;
    	int rightChild;
    
    	//huffmanTab使用剩下的 alphaVariety - 1个空间
    	for(i = 0; i < alphaVariety - 1; i++) {
    		leftChild = getMinFreq(huffmanTab, alphaVariety + i);
    		rightChild = getMinFreq(huffmanTab, alphaVariety + i);
    		huffmanTab[alphaVariety + i].alphaFreq.alpha = '#';
    		huffmanTab[alphaVariety + i].alphaFreq.freq = huffmanTab[leftChild].alphaFreq.freq
    																									 + huffmanTab[rightChild].alphaFreq.freq;
    		huffmanTab[alphaVariety + i].leftChild = leftChild;
    		huffmanTab[alphaVariety + i].rightChild = rightChild;
    		huffmanTab[alphaVariety + i].visited = FALSE;
    	}
    }

    生成的哈夫曼树的表格形式如下

    4、生成哈夫曼编码

    哈夫曼树都已经生成,那么就需要生成哈夫曼编码了。

    思路:需要把哈夫曼树从根节点除法,进行遍历,向左子树为‘1’,右子树为‘0’;若碰到叶子结点,需要把编码存给对应的字符。若没有碰到叶子结点,则需要继续向下遍历。所以,这需要一个递归程序完成。

    void makeHuffmanCode(HUFFMAN_TAB *huffmanTab, int root, int index, char *code) {
    	if(huffmanTab[root].leftChild != -1 && huffmanTab[root].rightChild != -1) {
    		code[index] = '1';
    		makeHuffmanCode(huffmanTab, huffmanTab[root].leftChild, index + 1, code);
    		code[index] = '0';
    		makeHuffmanCode(huffmanTab, huffmanTab[root].rightChild, index + 1, code);
    	} else {
    		code[index] = 0;
    		strcpy(huffmanTab[root].code, code);
    	}
    }

    5、把哈夫曼编码以二进制位形式写入目标文件中

    此时,我们需要考虑一个问题。如果,光把“siytweusitweusitweusitwesitesitesitesieieieeeeee”这个字符串的哈夫曼编码以二进制形式写入目标文件,形成的目标文件中全是0101这种二进制代码,那如何解密呢?没有人能看懂这种二进制代码,所以,我们需要给目标文件的头部写入元数据(解释数据的数据),这些元数据主要包括源文件字符种类,字符频度。有了元数据,那么,就可以在解压缩程序中再构造一个完全相同的哈夫曼树,完成解压缩。

    所以,我们也可以构造我们的文件头部元数据,定义一个结构体如下:

    typedef struct HUF_FILE_HEAD {
    	unsigned char flag[3];				//压缩二进制文件头部标志 ycy
    	unsigned char alphaVariety;		//字符种类
    	unsigned char lastValidBit;		//最后一个字节的有效位数
    	unsigned char unused[11];			//待用空间
    } HUF_FILE_HEAD;								//这个结构体总共占用16个字节的空间

    依次给文件头部写入头部标志“ycy”, 字符种类alphaVariety, 最后一字节的有效位数lastValidBit。

    HUF_FILE_HEAD fileHead = {'y', 'c', 'y'};
    fileHead.alphaVariety = (unsigned char) alphaVariety;
    fileHead.lastValidBit = getlastValidBit(huffmanTab, alphaVariety);
    
    fwrite(&fileHead, sizeof(HUF_FILE_HEAD), 1, fpOut);
    fwrite(alphaFreq, sizeof(ALPHA_FREQ), alphaVariety, fpOut);

    lastValidBit计算过程:

    //取最后一个字节的有效位数
    int getlastValidBit(HUFFMAN_TAB *huffmanTab, int alphaVariety) {
    	int sum = 0;
    	int i;
    	
    	for(i = 0; i < alphaVariety; i++) {
    		sum += strlen(huffmanTab[i].code) * huffmanTab[i].alphaFreq.freq;
    		//如果不执行这一步,当数据长度超过int的表示范围,就会出错
    		sum &= 0xFF; //0xFF化为二进制位1111 1111,这样做sum始终是最后一个字节,8位
    	}
    	//举例:若最后生成7位二进制,划分为一个字节,那么,这一个字节只有7位为有效位,其余都是垃圾位。
    	//我们只需要取出这个字节的那7个有效位,所以sum和8取余即可
    	//sum = sum % 8 <=> sum = sum & 0x7
    	//返回最后一个字节的有效位数
    	sum &= 0x7;
    		
    	return sum == 0 ? 8 : sum;
    }

    完后,我们的.ycyHuf文件头部就写好了:

    头部元数据写好后,就需要写入真正的压缩信息了。但是,如何根据字符,迅速找到其哈夫曼编码呢?有一种笨办法,就是每次都根据当前字符,在哈夫曼表中查找,如果字符匹配,就找到了哈夫曼编码。

    for(i = 0; i < alphaVariety; i++) {
    	if(str[index] == huffmanTab[i]) {
    	hufCode = huffmanTab[i].code;
        }
    }

     但是,这样每次查找进行的比较次数平均为n / 2,若字符串长度为len,则时间复杂度为O(len * n / 2)。所以,这样做不是很好,有一种方法,可以不进行“查找”,就能“查找到”,时间复杂度为O(1); 这样,需要构造出一个“字符”:“下标”的键值对关系,字符可以直接定位,就完成了这个“迅速查找”的任务。所以,我在初始化哈夫曼表initHuffmanTab()函数中,构造了这个键值对关系。

    //构造键值对
    hufIndex[alphaFreq[i].alpha] = i;	//把哈夫曼表中的字符和其对应的下标形成键值对,存到hufIndex中
    //查找
    hufCode = huffmanTab[hufIndex[ch]].code;

    下来,就可以正式的给目标压缩文件中写数据了。

    ch = fgetc(fpIn);
    	while(!feof(fpIn)) {
    		hufCode = huffmanTab[hufIndex[ch]].code;
    		//把每个字符的哈夫曼编码一个一个过。
    		//如果是字符'0',就转换为二进制的0
    		//如果是字符'1',就转换为二进制的1
    		for(i = 0; hufCode[i]; i++) {
    			if('0' == hufCode[i]) {
    				//value为一个字节
    				//从第1位依次赋值,若大于八位(一个字节)了,就写入文件中
    				CLR_BYTE(value, bitIndex);
    			} else {
    				SET_BYTE(value, bitIndex);
    			}
    			bitIndex++;
    			if(bitIndex >= 8) {
    				bitIndex = 0;
    				fwrite(&value, sizeof(unsigned char), 1, fpOut);
    			}
    		}
    		ch = fgetc(fpIn);
    	}
    	//如果最后一次不满一个字节,依然需要写到文件中,注意:写入的最后一个字节可能会存在垃圾位
    	if(bitIndex) {
    		fwrite(&value, sizeof(unsigned char), 1, fpOut);
    	}

     如果遇到了字符‘0’,就利用位运算转换为二进制0,否则,为二进制1。 如果最后一次不满一个字节,依然需要写到文件中,注意:写入的最后一个字节可能会存在垃圾位。

    三:解压缩

    1、统计字符种类和频度

    直接从压缩的文件中的头部读取。先匹配是不是自定义的格式:

    fileHead = readFileHead(sourceFileName);
    if(!(fileHead.flag[0] == 'y' && fileHead.flag[1] == 'c' && fileHead.flag[2] == 'y')) {
    	printf("不可识别的文件格式\n");
    }

     如果是“ycy”,那么再统计字符种类和频度:

    ALPHA_FREQ *getAlphaFreq(char *sourceFileName, int *alphaVariety, HUF_FILE_HEAD fileHead) {
    	int freq[256] = {0};
    	int i;
    	int index;
    	ALPHA_FREQ *alphaFreq = NULL;
    	FILE *fpIn;
    	int ch;
    
    	*alphaVariety = fileHead.alphaVariety;
    	alphaFreq = (ALPHA_FREQ *) calloc(sizeof(ALPHA_FREQ), *alphaVariety);
    	fpIn = fopen(sourceFileName, "rb");
    	//略过前16个字节的元数据
    	fseek(fpIn, 16, SEEK_SET);
    	fread(alphaFreq, sizeof(ALPHA_FREQ), *alphaVariety, fpIn);
    	fclose(fpIn);
    
    	return alphaFreq;
    }

     2、初始化哈夫曼表

    和压缩过程一样。

    3、生成哈夫曼树

    和压缩过程一样。

    4、生成哈夫曼编码

    和压缩过程一样。

    5、从压缩文件中读取二进制信息,还原文件

     应该先利用fseek()函数把文件指针跳过前面的元数据和字符种类及频度,定位到真正需要还原的地方。一位一位的进行判断,'1'向左子树走,'0'向右子树走;若到达叶子结点,向文件中写入叶子结点下标对应的字符。再回到根结点继续;若超过一个字节,8位,则需要读取下一个字节。

    void huffmanDecoding(HUFFMAN_TAB *huffmanTab, char *sourceFileName, char *targetFileName, int alphaVariety, HUF_FILE_HEAD fileHead) {
    	int root = 2 * alphaVariety - 2;
    	FILE *fpIn;
    	FILE *fpOut;
    	boolean finished = FALSE;
    	unsigned char value;
    	unsigned char outValue;
    	int index = 0;
    	long fileSize;
    	long curLocation;
    
    	fpIn = fopen(sourceFileName, "rb");
    	fpOut = fopen(targetFileName, "wb");
    	fseek(fpIn, 0L, SEEK_END);
    	fileSize = ftell(fpIn);	//文件总长度fileSize
    	fseek(fpIn, 16 + 5 * fileHead.alphaVariety, SEEK_SET);	//略过前面16个字节的元数据,5字节的字符种类和频度
    	curLocation = ftell(fpIn);
    	
    	//从根出发,'1'向左子树走,'0'向右子树走,若到达叶子结点,输出叶子结点下标对应的字符。再回到根结点继续。
    	fread(&value, sizeof(unsigned char), 1, fpIn);
    	while(!finished) {
    		if(huffmanTab[root].leftChild == -1 && huffmanTab[root].rightChild == -1) {
    			outValue = huffmanTab[root].alphaFreq.alpha;
    			fwrite(&outValue, sizeof(unsigned char), 1, fpOut);
    			if(curLocation >= fileSize && index >= fileHead.lastValidBit) {
    				break;
    			} 
    			root = 2 * alphaVariety - 2;
    		}
    		
    		//取出的一个字节从第一位开始看,'1'向左子树走,'0'向右子树走
    		//若超过一个字节,8位,则需要读取下一个字节
    		if(GET_BYTE(value, index)) {
    			root = huffmanTab[root].leftChild;
    		} else {
    			root = huffmanTab[root].rightChild;
    		}
    		if(++index >= 8) {
    			index = 0;
    			fread(&value, sizeof(unsigned char), 1, fpIn);
    			curLocation = ftell(fpIn);
    		}
    	}
    
    	fclose(fpIn);
    	fclose(fpOut);
    }

    五:结果演示

    六:总结

    哈夫曼压缩与解压缩的项目完成了(以后还会继续完善,优化)。这个项目涉及了C语言里更加高级的操作(文件,位运算,主函数带参······)。哈夫曼压缩与解压缩涉及的知识是我目前以来接触的项目里最多,最广的,收获很多。经过这个练习,还是觉得写程序前,一定一定要认真,仔细的进行手工过程的分析,一定要分析的很到位,否则,程序的逻辑就会出错,酿成大错。最后,不要忘记free申请的空间,以免造成内存泄漏。

    七:源码地址

    https://github.com/yangchaoy259189888/Huffman-compress/

    纠错:
    感谢下面这位前辈指出的这两个问题,经过测试,确实,当初测试了一个bmp文件,成功压缩和解压缩之后,以为大功告成。其实,还有很多极端情况没有考虑到。比如:一个全是a的txt文件就会失败。

    本人能力有限,毕竟这个代码不是我一个人从头到尾完成的,其中的很多思想都来自教主。

    还请看到的大神和我沟通,争取把这个错误解决······

    展开全文
  • 哈夫曼压缩(一)——英文文本

    千次阅读 2018-09-08 20:08:26
    一、哈夫曼压缩原理 哈夫曼压缩是一种无损的压缩算法,在压缩过程中不会损失信息熵,因此常用哈夫曼算法去压缩一些重要的文件资料。 哈夫曼压缩是通过采用特定长度的位序列去替代原来的个体符号(如字节)。对于...

    本文主要介绍如何实现哈夫曼压缩以及提高哈夫曼压缩过程的读写速率,对于哈夫曼树的概念及其构造则没有介绍,感兴趣的朋友可以先百度一下了解相关知识。

    一、哈夫曼压缩原理

    哈夫曼压缩是一种无损的压缩算法,在压缩过程中不会损失信息熵,因此常用哈夫曼算法去压缩一些重要的文件资料。

    哈夫曼压缩是通过采用特定长度的位序列去替代原来的个体符号(如字节)。对于一些高频率出现的字节,使用短字节表示,而对于一些低频率出现的字节,则采用较长的位序列来代替,这从而降低整个文本的位序列长度,达到压缩目的。

    二、哈夫曼压缩与解压缩过程

    要实现哈夫曼压缩,我们需要做如下工作:

    1、读取文本;

    2、统计文本中各字节出现的次数;

    3、根据第二步统计出来结果构造哈夫曼树;

    4、生成哈夫曼编码;

    5、将文件转换为哈夫曼编码格式的字节文件;

    6、写入哈夫曼编码。

    哈夫曼解压缩是压缩的逆过程,其主要步骤如下:

    1、读取压缩文件;

    2、还原哈夫曼编码;

    3、根据哈夫曼编码还原文件。

    三、哈夫曼压缩

    压缩思路:

    1、int [ ] byteCount和String [ ] charCode

    创建两个数组分别保存各字节出现的次数和哈夫曼编码,由于本文压缩的是英文文本,只需要用基础ASCII码(0-127),所以数组长度均设为128位,利用数组索引来存储对应的字节,索引位置的值存储相应信息;

    2、采用优先队列来构建哈夫曼树,通过调用poll( )方法可快速构建哈夫曼树,需要注意的是,这里需要加入一个比较器,重写compare()方法,采用按字节出现次数排序(从小到大);

    3、读写数据时采用字节缓冲流加字节数组的方法提高读写效率,减少对磁盘文件的操作;

    4、本文将编码文件与文件编码合并后一起生成字节文件后,再一次性写入压缩文件;

    5、生成字节文件时,最后一个字节不足8位时,加0补齐8位生成字节写入;

    6、压缩文件格式:

            本文压缩文件分为三段,分别为: 

            a.各字节编码长度( 0-127);

            b.末位补0数(128);

            c.字节编码文件(含编码字节);

    7、整型数据转换为字节方法:new Integer( int value).byteValue

    package com.liao.Huffman0830v1;
    
    import java.io.BufferedInputStream;
    import java.io.BufferedOutputStream;
    import java.io.File;
    import java.io.FileInputStream;
    import java.io.FileNotFoundException;
    import java.io.FileOutputStream;
    import java.io.IOException;
    import java.util.Comparator;
    import java.util.PriorityQueue;
    
    public class HufTree {
    	private static final int LEN = 128;
    	private int[] byteCount = new int[LEN];// 统计各字节出现次数
    	private String[] charCode = new String[LEN];// 记录各字节哈夫曼编码
    	private PriorityQueue<hufNode> nodeQueue = new PriorityQueue<>(LEN, new Comparator<hufNode>() {
    		@Override
    		public int compare(hufNode o1, hufNode o2) {
    			return o1.count - o2.count;// 按次数排序
    		}
    	});
    
    	// 成员内部类
    	private static class hufNode {
    		private hufNode lchild;// 左分支
    		private hufNode rchild;// 右分支
    		private String str;// 记录字符
    		private int count;// 统计次数
    		// 构造方法
    
    		public hufNode(String str, int count) {
    			super();
    			this.str = str;
    			this.count = count;
    		}
    	}
    
    	// 主函数
    	public static void main(String[] args) {
    		File file = new File("file\\01.txt");
    		File file2 = new File("file\\压缩文件.txt");
    		new HufTree().compress(file, file2);// 压缩文件
    		System.out.println("原文件大小:" + file.length() + "b");
    		System.out.println("压缩文件大小:" + file2.length() + "b");
    	}
    
    	// 压缩文件
    	private void compress(File file, File file2) {
    		byte[] bs = readFile(file);// 读取文件
    		countChar(bs);// 统计词频
    		hufNode root = createTree();// 创建哈夫曼树
    		generateCode(root, "");// 生成哈夫曼编码
    		printCode();// 打印哈夫曼编码
    		writeFile(bs, file2);// 写入压缩文件
    	}
    
    	// 将文件转换为字节数组保存
    	private byte[] readFile(File file) {
    		byte[] bs = new byte[(int) file.length()];// 创建字节数组
    		BufferedInputStream bis = null;// 声明字节缓冲流
    		try {
    			bis = new BufferedInputStream(new FileInputStream(file));
    			bis.read(bs);// 将文件读取到字节数组中
    		} catch (FileNotFoundException e) {
    			e.printStackTrace();
    		} catch (IOException e) {
    			e.printStackTrace();
    		} finally {
    			try {
    				if (bis != null)
    					bis.close();// 关闭输入流
    			} catch (IOException e) {
    				e.printStackTrace();
    			}
    		}
    		return bs;
    	}
    
    	// 统计词频
    	private void countChar(byte[] bs) {
    		for (int i = 0, length = bs.length; i < length; i++) {
    			byteCount[bs[i]]++;
    		}
    	}
    
    	// 创建哈夫曼树
    	private hufNode createTree() {
    		for (int i = 0; i < LEN; i++) {
    			if (byteCount[i] != 0) {// 使用优先队列保存
    				nodeQueue.add(new hufNode((char) i + "", byteCount[i]));
    			}
    		}
    		// 构建哈夫曼树
    		while (nodeQueue.size() > 1) {
    			hufNode min1 = nodeQueue.poll();// 获取并移除队列头元素
    			hufNode min2 = nodeQueue.poll();
    			hufNode result = new hufNode(min1.str + min2.str, min1.count + min2.count);
    			result.lchild = min1;
    			result.rchild = min2;
    			nodeQueue.add(result);// 加入左节点
    		}
    		return nodeQueue.peek();// 返回根节点
    	}
    
    	// 生成哈夫曼编码
    	private void generateCode(hufNode root, String s) {
    		// 叶子节点
    		if (root.lchild == null && root.rchild == null) {
    			// 保存至编码数组对应位置
    			charCode[(int) root.str.charAt(0)] = s;
    		}
    		if (root.lchild != null) {// 左边加0
    			generateCode(root.lchild, s + "0");
    		}
    		if (root.rchild != null) {// 右边加1
    			generateCode(root.rchild, s + "1");
    		}
    	}
    
    	// 写入压缩文件 :1、各字节编码长度 2、各字节编码 3、编码后的文件
    	private void writeFile(byte[] bs, File file2) {
    		BufferedOutputStream bos = null;// 声明字符缓冲流
    		try {
    			// 创建字符缓冲流
    			bos = new BufferedOutputStream(new FileOutputStream(file2));
    			// 写入各字节编码长度
    			String binaryCode = writeCodeLength(file2, bos);
    			// 字节数组文件转码成二进制文件
    			String binaryFile = transFile(bs);
    			// 合并二进制编码及文件
    			String codeAndFile = binaryCode + binaryFile;
    			// 生成字节并写入合并后二进制文件
    			generateFile(bos, codeAndFile);
    		} catch (IOException e) {
    			e.printStackTrace();
    		} finally {
    			try {
    				if (bos != null)
    					bos.close();// 关闭输入流
    			} catch (IOException e) {
    				e.printStackTrace();
    			}
    		}
    	}
    
    	// 写入各字节编码长度
    	private String writeCodeLength(File file2, BufferedOutputStream bos) throws IOException {
    		StringBuilder sb = new StringBuilder();// 创建字符缓冲流
    		for (int i = 0; i < LEN; i++) {
    			if (charCode[i] == null) {
    				bos.write(0);
    			} else {
    				sb.append(charCode[i]);// 存储哈夫曼编码
    				bos.write(charCode[i].length());
    			}
    		}
    		return sb.toString();// 返回各字节哈夫曼编码
    	}
    
    	// 文件转码
    	private String transFile(byte[] bs) {
    		StringBuilder sb = new StringBuilder();
    		for (int i = 0, length = bs.length; i < length; i++) {
    			sb.append(charCode[bs[i]]);
    		}
    		return sb.toString();
    	}
    
    	// 生成字节文件
    	private void generateFile(BufferedOutputStream bos, String codeAndFile) throws IOException {
    		int lastZero = 8 - codeAndFile.length() % 8;// 补0数
    		int len = codeAndFile.length() / 8 + 1;// 取商+1
    		if (lastZero != 8) {// 余数不为0,则补加1位
    			len = len + 1;
    			for (int i = 0; i < lastZero; i++) {
    				codeAndFile += "0";// 加0补齐8位
    			}
    		}
    		// 创建字符数组,保存字节
    		byte[] bv = new byte[len];
    		bv[0] = new Integer(lastZero).byteValue();
    		for (int i = 1; i < len; i++) {
    			// 先将8位01字符串二进制数据转换为十进制整型数据,再转为一个byte
    			byte bytes = new Integer(changeString(codeAndFile.substring(0, 8))).byteValue();
    			bv[i] = bytes;// 加入到数组中
    			codeAndFile = codeAndFile.substring(8);// 去除前8个字节
    		}
    		// 写入文件
    		bos.write(bv);
    	}
    
    	// 8位01字符串转换为十进制整型数据
    	private int changeString(String str) {
    		return (int) (str.charAt(0) - 48) * 128 + (str.charAt(1) - 48) * 64 + (str.charAt(2) - 48) * 32
    				+ (str.charAt(3) - 48) * 16 + (str.charAt(4) - 48) * 8 + (str.charAt(5) - 48) * 4
    				+ (str.charAt(6) - 48) * 2 + (str.charAt(7) - 48);
    	}
    
    	// 打印编码
    	private void printCode() {
    		for (int i = 0; i < LEN; i++) {
    			if (charCode[i] != null) {
    				System.out.println("(" + i + "," + (char) i + "," + byteCount[i] + "," + charCode[i] + ","
    						+ charCode[i].length() + ")");
    			}
    		}
    	}
    }

    四、哈夫曼解压缩

    解压缩思路:

    1、利用String类的substring()方法和Arrays类的copyOfRange方法对字符串进行复制及截取;

    2、利用BigInteger类的 new BigInteger(1, byte [ ]).toString(2)方法将字节数组转换为二进制字符串形式;

    package com.liao.Huffman0830v1;
    
    import java.io.BufferedInputStream;
    import java.io.BufferedOutputStream;
    import java.io.File;
    import java.io.FileInputStream;
    import java.io.FileNotFoundException;
    import java.io.FileOutputStream;
    import java.io.IOException;
    import java.math.BigInteger;
    import java.util.ArrayList;
    import java.util.Arrays;
    
    public class Decompress {
    	private final static int LEN = 128;// 编码字节个数
    	private String[] charCode = new String[LEN];
    
    	// 主函数
    	public static void main(String[] args) {
    		File file = new File("file\\压缩文件.txt");
    		File file3 = new File("file\\解压文件.txt");
    		new Decompress().decompress(file, file3);
    		System.out.println("解压前文件大小:" + file.length() + "b");
    		System.out.println("解压后文件大小:" + file3.length() + "b");
    	}
    
    	// 解压文件
    	private void decompress(File file, File file3) {
    		// 读取文件
    		byte[] bs = readFile(file);
    		// 获取各字节编码长度并返回哈夫曼编码总长度
    		int codeLengths = getCodeLength(bs);
    		// 截取记录哈夫曼编码长度部分
    		byte[] CodeLength = Arrays.copyOfRange(bs, 0, LEN);
    		// 末位补0数
    		int lastZero = bs[LEN];		
    		// 截取二进制数据部分
    		bs = Arrays.copyOfRange(bs, LEN+1, bs.length);
    		// 将字节数组转换为二进制字符串
    		String codeAndFile =processData(bs);
    		// 截取编码表部分
    		String binaryCode = codeAndFile.substring(0, codeLengths);
    		// 截取文件部分(增补0)
    		String binaryFile = codeAndFile.substring(codeLengths, codeAndFile.length() - lastZero);
    		// 还原编码表
    		restoreCode(binaryCode, CodeLength);
    		// 将二进制文件转换为字节数组
    		byte[] byteArray = restoreFile(binaryFile);
    		// 写入文件
    		writeFile(file3, byteArray);
    	}
    
    	// 将文件转换为字节数组保存
    	private byte[] readFile(File file) {
    		byte[] bs = new byte[(int) file.length()];// 创建字节数组
    		BufferedInputStream bis = null;// 声明字节缓冲流
    		try {
    			bis = new BufferedInputStream(new FileInputStream(file));
    			bis.read(bs);// 将文件读取到字节数组中
    		} catch (FileNotFoundException e) {
    			e.printStackTrace();
    		} catch (IOException e) {
    			e.printStackTrace();
    		} finally {
    			try {
    				if (bis != null)
    					bis.close();// 关闭输入流
    			} catch (IOException e) {
    				e.printStackTrace();
    			}
    		}
    		return bs;
    	}
    
    	//数据处理(转为二进制)
    	private String processData(byte [] bs) {
    		//将数据转换为二进制
    		String codeAndFile =new BigInteger(1, bs).toString(2);
    		//判断首位是否需要补0
    		if(bs[0]>0) {
    			//转为二进制,根据位数得到补0数
    			int firstZero=8-Integer.toBinaryString(bs[0]).length();
    			for(int i=0;i<firstZero;i++) {
    				codeAndFile="0" + codeAndFile;
    			}
    		}
    		return codeAndFile;
    	}
    
    	
    	// 获取各字节编码长度并返回哈夫曼编码总长度
    	private int getCodeLength(byte[] bs) {
    		int codeLengths = 0;
    		for (int i = 0; i < LEN; i++) {
    			if (bs[i] != 0) {
    				codeLengths += bs[i];// 统计哈夫曼编码总长度
    			}
    		}
    		return codeLengths;
    	}
    
    	// 还原编码
    	private void restoreCode(String binaryCode, byte[] CodeLength) {
    		for (int i = 0; i < LEN; i++) {
    			charCode[i] = binaryCode.substring(0, CodeLength[i]);// 存储该编码
    			binaryCode = binaryCode.substring(CodeLength[i]);// 更新编码文件
    			if (CodeLength[i] != 0) {
    				System.out.println("(" + i + "," + (char) i + "," + charCode[i] + "," + CodeLength[i] + ")");
    			}
    		}
    	}
    
    	// 将二进制文件转换为字符串
    	private byte[] restoreFile(String binaryFile) {
    		ArrayList<Byte> byteList = new ArrayList<>();// 创建字节队列保存读取字节
    		for (int i = 0; i < binaryFile.length(); i++) {
    			String charcode = binaryFile.substring(0, i + 1);
    			for (int j = 0; j < LEN; j++) {
    				if (charcode.equals(charCode[j])) {
    					byteList.add(new Integer(j).byteValue());
    					// 更新参数
    					binaryFile = binaryFile.substring(i + 1);
    					i = 0;
    					break;
    				}
    			}
    		}
    		// 将字节队列数据转移至数组中
    		byte[] byteArray = new byte[byteList.size()];
    		for (int i = 0, len = byteList.size(); i < len; i++) {
    			byteArray[i] = byteList.get(i);
    		}
    		return byteArray;
    	}
    
    	// 写入文件
    	private void writeFile(File file3, byte[] byteArray) {
    		BufferedOutputStream bos = null;
    		try {
    			bos = new BufferedOutputStream(new FileOutputStream(file3));
    			bos.write(byteArray);
    			bos.flush();
    		} catch (FileNotFoundException e) {
    			e.printStackTrace();
    		} catch (IOException e) {
    			e.printStackTrace();
    		} finally {
    			if (bos != null) {
    				try {
    					bos.close();
    				} catch (IOException e) {
    					e.printStackTrace();
    				}
    			}
    		}
    
    	}
    }
    

    五、测试类

    通过压缩文件与解压缩文件内容对比测试压缩是否成功:

    package com.liao.Huffman0830v1;
    
    import java.io.BufferedInputStream;
    import java.io.File;
    import java.io.FileInputStream;
    import java.io.IOException;
    import java.util.Arrays;
    
    public class Test {
    
    	public static void main(String[] args) throws IOException {
    		File file1 = new File("file\\001.txt");
    		File file2 = new File("file\\解压文件.txt");
    		File file3 = new File("file\\压缩文件.txt");
    		BufferedInputStream bis1 = new BufferedInputStream(new FileInputStream(file1));
    		BufferedInputStream bis2 = new BufferedInputStream(new FileInputStream(file2));
    		byte[] bs1 = new byte[(int) file1.length()];
    		byte[] bs2 = new byte[(int) file2.length()];
    		bis1.read(bs1);
    		bis2.read(bs2);
    		bis1.close();
    		bis2.close();
    		System.out.println(Arrays.equals(bs1, bs2) );
    		System.out.println("原文件大小:" + file1.length() / 1000 + "kb" + "----" + "压缩文件大小:"
    				+ file3.length() / 1000 + "kb");
    	}
    }
    

    测试结果:

    根据测试结果,可以看出文件压缩成功,压缩率约为57% 。

    六、注意事项

    1、本文只适用于英文文本压缩,对于中文文本压缩,下篇会介绍;

    2、本文基本上都是用一个字符串或字节数组保存整篇文档,然后再进行读写操作(获得更高效的读写速率),对于较大的文件(超过100Mb)可考虑将文件分成若干段再进行相关操作;

    3、为进一步提高压缩与解压缩效率,可考虑使用多线程,但须注意数据同步的问题。

    展开全文
  • 一、 哈夫曼编码开关、 二、 哈夫曼编码原理、 三、 libjpeg-turbo 函数库、 四、 libjpeg-turbo 函数库下载



    【Android 内存优化】图片文件压缩 ( Android 原生 API 提供的图片压缩功能能 | 图片质量压缩 | 图片尺寸压缩 ) 简要介绍了 图片文件压缩格式 , 以及 Android 提供的图片质量 , 尺寸压缩原生 API ;


    【Android 内存优化】Android 原生 API 图片压缩代码示例 ( PNG 格式压缩 | JPEG 格式压缩 | WEBP 格式压缩 | 动态权限申请 | Android10 存储策略 ) 主要使用了上述 Android 原生 API 压缩图片功能进行图片压缩 ;


    【Android 内存优化】Android 原生 API 图片压缩原理 ( 图片质量压缩方法 | 查找 Java 源码中的 native 方法对应的 C++ 源码 ) 中主要查找 Bitmap.java 对应的 Native 层的 C++ 类 Bitmap.cpp 源码文件 , 并分析了其动态注册 Native 方法的过程 ;


    【Android 内存优化】Android 原生 API 图片压缩原理 ( Bitmap_compress 方法解析 | Skia 二维图形库 | libjpeg 函数库 | libpng 函数库 ) 博客中分析了 Bitmap.cpp 中的 Bitmap_compress 方法 ;






    一、 哈夫曼编码开关



    上一篇博客 【Android 内存优化】Android 原生 API 图片压缩原理 ( Bitmap_compress 方法解析 | Skia 二维图形库 | libjpeg 函数库 | libpng 函数库 ) 分析到了 实际的图片压缩方法是由 Skia 图形库执行的 , Skia 图形库根据不同的压缩格式 , 选择不同的函数库进行压缩 , 如果压缩格式是 JPEG 格式 , 那么使用 libjpeg 库进行图片压缩 , 如果压缩格式是 PNG 库 , 那么使用 libpng 库进行压缩 ;


    1. 哈夫曼编码 : 在 libjpeg 中提供了图片哈夫曼编码功能 , 该功能非常消耗 CPU 性能 , 因此早期的 Android 版本禁用了该功能 , 在 7.0 之后的版本 , 此时 Android 设备上的 CPU 性能很高 , 这时才将哈夫曼编码功能打开 ; ( SkImageDecoder_libjpeg.cpp 代码参考 )


    2. 打开哈夫曼编码 : 将 jpeg_compress_struct 结构体的 optimize_coding 成员设置成 TRUE ; 作用是 通知 libjpeg-turbo 为图像计算最佳的哈夫曼编码表 , 该操作可以 提高图片压缩比例 , 代价是编码速度较慢 ;


    3. 源码参考 :

    SkImageDecoder_libjpeg.cppSkJPEGImageEncoder 类 ( SkImageEncoder 对应的 JPEG 格式图片压缩实现类 ) 中的 onEncode 方法 , 在 7.0 以后的版本 , 打开图片压缩哈夫曼编码功能 ;

    // 该类是 SkImageEncoder 的子类 , 在 Bitmap.cpp 中使用的就是
    class SkJPEGImageEncoder : public SkImageEncoder {
    protected:
        virtual bool onEncode(SkWStream* stream, const SkBitmap& bm, int quality) {
    		// ... 
    		jpeg_compress_struct    cinfo;
    		// ... 
            // 打开哈夫曼编码 
            // 通知 libjpeg-turbo 为图像计算最佳的哈夫曼编码表
            // 该功能可以提高压缩比例 , 代价是编码速度较慢
            cinfo.optimize_coding = TRUE;
            // ... 
            return true;
        }
    };
    
    

    源码位置 7.0.0/external/skia/src/images/SkImageDecoder_libjpeg.cpp ( 7.0.0 以后的源码才添加了上述功能 )





    二、 哈夫曼编码原理



    在 libjpeg 编码中 , 如果没有开启哈夫曼编码 , 采用的是定长的编码方式 , 如果打开了哈夫曼编码 , 采用的就是变长哈夫曼编码 , 可以大幅度压缩数据大小 ;


    简介 : 哈夫曼编码是字符编码 , 适用于数据文件压缩场景 , 能大幅度压缩文件大小 ;


    哈夫曼编码原理 : 每个数据的编码长度可变 , 文件中出现较多的字符使用短编码 , 出现较少的字符使用长编码 , 另外额外维护一张哈夫曼编码表 , 用于维护字符与编码的对应关系 , 总体的文件大小会降低 20% 至 90% ;





    三、 libjpeg-turbo 函数库



    使用哈夫曼编码进行图片压缩 , 能最大幅度压缩图片大小 , 但是 Android 原生编码中只有 7.0 以后的系统才打开了哈夫曼编码功能 , 目前的主流应用都要向下兼容到 android-17 平台版本 , 对应的系统版本是 Android 4.2 Jelly Bean , 这里就需要引入第三方库 libjpeg-turbo 函数库 , 进行哈夫曼编码图片压缩 , 该函数库是由 C 语言开发 , 需要在 Ubuntu 中进行交叉编译成 ARM 架构的函数库 ( 动态库 / 静态库 ) , 然后导入到 Android Studio 中使用 ;


    Android 源码中有 libjpeg-turbo 库 , 但是Java 框架中提供的 Bitmap.java 只能调用 Bitmap.cpp 中的代码 , Bitmap.cpp 中通过 Skia 2D 图形库调用 libjpeg 库 , 在该 C++ 代码中是固定的 , 开发者无法修改框架层的源码 , 因此该函数库无法被开发者调用到 ;


    NDK 交叉编译开发参考 : Android NDK 开发 专栏





    四、 libjpeg-turbo 函数库下载



    1. libjpeg-turbo 相关资源链接 :


    ① libjpeg-turbo 官方网站 : https://libjpeg-turbo.org/

    ② GitHub 地址 : libjpeg-turbo/libjpeg-turbo

    ③ libjpeg-turbo 文档 : 文档地址



    2. 下载发布版本 :


    在 Android 工程中使用该函数库 , 尽量下载发布的稳定版本 , 最好不要直接下载开发中的 DEBUG 版本 , 可能存在 BUG ;

    如下图 , 找到 release 发布版本界面 , 下载最新的发布版本 ; 或者直接点击 libjpeg-turbo/libjpeg-turbo 项目的 Release 发布版本地址 进入该界面 ;

    在这里插入图片描述


    进入 Release 界面后 , 查看到目前最新的发布版本是 2.0.5 版本 , 直接下载该源码 ; 之后需要到 Ubuntu 中进行交叉编译 ;

    在这里插入图片描述


    下载这个 Source code (tar.gz) 源码 , 到 Ubuntu 中进行交叉编译 ; ( 也可以直接点击上述连接下载 )

    在这里插入图片描述

    展开全文
  • 哈夫曼压缩

    2014-09-26 20:47:07
    以前也学习过哈夫曼的算法结构,但是没有自己去写代码实现,这次再学习了一遍,更加深刻理解哈夫曼压缩原理,如何真正实现文件的压缩节省内存资源。下面梳理下我的代码和分析逻辑。 第一步是打开文件,读取文件...
  • java实现哈夫曼压缩与解压缩

    千次阅读 2019-09-30 10:30:03
    哈夫曼压缩与解压缩(java版) 一哈夫曼树以及文件压缩原理: 1.哈夫曼树 : 2.如何利用haffman编码实现文件压缩: 二主要技术点: 三实现过程: 四运行展示: 哈夫曼压缩与解压缩(java版) 一哈夫曼树以及...
  • 哈夫曼压缩软件

    2018-05-03 23:54:19
    利用哈夫曼编码的原理,编写一个压缩软件。可以压缩基本的文件,如doc、docx、excel、ppt、pptx、pdf、txt等文档,也可以压缩png、gif、jpg、mp3、mov、mp4等图片、声音、视频等文件。
  • 哈夫曼树(HuffManTree)是用来压缩数据的一种数据结构,它适合压缩数据重复率较高的情况。 文本A:123456789,这串文本重复率为0,因为每个字符都是唯一的,没有重复率而言; 文本B:111222334,这串文本重复率明显...
  • 哈夫曼压缩与解压缩(c语言版)

    千次阅读 多人点赞 2019-09-29 19:18:13
    学过数据结构的同学,应该都听过哈夫曼树,和哈夫曼压缩算法,今天小编向大家讲解哈夫曼压缩与压缩的过程以及代码也算是记录一下自己所学所做的东西。 哈夫曼压缩,其实效率不是很高,一般情况下压缩率1...
  • 利用mfc写的一个压缩软件,利用哈夫曼原理,可以对文件进行压缩和解压缩(软件支持txt和doc,可以自行更改)。运用了移位运算,有进度条和动态文字。
  • 一、哈夫曼压缩原理 我们知道计算机中的文件采用二进制编码,为了使文件尽可能的缩短(压缩),可以对文件中每个字节出现的次数进行统计,设法让出现次数多的字节的二进制码短些,而让那些很少出现的字节的二进制码长...
  • 摘要:图像压缩技术是目前计算机应用领域的一项热门技术.随着计算机技术,现代通信技术,网络技术和信息处理技术的迅速发展,图像作为一种重要的信息载体已经成为应用最广泛的信息表现形式之一.但是由于未经处理的图像...
  • 哈夫曼原理、画法和具体例子

    千次阅读 2020-04-08 21:03:34
    1.哈夫曼压缩原理 当各种指令出现的频度不均等时,对出现频度最高的指令用最短的位数表示,出现频度较低的则用较长的位数表示,从而使指令的平均长度缩短。 构造哈夫曼树核心思想:最小概率合并。 2.构造哈夫曼树...
  • 哈夫曼编码原理

    2021-02-24 00:15:59
    哈夫曼编码原理 参考: 百度百科 哈夫曼(huffman)树和哈夫曼编码 关于哈夫曼树编码 1. 简介 定义 哈夫曼编码(Huffman Coding),又称霍夫曼编码,是Huffman于1952年提出的一种编码方式,是一种可变字长编码...
  •  学到哈夫曼压缩的时候首先就得了解哈夫曼树,我想说,对于数据结构挂科的人来说,额,这是一个沉重的话题。不过我还真感谢老师把我的数据结构挂了,因为我那一学期根本没听课,考试时什么都不会,而后来为了补考...
  • 哈夫曼压缩与解压

    2017-12-09 21:24:01
    压缩过程(不对哈夫曼编码原理进行详细解释): 1:读取文件内容到StringBuffer中,并使用hashmap统计每个字符出现的频率,按字符出现的频率升序排序(并保存在文件,备解压使用)。 2:对排序结束的字符频率建立...
  • 1、哈夫曼树 1.1哈夫曼树基本介绍 给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度(wpl) 达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree) 路径:在一棵树中,从一个结点往...
  • 哈夫曼压缩/解压缩(控制台,C++)

    千次阅读 2016-11-20 16:53:50
    即是如此,在初步了解哈夫曼原理之后,我只是隐隐约约的了解它的原理,在完成它的过程之中,依旧遇到了许多的问题,但是一切都已经成功的克服,下面我会简单的介绍哈夫曼编码的压缩和解压缩原理。Ⅰ.哈夫曼原理 ...
  • 精讲哈夫曼压缩算法

    千次阅读 2016-01-13 09:58:35
    哈夫曼压缩算法编码是无损压缩当中最好的方法。它使用预先二进制描述来替换每个符号,长度由特殊符号出现的...哈夫曼压缩算法之原理 我不打算探究哈夫曼编码的所有实际的细节,但基本的原理是为每个符号找到新的二
  •  在写代码之前,你要清楚的知道哈夫曼压缩是要分很多步的,为了你能在写代码时能很好地知道接下来要做什么,现在这一步是为了什么,所以最好提前将哈夫曼压缩的步骤罗列清楚。    哈夫曼压...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,400
精华内容 1,760
关键字:

哈夫曼压缩原理