`
lfp001
  • 浏览: 100703 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

（九）用JAVA编写MP3解码器——哈夫曼解码

Java数据结构HTCJVM算法 
阅读更多

解码一帧Layer3第3步：哈夫曼解码 -- huffmanDecoder方法

 

　　1.哈夫曼码表　共有33张码表，从ISO/IEC 11172-3复制一张码表出来，看看码表的庐山真面目，下面说到的哈夫曼树的构造及解码过程都以这一张表为例。码表如下所示：

Huffman code table 6
x y hlen hcod No.
0 0 3 111 0
0 1 3 011 1
0 2 5 00101 2
0 3 7 0000001 3
1 0 3 110 4
1 1 2 10 5
1 2 4 0011 6
1 3 5 00010 7
2 0 4 0101 8
2 1 4 0100 9
2 2 5 00100 10
2 3 6 000001 11
3 0 6 000011 12
3 1 5 00011 13
3 2 6 000010 14
3 3 7 0000000 15

　　码表的每一行由4个元素x、y、hlen、hcod组成，其最后一列是为了后文描述问题方便，我加上去的。解码大值区，一个码字(hcod)解码得到x、y两个值，hlen是码字的长度。33张码表中这几个值的取值范围是：x=0..15，y=0..15，hlen=0..19。其实33张码表只有象“Huffman code table 6”这样的表15张，码表有“共用”的情况，但是“共用”码表的linbits不同，看一看HuffmanBits的构造方法就明白这一点了。

 

　　2.哈夫曼树　哈夫曼解码用位流索引查表法，无论你采用何种数据结构存储码表，码表在逻辑是仍然是树形结构。

　　(1).2叉树　可以构造一棵2叉树装入这张码表，从位流中读入一位，根据是0还是1确定指向左子树还是右子树，直至到达叶结点，叶结点保存x、y，这样就可以由位流解得一个码字的2个码值的x和y了。

　　(2).N叉树　采用2叉树这种数据结构一次只能从位流处理1位，效率比较低。如果一次处理位流中的n位，采用N(N=2^n)叉树这种数据结构。以一次处理2位的4叉树为例，上面的码表“Huffman code table 6”构造出的4叉树如下：

4叉树Huffman code table 6

  • 图中每一个２行４列的表格表示４叉树的的一个结点；
  • 每个结点的第一行中的数字0..15表示码表“Huffman code table 6”中的序号，例如15表示NO.15这一行，存储4叉树的时候，编号0..15的域(图中的1格)存储码表的x、y、hlen，根据其取值范围，存储x和y各需4比特，存储hlen需5比特，所以这3个值可以存储在一个short类型的整数内；
  • 每个结点第1行的p1..p7表示该结点不是叶结点，该结点的这个域存储的是指向下一个结点的“指针”，JAVA没有指针类型，这个4叉树采用数组来存储，用p1..p7存储数组下标，这个下标值同样用 一个 short类型的整数值表示 ；
  • 存储4叉树用short类型的数组，其数组元素既有“指针”也有叶结点中某个域的值，用正、负号来区分它们。
  • 每个结点第2行的00、01、10、11表示一个结点内“子树”的编号。2叉树用左子树、右子树描述其子孙；4叉树用00子树、01子树...去描述。
  • 如果hlen为奇数，需要在末尾分别补上0和1凑成偶数。例如No.4这一行，hlen=3，hcod=110，要补成1100和1101，这两个二进制串都表示No.4这一行。这就是说，采用N叉树会使存储表冗余，n越大冗余度越大。
  • 4叉树示意图举例：No.3这一行hcod=0000001，按长度2将hcod分为00、00、00、10(或11)共4部分，分别对应图中4个结点的p1、p4、p7、3这4个域。No.3这一行的hlen=7，为奇数，同样要补成偶数，所以图中有一个结点的两个域都是“3”。
  • 遍历如图所示的4叉将结点的各个域存储到一个short类型的数组内，就存储好这张码表了。可以用任意一种方式遍历，先根次序、后根次序、层次遍历都可以。上图“Huffman code table 6”的4叉树存储在数组中为：
private final static short htbv6[] = {	//32
	-4, -24, 529, -28,  -8, -16, -20,1042, -12,1571,1586,1584,1843,1843,1795,1795,
	1299,1299,1329,1329,1314,1314,1282,1282,1057,1056, 769, 769, 784, 784, 768, 768};

htbv6被初始化到解码用的码表htBV[6]，见下文给出的源代码 HuffmanBits.java的第52行，这一行中的0表示该码表的linbits=0。

 

　　3.哈夫曼解码　 下文给出的源代码 HuffmanBits.java的第135行是选择码表，假设当前选中的是 htBV[6]，即htCur= htBV[6]，htCur.table=htbv6：

  • 136行取得linbits，对htCur而言linbits=0；
  • 138行刷新intMask，从位流中读入32位存储在intMask中，intMask的高几位为某一hcod，假如intMask=00010xxx　xxxxxxxx 　xxxxxxxx 　xxxxxxxx ，这里的x可能为0，也可能为1；
  • 139行用iTmp暂存intMask的值；
  • 140行iTmp>>>30表示取iTmp的高2位(00)，y=htbv6[0]=-4， y<0表示示该值是一个“指针”，其绝对值表示在htbv6[]中的下标 ；
  • 141行，y<0进入while循环，这个while循环就是查表的过程。
  • 第1次循环：142行iTmp <<= 2表示iTmp最高2位被移去，iTmp变为010xxxxx　xxxxxxxx　xxxxxxxx　xxxxxxxx；143行iTmp >>> 30表示取iTmp最高2位(01)，此时y=htbv6[1-(-4)]=htbv[5]=-16，y<0继续执行循环；
  • 第2次循环：142行iTmp 最高2位被移去，iTmp变为0xxxxxxx　xxxxxxxx　xxxxxxxx　xxxxxxxx；143行 取iTmp最高2位，可能为00，也可能为01：
    • 假如为00，y=htbv6[0-(-16)]=htbv[16]=1299，y>0结束循环；
    • 假如为01，y=htbv6[1-(-16)]=htbv[17]=1299，y>0结束循环；
  • 145行y>>8将y的16..23位被移到低字节，这一字节存储的是hlen，x=1299>>8=5；
  • 146行intBitNum表示intMask剩余的比特数，本次解码用去5位，执行intBitNum-=5，表示要从intMask取走5位;
  • 147行，将intMask的最高5位移出；
  • y的低字节存储的是码表中的x和y，各4位；149行(y >> 4) & 0xf表示取y最低字节的高4位，所以x=(1299>>4) & 0xf=1;
  • 150行 表示取y最低字节的低4位，所以y=1299 & 0xf=3;
  • 此时已经解得码表中的No.7这一行：x=1，y=3，用去5比特；
  • 152行是对x进一步处理。如果当前选择的某一码表解得的x=15并且码表的linbits>0，需要从位流中读入linbits得到一个整数值与x相加；
  • 159行intMask<0意思是intMask的最高位为1，这一位表示x的符号位，若为1表示解得的x是一负数，反之表示解得的x为正数；
  • 160行将解得的x保存到intHuffValue[]；
  • 168--182行对y进一步处理，同对x进一步处理的过程一样；

 

　　主信息的第二部分内容是以哈夫曼编码的主数据（main_data）。MP3编码器在将PCM编码过程中先是用有损压缩使数据长度大大缩短，然后用哈夫曼编码这种无损压缩方式进一步减小数据流长度。每个粒度组内的频谱值使用不同的哈夫曼码表编码，全频率段从0到奈奎斯特频率(Nyquist frequency，等于采样率的二分之一)被划分为几个按不同码表编码的区段，区段是根据最大量化值来划分的。对高频率低幅值的信号不编码，即被压缩掉了。为了提高编码过程中哈夫曼编码效率，主数据被划分为三部分：大值区、小值区、零值区。示意图如下：

Huffman Bits

大值区 一个码字(hcod)解码得到两个值，码表的成员变量linbits的值为0..13，如果linbits不为0并且x(或y)=15，还需要从位流中读入linbits位得到一个整数值与x(或y)相加，可以计算出解码大值区得到的最大值(绝对值)为15+(2^13-1)=8206。解码大值区最多可能用到三张不同的码表。怎么知道当前的码流该用哪一张码表呢？GRInfo内定义了两个成员变量：region1Start和region2Start，它表示一张码表解码得到的值的个数，解得指定个数的值之后更换另一张码表。该更换到哪一张码表呢？解码帧边信息时已经初始化了GRInfo的成员变量table_select，当前可能用到的码表(最多3张)编号就存储在其中。

　　 region1Start和region2Start 这两个变量在 Layer3的huffmanDecoder方法内被初始化，根据MPEG的版本（1.0/2.0/2.5）和“块”的类型初始化为不同的值。不同的块，子带的宽度不同。块和子带这些概念在后文再作交待。

　　供解码大值区使用的共有31张码表，其中第0张表hlen=0（其实不会被使用吧），第4、14码表不用。大值区中的一个码字（hcod）解得两个值，由帧边信息结构中的big_values可以计算出解码出大值区得到的值的个数 。

 

小值区 又称为count1区 ，解码得到的值为0，1或-1，整个小值区解码只用一张码表。供解码小值区使用的共有两张码表。小值区中的一个码字解得4个值。

 

零值区 未编码，所以不用解码，直接置为缺省值0。

 

位流中一帧主数据的末尾可能填充了几位而使之凑足一个字节，解码时对填充位作舍弃处理。调试程序时发现有填充位超过一字节的情况。

 

class Layer3内的huffmanDecoder方法源码如下：

	//3.
	//>>>>HUFFMAN BITS=========================================================
	/*
	 * nozero_index[]: 调用objHuffBits.decode()方法赋值;在Requantizer()方法内被修正;
	 * 在hybird方法内使用.
	 */
	private static int[] rzero_index = new int[2];
	private static int[] is;	//[32 * 18 + 4];
	private static HuffmanBits objHuffBits;

	private void huffmanDecoder(final int ch, final int gr) {
		GRInfo s = objSI.ch[ch].gr[gr];
		int r1, r2;

		if (s.window_switching_flag != 0) {
			int v = objHeader.getVersion();
			if(v == Header.MPEG1 || (v == Header.MPEG2 && s.block_type == 2)){
				s.region1Start = 36;
				s.region2Start = 576;
			} else {
				if(v == Header.MPEG25) {
					if(s.block_type == 2 && s.mixed_block_flag == 0)
						s.region1Start = intSfbIdxLong[6];
					else
						s.region1Start = intSfbIdxLong[8];
					s.region2Start = 576;
				} else {
					s.region1Start = 54;
					s.region2Start = 576;
				}
			}
		} else {
			r1 = s.region0_count + 1;
			r2 = r1 + s.region1_count + 1;
			if (r2 > intSfbIdxLong.length - 1) {
				r2 = intSfbIdxLong.length - 1;
			}
			s.region1Start = intSfbIdxLong[r1];
			s.region2Start = intSfbIdxLong[r2];
		}

		rzero_index[ch] = objHuffBits.decode(ch, s, is);  // 哈夫曼解码
	}
	//<<<<HUFFMAN BITS=========================================================

 

实例化class HuffmanBits类型变量objHuffBits，用语句objHuffBits.decode()调用HuffmanBits的decode方法就完成了解码一个粒度组中的一个声道的哈夫曼解码。解码输出的结果暂存到is[]供下一步使用。

 

进一步了解哈夫曼解码细节 哈夫曼解码是MP3的关键模块之一，对解码器的效率（速度和内存开销）有较大影响。怎样设计出高效的哈夫曼解码器，至今仍有不少人在探索。我的哈夫曼解码方法只是一个尝试。我的另一篇贴子《MP3解码之哈夫曼解码快速算法》也是讲哈夫曼解码的，网址：

论坛：http://www.iteye.com/topic/737963

博客：http://lfp001.iteye.com/blog/737850

 

 

HuffmanBits.java源码如下： 

/*
* HuffmanBits.java -- MPEG 1.0/2.0/2.5 Audio Layer I/II/III 哈夫曼解码
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/
package decoder;
import decoder.Layer3.GRInfo;

public final class HuffmanBits {
	private final class HuffTab {
		public int linbits;
		public short[] table;
		public HuffTab(int l, short[] t) {
			this.linbits = l;
			this.table = t;
		}
	}

	/*
	 * intMask: 暂存位流缓冲区不超过32比特数据,位流2级缓冲
	 * intBitNum: intMask剩余的比特数
	 * intPart2Remain: 哈夫曼编码的主数据剩余的比特数
	 * intRegion[]: 大值区某一码表解码主数据的区域
	 */
	private int intBitNum, intMask, intPart2Remain;
	private static final int[] intRegion = new int[3];

	private BitStream bsMainData;
	private static final HuffTab[] htBV = new HuffTab[32];
	private static final HuffTab[] htCount1 = new HuffTab[2];

	public HuffmanBits(BitStream objBS) {
		this.bsMainData = objBS;

		htBV[0] = new HuffTab(0, htbv0);	//hlen=0
		htBV[1] = new HuffTab(0, htbv1);
		htBV[2] = new HuffTab(0, htbv2);
		htBV[3] = new HuffTab(0, htbv3);
		htBV[4] = new HuffTab(0, htbv0);	//not used
		htBV[5] = new HuffTab(0, htbv5);
		htBV[6] = new HuffTab(0, htbv6);
		htBV[7] = new HuffTab(0, htbv7);
		htBV[8] = new HuffTab(0, htbv8);
		htBV[9] = new HuffTab(0, htbv9);
		htBV[10] = new HuffTab(0, htbv10);
		htBV[11] = new HuffTab(0, htbv11);
		htBV[12] = new HuffTab(0, htbv12);
		htBV[13] = new HuffTab(0, htbv13);
		htBV[14] = new HuffTab(0, htbv0);	//not used
		htBV[15] = new HuffTab(0, htbv15);
		htBV[16] = new HuffTab(1, htbv16);
		htBV[17] = new HuffTab(2, htbv16);
		htBV[18] = new HuffTab(3, htbv16);
		htBV[19] = new HuffTab(4, htbv16);
		htBV[20] = new HuffTab(6, htbv16);
		htBV[21] = new HuffTab(8, htbv16);
		htBV[22] = new HuffTab(10, htbv16);
		htBV[23] = new HuffTab(13, htbv16);
		htBV[24] = new HuffTab(4, htbv24);
		htBV[25] = new HuffTab(5, htbv24);
		htBV[26] = new HuffTab(6, htbv24);
		htBV[27] = new HuffTab(7, htbv24);
		htBV[28] = new HuffTab(8, htbv24);
		htBV[29] = new HuffTab(9, htbv24);
		htBV[30] = new HuffTab(11, htbv24);
		htBV[31] = new HuffTab(13, htbv24);

		htCount1[0] = new HuffTab(0, htc0);
		htCount1[1] = new HuffTab(0, htc1);
	}

	private void refreshMask() {
		while(intBitNum < 24) {
		    intMask |= bsMainData.get1Byte() << (24-intBitNum);
		    intBitNum += 8;
		    intPart2Remain -= 8;
		}
	}

	/*
	 * decode方法: 一个粒度组内的一个声道哈夫曼解码
	 *
	 * ch: 声道
	 * objGRI: 粒度组信息
	 * intHuffValue[]: 接收解码得到的576个值
	 * 返回值: 576减去rzone区长度.
	 */
	public int decode(final int ch, final GRInfo objGRI, int[] intHuffValue) {
		int i, x, y, iTmp, linbits, intIndex=0;
		HuffTab htCur;

		/*
		 * 1. 初始化4个成员变量intBitNum,intMask,intPart2Remain,intRegion[]
		 */
		intBitNum = intMask = 0;
		intPart2Remain = objGRI.part2_3_length - objGRI.part2_bits;
		x = objGRI.region1Start;		// region1
		y = objGRI.region2Start;		// region2
		i = objGRI.big_values << 1;		// bv
		if(i > 574)
			i = 574;					// 错误的big_value置为0 ?
		if(x < i) {
			intRegion[0] = x;
			if(y < i) {
				intRegion[1] = y;
				intRegion[2] = i;
			} else
				intRegion[1] = intRegion[2] = i;
		} else
			intRegion[0] = intRegion[1] = intRegion[2] = i;

		/*
		 * 2. 使位流缓冲区bsMainData字节对齐
		 */
		intBitNum = 8 - bsMainData.getBitPos();
		intMask = bsMainData.getBits9(intBitNum);
		intMask <<= 32 - intBitNum;
		intPart2Remain -= intBitNum;

		/*
		 * 3. 解码大值区
		 */
		for (i = 0; i < 3; i++) {
			htCur = htBV[objGRI.table_select[i]];
			linbits = htCur.linbits;
			while(intIndex < intRegion[i]) {
				refreshMask();
				iTmp = intMask;
				y = htCur.table[iTmp >>> 30];
				while (y < 0) {
					iTmp <<= 2;
					y = htCur.table[(iTmp >>> 30) - y];
				}
				x = y >> 8;				// hlen
				intBitNum -= x;
				intMask <<= x;

				x = (y >> 4) & 0xf;	// 解得两个值
				y &= 0xf;

				if (x != 0) {
					if(x == 15 && linbits != 0) {
						refreshMask();
						x += intMask >>> (32 - linbits);	// 循环右移
						intBitNum -= linbits;
						intMask <<= linbits;
					}
					if(intMask < 0)
						intHuffValue[intIndex++] = -x;
					else
						intHuffValue[intIndex++] = x;
					intBitNum--;
					intMask <<= 1;
				} else
					intHuffValue[intIndex++] = 0;

				if (y != 0) {
					if (y == 15 && linbits != 0) {
						refreshMask();
						y += intMask >>> (32 - linbits);
						intBitNum -= linbits;
						intMask <<= linbits;
					}
					if(intMask < 0)
						intHuffValue[intIndex++] = -y;
					else
						intHuffValue[intIndex++] = y;
					intBitNum--;
					intMask <<= 1;
				} else
					intHuffValue[intIndex++] = 0;
			}
		}

		/*
		 * 4. 解码count1区
		 */
		htCur = htCount1[objGRI.count1table_select];
		while(intIndex < 572) {
			refreshMask();
			iTmp = intMask;
			y = htCur.table[iTmp >>> 28];
			while (y < 0) {
				iTmp <<= 4;
				y = htCur.table[(iTmp >>> 28) - y];
			}
			x = y >> 8;		// hlen
			intBitNum -= x;
			intMask <<= x;

			if(intPart2Remain + intBitNum <= 0) {
				intBitNum -= intPart2Remain + intBitNum;
				break;
			}

			y <<= 28;
			for(i = 0; i < 4; i++) {	// 一个码字(hcod)解码得到4个值
				if(y < 0) {
					if(intMask < 0)
						intHuffValue[intIndex++] = -1;
					else
						intHuffValue[intIndex++] = 1;
					intBitNum--;
					intMask <<= 1;
				} else
					intHuffValue[intIndex++] = 0;
				y <<= 1;
			}
		}

		/*
		 * 5. rzone区直接置0,即intHuffValue[nozero_index..575]=0
		 */
		int nozero_index = intIndex;
		while(intIndex < 576)
			intHuffValue[intIndex++] = 0;

		/*
		 * 6. 丢弃位流缓冲区中的填充位.填充位不超过多少位?
		 */
		intPart2Remain += intBitNum;
		if(intBitNum > 0)
			bsMainData.backBits(intBitNum);		// intBitNum比特归还位流缓冲区
		if(intPart2Remain > 0) {
			while(intPart2Remain > 8) {
				bsMainData.getBits9(8);			// 不再是字节对齐的
				intPart2Remain -= 8;
			}
			if(intPart2Remain != 0)
				bsMainData.getBits9(intPart2Remain);
		}

		return nozero_index;
	}

	///////////////////////////////////////////////////////////////////////////
	// 码表
	// 码表较长，压缩后放在附件里的。打开附件htbv_htc.txt把代码COPY到这就OK啦~
}

 

JAVA没的“指针”类型，操作N叉树只能用JAVA的数组。尽管制作的码表存放在数组内，“逻辑上”仍然用N叉树存放的，这样去看待它，就很容易理解这N叉哈夫曼树。

 

上一篇：（八）用JAVA编写MP3解码器——解码增益因子

下一篇：（十）用JAVA编写MP3解码器——逆量化和重排序

 

【本程序下载地址】http://jmp123.sourceforge.net/

  • 大小: 4.5 KB
  • 大小: 8.2 KB
分享到：
| （八）用JAVA编写MP3解码器——解码增益因 ...
评论
3 楼 lfp001 2010-08-22  
sdh5724 写道
通常， 查表来说， 性能是差不多的。 Java最大的问题， 出在bit位的读取上， 我建议你使用long的移位来解决这个问题。 这样能让CPU最大程度的对齐数据操作。
最近我们在做jpeg解码， 感觉huffman解码速度还是很快的。 我看你的代码有点复杂啊。 建议你减少方法调用， 你可以测试下， Java的方法调用非常消耗性能。在C下面， 可以通过宏定义或者inline来解决问题， Java下显得非常无奈。 在做解码器上， 我建议是：
1. 数据的连续处理。
2. 减少方法使用
3. 避免浮点运算
4. 运算连续， 不做中间参数交换。
5. 避免小循环，避免重复循环

虽然， JVM能为我们调整以上建议， 不过， 我还是建议代码这么写比较好。

以解码大值区为例，第122--127行为查表的过程，一次处理位数多，循环次数就越少；135--165行是对解的ISO/IEC中给出的x，y进一步处理得到啥夫曼解码结果，这部分代码与码表的设计无关，都是相同的。加上解码小值区、丢弃填充位的处理，代码是比较长的。

MP3和JPEG的哈夫曼解码方法类似。
2 楼 sdh5724 2010-08-21  
通常， 查表来说， 性能是差不多的。 Java最大的问题， 出在bit位的读取上， 我建议你使用long的移位来解决这个问题。 这样能让CPU最大程度的对齐数据操作。
最近我们在做jpeg解码， 感觉huffman解码速度还是很快的。 我看你的代码有点复杂啊。 建议你减少方法调用， 你可以测试下， Java的方法调用非常消耗性能。在C下面， 可以通过宏定义或者inline来解决问题， Java下显得非常无奈。 在做解码器上， 我建议是：
1. 数据的连续处理。
2. 减少方法使用
3. 避免浮点运算
4. 运算连续， 不做中间参数交换。
5. 避免小循环，避免重复循环

虽然， JVM能为我们调整以上建议， 不过， 我还是建议代码这么写比较好。
1 楼 pujia12345 2010-08-21  
你够牛逼！！
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    数据结构课程设计——哈夫曼编/译码器

    在这个“数据结构课程设计——哈夫曼编/译码器”项目中，我们将深入学习哈夫曼编码的原理和实现。哈夫曼编码的过程主要包括以下几个步骤： 1. **统计字符频率**：首先，我们需要统计输入文本中每个字符出现的次数，...

    树的应用——哈夫曼编码

    树的应用——哈夫曼编码 二、 实验内容： 利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。 从...

    数据结构——哈夫曼编码

    它的核心思想是通过构建一个特殊的二叉树——哈夫曼树（Huffman Tree），来为数据的各个符号分配最短的编码，使得频率高的符号编码较短，频率低的符号编码较长，从而实现数据的平均码长最小化，达到压缩数据的目的。...

    课设——哈夫曼树的源代码

    6. 编码和解码功能：将原始数据用哈夫曼编码进行编码，并提供解码功能将编码后的数据还原。 在VS2005环境下编写，源代码可能采用了C++语言，利用了STL库，例如`std::vector`或`std::queue`来实现数据结构和算法。在...

    数据结构课程设计——哈夫曼树

    在实现过程中，你可能会使用到数据结构如队列（用于最小堆）、栈（辅助构建哈夫曼树）等，以及文件操作和编码解码的逻辑。此外，测试是必不可少的环节，你需要编写测试用例确保压缩和解压缩过程的正确性。 总之，...

    哈工大数据结构——哈夫曼编码

    哈工大的数据结构课程是计算机科学与技术领域的重要组成部分，其中哈夫曼编码是一项关键的压缩和解压缩技术...通过对这个压缩包的学习，你将能够深入理解哈夫曼编码的工作原理，并能够自己编写程序实现编码和解码过程。

    《数据结构》实验——哈夫曼编码

    哈夫曼编码是一种高效的数据压缩方法，源自于数据结构中的树形数据结构，主要用于无损数据压缩。...在实际编程中，可以通过编写程序来实现哈夫曼编码的构建、编码、解码功能，以加深理解并提高实践能力。

    数据结构课设——哈夫曼树

    下面将详细阐述哈夫曼树的概念、构建过程、应用及其在编码解码中的作用。 哈夫曼树是一种特殊的二叉树，它的每个叶子节点代表一个需要编码的字符，且字符的频率作为权重。树中任意两个叶子节点之间的路径不交叉，...

    c语言程序 数据结构课程设计模——哈夫曼编码译码器

    ### 哈夫曼编码译码器：C语言程序设计详解 #### 1. 哈夫曼编码原理概述 哈夫曼编码是一种基于字符出现频率的变长前缀编码方式，由David A. Huffman在1952年提出。其核心思想是在编码过程中为出现频率高的字符分配...

    mp3解码算法原理——具体解码算法

    MP3解码的过程涉及多个模块协同工作，主要包括同步及差错检查、主控模块、尺度因子解码、哈夫曼解码、逆量化、立体声解码、混淆缩减、IMDCT、频率反转以及合成多相滤波等关键步骤。 1. **同步及差错检查**：该模块...

    哈夫曼编码解码器 c++源代码

    在C++中实现哈夫曼编码解码器涉及到以下几个关键知识点： 1. **哈夫曼树**：哈夫曼树（Huffman Tree）也称为最优二叉树，是一种带权路径长度最短的二叉树。它的构建基于贪心算法，通过将频率最低的两个节点合并来...

    C++课程设计——哈夫曼树.txt

    设计内容： 欲发一封内容为AABBCAB ……(共长 100 字符,其中:A 、B 、C 、D 、E 、F分别有7 、9 、12 、22 、23、27个)的电报报文,实现哈夫曼编码。

    数据结构——哈夫曼树（自己编的）

    哈夫曼树 基本功能： （1） 从文件中读出一篇英文文章，包含字母和空格等字符。 （2） 统计各个字符出现的频度。 （3） 根据出现的频度，为每个出现的字符建立一个哈夫曼编码，并输出。 （4） 输入一个字符串，为其...

    java编写mp3播放器.doc

    《使用Java编写MP3播放器》是一份关于利用Java编程语言实现MP3音频解码的文档。MP3作为广泛使用的音频压缩格式，其解码技术是数字音频处理领域的重要组成部分。该文档旨在介绍如何利用Java编写一个MP3解码器，并提供...

    哈夫曼编码解码

    它通过构建一棵特殊的二叉树——哈夫曼树，来实现对原始数据的编码和解码。 哈夫曼编码的过程主要包括以下几个步骤： 1. **频率统计**：首先，统计输入数据中每个字符或符号出现的频率。这一步骤对于构建哈夫曼树...

    数据结构——哈夫曼编码 完整代码

    哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。...因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。

    树的应用——哈夫曼编码（C语言版）

    构建Huffman树，详细展示Huffman的初态和终态，通过Huffman树生成Huffman编码。

    最优二叉树——哈夫曼树.doc

    树结构的特点是：它的每一个结点都可以有不止一个直接后继，除根结点外的所有结点都有且只有一个直接前趋。

Magicbox
Global site tag (gtag.js) - Google Analytics