变种LZ77数据无损压缩算法

　　这是我在学习字典压缩算法时自己设计的，采用64K固定窗口对数据进行分块压缩，编码时使用了变长偏移长度，变长匹配长度，哈希字典等对算法进行了优化，压缩率和压缩速度均比较理想，很适合用于网络传输中的数据实时压缩。

算法提供的两个外部调用函数：

// ---------------------------------------------------------------------------

// 使用LZ77压缩算法对数据进行压缩

// dst:压缩输出缓冲区（输出缓冲区长度至少应保留原始数据长度+128K）

// src:原始数据

// len:原始数据长度

// level:压缩等级（可选0 - 4，一般使用2）

// return 返回压缩后数据长度

// ---------------------------------------------------------------------------

int Lz77Compress(void *dst, void *src, int len, int level);

// ---------------------------------------------------------------------------

// 解压LZ7算法压缩过的数据

// dst:解压输出缓冲区

// src:压缩数据

// len:压缩数据长度

// return 返回解压后数据长度

// ---------------------------------------------------------------------------

int Lz77Decompress(void *dst, void *src, int len);

lz77.c

#ifdef WIN32

#include <windows.h>

#define malloc(s) HeapAlloc(GetProcessHeap(), 0, s)

#define free(p) HeapFree(GetProcessHeap(), 0, p)

#else

#include <stdlib.h>

#include <string.h>

#endif

#define MAXBITS 15

#define MINOFFSET 0x01

#define MINMATCH 0x03

#define MAXMATCH ((1 << 24) + MINMATCH)

#define MAXWND (1 << MAXBITS)

#define NIL 0xffff

#define M 3

#define MAX(a, b) ((a) > (b) ? (a) : (b))

#define MIN(a, b) ((a) < (b) ? (a) : (b))

typedef unsigned char UCHAR;

typedef unsigned short USHORT;

typedef unsigned long ULONG;

typedef struct _LZ77_MATCHINFO

{

ULONG len;

ULONG off;

} LZ77_MATCHINFO;

typedef struct _LZ77_RUNSTATE

{

ULONG wsize;

UCHAR *pwnd;

ULONG confine;

USHORT *head;

USHORT *prev;

ULONG nice;

} LZ77_RUNSTATE;

typedef struct _LZ77_IOSTATE

{

UCHAR *pbuf;

ULONG bytenum;

UCHAR bitnum;

UCHAR codelen;

} LZ77_INPUTS, LZ77_OUTPUTS;

// ---------------------------------------------------------------------------

// 计算用二进制表示指定数值至少需要多少位

// ---------------------------------------------------------------------------

static UCHAR log2(ULONG n)

{

UCHAR c, i;

if (n > 0xffff)

{

for (i = 16; n > ((ULONG)-1 >> (sizeof(ULONG) * 8 - i)); i++);

return i;

}

if (n & 0xff00)

{

if (n & 0xf000)

{

if (n & 0xc000)

{

if (n & 0x8000)

{

c = 16;

}

else

{

c = 15;

}

else

{

if (n & 0x2000)

{

c = 14;

}

else

{

c = 13;

}

else

{

if (n & 0x0c00)

{

if (n & 0x0800)

{

c = 12;

}

else

{

c = 11;

}

else

{

if (n & 0x0200)

{

c = 10;

}

else

{

c = 9;

}

else

{

if (n & 0x00f0)

{

if (n & 0x00c0)

{

if (n & 0x0080)

{

c = 8;

}

else

{

c = 7;

}

else

{

if (n & 0x0020)

{

c = 6;

}

else

{

c = 5;

}

else

{

if (n & 0x000c)

{

if (n & 0x0008)

{

c = 4;

}

else

{

c = 3;

}

else

{

if (n & 0x0002)

{

c = 2;

}

else

{

c = 1;

}

return c;

}

// ---------------------------------------------------------------------------

// 输出指定长度的二进制位，最大长度为sizeof(ULONG)

// ---------------------------------------------------------------------------

static void PutBits(LZ77_OUTPUTS *out, ULONG v, int num)

{

UCHAR *s = out->pbuf + out->bytenum;

ULONG i = 0;

ULONG temp = v & ~(-1 << num);

{

s[i] &= ~(-1 << out->bitnum);

s[i] |= (UCHAR)(temp << out->bitnum);

if (8 - out->bitnum >= num)

break;

s[i + 1] = (UCHAR)(temp >> (8 - out->bitnum));

temp >>= 8;

} while ((++i << 3) < (ULONG)num);

out->bitnum += (UCHAR)num;

out->bytenum += out->bitnum >> 3;

out->bitnum &= 7;

}

// ---------------------------------------------------------------------------

// 获取指定长度的二进制位，最大长度为sizeof(ULONG)

// ---------------------------------------------------------------------------

static ULONG GetBits(LZ77_INPUTS *in, int num)

{

UCHAR *s = in->pbuf + in->bytenum;

ULONG i = 0, v = 0;

{

v |= (s[i] >> in->bitnum) << (i << 3);

if (8 - in->bitnum >= num)

break;

v |= (s[i + 1] << (8 - in->bitnum)) << (i << 3);

} while ((++i << 3) < (ULONG)num);

in->bitnum += (UCHAR)num;

in->bytenum += in->bitnum >> 3;

in->bitnum &= 7;

return v & ~(-1 << num);

}

// ---------------------------------------------------------------------------

// 将指定位置开始的字节串添加到字典中

// ---------------------------------------------------------------------------

static void insert(LZ77_RUNSTATE *rs, ULONG at, ULONG len)

{

ULONG ins_h, ins_t;

if (len == 1)

{

ins_h = *(USHORT *)(rs->pwnd + at);

rs->prev[at] = rs->head[ins_h];

rs->head[ins_h] = (USHORT)at;

return;

}

if ((at + len) < MAXWND)

{

ins_t = -1;

len += at--;

while (++at != len)

{

ins_h = *(USHORT *)(rs->pwnd + at);

if ((ins_t - rs->head[ins_h]) <= 2)

continue;

ins_t = at;

rs->prev[at] = rs->head[ins_h];

rs->head[ins_h] = (USHORT)at;

}

// ---------------------------------------------------------------------------

// 标志位定义：

// 长度：1，值：0，表示后面有一字节未压缩数据

// 长度：2，值：10，表示后面有一个匹配（变长偏移+变长长度）

// 长度：3，值：110，表示后面有一个匹配（7位偏移+1位长度，偏移为128时表示压缩流结束）

// 长度：3，值：111，表示后面有多个字节未压缩数据

// ---------------------------------------------------------------------------

#define CHARBITS1 4

#define CHARBITS2 7

#define CHARBITS3 16

#define CHARNUMS0 7

#define CHARNUMS1 ((1 << CHARBITS1) - 1 + (CHARNUMS0 + 1) - 2)

#define CHARNUMS2 ((1 << CHARBITS2) - 1 + (CHARNUMS1 + 1))

#define CHARNUMS3 ((1 << CHARBITS3) - 1 + (CHARNUMS2 + 1))

// ---------------------------------------------------------------------------

// 以压缩格式输出指定长度的字节串并针对格式长度进行优化

// ---------------------------------------------------------------------------

static void outcodec(LZ77_OUTPUTS *out, UCHAR *buffer, ULONG length)

{

ULONG i, temp;

if (length <= CHARNUMS0)

{

for (i = 0; i < length; i++)

{

// 逐字节输出，额外输出位(length)

temp = 0x00 | (buffer[i] << 1);

PutBits(out, temp, 1 + 8); // 标志位(1)，数据位(8)

}

else

{

if (length <= CHARNUMS1)

{

// 输出(0-13)表示有(0-13)+8个连续字节未压缩，额外输出位(7)

temp = 0x07 | ((length - CHARNUMS0 - 1) << 3);

PutBits(out, temp, 3 + CHARBITS1); // 标志位(3)，数据位(4)

}

else if (length <= CHARNUMS1 * 2)

{

// 优化输出，最大额外输出位(14)

outcodec(out, buffer, CHARNUMS1);

outcodec(out, buffer + CHARNUMS1, length - CHARNUMS1);

return;

}

else if (length <= CHARNUMS2)

{

// 输出(14)表示未压缩字节数由后面7位决定，额外输出位(14)

temp = 0x07 | (14 << 3);

PutBits(out, temp, 3 + CHARBITS1); // 标志位(3)，数据位(4)

temp = length - CHARNUMS1 - 1;

PutBits(out, temp, CHARBITS2); // 数据位(7)

}

else if (length <= CHARNUMS2 + CHARNUMS1)

{

// 优化输出，最大额外输出位(21)

outcodec(out, buffer, CHARNUMS2);

outcodec(out, buffer + CHARNUMS2, length - CHARNUMS2);

return;

}

else

{

// 输出(15)表示未压缩字节数由后面两字节决定，额外输出位(23)

temp = 0x07 | (15 << 3);

PutBits(out, temp, 3 + CHARBITS1); // 标志位(3)，数据位(4)

// 输出(0-65535)+18个连续字节未压缩

temp = length - CHARNUMS2 - 1;

PutBits(out, temp, CHARBITS3); // 数据位(16)

}

{

UCHAR *s = out->pbuf + out->bytenum;

UCHAR x = out->bitnum;

temp = buffer[0];

PutBits(out, temp, 8 - x);

// 拷贝连续的未压缩字节

for (i = 1; i < length; i++)

{

s[i] = buffer[i];

}

temp >>= 8 - x;

out->bytenum += length - 1;

PutBits(out, temp, x);

}

// ---------------------------------------------------------------------------

// 以压缩格式输出字节串匹配信息并针对信息长度进行优化

// ---------------------------------------------------------------------------

static void outcodex(LZ77_OUTPUTS *out, ULONG offset, ULONG length)

{

UCHAR i = 0;

ULONG temp, m, n;

switch (length)

{

// case 1:

// temp = 0x03 | ((offset - MINOFFSET) << 3);

// PutBits(out, temp, 3 + 4); // 标志位(3)，数据位(4)

// return;

case 3:

if (offset > 127)

break;

case 2:

temp = 0x03 | ((offset - MINOFFSET) << 3); // 短匹配优化

temp |= (length - 2) << (3 + 7);

PutBits(out, temp, 3 + 7 + 1); // 标志位(3)，数据位(1+7)

return;

}

// 写入变长匹配偏移

temp = 0x01 | ((offset - MINOFFSET) << 2);

PutBits(out, temp, 2 + out->codelen); // 标志位(2)，数据位(log2(数据))

length -= MINMATCH;

m = 1 << (M - 1);

// 计算匹配长度最少占用多少位

{

n = ~(-1 << i++) << M;

m <<= 1;

} while ((m + n) <= length);

// 写入匹配长度位数

temp = ~(-1 << (i - 1));

PutBits(out, temp, i);

// 写入变长匹配长度

temp = length - n;

PutBits(out, temp, i + 3 - 1);

}

// ---------------------------------------------------------------------------

// 从当前字典中查找一个匹配字节串，成功返回1同时设置匹配字节串所在位置和长度

// ---------------------------------------------------------------------------

static int match(LZ77_RUNSTATE *rs, ULONG strat, LZ77_MATCHINFO *mi)

{

UCHAR *src, *s, *d, *c, *t;

USHORT index, *prev;

ULONG i, m = 0, n, nice, flag = 0;

src = rs->pwnd;

index = rs->head[*(USHORT *)(src + strat)]; // 从字典中取出匹配信息

if (NIL != index)

{

c = src + MIN(rs->confine, MAXMATCH); // 限制最大匹配长度

t = src + strat;

m = MINMATCH - 1;

prev = rs->prev;

nice = rs->nice;

{

// 开始寻找相同的字节串

s = t;

d = src + index;

// 优化速度，一次循环比较8个字节

while (s < (c - 8)

&& *(USHORT *)(s += 2) == *(USHORT *)(d += 2)

&& *(USHORT *)(s += 2) == *(USHORT *)(d += 2));

while (s < c && *s == *d)

{

s++;

d++;

}

if (s >= c) // 达到限制长度了？

{

m = c - t; // 如果是便是能找到的最好匹配了

n = index;

break;

}

i = s - t;

if (m < i) // 是否达到最小长度要求？

{

m = i;

n = index; // 记录下找到的信息

if (m > nice)

flag = 1; // 如果达到预设的最优匹配长度则设置该标志，然后再次查找最优匹配

}

else if (flag) // 如果已达到过预设的最优匹配长度则可以退出查找了

break;

index = prev[index]; // 取出字典中的下一次匹配记录

} while (NIL != index);

}

if (MINMATCH <= m) // 是否找到合适的匹配信息？

{

mi->len = m;

mi->off = strat - n;

return 1;

}

else

{

if (strat + 2 <= rs->confine) // 检查所剩字节数是否足够2个字节

{

index = rs->head[*(USHORT *)(src + strat)]; // 找不到合适的匹配时尝试查找2个字节的短匹配

if (strat - index <= 127) // 短匹配要求所在位置与当前位置之间不能超过127个字节

{

mi->len = 2;

mi->off = strat - index;

return 1;

}

// 从前面16字节中查找1字节匹配

}

return 0;

}

// ---------------------------------------------------------------------------

// 压缩算法主循环，将输入数据压缩成一个独立的块

// ---------------------------------------------------------------------------

static ULONG deflate(LZ77_RUNSTATE rs, UCHAR *dst, ULONG *inbytes)

{

LZ77_OUTPUTS out, prev_out;

ULONG strstart = 0, prev_start = 0, count = 0, prev_count = 0;

LZ77_MATCHINFO mi;

out.pbuf = dst;

out.bytenum = 0;

out.bitnum = 0;

out.codelen = 1;

prev_out = out;

memset(rs.head, NIL, sizeof(USHORT) * 65536);

{

if (match(&rs, strstart, &mi))

{

if (count > 0)

{

outcodec(&out, rs.pwnd + strstart - count, count); // 输出无匹配字节

count = 0;

}

if ((ULONG)(1 << out.codelen) <= (ULONG)(strstart - MINOFFSET))

out.codelen = log2(strstart - MINOFFSET);

insert(&rs, strstart, mi.len); // 更新字典记录

outcodex(&out, mi.off, mi.len); // 输出压缩代码

strstart += mi.len;

}

else

{

insert(&rs, strstart, 1); // 更新字典记录

count++; // 增加无匹配字节数量

strstart += 1;

}

if (strstart - prev_start >= 0x1000) // 跟踪压缩率变化

{

// 压缩后的数据是否比原始数据大？

if (strstart - prev_start + 4 < out.bytenum - prev_out.bytenum)

{

// 不压缩直接输出原始数据

out = prev_out;

outcodec(&out, rs.pwnd + prev_start - prev_count, strstart - prev_start + prev_count);

count = 0;

}

prev_out = out;

prev_start = strstart;

prev_count = count;

}

} while (strstart < rs.wsize);

if (count > 0)

{

outcodec(&out, rs.pwnd + strstart - count, count); // 输出无匹配字节

}

// 压缩后的数据是否比原始数据大？

if (strstart - prev_start + 4 < out.bytenum - prev_out.bytenum)

{

// 不压缩直接输出原始数据

out = prev_out;

outcodec(&out, rs.pwnd + prev_start - prev_count, strstart - prev_start + prev_count);

}

// 压缩后的全部数据是否比原始数据大？

if (strstart + 4 < out.bytenum)

{

// 直接输出全部数据

out.pbuf = dst;

out.bytenum = 0;

out.bitnum = 0;

out.codelen = 1;

outcodec(&out, rs.pwnd, strstart);

}

outcodex(&out, 128, 2); // 输出压缩流结束标记

if (out.bitnum)

out.bytenum++;

*inbytes = strstart;

return out.bytenum;

}

// ---------------------------------------------------------------------------

// 解压算法，每次处理一个压缩块

// ---------------------------------------------------------------------------

static ULONG inflate(UCHAR *src, UCHAR *dst, ULONG len, ULONG *inbytes)

{

ULONG offset, length;

UCHAR i, t;

UCHAR *out, *s;

LZ77_INPUTS in;

in.pbuf = src;

in.bytenum = 0;

in.bitnum = 0;

in.codelen = 1;

out = dst;

while (in.bytenum < len)

{

if (!GetBits(&in, 1)) // 0表示有一个未压缩的字节

{

*out++ = (UCHAR)GetBits(&in, 8); // 输出一个未压缩字节

}

else

{

if (!GetBits(&in, 1)) // 10表示有一个长匹配

{

if ((ULONG)(1 << in.codelen) <= (ULONG)(out - dst - MINOFFSET))

in.codelen = log2(out - dst - MINOFFSET);

offset = GetBits(&in, in.codelen) + MINOFFSET;

for (i = 0; GetBits(&in, 1); i++); // 计算匹配长度位数

length = GetBits(&in, i + M);

length += (~(-1 << i) << M) + MINMATCH; // 计算匹配长度

{

*out++ = *(out - offset);

} while (--length);

}

else

{

if (!GetBits(&in, 1)) // 110表示有一个短匹配

{

offset = GetBits(&in, 7) + MINOFFSET;

length = GetBits(&in, 1) + 2;

if (offset == 128) // offset值128为压缩流结束标志

break;

{

*out++ = *(out - offset); // 解压短匹配

} while (--length);

}

else // 111表示有一个未压缩的字节串

{

length = GetBits(&in, CHARBITS1);

switch (length)

{

case 14:

length = GetBits(&in, CHARBITS2); // 长度为14时表示实际长度用后面的7位记录

length += CHARNUMS1 + 1;

break;

case 15:

length = GetBits(&in, CHARBITS3); // 长度为15时表示实际长度用后面的16位记录

length += CHARNUMS2 + 1;

break;

default:

length += CHARNUMS0 + 1;

break;

}

s = in.pbuf + in.bytenum;

offset = 1;

i = in.bitnum;

{

out[offset] = s[offset]; // 还原字节串

} while (++offset < length);

t = (UCHAR)GetBits(&in, 8 - i);

in.bytenum += length - 1;

t |= (UCHAR)(GetBits(&in, i) << (8 - i));

*out = t;

out += length;

}

*inbytes = in.bytenum;

*inbytes += in.bitnum == 0 ? 0 : 1;

return out - dst;

}

// ---------------------------------------------------------------------------

// LZ77压缩算法

// dst:压缩输出缓冲区

// src:原始数据

// len:原始数据长度

// level:压缩等级(0 - 4)

// return 压缩后数据大小

// ---------------------------------------------------------------------------

int Lz77Compress(void *dst, void *src, int len, int level)

{

LZ77_RUNSTATE rs;

int m, n, count = 0;

if (len <= 0)

return 0;

if (!src || !dst)

return -1;

// 设置压缩等级，等级越高引擎会花越多时间去查找一个更长的匹配

switch (level)

{

case 0:

rs.nice = 3;

break;

case 1:

rs.nice = 30;

break;

case 2:

rs.nice = 70;

break;

case 3:

rs.nice = 150;

break;

case 4:

rs.nice = -1;

break;

}

// 为压缩字典分配内存空间

rs.prev = (USHORT *)malloc(sizeof(USHORT) * 65536);

rs.head = (USHORT *)malloc(sizeof(USHORT) * 65536);

if (!rs.prev || !rs.head)

{

free(rs.head);

free(rs.prev);

return -1;

}

{

rs.wsize = MIN(len, MAXWND);

rs.pwnd = src;

// rs.confine = len;

rs.confine = MIN(len, MAXWND);

n = deflate(rs, dst, &m);

len -= m;

(UCHAR *)src += m;

(UCHAR *)dst += n;

count += n;

} while (len > 0);

free(rs.head);

free(rs.prev);

return count;

}

// ---------------------------------------------------------------------------

// LZ77解压算法

// dst:解压输出缓冲区

// src:压缩数据

// len:压缩数据长度

// return 解压后数据大小

// ---------------------------------------------------------------------------

int Lz77Decompress(void *dst, void *src, int len)

{

int c = 0, i, o, a = 0;

if (len <= 0)

return 0;

if (!src || !dst)

return -1;

{

o = inflate(src, dst, len, &i);

(UCHAR *)src += i;

(UCHAR *)dst += o;

len -= i;

c += o;

} while (len > 0);

return c;

}

测试代码：

main.c

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <windows.h>

//---------------------------------------------------------------------------

extern int Lz77Compress(void *dst, void *src, int len, int level);

extern int Lz77Decompress(void *dst, void *src, int len);

//---------------------------------------------------------------------------

int main(int argc, char *argv[])

{

FILE *input, *output;

BYTE *inbuf, *outbuf;

DWORD insize, outsize, len, a = 0;

SYSTEMTIME t1, t2;

DWORD milliS;

if (argc < 4)

return 0;

input = fopen(argv[2], "rb");

output = fopen(argv[3], "wb");

if (!input || !output)

return 0;

fseek(input, 0, SEEK_END);

insize = ftell(input);

fseek(input, 0, SEEK_SET);

inbuf = (BYTE *)malloc(insize);

GetSystemTime(&t1);

if (*argv[1] == 'c')

{

outbuf = (BYTE *)malloc(insize * 2);

fread(inbuf, insize, 1, input);

fwrite(&insize, sizeof(DWORD), 1, output);

len = Lz77Compress(outbuf, inbuf, insize, 2);

}

else if (*argv[1] == 'd')

{

fread(&outsize, sizeof(DWORD), 1, input);

insize -= sizeof(DWORD);

outbuf = (BYTE *)malloc(outsize * 2);

//fseek(input, sizeof(DWORD), SEEK_SET);

fread(inbuf, insize, 1, input);

Lz77Decompress(outbuf, inbuf, insize);

len = outsize;

}

else

return 0;

GetSystemTime(&t2);

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);

fwrite(outbuf, len, 1, output);

fclose(output);

fclose(input);

free(inbuf);

free(outbuf);

return 0;

}

//---------------------------------------------------------------------------

变种LZ77数据无损压缩算法

继续阅读

查找算法学习之二分查找（Python版本）——BinarySearch

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

Command Network(POJ 3164)---定根最小树形图模板题题目描述输入格式输出格式输入样例输出样例分析源程序

开源低带宽语音编解码器

241 Different Ways to Add Parentheses（C代码版）

【趋高机器视觉】机器视觉技术原理解析及解决方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制规程及特点4． CSMA/CD协议5． CSMA/CD的优点6．结束语

极大似然法(ML)与最大期望法(EM)

C++ 第十五周报告1--《冒泡法排序》

笔试面试题目：滑动窗口(二)

数据结构与算法（27）——排序（二）

Dijkstra--简易版（最短路径）

Git学习笔记5 merge冲突时二选一

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

Linux设备模型（中）之上层容器

hdu7108哈希