核心内容摘要
【tkvk】探索数字时代的无限可能，连接你我，点亮未来
日志文件压缩
实验内容ALPD公司(爱乐普第)名下有一个网站 (ALPDOJ, 爱乐普第Orange Juice) 用于在线预约橙汁。
该公司的橙汁特别好喝而且十分畅销导致网站访问量特别大每天都有上百人登录网站预约橙汁所以导致公司的日志记录非常的长。
公司负责人wws在归档网站日志的时候发现公司服务器硬盘实在是太小导致不够存了所以在考虑怎么压缩数据以保存这些一点也不重要的数据。
可是wws实在是太菜了思来想去也不知道这份文件该怎么压缩。
随着日子渐渐推移服务器的硬盘空间越来越小一旦空间到了0那么整个网站都会崩溃。
这可急坏了wws于是他找到了你希望你能帮帮他压缩这些文件。
设计思路与功能描述
1 项目思路说明
2.
1 压缩算法的选择通过对OJ网站上给出内容与要求的分析可知本次大作业的主要目的是设计一套压缩与解压程序实现文本内容即题目给出ser.log的有效压缩。
而正如OJ平台的介绍所述压缩分为无损压缩与有损压缩但考虑到有损压缩一般多用于视频、图片的压缩处理上。
而且在正常情况下人们对文本中缺字少字的敏感度要远高于对图片像素降低的敏感度。
所以基于上述的综合考量本次大作业的目标可以细化为使用某种无损压缩方式实现ser.log的压缩与解压。
而OJ平台上给出的示例程序采取的是有损压缩的方式所以在本次大作业的编写过程中不对平台给出代码进行参考。
通过在网络上查阅相关资料可以得知目前常见的无损压缩方法主要有如下几类①哈夫曼编码②Lempel-Ziv压缩算法③算术编码哈夫曼编码主要是基于各个文字在待压缩文本中的出现频度构建起一颗huffman树该huffman树的主要特点是每一个叶结点都是一个文字而每一个中间结点一定不包含文字所以当我们想要表示某个文字时只需要说明该文字是从根节点出发每到一个新节点是向左还是向右即可——而这种表示方式可以用简单的bool变量
来完成。
同时huffman树能够保证出现频度高的字母能够对应较短的编码从而使压缩后的文本尽可能小。
LZ算法主要分为LZ77算法及其变种与LZ78算法及其变种。
LZ算法的共同特征就是用前面出现过的文本来替换之后再次出现文本。
而替换时只需要记录替换位置即可从而达到压缩文本的目的。
同时由于被替换的内容一定可以从之前已经生成的文本中找到所以不用像哈夫曼编码一样需要给出字母表。
而LZ系列算法中的不同算法则给出了不同的替换方式其中不乏有著名的LZM、LZO等应用广泛的压缩算法算术编码的主要思想就是将文本文件转换为
的二进制编码然后用一个一个相互独立的实数来表示0和1之间的距离随着消息的逐渐变长从而逐步形成更为紧密的压缩文本。
而在本次大作业中考虑到本人在上学期的《数据结构》课程上已经对哈夫曼编码和LZ77编码有所了解掌握故在本次大作业中将选用这两种无损编码方式来进行ser.log的压缩处理。
2.
2 哈夫曼编码的思路说明
2.
1.
1 哈夫曼编码压缩文件哈夫曼编码算法压缩文件的主要思路如下图所示正如上图所示huffman编码压缩文件过程主要有四步以下将对这四步内容进行详细说明1构建huffman树为了让出现频度较高的字母能够对应较短的编码huffman树在构建时就选择从出现频度低的叶结点开始构建从而使得这些出现频度低的叶结点占据的层次较低把层次较高的叶子留给出现频度高的叶结点。
所以在构建时首先要获取一张所有字符的出现频度表然后选取出频度表中出现次数最小的两个字符组合为一个新的“字符”而该新“字符”的出现频度即为两个子字符的出现频度之和再将该新“字符”放回到频度表中参与后续比较与运算。
与此同时每产生一个新“字符”生成一个新“字符”对应的结点使得该结点的左孩子指向出现频度较小的子字符对应的叶结点、右孩子指向另一个子字符对应的叶结点。
该生成过程随着频度表的更新操作往复循环直至频度表中只剩一个字符即所有节点都汇聚在了一个根结点上时说明huffman树构建完成退出操作。
2遍历huffman树生成字母转化表huffman树的本质其实就是一个较为特殊的二叉树所以huffman树的遍历可以直接套用一般二叉树的遍历规则每当遍历到一个叶结点时就在转换表中加入该叶结点所表示的字母其对应的转换方式即为从根结点走到该结点的每一步是向左还是向右的组合在本次大作业中用0表示向左1表示向右。
考虑到这里对到达叶结点的路径较为关心所以采用深度优先遍历的方式对huffman树进行搜索在本次大作业中选择了DLR的方式。
而对于字母表的生成考虑到log.src文件中的字符均在ASCII码的表示范围内所以在本题构建了一个长度为256的字符串集合用以对应每一个ASCII码的转换关系。
3向目标文件输出字母转化表由于huffman编码方式不具备让编码文本自我解码的能力所以会在压缩文本的开始先输入字母转化表以便解压时使用。
而在本次大作业中通过预先编码发现log.src文本中最长的字母转化方式长度为17所以这里采用int类型4个字节32个bit位来存储每一个字母的转化方式。
而考虑到待编译字符都在ASCII码表示范围内所以采用char类型1个字节8个bit位来存储每一个字母。
同时由于字母表读取时0和1都是有效位所以还需要额外注明该段转化关系是前多少位该位数的注明采用char类型1个字节。
4根据字母转化表输出压缩文件再次读取待转化文本将每一个字母转化为字母表中对应的转化方式再输出到目标文件。
在这里要特别指出的是由于huffman编码能够保证任意两种转化方式一定互不为对方从第一位开始的子串所以在压缩时不用考虑字母与字母之间分隔符的问题直接输出即可。
2.
1.
2 哈夫曼编码解压文件相交于压缩文件来说huffman编码解压文件就变得较为简单。
其主要流程为如图所示huffman编码解压文件主要有上述三步以下将对这三个步骤进行详细说明1读取字母转换表根据之前压缩时商定的方式即1个字节的字母1个字节的编码长度4个字节的编码方式可以识别文本中的每一对字母转换表。
值得一提的是为了在解压时能够知晓每一步的读取到哪里结束本次大作业在设计压缩算法时在文本的最开始额外输入了两个数据分别代表字母转换表的长度与文本的总字符。
前者为char型占据1个字节后者为int型占据4个字节。
这样在解压时就可以根据这两个数据的限制完成字母转换表与文本内容的分割以及文本翻译的结束判断。
2生成huffman树该步骤其实是与第一个步骤一并进行的其具体方式为从根结点开始按照0和1的指引转换到左孩子或是右孩子如果当前结点没有要指向走向的孩子那就临时生成一个孩子并转移到该孩子继续转移。
当完成该字母对应的所有转移后当前所在的结点即为该字母对应的叶结点。
在huffman树上对该叶结点进行标记一遍后续的使用。
3根据huffman树翻译压缩文件该过程即为解压原压缩文本其方式是让工作指针从根结点开始逐一读取压缩文件中的每一个bit位0表示工作指针转移到左孩子1表示工作指针指向右孩子。
如此循环读入bit直至工作指针指向了一个叶结点则立即输出该叶结点并将工作指针重新指向根结点翻译下一个字母。
从而可以逐字母地解压得到解压后的原始文件。
2.
3 lz77 编码的思路说明
2.
1.
1 lz77 编码压缩文件lz77编码压缩文件的主要思路如下正如上图所示lz77编码压缩文件的主要步骤都集中在一个不同变化的循环内一下将对该循环中的内容以及两个区域的定义进行详细说明。
1窗口区与前置区的建立窗口区相当于是“暂存”了指定长度的已经被表示过的文本内容划定了重复子串的搜索范围而前置区则用于指定当前要进行表示的文本位置同时划定了重复子串的最大长度。
2重复子串搜索正如
1所述lz系列压缩算法的核心就是在不借助字母表的情况下使用已经解压完成的文本来进行当前文本的解压。
而对于lz77算法来说这种复用的方式即体现在搜索当前要表示的字符串是否在前述文本中已经被表述过。
为了让压缩结果最好自然要找寻能够让所有所有更多的字符被一同表示的重复子串但同时又为了避免因为搜索范围过大而导致时间复杂度升级的情况只考虑窗口区范围内的文本内容即可。
3目标文件输出由于每一个调用前序子串的操作都需要指定调用位置、调用长度以及后缀的一位待压缩文本都是char类型共计3个字节所以只有当最长的重复子串长度大于等于3时才有必要使用调用前序子串的方式来生成压缩文件。
而在其他情况下只需要直接将前置区的第一位文本输出即可。
但在输出到目标文件时要特别注意的是在解压文件的时候两种不同的输出方式对应的解压方式也有所不同所以在本次大作业中采用了前置“标志位”的方式来告诉解压程序这里是直接输出还是调用前序子串本次大作业的标志位为char类型占据1个字节。
当它为‘0’时说明采用调用前序子串的方式输出为‘1’时说明采用直接输出的方式。
4窗口区与前置区后移当完成当前字符或字符串的编码之后就应当将前置区移动到下一个要进行编码的位置而这些刚刚编码完成的字符则应当要按顺序进入到窗口区的队列中去先进后出。
但同时为了保证窗口区的长度保持不变就需要让窗口区队列出队等量的字符。
至此便完整地完成了一段的文本的压缩并已经调整好了窗口区和前置区的位置以便于下一步操作。
故可以返回至第2步循环往复直至所有的待压缩文本都被压缩编码输出到了目标文件。
2.
1.
2 lz77 编码解压文件使用lz77编码方式解压文件的基本思路为正如上图所示lz77编码解压文件的主要步骤即为压缩文件的“倒置”只需要进入循环并逐个步骤进行操作即可。
其过程较为简单故不在此进行赘述。
2 功能描述
2.
1 压缩文件生成说明调用本次大作业所设计的程序对ser.log文件进行压缩可以得到生成的文件目录如下其中ser.log文件是OJ上提供的待压缩文件ser.huff文件是使用huffman编码压缩得到的文件ser.v1文件是使用huffman编码解压ser.huff得到的文件ser.lz77文件是使用lz77编码压缩得到的文件ser.v2文件是使用lz77编码解压ser.lz77得到的文件。
在这里要特别指出的是通过截图不难发现ser.v1的文件大小并不是严格等于源文件ser.log。
通过人工对文本文件的反复比对发现两者在文本内容、空格等可能会影响阅读体验的方面均完全一样推测可能是由于换行符的不同或是其他不可见字符例如超过ASCII表示范围的字符的影响导致的。
由于这里的错误完全不会影响阅读体验故在此可认为这种纰漏是可以被允许的。
2.
2 命令行窗口说明由于本次大作业在OJ平台上标明了有运行时间、压缩比的要求故将这些信息一并在命令行窗口进行展示同时加入了人性化提示。
当使用本程序压缩ser.log时命令行窗口的显示内容如下通过本例对比不难看出huffman编码方式和lz77编码方式相比各有利弊。
huffman算法的压缩时间与解压时间均短于lz77算法但lz77的压缩效率却要优于huffman算法。
项目亮点与情况说明
1 项目亮点①本次大作业的所有内容均是在本人浏览学习了网络介绍资料后独自开发的除了这一允许的头文件外没有使用任何未学习的内容自认为达到了高程群中所谓的“生写”标准。
②本次大作业同时完成了两种不同压缩算法的实现以便于相互比较体现各自优劣。
③两种算法的具体实现都进行了一定优化保证两种算法的运行时间都远低于OJ平台要求的15秒同时均有不错的压缩比。
④本次大作业实现的huffman编码和lz77编码都是目前使用较为广泛的压缩算法自认为其符合OJ要求的“高阶的核心算法”同时由于本次大作业实现的是无损压缩压缩方式与文本内容本身无关所以该算法的适用范围应该比有损压缩要广。
⑤自认为命令行窗口的内容弹出设计得较为人性化能够清晰地比对两种压缩算法的特点。
遇到的问题与解决方法
1 遇到的问题在刚开始进行huffman编码的过程中为了节约内存我选择了将所有的内容都按照比特位相连接然后每8位输出一次的方式来进行压缩文件的生成。
但在我进行调试时发现解压程序总会在压缩文件中识别乱码从而导致.huff压缩文件无法正确解压。