还剩18页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
实验报告课程名称交互式媒体原理开课学期专业软件工程年级班级学生姓名学号指导教师计算机与信息科学学院软件学院
46.huffmanCode[root-ch]=str;
47.
48.encoderoot-left,str+nOn,huffmanCode;
49.encoderoot-right,str+”1,huffmanCode;
50.
51.void decodeHNode*root,int index,string str
52.{
53.if root==nullptr{
54.return;
55.}
56.//found aleaf node
57.if!root-left!root-right
58.{
59.cout«root-ch;
60.return;
61.}
62.index++;
63.if str[index]==V
64.decoderoot-left,index,str;
65.else
66.decoderoot-right,index,str;
67.}
68.〃建立赫夫曼树,解码输入的字符串
69.void buildHuffmanTreestringtext
70.
71.unordered_mapchar,int freq;
72.for char ch:text{
73.freq[ch]++;
74.}
75.priority_queueHNode*,vectorHNode*,comp pq;
76.for autopair:freq{
77.pq.pushgetNodepair.first,pair.second,nullptr,nullptr;
78.
79.while pq.size!=
180.
90.HNode*left=pq.top;pq.popQ;
91.HNode*right=pq.topO;pq.popO;
92.
93.int sum=left-freq+right-freq;
94.pq.pushgetNode\0,sum,left,right;
95.
96.
97.HNode*root=pq.topO;
98.
99.//遍历赫夫曼树并存储编码到map里同时打印
100.unordered_mapchar,string huffmanCode;
101.encoderoot,,H,,huffmanCode;
102.
103.cout«Huffman Codesare:\nn«\n;
104.for autopair:huffmanCode{
105.cout«pair.first««pair.second«An,;
106.}
107.
108.cout«AnOriginal stringwas:\n«text«endl;
109.
110.〃打印
111.string str=”;
112.for char ch:text{
113.str+=huffmanCode[ch];
114.
1115.
116.cout«\nEncoded stringis:\n«str«endl;
117.
118.〃遍历赫夫曼树
119.〃解码
120.int index=-1;
121.cout«\nDecoded stringis:\n;
122.while indexintstr.size-2{
123.decoderoot,index,str;
124.}
125.}M.h
1.#pragma once
2.#includeiostream
3.#includestring
4.#includemapLZ
5.#includevector、
6.
7.using namespacestd;
8.
9.class LZW
10.{
11.public:
12.struct encodeinfo
13.
14.string P;
15.int index;};〃键值对
16.
17.LZW;
18.
19.vectorencodeinfo LZW_encodestring s,int encodenum;
20.string LZW_decodevectorencodeinfo code,int beginnum;
21.
22.map string,int diet;〃字典
23.map int,string revdict;〃解码时使用
24.〜LZW;
25.};McppLZ、
1.include LZW.h
2.using namespacestd;
3.
4.
5.LZW::LZW
6.
7.dict.clearQ;
8.revdict.clear;
9.for int i=0;i128;i++
10.
11.string s=nt;
12.s
[0]=chari;
13.dict[s]=i;
14.revdict[i]=chari;
15.}
16.}
17.
18.vectorLZW::encodeinfo LZW::LZW_encodestring s,int encodenum
19.
120.string P=n;
21.char C;
22.vectorencodeinfo EncodeResult;//存储编码之后的结果
23.for inti=0;is.length;i++
24.{
25.C=s[i];
26.string tempStr=P+C;
27.〃在字典里面寻找这个字符串
28.mapstring,int::iterator iter=dict.findtempStr;
29.if iter!=dict.end{〃找到了
30.P=tempStr;
31.}
32.else{〃没找到
33.encodeinfo a={P,dict[P]};
34.EncodeResuIt.push_backa;〃将P的对应的编码存放起来
35.〃建立起一个新的索引
36.encodenum++;
37.dict[tempStr]=encodenum;
38.P=C;
39.}
40.
41.encodeinfo a={P,dict[P]};
42.EncodeResult.push_backa;〃最终结尾处
43.〃这是编码过程的输出
44.cout«LZW编码输出的信息如下n«endl;
45.for inti=0;iEncodeResult.size;i++{
46.cout«EncodeResult[i].P««EncodeResult[i].index«endl;
47.}
48.return EncodeResult;
49.}
50.string LZW::LZW_decodevectorencodeinfo code,int beginnum{
51.string ret=〃最终译码的输出
52.string P=n;
53.char C;
54.int pW,cW;
55.〃第一步,初始化,读入第一个的符号cW,解码输出
56.cW=code
[0].index;
57.ret+=revdict[cW];〃解码输出
58.for inti=1;icode.size;i++{
59.pW=cW;
60.cW=code[i].index;
61.mapint,string:iterator iter=revdict.findcW;
62.if iter!=revdict.end{〃找至lj了
63.〃解码输出
64.ret+=iter-second;
65.P=revdict[pW];
66.C=revdict[cW]
[0];
67.string tempStr=P+C;
68.beginnum++;
69.revdict[beginnum]=tempStr;
70.}
71.else
72.
73.P=revdictfpW];
74..C=revdict[pW]
[0];
75.beginnum++;
76.string tempStr=P+C;
77.revdict[beginnumj=tempStr;
78.ret+=tempStr;
79.}
80.}
81.return ret;
82.}
83.LZW::〜LZW
84.
85.}Range.h
1.#pragma once
2.class range
3.
4.public:
5.range;
6.〜range;
7.double GetLow;
8.double GetHigh;
9.void SetLowdouble low;
10.void SetHighdouble high;
11.void SetDeltadouble delta;
12.private:
13.doublelow;
14.doublehigh;
15.double deltalevel;
16.1;Range.cpp
1.〃用于存储算术编码中的上下界
2.#include nrange.h
3.range::range
4.
5.low=
0.0;
6.high=
1.0;
7.deltalevel=
1.0;
8.
9.range::-range
10.{
11.low=0;
12.high=0;
13.deltalevel=0;
14.}
15.double range::GetLow
16.
17.return this-low;
18.
19.double range::GetHigh
20.{
21.return this-high;
22.}
128.void range::SetLowdouble low
129.
130.this-low=low;
131.}
132.void range::SetHighdouble high
133.
134.this-high=high;
135.}
136.void range::SetDeltadouble delta
137.
138.this-deltalevel=delta;
139.}Arithmetic.h
1.#pragma once
2.#include iostream
3.#include range.h
4.#include map
5.#include string
6.using namespacestd;
7.class Arithmetic
8.
9.public:
111.Arithmetic;
112.〜Arithmetic;
13.void RequireCodestring str;
14.double Encodestring str;
15.string Decodedouble value;j
17.int getLength;
18.private:
19.int length;
20.mapchar,rangemap;
21.};Arithmetic.cpp
1.#include Arithmetic.h
2.Arithmetic::Arithmetic
3.{
4.length=0;
5.}
6.Arithmetic::〜Arithmetic
7.
8.}
9.void Arithmetic::RequireCodestring str
10.
11.double lowlevel=
0.0;
12.double highlevel=
0.0;
13.double probability=
0.0;
14.for inti=0;istr.length;i++
15.
16.cout«Please input the probability«endl;
17.cin»probability;
18.lowlevel=highlevel;
19.highlevel=lowlevel+probability;
20.range r;
21.r.SetLowlowlevel;
22.r.SetHighhighlevel;
23.r.SetDeltaprobability;
24.map.insertstd::pairchar,rangestr[i],r;
25.}
26.}
27.double Arithmetic::Encodestring str
28.{
29.double LowRange=
0.0,HighRange=
1.0;
30.for string::iterator itr=str.beginQ;itr!=str.end;++itr
31.{
32.doubledelta=HighRange-LowRange;
33.HighRange=LowRange+delta*map[*itr].GetHigh;
34.LowRange=LowRange+delta*map[*itr].GetLow;
35.++length;
36.}
37.return LowRange;
38.}
39.string Arithmetic::Decodedoublevalue
40.{
41.double Lowlnterval=0;
42.double Highlnterval=0;
43.string symbol=
44.for autoitr=map.begin;itr!=map.end;++itr
45.{
46.if itr-second.GetLowvalueitr-second.GetHighvalue
55.
56.Lowlnterval=itr-second.GetLow;
57.Highlnterval=itr-second.GetHigh;
58.symbol+=itr-first;
59.break;
60.
61.
62.for inti=0;ilength-1;++i
63.
64./*decode code*/
65.double deltalnterval;
66.deltalnterval=Highlnterval-Lowlnterval;
67.value-=Lowlnterval;
68.value/=deltalnterval;
69.
70.for autoi=map.begin;i!=map.end;++i{
71.if i-second.GetLowvaluei-second.GetHighvalue{
72.Lowlnterval=i-second.GetLow;
73.Highlnterval=i-second.GetHigh;
74.symbol+=i-first;
75.break;
76.
77.
78.
79.
80.return symbol;
81.}Main.cpp
1.#include nchoice.h
2.using namespacestd;
3.int main
4.
5.Choice choice;
6.choice.input;
7.
四、实验结果(可给出截图等加以说明)WMicrosoftVisualStudio调记0空制台Please input a stringaaerwPlease chosse a mode
1.Run-Length Encodinig
2.Shannon-Fano Algorithm
3.Huffman encoding
4.LZW CompressionDecompression
5.Arithmetic Encoding1After compressa2elrlwlPlease input a stringaaerwPlease chossea mode:
1.Run-Length Encodinig
2.Shannon-Fano Algorithm
3.Huffman encoding
4.LZW Compression也Decompression
5.Arithmetic EncodingPlease input a stringabPlease chossea mode
1.Run-Length Encodinig
2.Shannon-Fano Algorithm
3.Huffman encoding
4.LZW CompressionDecompression
5.Arithmetic Encoding3Huffman Codesaxea0b1Original stringwas:abEncoded stringis01Decoded stringis aPlease input a string abcsdawPlease chossea mode:
1.Run-Length Encodinig
2.Shannon-Fano Algorithm
3.Huffman encoding
4.LZW CompressionDecompression
5.Arithmetic Encoding4LZ噬码输出的信息如下:a97b98c99s115d100a97w119解码输i出字符串abcsdawPlease inputastringasPlease chosseamode
1.Run-Length Encodinig
2.Shannon-Fano Algorithm
3.Huffman encoding
4.LZW Compression也Decompression Pleaseinputastring asaPleasechossemode
1.Run-Length Encodinig
2.Shannon-Fano Algorithm
3.Huffman encoding
4.LZW CompressionDecompression
5.Arithmetic EncodingPleaseinputthe probability
0.4Pleaseinputtheprobability
0.
60.16asaa Pleaseinputastring输入任意字符串,选择编码解码的方法实验项目名称实验四压缩算法实验时间年月日实验类型2020111□验证性设计性口综合性
一、实验目的/了解各种无损压缩算法的基本思想/掌握无损压缩算法的代码实现二实验要求/自选编程语言实现各种无损压缩算法
五、结果分析及总结(对实验的结果是否达到预期进行分析,总结实验的收获和存在的问题等)分析实验结果基本达到预期,其中赫夫曼编码和算术编码的结果正确但是输出有一定问题赫夫曼编码不会输出解码后的最后一位字符,算术编码会造成在解码的最后重复输出第一位字符收获
1.Run-Length Encoding基本思想为将重复且连续出现多次的字符使用(连续出现次数,某个字符)来描述缺点是如果文本重复较少,会白白浪费编码的资源却没有达到节省空间的效果
2.Shanno-Fano Encoding)对于给定的符号列表,指定相应的概率列表1)排序根据频率的符号列表,最常出现的符号在左边,最少出现的符号在右边2(个人认为类似二叉查找树))列表分为两部分,使得左边部分的总频率尽可能等于右边部分的总频率3)该列表左半边分配右半边分配40,1)对分好的两部分递归实现步骤直到每一个符号成为叶子结点53,4,
3.Huffman Encodinig类似于不同的是该方法是将概率最小的两个相加作为左右子Shanno-Fano Encoding,树,重复过程直到概率值最终等于
14.LZW compressionand decompression将出现过的字符串映射到记号上,这样可以用较短的编码表示长的字符串最开始会将所有字母用码存储在一个字典中,在这个基础上添加的新的映射即从ASCII256开始后添加的元素为扩展项例如编码ABABAB)遇到用表示,编码为1A,
9797.)遇到用表示,编码为2B,9898)发现了一个字串用表示,添加进字典中3AB,257)后面继续发现用表示4AB
2575.Arithmetic Encoding)假设有一段数据需要编码,统计其中所有的字符和出现的次数1)将区间[]不包括连续划分为多个子区间,每个子区间代表一个字符,20,11子区间大小正比与出现的概率所有子区间的和是[]不包括0,11)编码首先从初始区间开始[]不包括开始,设置30,11low=0,high=1)不断读入原始数据的字符,找到字符所在的区间[]4L,H()low=low+high-low*L()high=low+high-low*H最后得到的区间中的任一小数输出即为编码的数据存在问题面向对象编程和面向过程编程混用,代码不够规范
1.两个算法的解码输出结果有问题
2.实验目的和要求明确()A-E教实验内容与设计()A-E师实验结果()A-E评结果分析和总结()A-E阅实验报告规范性()A-E实验成绩()A-E
三、实验内容与设计代码展示
1.
2.choice.h
1.#pragma once
2.#include iostream
3.#include RunLcngth.h
4.include”LZW.h”
5.#include nArithmetic.h
6.#include ShannonFano.h
7.#include Huffman.h
8.#include string
9.#include cmath
10.#include cstdio
11.using namespacestd;
12.class Choice
13.{
14.public:
117.Choice;
118.void input;
19.~Choice;
20.private:
21.int choices;
22.string str;
23.};Choice.cpp
1.#include choice.h
2.#include n../../InteractionMedia/InteractionMedia/Huffman.h
3.struct CharacterT
4.
5.charc;
6.int freq;
7.string code;
8.;
9.void ShannonFanoCharacterT*chars,int end,int start=0,const stringbranch=n,const stringfullBranch=nn
10.
11.string code二fullBranch+branch;
12.〃找到某个字符,显示值
13.if start==end
14.
15.chars[start].code二code;
16.return;
17.}
18.int sum=0;//频率的和
19.〃计算从开始到结束的频率的总和
20.for inti=start;i=end;i++
21.sum+=chars[i].freq;
22.sum/=2;
23.inti,sum2=chars[start].freq;
24.for i=start+1;abssum-sum2+chars[i].freqabssum-sum2iend;i++
25.sum2+=chars[i].freq;
26.ShannonFanochars,i-1,start,O11,code;
27.ShannonFanochars,end,i,1,code;
28.}
29.Choice::Choice
30.
31.choices=0;
32.str=H\0n;
33.}
34.void Choice::input
35.{
36.while true
37.{
38.cout«Pleaseinputastring:\nn;
39.cin»str;
40.
41.break;
42.}
43.cout«Pleasechosse amode:\n;
44.cout«n
1.Run-Length Encodinig«endl;
45.cout«
2.Shannon-Fano Algorithm,«endl;
56.cout«
3.Huffman encoding«endl;
57.cout«
4.LZW CompressionDecompression«endl;cout«
5.Arithmetic Encoding«endl;
58.
59.cin»choices;
60.
61.switch choices
62.
63.case1:
64.
65.RunLength astr;
66.a.compress;
67.a.print;
68.break;
69.
70.case2:
71.
72.CharacterT*chars二new CharacterT[str.length];
73.int size=0;
74.
75.for inti=0;istr.length;i++{
76.intj=O;
77.
78.while jsizechars[j].c!=str[i]
79.j++;
80.
81.
82.if j==size{
83.chars|size].c=str[i];
84.chars[size++].freq=1;
85.
86.else
87.chars[j].freq++;
88.
89.
90.bool isSorted=false;
91.while!isSorted{
92.isSorted=true;
93.
94.for inti=0;isize-1;i++{
95.if chars[i].freqchars[i+l].freq{
96.CharacterT tmp=chars[i];
97.chars[i]=chars[i+1];
98.chars[i+1]=tmp;
99.isSorted=false;
100.}
101.}
102.}
103.
104.ShannonFanochars,size-1;
105.
106.cout«+----------------------+”«endl;
107.cout«|c|freq|code|n«endl;
108.cout«+--+-----------+--------+«endl;
109.for inti=0;isize;i++
110.printfn|%c|%4d|%6s|\n,chars[i].c,chars[i].freq,chars[i].code.c_str;
111.cout«+----------------------+”«endl;
112.
113.delete[]chars;
114.
115.break;
116.}
117.case3:
118.buildHuffmanTreestr;
119.break;
120.case4:
121.{
122.LZW b;
123.vectorLZW::encodeinfo res=b.LZW_encodestr,128;
124.cout«”解码输出字符串n«b.LZW_decoderes,128«endl;
125.cout«endl;
126.break;
127.}
128.case5:
129.
130.Arithmetic a;
131.a.RequireCodestr;
132.cout«a.Encodestr«endl;
133.cout«a.Decodea.Encodestr«endl;
134.break;
135.}
136.default:
137.break;
138.}
139.}
140.
141.}
142.
143.Choice::〜Choice
144.{
145.}RunLength.h
1.#pragma once
2.#include vector
3.#include iostream
4.using namespacestd;
5.class RunLength
6.
7.public:
8.RunLength;
9.RunLengthstring s;
10.string compress;
11.void print;
112.〜RunLength;
13.private:
14.stringstr;
15.};IRunLength.cpp
1.#include RunLength.h
2.#include string
3.RunLength::RunLength
4.
5.str=H\OH;
6.
7.RunLength::RunLengthstring s
8.
9.str=s;H.
12.string RunLength::compress
13.
14.if str==M\0n||str.length=
115.
16.return str;
17.
18.vectorchartemp;
19.vectorchar::iterator itrl;
20.string::iterator itr2;
21.string re;
22.temp.push_backstr[O];
23.char pre_c=str
[0];
24.int count=1;
25.for itr2=str.begin+1;itr2str.end;itr2++
26.{
27.charc=*itr2;
28.if c==pre_c
29.
30.count++;
31.}
32.else
33.{
34.temp.push_backcharcount+*0*;
35.temp.push_backc;
36.count=1;
37.pre_c=c;
38.}
39.
40.temp.push_backcharcount+10;
41.for itrl=temp.begin;itrl!=temp.end;itrl++
42.{
43.re+=*itrl;
44.
45.return re;
46.}
47.void RunLength::print
48.
49.cout«After compress:«RunLength::compress«endl;
50.}
51.RunLength:RunLength
52.
53.}Huffman.h
1.#include iostream
2.#include string
3.#include queue
4.#include unordered_map
5.using namespacestd;
6.〃一个树结点
7.struct HNode
8.
9.char ch;
10.int freq;
11.HNode*left,*right;
12.};
13.〃创建一个新树
14.HNode*getNodechar ch,int freq,HNode*left,HNode*right
15.
16.HNode*node=new HNode;
17.node-ch=ch;
18.node-freq=freq;
19.node-left=left;
20.node-right=right;
21.return node;
22.}
23.struct comp
24.{
25.bool operatorOCHNode*1,HNode*r
26.
27.return l-freqr-freq;
28.}
29.};
30.void encodeHNode*root,stringstr,
31.unordered_mapchar,string huffmanCode
32.{
33.if root==nullptr
34.return;
35.//找到一个叶子结点
36.if!root-left!root-right{。