作者 Maxwell
转载请注明 转自轩辕春秋文化论坛 设计与修改区http://www.xycq.net/forum/index.php?showforum=48
原帖地址http://www.xycq.net/forum/index.php?showtopic=64471
谢谢合作
转载前请先联系作者
LS的解压算法见《ls11格式详解》http://www.xycq.net/forum/index.php?showtopic=35276
这里用一篇冗长的文章来讨论一下压缩算法。文章分为四个部分字典压缩、LZSS算法、编码、实现。文章的四个部分间相互独立并且几乎没有顺序要求，读者可以以自己喜欢的顺序或者挑自己喜欢的部分阅读。文中的代码是伪代码，并且未经严格考验，仅供参考。
LS压缩全过程是经过了两遍压缩，先从简单的字典压缩开始讨论。
一、字典压缩
字典压缩就是把原文中较长的数据用一个较短的数据代替的过程，在这里将较短的数据称作索引，而较长的数据称作值，每个(索引, 值)对称作一项。
LS算法使用一个256项的字典，每项的值都是一个字节，并且不保存索引而是用项的顺序号代替。比如一个字典是这样的 235, 100, 4...7，这代表如果原文中遇到235就用0代替，遇到100就用1代替依此类推。由于在LS算法中值越小的数占的位数越少，因此将出现频率高的项放在前面可获得最大压缩率。
要统计原文中一字节取值的频率非常简单，只需要有一个256项的计数器，顺序读入原文，根据原文的值增加相应的计数器即可，可以很容易写出如下代码：
int counter[256];
for (int i = 0; i < src.length; i++)
{
counter[src[i]]++;
}
得到频率统计之后就可以生成字典了。仔细考虑一下如果压缩时跟解压时用同一个字典的话，需要每次从字典里按值搜索以确定索引，所以可以将解压字典的索引和值调换位置并排序供压缩使用，而解压字典是需要写入到压缩文件中的，所以我们需要生成两个字典。先考虑压缩字典，项的顺序是按频率从高到低排列，考虑最直观的方法可以每次选出频率最高的一个写入字典，然后将这一项移出，将这一方法略做改动后代码如下：
BYTE decode_dict[256];
int max_index;
for (int i = 0; i < decode_dict.length; i++)
{
max_index = 0;
for (int j = 0; j < counter.length; j++)
{
if (counter[j] > counter[max_index])
{
max_index = j;
}
}
decode_dict[i] = j;
counter[j] = -1;
}
调换解压字典的索引和值的位置，并根据新的索引排序即可获得压缩字典，从解压字典出发，按每项的值将索引赋值给压缩字典：
BYTE encode_dict[256];
for (int i = 0; i < decode_dict.length; i++)
{
encode_dict[decode_dict[i]] = i;
}
生成了字典之后使用是非常容易的大致是这样的格式：
for (int i = 0; i < src.length; i++)
{
dest[i] = encode_dict[src[i]];
}
这个地方有个问题，索引和值的大小都是1个字节，字典压缩后根本没减少原文长度。这是因为字典压缩后还要进一步处理才能达到压缩的效果，这个问题将在第三部分讨论。
二、LZSS算法
LS中的另外一种压缩算法是LZSS的一种变形。其实LZSS也是一种字典压缩，不过为了与第一部分的压缩区别开来，只在这里提到字典这个词，在本部分剩下的篇幅里不再出现。LZSS是一种思路非常简单的算法，但是这不代表容易理解和好实现。对LZSS算法感兴趣的读者可以自己去网上搜索相关文章，这里只介绍LS中用到的变形算法，不过仍称这个变形算法为LZSS算法。
LZSS算法的思路是搜索目前待压缩串是否在以前出现过，如果出现过则利用前次出现的位置和长度来代替现在的待压缩串以起到压缩的目的。思路一句话就能表述完，如果涉及到细节则有多种变化，但是LZSS算法最大的好处是压缩算法的细节处理不同只对压缩率和压缩时间有影响，却不会影响到解压程序。因此在这里讨论的压缩在细节上可能与光荣实际的压缩程序有所不同，我们可以根据自己的需要来裁剪这个算法。
下面以实例来讲解算法。考虑如下一段原文"abcdefabcdgabcdefabcdgabcf"，目前已经压缩到"abcdefabcd"，而"gabcdefabcdgabcf"是待压缩串。
原文 abcdefabcdgabcdefabcdgabcf
已压缩串 abcdefabcd
未压缩串 gabcdefabcdgabcf
"g"是在原文串中第一次出现，所以显然不可能找到匹配串，因此直接输出g
原文 abcdefabcdgabcdefabcdgabcf
已压缩串 abcdefabcdg
未压缩串 abcdefabcdgabcf
依次向前匹配"g..."、"d..."、"b..."都不能匹配，下一个串是"abcd..."与未压缩的串有四个字符匹配，
原文 abcdefabcdgabcdefabcdgabcf
已压缩串 abcdefabcdg
未压缩串 abcdefabcdgabcf
由于要达到最大匹配，所以记录下偏移5（相对于首个未压缩字节的偏移）和长度4继续向前匹配，依次匹配"f..."、"e..."、"d..."、"c..."、"b..."都无法匹配。再向前一个串开头是"a"，依次向下匹配看看"bcdefabcdg"都匹配，居然发现如果越过已压缩的位置还可以继续匹配
原文 abcdefabcdgabcdefabcdgabcf
已压缩串 abcdefabcdg
未压缩串 abcdefabcdgabcf
既然能匹配为什么不匹配呢，因为这次匹配长度比上次长，放弃上次记录，记录偏移11和长度14。
再向前已经到达了原文头了，匹配结束，输出偏移11和长度14，并且将未压缩位置向后移动14
原文 abcdefabcdgabcdefabcdgabcf
已压缩串 abcdefabcdgabcdefabcdgabc
未压缩串 f
按照这个流程继续执行直到所有的原文都被压缩为止。
[/code]
写出来的代码看起来像是这个样子：
for (int i = 0; i < src.length; i += max_match_length)
{
int max_match_offset = 0;
int max_match_length = 1;
for (int j = i - 1; j >= 0; j--)
{
int match_length = match(src[j], src[i]);
if (match_length >= 3 && match_length > max_match_length)
{
max_match_length = match_length;
max_match_offset = i - j;
}
}
if (max_match_length >= 3)
{
output(max_match_offset + 256, max_match_length - 3); // 注1
}
else
{
output(src[i]);
}
}
注1：加256和减3涉及到实现，可见第四部分。
三、编码
任何一个正二进制数b可以分解为两个m位数x,y之和，其中x由m-1个1和1个0组成，y = b - x。LS算法对字典压缩和LZSS压缩后的结果要进行如上形式的编码。考虑两个m位数可以表示的最大数，显然，当y全部为1时表示的数最大，这个数为1...(m-1个1)01。为了要分解b，首先要确定m的值，显然m不会大于b的位数n，m也不会小于n-1，因此m的取值只有两个n和n-1。两个m位数表示的最大值只比m+1位数能表示的最大值1...(m+1个1)小2，所以对于大多数n位数，其m取值为n-1。
由于目前常见的windows系统下整型值为32位，并且算法中一般很难出现比较大的数值，因此限定需分解的数最多为32位。可以用如下代码判断指定值的位数n：
int bit_count(unsigned int value)
{
int count = 0;
do
{
value >>= 1;
count++;
} while (value != 0);
return count;
}
获得value的位数n之后只需要判断一下value与2^n - 3的关系，如果value <= 2^n - 3则用n-1位表示，否则用n位表示。
int n = bit_count(value);
unsigned int edge = ~0;
// 2^n - 1
edge >>= sizeof(unsigned int) * 8 - n;
int m = (value <= (int)(edge - 2)) ? n - 1 : n;
取得m之后获得x,y就非常简单了
unsigned int x = (~0 >> (sizeof(unsigned int) * 8 - m)) & ~1;
unsigned int y = value - x;
四、实现
前面几部分分别分析了算法中的几个部分，但是要将这些组合起来形成实用的程序还需要处理一些额外的问题。最大的问题出在LZSS算法上。
LZSS算法最大的问题是速度，每次都需要向前搜索到原文开头，对于较长的原文需要的时间是不可忍受的。为了在压缩较长的原文时有可以忍受的速度，就需要对向前搜索的长度有所限制，比如最多向前搜索10k字节。也可以考虑在搜索时遇到第一个匹配的就输出，而不是找一个最大匹配的。另外还可以限制最大匹配长度，比如最多匹配128字节，即使还可以继续匹配下去也不再匹配了。另外匹配算法的改进对整个LZSS算法影响也很大，不过在这里不打算讨论这个问题。
另外，还需要考虑如何区分字节和(偏移, 长度)二元组，因为编码可以编超过255的数，而字节最大只有255，因此将偏移加256之后可以与字节区分开来，而解压的时候只需要对大于256的数减去256当偏移使用即可。对于长度，显然如果长度小于3对于压缩不合算，而输出的时候数越小占用的位数越小，所以将长度减去3再编码可以略微增大压缩率。
将字典中每项的值随便设置只保证各项值不重复即可忽略掉字典压缩，但是由于字典压缩本来就不怎么复杂，所以不建议省去这一步。而LZSS算法更是可以完全忽略掉。将两种压缩都忽略之后可以写出一个非常简单的伪压缩程序，可以应对部分不压缩就不能使用的文件。
生成压缩字典的时机可以是原文也可以是LZSS压缩后没有被压缩的部分。统计原文生成压缩字典算法简单，不需要识别哪些是被LZSS压缩过的，但是可能统计中高频的部分在LZSS压缩后反而成了低频的，在压缩率上有所损失。如果统计LZSS压缩的中间结果，就需要考虑如何存储这个中间结果，因为识别偏移和字节值是不可能的。根据编码后的情形，考虑中间结果用整型存储，对于偏移在原值上加256，这样带来的问题是中间结果可能会膨胀大约300%，即使做一些限制使用短整型存储，也可能多消耗100%的存储空间。另外一种解决方案可以使用转义符实现，比如用0xf0 0x00作为转义符，0xf0的选择要选择不容易出现值，而0x00选择一个跟0xf0不同的任意值即可。使用规则是遇到原文中的0xf0则输出0xf0 0xf0，如果需要输出(偏移, 长度)二元组则输出0xf0 0x00 偏移(整型) 长度(整型)。在读取时则判断0xf0后是否跟着另外一个0xf0，如果是则当作字节0xf0读取，如果后面跟着0x00则其后两个整型值分别为偏移和长度。其实0x00的作用就是保证在输出(偏移, 长度)二元组时不会遇到两个连续的0xf0，如果能保证偏移的首字节值不会取到0xf0则不必用0x00这个字节，但是这个涉及到整型的存储方式，处理起来略有难度，不如用一个额外的字节消除这个麻烦。
有了上面几部分的内容，写一个LS的压缩算法就不是很困难了，对于其中一些实现中的问题也做了简单的讨论，提出了一些解决方案，在编程的过程中也有一些更有效率的方法，不过这里主要讨论原理，因此没有进一步的讨论，读者可以自己思考。
[ 本帖最后由 东方无翼 于 2006-10-23 11:40 编辑 ]
