一、LZ77算法
1、压缩原理
如果文件中有两块内容相同的话，那么只要知道前一块的位置和大小，我们就可以确定后一块的内容。所以我们可以用（两者之间的距离，相同内容的长度）这样一对信息，来替换后一块内容。由于（两者之间的距离，相同内容的长度）这一对信息的大小，小于被替换内容的大小，所以文件得到了压缩。
简单的讲， LZ 算法被认为是字符串匹配的算法。例如：在一段文本中某字符串经常出现，并且可以通过前面文本中出现的字符串指针来表示。当然这个想法的前提是指针应该比字符串本身要短。
例1：在上一段短语“字符串”经常出现，可以将除第一个字符串之外的所有用第一个字符串引用来表示从而节省一些空间。
例2：有一个文件的内容如下
http://jiurl.yeah.nethttp://jiurl.nease.net
其中有些部分的内容，前面已经出现过了，下面用()括起来的部分就是相同的部分。
http://jiurl.yeah.net(http://jiurl.)nease(.net)
我们使用 (两者之间的距离，相同内容的长度) 这样一对信息，来替换后一块内容。
http://jiurl.yeah.net(22,13)nease(23,4)
(22,13)中，22为相同内容块与当前位置之间的距离，13为相同内容的长度。
(23,4)中，23为相同内容块与当前位置之间的距离，4为相同内容的长度。
由于（两者之间的距离，相同内容的长度）这一对信息的大小，小于被替换内容的大小，所以文件得到了压缩。
2、 LZ77使用滑动窗口寻找匹配串
LZ77算法使用"滑动窗口"的方法，来寻找文件中的相同部分，也就是匹配串。我们先对这里的串做一个说明，它是指一个任意字节的序列，而不仅仅是可以在文本文件中显示出来的那些字节的序列。这里的串强调的是它在文件中的位置，它的长度随着匹配的情况而变化。
LZ77从文件的开始处开始，一个字节一个字节的向后进行处理。一个固定大小的窗口（在当前处理字节之前，并且紧挨着当前处理字节），随着处理的字节不断的向后滑动，就象在阳光下，飞机的影子滑过大地一样。对于文件中的每个字节，用当前处理字节开始的串，和窗口中的每个串进行匹配，寻找最长的匹配串。窗口中的每个串指，窗口中每个字节开始的串。如果当前处理字节开始的串在窗口中有匹配串，就用(之间的距离，匹配长度) 这样一对信息，来替换当前串，然后从刚才处理完的串之后的下一个字节，继续处理。如果当前处理字节开始的串在窗口中没有匹配串，就不做改动的输出当前处理字节。
处理文件中第一个字节的时候，窗口在当前处理字节之前，也就是还没有滑到文件上，这时窗口中没有任何内容，被处理的字节就会不做改动的输出。随着处理的不断向后，窗口越来越多的滑入文件，最后整个窗口滑入文件，然后整个窗口在文件上向后滑动，直到整个文件结束。
3、使用LZ77算法进行压缩和解压缩
为了在解压缩时，可以区分“没有匹配的字节”和“（之间的距离，匹配长度）对”，我们还需要在每个“没有匹配的字节”或者“（之间的距离，匹配长度）对”之前，放上一位，来指明是“没有匹配的字节”，还是“（之间的距离，匹配长度）对”。我们用0表示“没有匹配的字节”，用1表示“（之间的距离，匹配长度）对”。
实际中，我们将固定（之间的距离，匹配长度）对中的，“之间的距离”和“匹配长度”所使用的位数。由于我们要固定“之间的距离”所使用的位数，所以我们才使用了固定大小的窗口，比如窗口的大小为32KB，那么用15位（2^15=32K）就可以保存0-32K范围的任何一个值。实际中，我们还将限定最大的匹配长度，这样一来，“匹配长度”所使用的位数也就固定了。
实际中，我们还将设定一个最小匹配长度，只有当两个串的匹配长度大于最小匹配长度时，我们才认为是一个匹配。我们举一个例子来说明这样做的原因。比如，“距离”使用15位，“长度”使用8位，那么“（之间的距离，匹配长度）对”将使用23位，也就是差1位3个字节。如果匹配长度小于3个字节的话，那么用“（之间的距离，匹配长度）对”进行替换的话，不但没有压缩，反而会增大，所以需要一个最小匹配长度。
压缩：
从文件的开始到文件结束，一个字节一个字节的向后进行处理。用当前处理字节开始的串，和滑动窗口中的每个串进行匹配，寻找最长的匹配串。如果当前处理字节开始的串在窗口中有匹配串，就先输出一个标志位，表明下面是一个(之间的距离，匹配长度) 对，然后输出(之间的距离，匹配长度) 对，然后从刚才处理完的串之后的下一个字节，继续处理。如果当前处理字节开始的串在窗口中没有匹配串，就先输出一个标志位，表明下面是一个没有改动的字节，然后不做改动的输出当前处理字节，然后继续处理当前处理字节的下一个字节。
解压缩：
从文件开始到文件结束，每次先读一位标志位，通过这个标志位来判断下面是一个(之间的距离，匹配长度) 对，还是一个没有改动的字节。如果是一个（之间的距离，匹配长度）对，就读出固定位数的（之间的距离，匹配长度）对，然后根据对中的信息，将匹配串输出到当前位置。如果是一个没有改动的字节，就读出一个字节，然后输出这个字节。
我们可以看到，LZ77压缩时需要做大量的匹配工作，而解压缩时需要做的工作很少，也就是说解压缩相对于压缩将快的多。这对于需要进行一次压缩，多次解压缩的情况，是一个巨大的优点。
二、RLE
1、原理
RLE（Run LengthEncoding行程编码）算法是一个简单高效的无损数据压缩算法，其基本思路是把数据看成一个线性序列，而这些数据序列组织方式分成两种情况：一种是连续的重复数据块，另一种是连续的不重复数据块。对于连续的重复数据快采用的压缩策略是用一个字节（我们称之为数据重数属性）表示数据块重复的次数，然后在这个数据重数属性字节后面存储对应的数据字节本身，例如某一个文件有如下的数据序列AAAAA，在未压缩之前占用5个字节，而如果使用了压缩之后就变成了5A，只占用两个字节，对于连续不重复的数据序列，表示方法和连续的重复数据块序列的表示方法一样，只不过前面的数据重数属性字节的内容为1。一般的这里的数据块取一个字节，这篇文章中数据块都默认为一个字节。
例如：给出的数据序列为：A-A-A-A-A-B-B-C-D
未压缩前：A-A-A-A-A-B-B-C-D
（0x41-0x41-0x41-0x41-0x41-0x42-0x42-0x43-0x44）
压缩后：5-A-2-B-1-C-1-D
（0x05-0x41-0x02-0x42-0x01-0x43-0x01-0x44）
2、实现
在进行压缩时逐个扫描待压缩数据，如果碰到某个字节后有重复的字节则计数器就加1（计数器初始值默认为1，也可设置为0），直到找到一个不重复的字节为止，将当前计数器中的值存入数据重数属性的字节中，将对应的该字节的数据存放在数据字节中，然后计数器置1继续用同样的策略扫描剩下的未压缩文档的数据。这里需要主意的是，数据重数属性的单位是一个字节，故最大值为255，因此对于数据序列的某一个数据重复次数大于255时的数据，当计数器记到255时就必须强制将计数器值和当前数据值写入数据重数属性字节中和数据字节中，然后计数器置1继续扫描，直到到达文件末尾。
由于压缩后的数据格式为：数据重数，数据块值，数据重数，数据块值……，因此解压的算法很简单，就是读出第一个位置上的数据重数字节存放的数据块的个数N，然后将第二个位置上的数据字节存放的数据块向解压缓冲区写N份，然后再读出第三个位置上数据重数字节存放的数据块的个数M，然后将第四个位置上数据字节存放的数据块向解压缓冲区写M份，直到读到压缩数据末尾结束。
3、RLE算法改进一
虽然上述算法实现起来很容易，但是它的一个明显的缺点就是如果要压缩的数据很少有连续重复的数据块，采用上诉压缩算法之后数据量反而会“膨胀”，最坏情况下就是所有的数据都不连续重复，则压缩后的数据量会增大一倍。因此就提出了一种改进的RLE算法。算法思路和原始RLE算法大致相当，对于重复的连续数据块依然采用上述算法，不同的是对于不重复的数据块，不会再在它前面插入标志重复次数的字节了，而是直接将该不重复的数据块写入压缩文件。这样即使原文件所有的数据都不是连续重复出现的，压缩后的文件也不会膨胀。但是这样简单的逻辑显然是不行的，这里的一个问题就是在解压缩的时候，如何判断一个字节是原始数据字节还是数据重数字节标志。为了解决这个问题，我们将数据重数字节的高两位置1，用字节剩下的六位来表示（此时能表示的最大长度为63）数据重数，这样在解压的时候如果遇到的字节高两位不全为1则一定是数据字节，但是这里还有一个问题是，如果遇见的字节的高两位全1是就不能判断是数据重数字节还是数据字节，因此，光处理数据重数属性字节的高位是不行的，实现的办法只能是，在数据压缩的时候如果发现数据的高两位是1只能再在该数据字节前面插入数据重数字节，置其值为1（此时由于高两位作为标记位已经置为1，故这里实际存储的是0XC1）。这样这个改进的RLE算法就完成了，其平均压缩率也比原始RLE算法更高，但是相对的压缩速度就稍微慢了。同样的与原始RLE算法一样也有最大长度问题，处理方法与原始RLE一样。
例如：给出的数据序列为：A-A-A-A-A-B-B-C-D
未压缩前：A-A-A-A-A-B-B-C-D
（0x41-0x41-0x41-0x41-0x41-0x42-0x42-0x43-0x44）
压缩后：5-A-2-B-C-D
（0xC5-0x41-0xC2-0x42-0x43-0x44）
该算法的解压算法很简单，就是将读取器指针指向第一个字节，逐个读取每个字节，判断该字节高两位是否全为1，如果是，则表示该字节是数据重数字节，则从该字节后六位读取重复次数N，然后将下一个字节向解压缓冲区写入N份，令读取器加指针加2接着读取下面的字节，如果该字节高两位不全为1，则表明该字节是数据字节，故将该字节直接写入解压缓冲区，并使读取器指针加1接着读取下面的字节，直到读取器指针达到文件末尾为止。
4、RLE算法改进二
上述优化后的RLE算法，在原始数据普遍大于192（0xC0）的情况下，其优化效果相对于优化前的算法没有明显改善。原因在于，原始的RLE算法和改进后的RLE算法对于连续出现的不重复数据的处理方式都是一个一个处理的，没有把不重复数据作为一个整体进行处理。RLE改进二算法的优化思想就是对连续的不重复数据的处理和连续重复数据的处理统一起来，不论数据是否连续重复，都在之前设置一个数据重数字节，这样在解压的时候就不需要区分是数据重数字节还是原始数据字节了。唯一需要区分的是后面跟的数据类型。区分的方法就是数据重数字节的最高位，如果最高位是1则表示后面跟的是连续重复的数据，如果最高位是0则表示后面跟的是连续不重复的数据。标志字节的低7位存储数值（最大值是127），对于连续重复的数据，这个数字表示需要重复的次数，对于连续不重复数据，这个数字表示连续不重复数据块的长度。需要注意的是，只有重复次数超过2的数据才被认为是连续重复数据，因为如果数据的重复次数是2，压缩后加上标志字节后总的长度没有变化，因此没有必要处理。
例如：给出的数据序列为：A-A-A-A-A-B-B-C-D
未压缩前：A-A-A-A-A-B-B-C-D
（0x41-0x41-0x41-0x41-0x41-0x42-0x42-0x43-0x44）
压缩后：5-A-4-B-B-C-D
该RLE改进二的算法的压缩算法设计如下：扫描指针从数据开始处读取数据，并依次向后扫描各个字节，每向后读取一个字节计数器加1，在扫描的同时比较每个字节是否相同，这样就会有两种情况：一种情况是扫描过程中前三个字节出现的都是连续重复的字节，则将计数器最高位置1，然后继续扫描，直到出现1个不相同的字节，此时令扫描指针回退1个字节，计数器减1，然后将计数器的值写入数据重数字节中，并将当前扫描指针指向字节写到随后的数据字节中。另一种情况是扫描过程中前两个字节就不相同，则将计数器最高位置0，然后接着向后扫描，若在此后的扫描过程中出现连续3个相同的字节，则停止扫描，并令扫描指针回退到初始值，计数器减3，然后将当前计数器的值写入数据重数字节中，并将当前扫描指针指向字节及其后N个字节写到随后的数据字节中。
RLE改进二的解压缩算法很简单，因为压缩后的格式是：数据重数，数据块（组），数据重数，数据块（组）……，因此从头扫描，取出数据重数字节并判断其标志位，若为1，则将接下来的一个字节向解压缓冲区写N份（这里的N是由数据重数字节低七位计算出来的），然后扫描指针加2，接着向后扫描。若为0，则将数据重数字节后面的N个字节都写入解压缓冲区，然后扫描指针加N+1，接着向后扫描。整个解压过程直到扫描指针独到整个数据尾部为止。
5、RLE算法改进三
以上算法中块数属性占用一个字节，原始RLE算法能表示的最大的数据重数为MAX=255，RLE改进一中由于高两位做了标记位，则能表示的最大数据重数为MAX=63，RLE改进二中由于高一位做了标记位，则能表示的最大数据重数为MAX=127，所以如果某数据块重复次数超过了最大值MAX，则按以上各算法，该连续重数的数据块只能被分割成多个（数据重数，数据块）对来表示，这样就加大了空间的开销。
针对上诉算法中出现的连续重复数据块数超过MAX值的情况，规定如果数据重数字节的值为FF则在其后的一个字节仍为数据重数字节，最终的值为这几个数据重数字节值的和，如果特殊的，某数据块连续重复数正好是MAX值，则在该数据块对应的数据重数字节F后再添加一个数据重数字节置其值为0x00。
三、Huffman编码的压缩原理
1、原理
我们把文件中一定位长的值看作是符号，比如把8位长的256种值，也就是字节的256种值看作是符号。我们根据这些符号在文件中出现的频率，对这些符号重新编码。对于出现次数非常多的，我们用较少的位来表示，对于出现次数非常少的，我们用较多的位来表示。这样一来，文件的一些部分位数变少了，一些部分位数变多了，由于变小的部分比变大的部分多，所以整个文件的大小还是会减小，所以文件得到了压缩。这个算法适合压缩具有较高信息重复率的文件。
2、Huffman编码使用Huffman树来产生编码
要进行Huffman编码，首先要把整个文件读一遍，在读的过程中，统计每个符号（我们把字节的256种值看作是256种符号）的出现次数。然后根据符号的出现次数，建立Huffman树，通过Huffman树得到每个符号的新的编码。对于文件中出现次数较多的符号，它的Huffman编码的位数比较少。对于文件中出现次数较少的符号，它的Huffman编码的位数比较多。然后把文件中的每个字节替换成他们新的编码。
3、使用Huffman编码进行压缩和解压缩
压缩：
读文件，统计每个符号的出现次数。根据每个符号的出现次数，建立Huffman树，得到每个符号的Huffman编码。将每个符号的出现次数的信息保存在压缩文件中，将文件中的每个符号替换成它的Huffman编码，并输出。
解压缩：
得到保存在压缩文件中的，每个符号的出现次数的信息。根据每个符号的出现次数，建立Huffman树，得到每个符号的Huffman编码。将压缩文件中的每个Huffman编码替换成它对应的符号，并输出。