基于C++和C#窗体实现各种无损压缩算法并进行比较分析.zip

# 基于 C 语言创作第一个网页 一、实验目的 编程实现各种无损压缩算法并进行比较分析 编程实现 huffman，自适应 huffman，算术编码和 LZW 编码算法 自己设置三种不同的统计数据源来进行测试，就每种数据源的压缩率，比较和评价各种算法的性能 二、实验要求 统计数据源要求： String 长度大于 30,构成 String 的每个 element 出现频率大于 4 次 输入输出要求： 输入可以通过文本或者屏幕输入\读取文件 输出可以保存到文本或者屏幕显示均可，需要输出每个字符的编码，以及整个输入 string 的整体编码，string 对应算法的压缩率，算法的运行时间 三、测试数据和执行结果 （在给定数据下，执行操作、算法和程序的结果，可使用数据、图表、截图等给出） **综述：** 哈夫曼算法相对比较简单，所以我使用了 winform 窗口应用程序和 C#；其他因为多处用到 STL 的 vector，map，deque 等所以使用的 C++；压缩效率我是用的公式为：（压缩前位数-压缩后位数）/压缩前位数；时间以毫秒为单位。测试字符串第一个是乱码，第二个是有意义的句子，第三个是含了多种符号的句子。 **Huffman Coding:** 1、拖进所需的控件后在 button 中进行编码。先新建字符串、各字符权重和出现次数的数组，再接受用户输入的字符串。在开始编码时就记下当前时间以便结束计算编码耗时。  1、先用 struct 设置节点，先找到两个最小值赋给 min1,min2。 2、统计各个字符出现的次数记为权重放在 weight 数组中。接着初始化树。建树时先找出最小的两位数，然后不断用 strcut 的 min.s1, min.s2 给它们的父母节点和左右孩子节点赋值。 3、将输入字符利用所建的树进行编码。这里比较简单，直接遍历树找到树所在的遍历序列即为本字符的编码。输出总的编码需要新建一个总编码数组，赋值使其不断加上新的到的单个字符编码。 4、结束编码，再获得一个当前时间。将此时间和开始时间相减获得总时间。 5、效率的计算首先统计编码前位数。在 ASCII 码中 26 字母均为 8 位 2 进制尾数表示，所以直接长度*8 即可；而编码后位数则在显示各个字符位数时，不断加上个各字符编码长度即可。 6、最后显示各个属性：效率、时间、总编码。 **代码：**     ## 实验结果分析及总结（对实验的结果是否达到预期进行分析，总结实验的收获和存在的问题等） **关于选取测试串：** ``` 三个测试串分别为普通乱码和有意义的字段。第一个为较乱且无意义的串，可进行初步测试，后面两个字符串模拟了有意义的文本内容且又分为两类：第二个为一般的长句子，只由26字母构成的；第三个为加了许多特殊符号的字符串**。** ``` \1. 根据算法来看明显哈夫曼的算法是最简单的，效率也较高。算术算法需要使用概率区间，相对来说不是最优的，因为此算法开始必须先扫描统计以便所有字符出现的概率，之后才不断更新区间。字典算法需要用到 map 的结构来构建字典，在每次接收字符时与上一个合并获得新的串加入字典中。 \2. 自适应哈夫曼算法最常用的有两种，这里使用了 FGK 算法。它在哈夫曼的算法上给每个节点加了权重，赋予了兄弟性质。同时可以满足动态接收字符串赋值，比哈夫曼算法更高效。在算法中 0 节点的使用在于接收之前没接受过的字符，一旦接收新字符就在原有左节点增加两个孩子：左为 0，右为此字符。在接收已有的字符时，如果破坏了兄弟性质则需交换子树。相对来说更加动态。 \3. 在算术算法的效率中，因为编码结果是概率区间，转化成二进制小数时有可能出现无限小数所以需要设定结果编码长度以防死循环。由此造成结果编码长度不准确，导致压缩率计算不准确。 \4. 关于三种算法的统计平均值统计：  由表可看出压缩效率最高的算法是算术算法，但因为计算编码长度有差异所以待定。LZW 的压缩效率最低，因为在不断接收字符时需要新建字符串加入字典中，如果字符串重复较高时字典才优先选择此算法。 时间上最短是哈夫曼算法；而自适应哈夫曼算法相对来说较高，因动态接收字符时可以随时得到二叉树的编码，可因为需要随时检查是否违法兄弟性质，在时间上最耗时。同时哈夫曼算法是无损算法，时间较短，效率相对较高随意比较适合短字符串的压缩。