文件压缩

    xiaoxiao2021-04-14  30

    文件压缩:

    1. (两者之间的距离,匹配长度这样一对信息,来替换后一块内容。

    2.使用"滑动窗口"的方法,来寻找匹配串。

    3.0表示没有匹配的字节,用1表示(之间的距离,匹配长度)对

    4.固定两者之间的距离匹配长度所使用的位数使用固定大小的窗口限定最大的匹配长度设定一个最小匹配长度,只有当两个串的匹配长度大于最小匹配长度时,才认为是一个匹配。

    5.压缩: 从文件的开始到文件结束,一个字节一个字节的向后进行处理。用当前处理字节开始的串,和滑动窗口中的每个串进行匹配,寻找最长的匹配串。如果当前处理字节开始的串在窗口中有匹配串,就先输出一个标志位,表明下面是一个,然后输出,然后从刚才处理完的串之后的下一个字节,继续处理。如果当前处理字节开始的串在窗口中没有匹配串,就先输出一个标志位,表明下面是一个没有改动的字节,然后不做改动的输出当前处理字节,然后继续处理当前处理字节的下一个字节。

    6.解压缩: 从文件开始到文件结束,每次先读一位标志位,通过这个标志位来判断下面是一个,还是一个没有改动的字节。如果是一个,就读出固定位数的,然后根据中的信息,将匹配串输出到当前位置。如果是一个没有改动的字节,就读出一个字节,然后输出这个字节。

     

     

    Huffman

    1.要进行Huffman编码,首先要把整个文件读一遍,在读的过程中,统计每个符号的出现次数。然后根据符号的出现次数,建立Huffman树,通过Huffman树得到每个符号的新的编码。然后把文件中的每个字节替换成他们新的编码。

    2.建立Huffman树: 把所有符号看成是一个结点,并且该结点的值为它的出现次数。进一步把这些结点看成是只有一个结点的树每次从所有树中找出值最小的两个树,为这两个树建立一个父结点,然后这两个树和它们的父结点组成一个新的树,这个新的树的值为它的两个子树的值的和。如此往复,直到最后所有的树变成了一棵树。我们就得到了一棵Huffman树。

    3.这棵Huffman树是一棵二叉树,它的所有叶子结点就是所有的符号,它的中间结点是在产生Huffman树的过程中不断建立的。我们在Huffman树的所有父结点到它的左子结点的路径上标上0,右子结点的路径上标上1现在我们从根节点开始,到所有叶子结点的路径,就是一个01的序列。我们用根结点到一个叶子结点路径上的01的序列,作为这个叶子结点的Huffman编码。

    转载请注明原文地址: https://ju.6miu.com/read-670047.html

    最新回复(0)