++++++++++++ 求 解 （另外开帖给到300 分） ++++++++++++++

Question

我的想法是这样的:
把最大数减去最小数, 这个结果数最少可以用多少位表示. 即用这个
位数去表示你的数据. 我想这是理论上的最大压缩. 因为你数据的特
殊性:没有重复. 我想再想压缩,从理论上说不过去. 因为,位数如果再少,它不能表示这么多
数据.它已经是二进制的了.比如: 0-4096, 那么现在你每12bit表示一位数.
10 - 33778, 那么现在你每15bit表示一位数. 当然,前面可以用几个
字节表示位数及最小数. 这样:后续的数据0即为10, 11为21(每15bit取一数据)
其它类推.请讨论. 

Answer 1

试试这个算法！压缩字符串有效。
word
compress_block (
    const byte *src,
    byte *dst,
    word src_size)
{
    static short
          Hash [4096];
    short SymbolAddress;
    word  Key;
    word  Size;
    byte  Bit = 0;
    word  Command = 0;
    word  src_index = 0;
    word  dst_size = 3;
    word  HeaderIndex = 1;    dst [0] = FLAG_COMPRESS;
    for (Key = 0; Key < 4096; Key++)
        Hash [Key] = -1;    while ((src_index < src_size) && (dst_size <= src_size))
      {
        if (Bit > 15)
          {
            dst [HeaderIndex]     = (byte) ((Command >> 8) & 0x00ff);
            dst [HeaderIndex + 1] = (byte) ( Command       & 0x00ff);
            HeaderIndex = dst_size;
            dst_size += 2;
            Bit = 0;
          }
        for (Size = 1;; Size++)
            if ((word) (src_index + Size) >= src_size
            || (src [src_index] != src [src_index + Size])
            || (Size >= 0x0fff))
                break;        if (Size >= 16)
          {
            dst [dst_size++] = 0;
            dst [dst_size++] = (byte) (((word) (Size - 16) >> 8) & 0x00ff);
            dst [dst_size++] = (byte) ((Size - 16) & 0x00ff);
            dst [dst_size++] = src [src_index];
            src_index += Size;
            Command = (Command << 1) + 1;
          }
        else
        if (get_match (src, src_index, src_size,
                       Hash, &Size, &SymbolAddress) != 0)
          {
            Key = ((src_index - SymbolAddress) << 4) + (Size - 3);
            dst [dst_size++] = (byte) ((Key >> 8) & 0x00ff);
            dst [dst_size++] = (byte) (Key & 0x00ff);
            src_index += Size;
            Command = (Command << 1) + 1;
          }
        else
          {
            dst [dst_size++] = src [src_index++];
            Command = (Command << 1);
          }
        Bit++;
      }
    Command <<= (16 - Bit);
    dst [HeaderIndex]     = (byte) ((Command >> 8) & 0x00ff);
    dst [HeaderIndex + 1] = (byte) ( Command       & 0x00ff);     if (dst_size > src_size)
      {
         for (dst_size = 0; dst_size < src_size; dst_size++)
             dst [dst_size + 1] = src [dst_size];
         dst [0] = FLAG_COPY;
         return (src_size + 1);
       }
     return (dst_size);
}

Answer 2

bluebearboy(bluebearboy)非常感谢我马上去试大家继续讨论啊

Answer 3

#define FLAG_COPY             0x80
#define FLAG_COMPRESS         0x40/*  -------------------------------------------------------------------------
 *  get_match -- local
 *
 *  Finds a match for the bytes at the specified offset.
 */static byte get_match (const byte *source, word ptr, word source_size,
                       short *hash, word *size, short *pos)
{
    word hash_value;    hash_value = (word) (40543L * (long) ((((source [ptr]      << 4) ^
                                             source [ptr + 1]) << 4) ^
                                             source [ptr + 2]) >> 4) & 0xfff;
    *pos = hash [hash_value];
    hash [hash_value] = ptr;
    if ((word) ((*pos != -1) && ((ptr - *pos)) < 4096U))
      {
        for (*size = 0;; (*size)++)
            if ((*size >= 18)
            || ((word) (ptr + *size) >= source_size)
            || (source [ptr + *size] != source [*pos + *size]))
                break;        return (byte) (*size >= 3);
      }
    return (FALSE);
}