java字符串压缩算法_⼏个常见的压缩算法-JavaGG的个⼈空 间-OSCHINA-中⽂开。。。
再学习了haffman算法之后发现压缩算法很有意思，上⽹查了点资料，这是做好的⼀篇(主要是我能理解)。前⾯⼏种都能看懂，关键是那个LZ77算法。这个是很强⼤的压缩算法，zip，rar⽤得都是这种算法，让我们来感叹下两个犹太⼈的强⼤
⼏个常见的压缩算法(转)
(⼀) 字典算法
字典算法是最为简单的压缩算法之⼀。它是把⽂本中出现频率⽐较多的单词或词汇组合做成⼀个对应的字典列表，并⽤特殊代码来表⽰这个单词或词汇。例如：
首都休闲大学
秸秆有字典列表：
00=Chinese
01=People
02=China中世纪欧洲地图
李汝革源⽂本：I am a Chinese people,I am from China 压缩后的编码为：I am a 00 01,I am from 02。压缩编码后的长度显著缩⼩，这样的编码在SLG游戏等专有名词⽐较多的游戏中⽐较容易出现，⽐如《SD⾼达》。 (⼆) 固定位长算法(Fixed Bit Length Packing)
这种算法是把⽂本⽤需要的最少的位来进⾏压缩编码。
⽐ 如⼋个⼗六进制数：1，2，3，4，5，6，7，8。转换为⼆进制为：00000001，00000010，00000011，00000100，00000101，00000110，00000111，00001000。每个数只⽤到了低4位，⽽⾼4位没有⽤到(全为0)，因此对低4位进⾏压缩编 码后得到：0001，0010，0011，0100，0101，0110，0111，1000。然后补充为字节得到：00010010， 00110100，01010110，01111000。所以原来的⼋个⼗六进制数缩短了⼀半，得到4个⼗六进制数：12，34，56，78。
这也是⽐较常见的压缩算法之⼀。
(三) RLE算法
这种压缩编码是⼀种变长的编码，RLE根据⽂本不同的具体情况会有不同的压缩编码变体与之相适应，以产⽣更⼤的压缩⽐率。
变体1：重复次数+字符
⽂本字符串：A A A B B B C C C C D D D D，编码后得到：3 A 3 B 4 C 4 D。
变体2：特殊字符+重复次数+字符
⽂本字符串：A A A A A B C C C C B C C C，编码后得到：B B 5 A B B 4 C B B 3 C。编码串的最开始说明特殊字符B，以后B后⾯跟着的数字就表⽰出重复的次数。
变体3：把⽂本每个字节分组成块，每个字符最多重复 127 次。每个块以⼀个特殊字节开头。那个特殊字节的第 7 位如果被置位，那么剩下的7位数值就是后⾯的字符的重复次数。如果第 7 位没有被置位，那么剩下 7 位就是后⾯没有被压缩的字符的数量。例如：⽂本字符串：A A A A A B C D E F F F。编码后得到：85 A 4 B C D E 83 F(85H= 10000101B、4H= 00000100B、83H= 10000011B)
以上3种不RLE变体是最常⽤的⼏种，其他还有很多很多变体算法，这些算法在Winzip Winrar这些软件中也是经常⽤到的。
(四) LZ77算法
LZ77算法是由 Lempel-Ziv 在1977发明的，也是GBA内置的压缩算法。LZ77算法有许多派⽣算法(这⾥⾯包括 LZSS算法)。它们的算法原理上基本都相同，⽆论是哪种派⽣算法，LZ77算法总会包含⼀个动态窗⼝(Sliding Window)和⼀个预读缓冲器(Read Ahead Buffer)。动态窗⼝是个历史缓冲器，它被⽤来存放输⼊流的前n个字节的有关信息。⼀个动态窗⼝的数据范围可以从 0K 到 64K，⽽LZSS算法使⽤了⼀个4K的动态窗⼝。预读缓冲器是与动态窗⼝相对应的，它被⽤来存放输⼊流的前n个字节，预读缓冲器的⼤⼩通常在0 – 258 之间。这个算法就是基于这些建⽴的。⽤下n个字节填充预读缓存器(这⾥的n是预读缓存器的⼤⼩)。在动态窗⼝中寻与预读缓冲器中的最匹配的数据，如果匹 配的数据长度⼤于最⼩匹配长度 (通常取决于编码器，以及动态窗⼝的⼤⼩，⽐如⼀个4K的动态窗⼝，它的最⼩匹配长度就是2)，那么就输出⼀对〈长度(length)，距离 (distance)〉数组。长度(length)是匹配的数据长度，⽽距离(distance)说明了在输⼊流中向后多少字节这个匹配数据可以被到。 例如：(假设⼀个 10个字节的动态窗⼝, 以及⼀个5个字节的预读缓冲器)
⽂本：A A A A A A A A A A A B A B A A A A A
--------------------- =========
动态窗⼝ 预读缓存器
动 态窗⼝中包含10个A ，这就是最后读取的10个字节。预读缓冲器包含了 B A B A A。编码的第⼀步就是寻动态窗⼝与预读缓存器相似长度⼤于2的字节部分。在动态窗⼝中不到B A B A A，所以B就被按照字⾯输出。然后动态窗⼝滑过1个字节，现在暂时输出了⼀个B。
第⼆步：A A A A A A A A A A A B A B A A A A A
--------------------- =========
动态窗⼝ 预读缓存器
现 在预读缓冲器包含A B A A A，然后再和动态窗⼝进⾏⽐较。这时，在动态窗⼝到了相似长度为2的A B，因此⼀对〈长度, 距离〉就被输出了。长度(length)是2 并且向后距离也是2，所以输出为<2,2>，然后动态窗⼝滑过2个字节。现在已经输出了B <2,2>。北京高校对超期学生发逾期警告
第三步：A A A A A A A A A A A B A B A A A A A
--------------------- =========
中国市场经济地位动态窗⼝ 预读缓存器
继续上⾯的⽅法得到输出结果<5,8>。现在已经输出了B <2,2> <5,8>。
最终的编码结果是：A A A A A A A A A A A B <2,2> <5,8>。
但 数组是⽆法直接⽤⼆进制来表⽰的，LZ77会把编码每⼋个数分成⼀组，每组前⽤⼀个前缀标⽰来说明这⼋个数的属性。⽐如数据流：A B A C A C B A C A按照LZ77的算法编码为：A B A C<2,2> <4,5>，刚好⼋个数。按照LZ77的规则，⽤“0”表⽰原⽂输出，“1”表⽰数组输出。所以这段编码就表⽰为：00001111B(等于 0FH)，因此得到完整的压缩编码表⽰：F A B A C 2 2 4 5。虽然表⾯上只缩短了1个字节的空间，但当数据流很长的时候就会突出它的优势，这种算法在zip格式中是经常⽤到。
除此之外还有很多压缩算法，像霍夫曼编码(Huffman Encoding)等等。这些编码也是⾮常的著名⽽且压缩效率极⾼，不过这些编码的算法相对⽐较繁琐，规则也很复杂，由于篇幅就不逐⼀介绍了。如果⼤家对这⽅⾯感兴趣可以到⽹站相关⽹站查询资料。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议