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

实验报告课程名称：交互式媒体原理开课学期：专 业：软件工程年级班级：学生姓名：学 号：指导教师：计算机与信息科学学院软件学院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 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<char, int> freq;72. for (char ch : text) 73. freqch+;74. 75. priority_queue<HNode*, vector<HNode*>, 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;94. pq.push(getNode('0', sum, left, right);95. )96.97. HNode* root = pq.topO;98.99. /遍历赫夫曼树并存储编码到map里同时打印100. unordered_map<char, string> 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 « 'AnOriginal 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, str);124. 125. M.h1. #pragma once2. #include<iostream>3. #include<string>4. #include<map>5. #include<vector>LZ、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<encodeinfo> LZW_encode(string s, int encodenum);20. string LZW_decode(vector<encodeinfo> code, int beginnum);21.22. map <string, int> diet;字典23. map <int, string> revdict;解码时使用24. LZW();25. ;Mcpp1. include "LZW.h"2. 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:encodeinfo> LZW: LZW_encode(string s, int encodenum)19. 120. string P = "n;21. char C;22. vector<encodeinfo> EncodeResult; /存储编码之后的结果23. for (int i = 0; i < s.length(); i+)24. 25. C = si;26. string tempStr = P + C;27. 在字典里面寻找这个字符串28. map<string, int>:iterator iter = dict.find(tempStr);29. if (iter != dict.end。)找到了30. P = tempStr;31. 32. else 没找到33. encodeinfo 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 « EncodeResulti.P « " " « EncodeResulti.index « endl;47. 48. return EncodeResult;49. 50. string LZW:LZW_decode(vector<encodeinfo> 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+) 59. pW = cW;60. cW = codei.index;61. map<int, string>: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 = revdictpW0;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(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.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: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->deltalevel = delta;139. Arithmetic.h1. #pragma once2. #include <iostream>3. #include "range.h"4. #include <map>5. #include <string>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 getLength();18. private:19. int length;20. map<char, range>map;21. ;Arithmetic.cpp1. #include "Arithmetic.h"2. 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;14. 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<char, range>(stri, r);25. 26. 27. 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();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() < value && (itr->second).GetHigh() > value)55.(56.Lowlnterval = (itr->second).GetLow();57.Highlnterval = (itr->second).GetHigh();58.symbol += (itr->first);59.break;60.)61.)62.63.for (int i = 0; i < length - 1; +i) (64./* decode code */65.double deltalnterval;66.deltalnterval = Highlnterval - Lowlnterval;67.value -= Lowlnterval;68.69.value /= deltalnterval;70.for (auto i = map.begin(); i != map.end(); +i) 71.if (i->second).GetLow() < value && (i->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 symbol;81. Main.cpp1. #include nchoice.h"2. 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 Compression & 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 Encodinig2. 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. Huffman 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： asPlease 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日 实验类型验证性设计性口综合 性实验项目名称实验四：压缩算法一、实验目的/ 了解各种无损压缩算法的基本思想/ 掌握无损压缩算法的代码实现二' 实验要求/ 自选编程语言实现各种无损压缩算法五、结果分析及总结（对实验的结果是否达到预期进行分析，总结实验的收 获和存在的问题等）分析实验结果基本达到预期，其中赫夫曼编码和算术编码的结果正确但是输出有一定 问题。赫夫曼编码不会输出解码后的最后一位字符，算术编码会造成在解码的最 后重复输出第一位字符收获1. Run-Length Encoding基本思想为将重复且连续出现多次的字符使用（连续出现次数，某个字符）来 描述。缺点是如果文本重复较少，会白白浪费编码的资源却没有达到节省空间 的效果2. Shanno-Fano Encoding1） 对于给定的符号列表，指定相应的概率列表2）排序根据频率的符号列表，最常出现的符号在左边，最少出现的符号 在右边（个人认为类似二叉查找树）3）列表分为两部分，使得左边部分的总频率尽可能等于右边部分的总频 率4） 该列表左半边分配0,右半边分配15）对分好的两部分递归实现步骤3, 4,直到每一个符号成为叶子结点3. Huffman Encodinig类似于Shanno-Fano Encoding,不同的是该方法是将概率最小的两个相加作为 左右子树，重复过程直到概率值最终等于1。4. LZW compression and decompression将出现过的字符串映射到记号上，这样可以用较短的编码表示长的字符串。最 开始会将所有字母用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不包括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 <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 namespace std;12. class Choice13. 14. public:117. Choice();118. void input();19. Choice();20. private:21. int choices;22. string str;23. ;Choice.cpp1. #include "choice.h"2. #include n././InteractionMedia/InteractionMedia/Huffman.h"3. 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 二 fullBranch + 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) < abs(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. (41. 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.RunLength 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.)86.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(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);119. break;120. case4:121. 122. LZW b;123. vector<LZW:encodeinfo> 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. cout«a.Decode(a.Encode(str) « endl;134. break;135. 136. default:137. break;138. 139. 140.141. 142.143. Choice:Choice。144. 145. RunLength.h1. #pragma once2. #include <vector>3. #include <iostream>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 str;15. ； IRunLength.cpp1. #include "RunLength.h"2. #include <string>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. vector<char>temp;19. vector<char>:iterator itrl;20. string:iterator 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