无损数据压缩实验报告

多媒体技术基础

实验报告

院系：自动化学院 班级：11102003 姓名：胡嘉懿 学号：1110200302

·实验名称：无损压缩编码实验

·实验内容：任选一种无损编码方式，通过C++编程实现。 ·实验要求：

1) 字符串的输入是手工输入的；

2) 2) 通过程序实现编码，最终在屏幕上显示编码结果，例如，如果选用huffman编码，则要显示字符串的编码以及平均码长；

3) 3) 每人交一份实验报告电子版，以学号作为文件夹的名称，其中包括源程序。

·算法思想

按输入字符Ascii码值递增的顺序生成Hash表，并进行权重统计； 将Hash表中元素生成为Huffman树叶子节点； 对于所有无父的节点进行搜索，将次小和最小的节点作为子节点创建父节点（规定最小的总是右子节点，并总是标记为1）；

直到只剩下一个没有父节点的根节点；

对huffman树进行编码,采用递归的方法进行扫描，同时计算码长； 最后将叶子节点数据写回Hash表；

用Hash表的编码数据对原数据进行编码；

统计各叶子节点的码长来进行平均码长的计算。

Hash数组为一个长为128（ASCii）的数组，每个元素存储对应字符出现的频率和编码 元素结构： 统计权重 对应编码 编码长度

Huffman数组是一个按照节点创建顺序构造的数组 元素结构：

对应Ascii码，对于父节点，定为-1 权重

父节点位置

所在子树标识（规定0为左子树，1为右子树） 节点编码（为了显示方便使用字符串） 编码长度

哈夫曼码的编码性能与其包含字符种类的多少有较大关系，对于最坏情况，即一个包含全部Ascii字符，每个字符只出现一次的文本，算法本身性能最低。

·源程序

#include #include #define fileLenth 5000 typedef struct{ int value; char code[512]; int codeLen; }hashElement;

typedef struct{ int ascNum; int value; int fPoint; int lFlag; char code[512]; int codeLen; }huffElement;

char sourceS[fileLenth]; hashElement hashArray[128]; huffElement huffTree[512]; int huffTreeNum=0; int huffTreeLeafNum=0; int wholeValue=0; int sumCodeLen=0; void initALL() { int i;

for(i=0;i<256;i++) {

hashArray[i].value=0; strcpy(hashArray[i].code,\); hashArray[i].codeLen=-1; }

for(i=0;i<512;i++) {

huffTree[i].ascNum=-1; huffTree[i].value=0; huffTree[i].fPoint=-1; huffTree[i].lFlag=-1; strcpy(huffTree[i].code,\); huffTree[i].codeLen=-1;

} }

int huffTreeEncode(int huffTreeP) { int FP;

if(huffTree[huffTreeP].fPoint==-1) {

huffTree[huffTreeP].codeLen=0; return huffTreeP; }

if(huffTree[huffTreeP].codeLen!=-1) return huffTreeP; else {

FP=huffTreeEncode(huffTree[huffTreeP].fPoint);

strcpy(huffTree[huffTreeP].code,huffTree[FP].code); } }

int main() { int i;

int rootFlag=0;

int Minium=-1,exMinium=-1;

int MiniumV=fileLenth+1,exMiniumV=fileLenth+1; cout<<\请输入任意字符串\<<'\\n'; cin.getline(sourceS,5000); initALL();

for (i=0;i

hashArray[sourceS[i]].value++; }

for (i=0;i<256;i++) {

if (hashArray[i].value!=0)

{

huffTree[huffTreeNum].ascNum=i;

huffTree[huffTreeNum].value=hashArray[i].value; huffTreeNum++;

if(huffTree[huffTreeP].lFlag==0) strcat(huffTree[huffTreeP].code,\); else if(huffTree[huffTreeP].lFlag==1) strcat(huffTree[huffTreeP].code,\); huffTree[huffTreeP].codeLen=huffTree[FP].codeLen+1;

return huffTreeP;

} }

huffTreeLeafNum=huffTreeNum; while(rootFlag==0) {

for(i=0;i

if(huffTree[i].fPoint==-1)

{

if(huffTree[i].value<=MiniumV) {

Minium=i;

MiniumV=huffTree[i].value; } } }

for(i=0;i

if(huffTree[i].fPoint==-1)

{

if(huffTree[i].value<=exMiniumV&&i!=Minium) {

exMinium=i;

exMiniumV=huffTree[i].value; } } }

if(exMinium!=Minium&&exMinium!=-1&&Minium!=-1) {

huffTree[huffTreeNum].value=huffTree[Minium].value+huffTree[exMinium].value; huffTree[Minium].fPoint=huffTreeNum;

huffTree[Minium].lFlag=1; huffTree[exMinium].lFlag=0; exMinium=-1;

huffTree[exMinium].fPoint=huffTreeNum; huffTreeNum++; Minium=-1;

exMiniumV=fileLenth+1; MiniumV=fileLenth+1; }

else rootFlag=1; }

wholeValue=huffTree[huffTreeNum-1].value;

if(exMinium!=-1||Minium!=huffTreeNum-1||wholeValue!=strlen(sourceS))