经常看到.gz结尾的压缩文件，大家知道使用什么压缩软件弄的？？
比如：cint-5.16.19-source.tar.gz

gzip压缩算法
1 gzip所使用压缩算法的基本原理

　　 gzip 对于要压缩的文件，首先使用lz77算法进行压缩，对得到的结果再使用huffman编码的方法进行压缩。所以我们分别对lz77和huffman编码的原理进行说明。

　　 1.1 ... 1.2 ...

　　 2 gzip压缩算法实现方法

　　 2.1 LZ77算法的gzip实现

　　首先，gzip 从要压缩的文件中读入64KB的内容到一个叫window的缓冲区中。为了简单起见，我们以32KB以下文件的压缩为例做说明。对于我们这里使用32KB以下文件，gzip将整个文件读入到window缓冲区中。然后使用一个叫strstart的变量在window数组中，从0开始一直向后移动。strstart在每一个位置上，都在它之前的区域中，寻找和当前strstart开始的串的头3个字节匹配的串，并试图从这些匹配串中找到最长的匹配串。

　　如果当前的strstart开始的串，可以找到最少为3个字节的匹配串的话，当前的strstart开始的匹配长度那么长的串，将会被一个<匹配长度,到匹配串开头的距离>对替换。

　　如果当前的strstart开始的串，找不到任何的最少为3个字节的匹配串的话，那么当前strstart的所在字节将不作改动。

　　为了区分是一个<匹配长度,到匹配串开头的距离>对，还是一个没有被改动的字节，还需要为每一个没有被改动的字节或者<匹配长度,到匹配串开头的距离>对，另外再占用一
　　位，来进行区分。这位如果为1，表示是一个<匹配长度,到匹配串开头的距离>对，这位如果为0，表示是一个没有被改动的字节。

　　现在来说明一下，为什么最小匹配为3个字节。这是由于，gzip 中，<匹配长度,到匹配串开头的距离>对中，"匹配长度"的范围为3-258，也就是256种可能值，需要8bit来保存。"到匹配串开头的距离"的范围为0-32K，需要15bit来保存。所以一个<匹配长度,到匹配串开头的距离>对需要23位，差一位3个字节。如果匹配串小于3个字节的话，使用<匹配长度,到匹配串开头的距离>对进行替换，不但没有压缩，反而还会增大。所以保存<匹配长度,到匹配串开头的距离>对所需要的位数，决定了最小匹配长度至少要为3个字节。

　　下面我们就来介绍gzip如何实现寻找当前strstart开始的串的最长匹配串。

　　如果每次为当前串寻找匹配串时，都要和之前的每个串的至少3个字节进行比较的话，那么比较量将是非常非常大的。为了提高比较速度，gzip使用了哈希表。这是gzip实现LZ77的关键。这个哈希表是一个叫head的数组（后面我们将看到为什么这个缓冲区叫head）。gzip对windows中的每个串，使用串的头三个字节，也就是strstart,strstart 1,strstart 2，用一个设计好的哈希函数来进行计算，得到一个插入位置ins_h。也就是用串的头三个字节来确定一个插入位置。然后把串的位置，也就是 strstart的值，保存在head数组的第ins_h项中。我们马上就可以看到为什么要这样做。head数组在没有插入任何值时，全部为0。
当某处的当前串的三个字节确定了一个ins_h，并把当时当前串的位置也就是当时的strstart保存在了head[ins_h]中。之后另一处，当另一处的当前串的头三个字节，再为那三个字节时，再使用那个哈希函数来计算，由于是同样的三个字节，同样的哈希函数，得到的ins_h必然和前面得到的ins_h是相同的。于是就会发现head[ins_h]不为0。这就说明了，有一个头三个字节和自己相同的串把自己的位置保存在了这里，现在head[ins_h]中保存的值，也就是那个串的开始位置，我们就可以找到那个串，那个串至少前3个字节和当前串的前3个字节相同（稍后我们就可以看到这种说法不准确，这里是为了说明方便），我们可以找到那个串，做进一步比较，看到底能有多长的匹配。

　　我们现在来说明一下，相同的三个字节，通过哈希函数得到的ins_h必然是相同的。而不同的三个字节，通过哈希函数有没有可能得到同一个ins_h，我没有对这个哈希函数做研究，并不清楚，不过一般的哈希函数都是这样的，所以极大可能这里的也会是这种情况，即不同的三个字节，通过哈希函数有可能得到同一个ins_h，不过这并不要紧，我们发现有可能是匹配串之后，还会进行串的比较。

　　一个文件中，可能有很多个串的头三个字节都是相同的，也就是说他们计算得到的ins_h都是相同的，如何能保证找到他们中的每一个串呢？gzip使用一个链把他们链在一起。gzip每次把当前串的位置插入head的当前串头三个字节算出的ins_h处时，都会首先把原来的head[ins_h]的值，保存到一个叫prev的数组中，保存的位置就在现在的strstart处。这样当以后某处的当前串计算出ins_h，发现head[ins_h]不空时，就可以到prev[ head[ins_h] ]中找到更前一个的头三个字节相同的串的位置。对此我们举例说明。

　　例，串
　　 0abcdabceabcfabcg
　　 ^^^^^^^^^^^^^^^^^
　　 01234567890123456

　　整个串被压缩程序处理之后。

　　由abc算出ins_h。
　　这时的head[ins_h]中为 13,即"abcg"的开始位置。
　　这时prev[13]中为 9，即"abcfabcg"的开始位置。
　　这时prev[9]中为 5，即"abceabcfabcg"的开始位置。
　　这时prev[5]中为 1，即"abcdabceabcfabcg"的开始位置。
　　这时prev[1]中为 0。

　　我们看到所有头三个字母为abc的串，被链在了一起，从head可以一直找下去，直到找到0。

　　现在我们也就知道了，三个字节通过哈希函数计算得到同一ins_h的所有的串被链在了一起，head[ins_h]为链头，prev数组中放着的更早的串。这也就是head和prev名称的由
　　来。

　　 gzip寻找匹配串的另外一个值得注意的实现是，延迟匹配。会进行两次尝试。比如当前串为str,那么str发生匹配以后，并不发生压缩，还会对str 1串进行匹配，然后看哪种
　　匹配效果好。

　　例子 ...
从这个例子中我们就看到了做另外一次尝试的原因。如果碰到的一个匹配就使用了的话，可能错过更长匹配的机会。现在做两次会有所改善。

　　 ...

　　 2.2 问题讨论

　　我在这里对gzip压缩算法做出了一些说明，是希望可以和对gzip或者压缩解压缩感兴趣的朋友进行交流。
　　我对gzip的了解要比这里说的更多一些，也有更多的例子。如果哪位朋友愿意对下面的问题进行研究，以及其他压缩解压缩的问题进行研究，来这里http://jiurl. 和我交流的话，我也愿意就我知道的内容进行更多的说明。

　　下面是几个问题

　　这种匹配算法，即用3个字节(最小匹配)来计算一个整数，是否比用串比较来得高效，高效到什么程度。

　　哈希函数的讨论。不同的三个字节，是否可能得到同一个ins_h。ins_h和计算它的三个字节的关系。

　　几次延迟尝试比较好？

　　用延迟，两次尝试是否对压缩率的改善是非常有限的？

　　影响lz77压缩率的因素。

　　压缩的极限。

　　 2.3 ...

　　 3 gzip源码分析

　　 main() 中调用函数 treat_file() 。
　　 treat_file() 中打开文件，调用函数 zip()。注意这里的 work 的用法，这是一个函数指针。
　　 zip() 中输出gzip文件格式的头，调用 bi_init，ct_init，lm_init，
　　其中在lm_init中将 head 初始化清0。初始化strstart为0。从文件中读入64KB的内容到window缓冲区中。
　　由于计算strstart=0时的ins_h，需要0,1,2这三个字节和哈希函数发生关系，所以在lm_init中，预读0,1两个字节，并和哈希函数发生关系。

　　然后lm_init调用 deflate()。
　　 deflate() gzip的LZ77的实现主要deflate()中。

7-Zip是当前拥有较高压缩比的开源压缩工具，采用7-Zip格式压缩文件压缩率要比普通ZIP文件高30％～50％。LZMA是著名压缩算法Lz77的改进版本，它最大程度地提高了压缩率，并保留了解压时的高速度和低内存需求等优点。7-Zip程序的默认压缩算法就是LZMA。

测试压缩一个425K的文件需要9.4秒，压缩后的文件为177K。
http://blog.

/*********************************************************************
*
*   Project description:
*       Lz77 compression/decompression algorithm.
*
*********************************************************************/


#include <windows.h>
#include <conio.h>
#include <stdio.h>
#include <assert.h>

#define OFFSET_CODING_LENGTH    (10)
#define MAX_WND_SIZE            1024
//#define MAX_WND_SIZE          (1<<OFFSET_CODING_LENGTH)
#define OFFSET_MASK_CODE        (MAX_WND_SIZE-1)

const ULONG     m=3;


UCHAR   __buffer1__[0x200000];
UCHAR   __buffer2__[0x200000];


////////////////////////////////////////////////////////////////////////////////

void
Write1ToBitStream(
   PUCHAR  pBuffer,
   ULONG   ulBitOffset
   )
{
   ULONG   ulByteBoundary;
   ULONG   ulOffsetInByte;

   ulByteBoundary = ulBitOffset>>3 ;
   ulOffsetInByte = ulBitOffset&7;

   *(pBuffer+ulByteBoundary) |= (1<<ulOffsetInByte);
}

void
Write0ToBitStream(
   PUCHAR  pBuffer,
   ULONG   ulBitOffset
   )
{
   ULONG   ulByteBoundary;
   ULONG   ulOffsetInByte;

   ulByteBoundary = ulBitOffset>>3 ;
   ulOffsetInByte = ulBitOffset&7;

   *(pBuffer+ulByteBoundary) &= (~(1<<ulOffsetInByte));
}

ULONG
ReadBitFromBitStream(
   PUCHAR  pBuffer,
   ULONG   ulBitOffset
   )
{
   ULONG   ulByteBoundary;
   ULONG   ulOffsetInByte;

   ulByteBoundary = ulBitOffset>>3 ;
   ulOffsetInByte = ulBitOffset&7;

   return ((*(PULONG)(pBuffer+ulByteBoundary))>>ulOffsetInByte)&1 ;
}


ULONG WINAPI
WriteGolombCode(
   ULONG   x,
   PUCHAR  pBuffer,
   ULONG   ulBitOffset
   )
{
   ULONG           q, r;
   int             i;

   q = (x-1)>>m;
   r = x-(q<<m)-1;

   for(i=0; (ULONG)i<q; i++, ulBitOffset++)
   {
       Write1ToBitStream(pBuffer, ulBitOffset);
   }
   Write0ToBitStream(pBuffer, ulBitOffset);
   ulBitOffset++;

   for(i=0; i<m; i++, ulBitOffset++)
   {
       if( (r>>i)&1 )
       {
           Write1ToBitStream(pBuffer, ulBitOffset);
       }
       else
       {
           Write0ToBitStream(pBuffer, ulBitOffset);
       }
   }

   return m+q+1;
}


ULONG
ReadGolombCode(
   PULONG  pulCodingLength,
   PUCHAR  pBuffer,
   ULONG   ulBitOffset
   )
{
   ULONG   q, r;
   ULONG   bit;
   int i;

   for(q=0; ;q++)
   {
       bit = (ULONG)ReadBitFromBitStream(pBuffer, ulBitOffset);
       ulBitOffset++;
       if( !bit )
       {
           break;
       }
   }


   for(i=0, r=0; (ULONG)i<m; i++, ulBitOffset++)
   {
       bit = (ULONG)ReadBitFromBitStream(pBuffer, ulBitOffset);
       bit <<= i;
       r |= bit;
   }

   *pulCodingLength = m + q + 1;

   return r+(q<<m)+1;
}


ULONG
CompareStrings(
   PUCHAR  string1,
   PUCHAR  string2,
   ULONG   length
   )
{
   ULONG       i;
   PUCHAR      p1, p2;

   p1 = string1;
   p2 = string2;

   for(i=0; i<length; i++)
   {
       if( *p1==*p2 )
       {
           p1++;
           p2++;
       }
       else
       {
           break;
       }
   }

   return p1-string1;
}


void WINAPI
FindLongestSubstring(
   PUCHAR  pSourceString,
   PUCHAR  pString,
   ULONG   ulSourceStringLength,
   PULONG  pulSubstringOffset,
   PULONG  pulSubstringLength
   )
{
   PUCHAR  pSrc;

   ULONG   offset, length;

   ULONG   ulMaxLength;


   *pulSubstringOffset = offset = 0;
   *pulSubstringLength = 0;

   if( NULL==pSourceString || NULL==pString )
   {
       return;
   }

   ulMaxLength = ulSourceStringLength;
   pSrc = pSourceString;

   while( ulMaxLength>0 )
   {
       length = CompareStrings(pSrc, pString, ulMaxLength);

       if( length>*pulSubstringLength )
       {
           *pulSubstringLength = length;
           *pulSubstringOffset = offset;
       }

       pSrc++;
       offset++;
       ulMaxLength--;
   }
}


/*
void
FindLongestSubstring(
   PUCHAR  pSourceString,
   PUCHAR  pString,
   ULONG   ulSourceStringLength,
   PULONG  pulSubstringOffset,
   PULONG  pulSubstringLength
   )
{
   PUCHAR  pCurrentOffset;
   PUCHAR  p1, p2;

   ULONG   offset, length;

   pCurrentOffset = pSourceString;

   *pulSubstringOffset = offset = 0;
   *pulSubstringLength = length = 0;

   while( pCurrentOffset<pSourceString+ulSourceStringLength )
   {
       p1 = pCurrentOffset;
       p2 = pString;


       if( *p1==*p2 )
       {
           while( p1<pSourceString+ulSourceStringLength && *p1==*p2 )
           {
               p1++;
               p2++;
           }

           length = p1 - pCurrentOffset;
       }
       else
       {
           length = 0;
       }

       if( length>*pulSubstringLength )
       {
           *pulSubstringLength = length;
           *pulSubstringOffset = (ULONG)pCurrentOffset - (ULONG)pSourceString;
       }

       pCurrentOffset++;
   }
}
*/


void
WriteBits(
   PUCHAR  pDataBuffer,
   ULONG   ulOffsetToWrite,
   ULONG   ulBits,
   ULONG   ulBitLength
   )
{
   ULONG   ulDwordsOffset;
   ULONG   ulBitsOffset, ulBitsRemained;

   ulDwordsOffset = ulOffsetToWrite>>5;
   ulBitsOffset = ulOffsetToWrite&31;
   ulBitsRemained = 32 - ulBitsOffset;

   if( 0==ulBitsOffset )
   {
       *((PULONG)pDataBuffer+ulDwordsOffset) = ulBits;
   }
   else if( ulBitsRemained>=ulBitLength )
   {
       *((PULONG)pDataBuffer+ulDwordsOffset) |= (ulBits<<ulBitsOffset);
   }
   else
   {
       *((PULONG)pDataBuffer+ulDwordsOffset) |= (ulBits<<ulBitsOffset);
       *((PULONG)pDataBuffer+ulDwordsOffset+1) = ulBits>>ulBitsRemained;
   }
}

void
ReadBits(
   PUCHAR  pDataBuffer,
   ULONG   ulOffsetToRead,
   PULONG  pulBits
   )
{
   ULONG   ulDwordsOffset;
   ULONG   ulBitsOffset, ulBitsLength;

   ulDwordsOffset = ulOffsetToRead>>5;
   ulBitsOffset = ulOffsetToRead&31;
   ulBitsLength = 32 - ulBitsOffset;


   *pulBits = *((PULONG)pDataBuffer+ulDwordsOffset);
   if( 0!=ulBitsOffset )
   {
       (*pulBits) >>= ulBitsOffset;
       (*pulBits) |= (*((PULONG)pDataBuffer+ulDwordsOffset+1))<<ulBitsLength;
   }
}

void
lz77compress(
   PUCHAR  pDataBuffer,
   ULONG   ulDataLength,
   PUCHAR  pOutputBuffer,
   PULONG  pulNumberOfBits
   )
{
   LONG        iSlideWindowPtr;
   ULONG       ulBytesCoded;
   ULONG       ulMaxlength;
   PUCHAR      pSlideWindowPtr;
   PUCHAR      pUnprocessedDataPtr;

   ULONG   offset;
   ULONG   length;
   ULONG   ulCodingLength;

   ULONG   ulBitOffset;
   UCHAR   cc;

   int     i;

   iSlideWindowPtr = -MAX_WND_SIZE;
   pSlideWindowPtr = NULL;
   ulBitOffset = 0;
   ulBytesCoded = 0;

   while( ulBytesCoded<ulDataLength )
   {
       if( iSlideWindowPtr>=0 )
       {
           pSlideWindowPtr = pDataBuffer+iSlideWindowPtr;
           ulMaxlength = MAX_WND_SIZE;

       }
       else if( iSlideWindowPtr>=-MAX_WND_SIZE )
       {
           pSlideWindowPtr = pDataBuffer;
           ulMaxlength = MAX_WND_SIZE + iSlideWindowPtr;
       }
       else
       {
           pSlideWindowPtr = NULL;
           ulMaxlength = 0;
       }

       pUnprocessedDataPtr = pDataBuffer + ulBytesCoded;
       if( ulMaxlength>ulDataLength-ulBytesCoded )
       {
           ulMaxlength = ulDataLength-ulBytesCoded;
       }

       FindLongestSubstring(
           pSlideWindowPtr,
           pUnprocessedDataPtr,
           ulMaxlength,
           &offset,
           &length
           );

       assert( length<=MAX_WND_SIZE );
       assert( offset<MAX_WND_SIZE );

       if(length>1)
       {

           Write1ToBitStream(pOutputBuffer, ulBitOffset);
           ulBitOffset++;

           for(i=0; i<OFFSET_CODING_LENGTH; i++, ulBitOffset++)
           {
               if( (offset>>i)&1 )
               {
                   Write1ToBitStream(pOutputBuffer, ulBitOffset);
               }
               else
               {
                   Write0ToBitStream(pOutputBuffer, ulBitOffset);
               }
           }

           ulCodingLength = WriteGolombCode(length, pOutputBuffer, ulBitOffset);

           ulBitOffset += ulCodingLength;
           iSlideWindowPtr += length;
           ulBytesCoded += length;

       }
       else
       {
           Write0ToBitStream(pOutputBuffer, ulBitOffset);
           ulBitOffset++;

           cc = (*pUnprocessedDataPtr);
           for(i=0; i<8; i++, ulBitOffset++)
           {
               if( (cc>>i)&1 )
               {
                   Write1ToBitStream(pOutputBuffer, ulBitOffset);
               }
               else
               {
                   Write0ToBitStream(pOutputBuffer, ulBitOffset);
               }
           }

           iSlideWindowPtr++;
           ulBytesCoded++;
       }

   }

   if( ulBytesCoded!=ulDataLength )
   {
       assert(ulBytesCoded==ulDataLength);
   }

   *pulNumberOfBits = ulBitOffset;

}


void lz77decompress(
   PUCHAR  pDataBuffer,
   ULONG   ulNumberOfBits,
   PUCHAR  pOutputBuffer,
   PULONG  pulNumberOfBytes
   )
{
   LONG        iSlideWindowPtr;
   PUCHAR      pSlideWindowPtr;

   ULONG   length, offset;
   ULONG   bit;
   UCHAR   cc;
   int     i;

   ULONG   ulBytesDecoded;
   ULONG   ulBitOffset;

   ULONG   ulCodingLength;
   PUCHAR  pWrite;

   iSlideWindowPtr = -MAX_WND_SIZE;
   pWrite = (PUCHAR)pOutputBuffer;
   ulBitOffset = 0;
   ulBytesDecoded = 0;


   while( ulBitOffset<ulNumberOfBits )
   {
       bit = ReadBitFromBitStream(pDataBuffer, ulBitOffset);
       ulBitOffset++;

       if( bit )
       {
           if( iSlideWindowPtr>=0 )
           {
               pSlideWindowPtr = pOutputBuffer + iSlideWindowPtr;

           }
           else if( iSlideWindowPtr>=-MAX_WND_SIZE )
           {
               pSlideWindowPtr = pOutputBuffer;
           }
           else
           {
               pSlideWindowPtr = NULL;
           }


           for(i=0, offset=0; i<OFFSET_CODING_LENGTH; i++, ulBitOffset++)
           {
               bit = ReadBitFromBitStream(pDataBuffer, ulBitOffset);
               offset |= (bit<<i);
           }

           length= ReadGolombCode(&ulCodingLength, pDataBuffer, ulBitOffset);

           assert(offset<MAX_WND_SIZE);

           if( length>MAX_WND_SIZE )
           {
               assert(length<=MAX_WND_SIZE);
           }
           ulBitOffset += ulCodingLength;

           RtlMoveMemory(pWrite, pSlideWindowPtr+offset, length);
           pWrite+=length;
           iSlideWindowPtr+=length;
           ulBytesDecoded+=length;
       }
       else
       {
           for(i=0, cc=0; i<8 ; i++, ulBitOffset++)
           {
               bit = ReadBitFromBitStream(pDataBuffer, ulBitOffset);
               cc |= ((UCHAR)bit<<i);
           }

           *pWrite++ = cc;
           iSlideWindowPtr++;
           ulBytesDecoded++;
       }

   }

   *pulNumberOfBytes = ulBytesDecoded;
}

extern "C"
void WINAPI
LZ77Compress(
   PUCHAR  __pDataBuffer,
   ULONG   __ulDataLength,
   PUCHAR  __pOutputBuffer,
   PULONG  __pulNumberOfBits
   );

extern "C"
void WINAPI
LZ77Decompress(
   PUCHAR  __pDataBuffer,
   ULONG   __ulNumberOfBits,
   PUCHAR  __pOutputBuffer,
   PULONG  __pulNumberOfBytes
   );

int
main(
   int     argc,
   char    *argv[]
   )
{
   FILE    *fp=NULL;
   FILE    *fp1;
   ULONG   fsize;
   ULONG   ulNumberOfBits;
   ULONG   ulFileCompressedSize;
   ULONG   ulFileDecompressedSize;
   SYSTEMTIME      t1, t2;

   if( 3!=argc )
   {
       printf("Usage: lz77 [/c | /d] filename\n");
       return -1;
   }



//  char    s1[]="abcdabcdefgabcdefaffasda";
//  ULONG   a, b;
//  FindLongestSubstring((PUCHAR)s1, (PUCHAR)s1+11, 11,&a, &b );
//  return 0;

   fp = fopen(argv[2], "rb");
   if( !fp )
   {
       return -1;
   }

   fseek(fp, 0, SEEK_END);
   fsize = ftell(fp);
   fseek(fp, 0, SEEK_SET);

   fread(__buffer1__, 1, fsize, fp);


   GetSystemTime(&t1);
   lz77compress(__buffer1__, fsize, __buffer2__, &ulNumberOfBits);
   //LZ77Compress(__buffer1__, fsize, __buffer2__, &ulNumberOfBits);
   GetSystemTime(&t2);
   ulFileCompressedSize = ((ulNumberOfBits+7)>>3);

   fp1=fopen("peinfo.c_", "wb+");
   if( !fp1 )
   {
       goto l1;
   }
   fwrite(__buffer2__, 1, ulFileCompressedSize, fp1);
   fclose(fp1);

   RtlZeroMemory(__buffer1__, sizeof(__buffer1__));

   lz77decompress(__buffer2__, ulNumberOfBits, __buffer1__, &ulFileDecompressedSize);
   //LZ77Decompress(__buffer2__, ulNumberOfBits, __buffer1__, &ulFileDecompressedSize);
   fp1=fopen("peinfo.d_", "wb+");
   if( !fp1 )
   {
       goto l1;
   }
   fwrite(__buffer1__, 1, ulFileDecompressedSize, fp1);
   fclose(fp1);

l1:
   if( fp )
   {
       fclose(fp);
   }

   ULONG   milliS;

   milliS = ((t2.wHour - t1.wHour)*3600 + (t2.wMinute-t1.wMinute)*60 + (t2.wSecond-t1.wSecond)) * 1000 + (t2.wMilliseconds-t1.wMilliseconds);
   printf("Totally %ld milliseconds elapsed!\n\n", milliS);

   printf("Press any key to exit!\n");
   getch();

   return 0;
}

最近终于有空研究研究E*F的K*KYU2。
和预料到的一样仍然是广泛使用LZ77，而且是毫不改变地使用LZ77……但是，时代进步了，图片文件都是真彩色的了，大小变大了3倍，仍然使用LZ77的代价就是速度……大家都知道LZ77的特点就是解压超快，压缩巨慢（不然就不会有LZW这种不伦不类的算法出来了……）
在png的相关网站上查找了一下优化方案，自己写了一下优化代码，虽然目前速度仍然不能很让人满意（在双核的机器上压缩一个160多兆的文件用了60多秒），但是勉强可以用于实际应用了。贴出来和大家分享。如果要进一步优化，估计要玩一些trick，或是借助于指令级别的。
以下讨论是基于4096字节定长窗口的字典的LZ77，字节组织是每bit表示查表或是原数据；查表是2字节，前16位表示索引，后16位表示长度，因此最长的序列只能有15字节。优化的思路是哈希表。
由环境可以看出，低于3个字节的码序列是不需要查表保存的，因此码的最短长度是3个字节。使用一个哈希算法将之转化成1个字节的哈希码。这种哈希码共有256个。当在查表前，首先要计算出当前字节及后面两个字节组成的序列的哈希码，然后在哈希码表中查得第一条匹配记录。当然，即使哈希码匹配，3字节并不一定完全一样，这之后还是需要按字节比较。但这可以提前淘汰大部分的数据。匹配后，再查下一条记录。
优化的负担是额外增加了一个哈希码头指针表和一个链表。每一个字节在字典中的更新都会造成它本身及前面两个字节处共3个字节的哈希码变化，即表项删除和增加。为了使这种删除和增加更有效率，做成了双向链表的形式（实际测试下来比单向节省约一半时间）。当然这里的链表是以数组形式实现的，不需要动态分配空间，否则所带来的负担将是不可承受的。字典定义如下：

typedef struct _tagLz77Dict ...{
    int     hash_start[256];
    int     hash_next[4096];
    int     hash_prev[4096];
    char    dict[4096];
} lz77_dict, *p_lz77_dict;

其中，hash_start是256个哈希码的首码索引。hash_next是每个哈希码的下一个编码，hash_prev是每个哈希码的前一个编码。均以-1表示无效。
字典初始化函数如下：

void init_dict(p_lz77_dict pdic)
...{
    int i;
    memset(pdic->dict, 0, 4096);
    for (i = 0; i < 256; ++i) pdic->hash_start[i] = -1;
    pdic->hash_start[HASH(0, 0, 0)] = 4096-16;
    for (i = 0; i < 4096; ++i) ...{
        if (i < 4096-16) ...{
            pdic->hash_next[i] = -1;
            pdic->hash_prev[i] = -1;
        } else ...{
            pdic->hash_next[i] = (i+1);
            pdic->hash_prev[i] = (i-1);
        }
    }
    pdic->hash_prev[0] = -1;
    pdic->hash_next[4095] = -1;
}

初始值仅后面16个码可用。
删除和增加哈希码函数：

void remove_dict_pos(p_lz77_dict pdic, int pos)
...{
    char a, b, c;
    unsigned char hash;
    int old_pos = pos;
    int s, last;
    a = pdic->dict[pos++];
    pos &= 0xFFF;
    b = pdic->dict[pos++];
    pos &= 0xFFF;
    c = pdic->dict[pos++];
    pos &= 0xFFF;
    hash = HASH(a, b, c);
    last = pdic->hash_start[hash];
    if (last == old_pos) ...{
        // head?
        last = pdic->hash_next[old_pos];
        pdic->hash_start[hash] = last;
        if (last >= 0) ...{
            pdic->hash_prev[last] = -1;
        }
    } else ...{
        last = pdic->hash_prev[old_pos];
        s = pdic->hash_next[old_pos];
        if (last >= 0) ...{
            pdic->hash_next[last] = s;
        }
        if (s >= 0) ...{
            pdic->hash_prev[s] = last;
        }
        pdic->hash_prev[old_pos] = -1;
    }
}
// add a position's hash rec
void add_dict_pos(p_lz77_dict pdic, int pos)
...{
    char a, b, c;
    unsigned char hash;
    int old_pos = pos;
    int last;
    a = pdic->dict[pos++];
    pos &= 0xFFF;
    b = pdic->dict[pos++];
    pos &= 0xFFF;
    c = pdic->dict[pos++];
    pos &= 0xFFF;
    hash = HASH(a, b, c);
    last = pdic->hash_start[hash];
    pdic->hash_start[hash] = old_pos;
    if (last >= 0) pdic->hash_prev[last] = old_pos;
    pdic->hash_next[old_pos] = last;
}

哈希算法随便选了一个（注意尽量不要全是3个字节异或，这样会使效率受影响，因为在实际应用中3个字节中有两个以上相同的比较多）

#define HASH(a, b, c)  (((unsigned char)a) + ((unsigned char)b) ^ ((unsigned char)c))

最后是解码函数主体：

// dest_buf should allocate size+size/8 bytes at least
// optimized algorithm
char* fast_lz77_encode(const char* buf, int size, int* dest_size)
...{
    nsg_auto_detect(__FUNCTION__);
    char* dest = (char*)malloc(size + size/8 + 1);
    char* org_dest = dest;
    lz77_dict dict;
    int dict_start = 4096 - 16;
    int left = size;
    unsigned char bits = 0;
    int bitcount = 8;
    char* bits_pos = dest;
    if (size == 0) ...{
        free(dest);
        return NULL;
    }
    init_dict(&dict);
    dest++;
    while(left > 0) ...{
        int max_len = 0;
        int table_index = 0;
        int i;
        if (left >= 3) ...{
            unsigned char hash = HASH(buf[0], buf[1], buf[2]);
            int offset = dict.hash_start[hash];
            if (offset >= 0) ...{
                int len = 0;
                while (offset >= 0) ...{
                    int pos = offset;
                    len = 0;
                    while (len < 15) ...{
                        if (dict.dict[pos++] != buf[len]) break;
                        pos &= 0xFFF;
                        ++len;
                    }
                    if (len > max_len) ...{
                        table_index = (offset - len) & 0xFFF;
                        max_len = len;
                    }
                    offset = dict.hash_next[offset];
                }
            }
        }
        if (max_len >= 3) ...{
            int i;
            int pos = dict_start - 2;
            int old_pos;
            *(unsigned short*)dest = (table_index << 4) | max_len;
            if (pos < 0) pos += 4096;
            old_pos = pos;
            // remove previous 2, next 2 dict
            for (i = max_len + 2; i >= 0; --i) ...{
                remove_dict_pos(&dict, pos++);
                pos &= 0xFFF;
            }
            // update dict
            for (i = 0; i < max_len; ++i ) ...{
                dict.dict[dict_start++] = buf[i];
                dict_start &= 0xFFF;
            }
            pos = old_pos;
            for (i = max_len + 2; i >= 0; --i) ...{
                add_dict_pos(&dict, pos++);
                pos &= 0xFFF;
            }
            dest += 2;
            buf += max_len;
            left -= max_len;
        } else ...{
            int pos = dict_start - 2;
            int i;
            /**//* bits |= 0; */  /**//* not necessary */
            if (pos < 0) pos += 4096;
            for (i = 0; i < 3; ++i ) ...{
                remove_dict_pos(&dict, pos++);
                pos &= 0xFFF;
            }
            dict.dict[dict_start++] = *buf;
            dict_start &= 0xFFF;
            pos -= 3;
            if (pos < 0) pos += 4096;
            for (i = 0; i < 3; ++i ) ...{
                add_dict_pos(&dict, pos++);
                pos &= 0xFFF;
            }
            *dest++ = *buf++;
            --left;
        }
        if (--bitcount == 0) ...{
            // full
            bitcount = 8;
            *bits_pos = bits;
            bits_pos = dest++;
            bits = 0;
        }
        bits >>= 1;
    }
    *bits_pos = bits >> bitcount;
    *dest_size = dest - org_dest;
    return org_dest;
}

楼主你在说什么啊.... 怎么C语言都出来了 你是要介绍软件还是给我们上C语言课啊