软件工程课程实验报告-压缩算法.docx

《软件工程课程实验报告-压缩算法.docx》由会员分享，可在线阅读，更多相关《软件工程课程实验报告-压缩算法.docx（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验报告课程名称：交互式媒体原理开课学期：专 业：软件工程年级班级：学生姓名：学 号：指导教师：计算机与信息科学学院软件学院46. huffmanCoderoot-ch = str;47. )48. encode(root-left, str + nOn, huffmanCode);49. encode(root-right, str + ” 1 ，huffmanCode);50. )51. void decode(HNode* root, int& index, string str)52. 53. if (root = nullptr) 54. return;55. 56. /found

2、a leaf node57. if (!root-left &!root-right)58. 59. cout root-ch;60. return;61. 62. index+;63. if (strindex= V)64. decode(root-left, index, str);65. else66. decode(root-right, index, str);67. 68. 建立赫夫曼树，解码输入的字符串69. void buildHuffmanTree(string text)70. (71. unordered_map freq;72. for (char ch : text)

3、 73. freqch+;74. 75. priority_queueHNode*, vector, comp pq;76. for (auto pair : freq) 77. pq.push(getNode(pair.first, pair.second, nullptr, nullptr);78. )79. while (pq.size()!= 1)80. (LZ、90. HNode* left = pq.top(); pq.popQ;91. HNode* right = pq.topO; pq.popO;92.93. int sum = left-freq + right-freq;9

4、4. pq.push(getNode(0, sum, left, right);95. )96.97. HNode* root = pq.topO;98.99. /遍历赫夫曼树并存储编码到map里同时打印100. unordered_map huffmanCode;101. encode(root,H, huffmanCode);102.103. cout Huffman Codes are :nn n;104. for (auto pair : huffmanCode) 105. cout pair.first pair.second An,;106. 107.108. cout AnOri

5、ginal string was :n text endl;109.110. 打印111. string str = ”；112. for (char ch : text) 113. str += huffmanCodech;114. 1115.116. cout nEncoded string is :n str endl;117.118. 遍历赫夫曼树119. 解码120. int index = -1;121. cout nDecoded string is: n；122. while (index (int)str.size() - 2) 123. decode(root, index

6、, str);124. 125. M.h1. #pragma once2. #include3. #include4. #include5. #includeLZ、6.7. using namespace std;8.9. class LZW10. 11. public:12. struct encodeinfo13. (14. string P;15. int index;16. ; 键值对17. LZW();18.19. vector LZW_encode(string s, int encodenum);20. string LZW_decode(vector code, int beg

7、innum);21.22. map diet;字典23. map revdict;解码时使用24. LZW();25. ;Mcpp1. include LZW.h2. using namespace std;3.4.5. LZW:LZW()6. (7. dict.clearQ;8. revdict.clear();9. for (int i = 0;i 128; i+)10. (11. string s = nt;12. s0 = char(i);13. dicts = i;14. revdicti = char(i);15. 16. 17.18. vector LZW: LZW_encode

8、(string s, int encodenum)19. 120. string P = n;21. char C;22. vector EncodeResult; /存储编码之后的结果23. for (int i = 0; i s.length(); i+)24. 25. C = si;26. string tempStr = P + C;27. 在字典里面寻找这个字符串28. map:iterator iter = dict.find(tempStr);29. if (iter != dict.end。)找到了30. P = tempStr;31. 32. else 没找到33. enco

9、deinfo a = P, dictP ;34. EncodeResuIt.push_back(a);将P的对应的编码存放起来35. 建立起一个新的索引36. encodenum+;37. dicttempStr=encodenum;38. P = C;39. 40. )41. encodeinfo a = P, dictP ;42. EncodeResult.push_back(a); 最终结尾处43. 这是编码过程的输出44. cout LZW编码输出的信息如下：n endl;45. for (int i = 0; i EncodeResult.size(); i+)46. cout En

10、codeResulti.P EncodeResulti.index endl;47. 48. return EncodeResult;49. 50. string LZW:LZW_decode(vector code, int beginnum) 51. string ret=最终译码的输出52. string P = n;53. char C;54. int pW, cW;55. 第一步，初始化，读入第一个的符号cW,解码输出56. cW = code0.index;57. ret += revdictcW; 解码输出58. for (int i = 1; i code.size(); i+

11、) 59. pW = cW;60. cW = codei.index;61. map:iterator iter = revdict.find(cW);62. if (iter != revdict.end。)找至lj 了63. 解码输出64. ret += iter-second;65. P = revdictpW;66. C = revdictcW0;67. string tempStr = P + C;68. beginnum+;69. revdictbeginnum = tempStr;70. 71. else72. (73. P = revdictfpW;74. .C = revdi

12、ctpW0;75. beginnum+;76. string tempStr = P + C;77. revdictbeginnumj = tempStr;78. ret += tempStr;79. 80. 81. return ret;82. 83. LZW:LZW()84. (85. Range.h1. #pragma once2. class range3. (4. public:5. range();6. range。；7. double GetLow();8. double GetHigh();9. void SetLow(double low);10. void SetHigh(

13、double high);11. void SetDelta(double delta);12. private:13. double low;14. double high;15. double deltalevel;16. 1;Range.cpp1. 用于存储算术编码中的上下界2. #include nrange.h3. 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

14、. 15. double range:GetLow()16. (17. return this-low;18. )19. double range:GetHigh()20. 21. return this-high;22. 128. void range:SetLow(double low)129. (130. this-low = low;131. 132. void range:SetHigh(double high)133. (134. this-high = high;135. 136. void range:SetDelta(double delta)137. (138. this-

15、deltalevel = delta;139. Arithmetic.h1. #pragma once2. #include 3. #include range.h4. #include 5. #include 6. using namespace std;7. class Arithmetic8. (9. public:111. Arithmetic();112. Arithmetic。；13. void RequireCode(string str);14. double Encode(string str);15. string Decode(double value);j 17.int

16、 getLength();18. private:19. int length;20. mapmap;21. ;Arithmetic.cpp1. #include Arithmetic.h2. Arithmetic: Arithmetic()3. 4. length = 0;5. 6. Arithmetic:Arithmetic。7. (8. 9. void Arithmetic:RequireCode(string str)10. (11. doublelowlevel = 0.0;12. doublehighlevel = 0.0;13. doubleprobability = 0.0;1

17、4. for (int i = 0; i str.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.SetLow(lowlevel);22. r.SetHigh(highlevel);23. r.SetDelta(probability);24. map.insert(std:pair(stri, r);25. 26. 2

18、7. double Arithmetic:Encode(string str)28. 29. double LowRange = 0.0, HighRange = 1.0;30. for (string:iterator itr = str.beginQ; itr != str.end(); +itr)31. 32. double delta = HighRange - LowRange;33. HighRange = LowRange + delta * map*itr.GetHigh();34. LowRange = LowRange + delta * map*itr.GetLow();

19、35. +length;36. 37. return LowRange;38. 39. string Arithmetic:Decode(double value)40. 41. double Lowlnterval = 0;42. double Highlnterval = 0;43. string symbol =44. for (auto itr = map.begin(); itr != map.end(); +itr)45. 46. if (itr-second).GetLow() second).GetHigh() value)55.(56.Lowlnterval = (itr-s

20、econd).GetLow();57.Highlnterval = (itr-second).GetHigh();58.symbol += (itr-first);59.break;60.)61.)62.63.for (int i = 0; i second).GetLow() second).GetHigh() value) 72.Lowlnterval = (i-second).GetLow();73.Highlnterval = (i-second).GetHigh();74.symbol + =(i-first);75.break;76.)77.)78.79.)80.return sy

21、mbol;81. Main.cpp1. #include nchoice.h2. using namespace std;3. int main()4. (5. Choice choice;6. choice.input();7. )四、实验结果（可给出截图等加以说明）W Microsoft Visual Studio 调记0空制台Please input a string： aaerwPlease chosse a mode：1. Run-Length Encodinig2. Shannon-Fano Algorithm3. Huffman encoding4. LZW Compressio

22、n & Decompression5. Arithmetic Encoding1After compress：a2elrlwlPlease input a string： aaerwPlease chosse a mode:1. Run-Length Encodinig2. Shannon-Fano Algorithm3. Huffman encoding4. LZW Compression 也 Decompression5. Arithmetic EncodingPlease input a string： abPlease chosse a mode：1. Run-Length Encod

23、inig2. Shannon-Fano Algorithm3. Huffman encoding4. LZW Compression & Decompression5. Arithmetic Encoding3Huffman Codes axe ：a 0b 1Original string was : abEncoded string is ： 01Decoded string is：aPlease input a string：abcsdawPlease chosse a mode:1. Run-Length Encodinig2. Shannon-Fano Algorithm3. Huff

24、man encoding4. LZW Compression & Decompression5. Arithmetic Encoding4LZ噬码输出的信息如下:a 97b 98c 99s 115d 100a 97w 119解码输i出字符串：abcsdawPlease input a string： asPlease chosse a mode：1. Run-Length Encodinig2. Shannon-Fano Algorithm3. Huffman encoding4. LZW Compression 也 DecompressionPlease input a string： as

25、Please chosse a mode：1. Run-Length Encodinig2. Shannon-Fano Algorithm3. Huffman encoding4. LZW Compression & Decompression5. Arithmetic EncodingPlease input the probability0.4Please input the probability0.60.16 asaa Please input a string：输入任意字符串，选择编码解码的方法实验时间2020年11月1日 实验类型验证性设计性口综合 性实验项目名称实验四：压缩算法一

26、、实验目的/ 了解各种无损压缩算法的基本思想/ 掌握无损压缩算法的代码实现二 实验要求/ 自选编程语言实现各种无损压缩算法五、结果分析及总结（对实验的结果是否达到预期进行分析，总结实验的收 获和存在的问题等）分析实验结果基本达到预期，其中赫夫曼编码和算术编码的结果正确但是输出有一定 问题。赫夫曼编码不会输出解码后的最后一位字符，算术编码会造成在解码的最 后重复输出第一位字符收获1. Run-Length Encoding基本思想为将重复且连续出现多次的字符使用（连续出现次数，某个字符）来 描述。缺点是如果文本重复较少，会白白浪费编码的资源却没有达到节省空间 的效果2. Shanno-Fano

27、Encoding1） 对于给定的符号列表，指定相应的概率列表2）排序根据频率的符号列表，最常出现的符号在左边，最少出现的符号 在右边（个人认为类似二叉查找树）3）列表分为两部分，使得左边部分的总频率尽可能等于右边部分的总频 率4） 该列表左半边分配0,右半边分配15）对分好的两部分递归实现步骤3, 4,直到每一个符号成为叶子结点3. Huffman Encodinig类似于Shanno-Fano Encoding,不同的是该方法是将概率最小的两个相加作为 左右子树，重复过程直到概率值最终等于1。4. LZW compression and decompression将出现过的字符串映射到记号上

28、，这样可以用较短的编码表示长的字符串。最 开始会将所有字母用ASCII码存储在一个字典中，在这个基础上添加的新的映 射即从256开始后添加的元素为扩展项。例如ABABAB编码1）遇到A,用97表示，编码为97.2）遇到B,用98表示，编码为983）发现了一个字串AB,用257表示，添加进字典中4）后面继续发现AB用257表示5. Arithmetic Encoding1）假设有一段数据需要编码，统计其中所有的字符和出现的次数2）将区间0, 1不包括1连续划分为多个子区间，每个子区间代表一个字 符，子区间大小正比与出现的概率。所有子区间的和是0, 1不包括13）编码首先从初始区间开始0, 1不包

29、括1开始，设置low = 0, high = 14）不断读入原始数据的字符，找到字符所在的区间L, Hlow = low+ （high-low） *Lhigh=low+ （high-low） *H最后得到的区间中的任一小数输出即为编码的数据存在问题1 .面向对象编程和面向过程编程混用，代码不够规范2 .两个算法的解码输出结果有问题实验目的和要求明确（A-E）：教实验内容与设计（A-E）：师实验结果（A-E）：评结果分析和总结（A-E）：阅实验报告规范性（A-E）实验成绩（A-E）：三、实验内容与设计1 .代码展示2 .choice.h1. #pragma once2. #include 3.

30、#include RunLcngth.h4. include ”LZW.h”5. #include nArithmetic.h6. #include ShannonFano.h7. #include Huffman.h8. #include 9. #include 10. #include 11. using namespace std;12. class Choice13. 14. public:117. Choice();118. void input();19. Choice();20. private:21. int choices;22. string str;23. ;Choice

31、.cpp1. #include choice.h2. #include n././InteractionMedia/InteractionMedia/Huffman.h3. struct CharacterT4. (5. char c;6. int freq;7. string code;8. )；9. void ShannonFano(CharacterT* chars, int end, int start = 0, const string& branch = n, const string & fullBranch = nn)10. (11. string code 二 fullBra

32、nch + branch;12. 找到某个字符，显示值13. if (start = end)14. (15. charsstart.code 二 code;16. return;17. 18. int sum = 0; / 频率的和19. 计算从开始到结束的频率的总和20. for (int i = start; i = end; i+)21. sum += chars i. freq;22. sum /= 2;23. int i, sum2 = charsstart.freq;24. for (i = start + 1; abs(sum - (sum2 + charsi.freq) ab

33、s(sum - sum2) & i end; i+)25. sum2 + = charsi.freq;26. ShannonFano(chars, i - 1, start, O11, code);27. ShannonFano(chars, end, i, 1, code);28. 29. Choice:Choice()30. (31. choices = 0;32. str = H0n;33. 34. void Choice:input()35. 36. while (true)37. 38. cout Please input a string:nn;39. cin str;40. (4

34、1. break;42. 43. cout Pleasechosse a mode:n;44. cout n 1.Run-LengthEncodinig endl;45. cout 2. Shannon-Fano Algorithm, endl;56.cout 3. Huffman encoding endl;57.cout 4. LZW Compression & Decompression 58.cout 5. Arithmetic Encoding endl;59.cin choices;60.61.switch (choices)62.(63.case 1:64.(65.RunLeng

35、th a(str);66.press();67.a.print();68.break;69.)70.case 2:71.(72.CharacterT* chars 二 new CharacterTstr.length();73.int size = 0;74.75.for (int i = 0; i str.length(); i+) 76.intj = O;77.78.while (j size & charsj.c != stri)79.j+；80.81.82.if (j = size) 83.chars|size.c = stri;84.charssize+.freq = 1;85.)8

36、6.else87.chars j.freq+;88.)89.90.bool isSorted = false;91.while (! isSorted) 92.isSorted = true;93.94.for (int i = 0; i size - 1; i+) 95.if (charsi.freq charsi + l.freq) 96.CharacterT tmp = charsi;97.charsi = charsi +1;98.charsi + 1 = tmp;99.isSorted = false;endl;100. 101. 102. 103.104. ShannonFano(

37、chars, size - 1);105.106. cout +” endl;107. cout | c | freq | code |n endl;108. cout +-+ endl;109. for (int i = 0; i size; i+)110. printf(n| %c | %4d | %6s |n, charsi.c, charsi.freq, charsi.code.c_str();111. cout +” endl;112.113. delete chars;114.115. break;116. 117. case3:118. buildHuffmanTree(str)

38、;119. break;120. case4:121. 122. LZW b;123. vector res = b.LZW_encode(str, 128);124. cout ”解码输出字符串：n b.LZW_decode(res, 128) endl;125. cout endl;126. break;127. 128. case5:129. (130. Arithmetic a;131. a.RequireCode(str);132. cout a.Encode(str) endl;133. couta.Decode(a.Encode(str) endl;134. break;135.

39、 136. default:137. break;138. 139. 140.141. 142.143. Choice:Choice。144. 145. RunLength.h1. #pragma once2. #include 3. #include 4. using namespace std;5. class RunLength6. (7. public:8. RunLength();9. RunLength(string s);10. string compress();11. void print();112.RunLength();13. private:14. string st

40、r;15. ； IRunLength.cpp1. #include RunLength.h2. #include 3. RunLength:RunLength()4. (5. str=HOH;6. )7. RunLength:RunLength(string s)8. (9. str = s;H. )12. string RunLength:compress()13. (14. if (str = M0n| str.length() = 1)15. (16. return str;17. )18. vectortemp;19. vector:iterator itrl;20. string:i

41、terator itr2;21. string re;22. temp.push_back(strO);23. char pre_c = str0;24. int count = 1;25. for (itr2 = str.begin() + 1; itr2 str.end(); itr2+)26. 27. char c = *itr2;28. if (c = pre_c)29. (30. count+;31. 32. else33. 34. temp.push_back(char)(count + *0*);35. temp.push_back(c);36. count = 1;37. pre_c = c;38. 3