LZW算法的实现以及注意事项

xieglt · 发表于 2020-8-11 10:21:39

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

lZW 压缩算法的原理是比较简单的，其通过建立一个字典，不断地把第一次出现的字符串加入字典，当字典中的字符串再次出现时，就将该字符串用字典中对应的编码替换。如果替换编码比原字符串短，则达到压缩的目的。LZW算法的优点是无需存储字典，因为其字典是根据处理内容动态创建的，压缩时，一边创建字典一边压缩，解压时也是一边创建字典一边解压，非常神奇。
压缩过程：以前一个读入的字符为前缀，以后一个读入的字符为后缀，组成一个词条，在字典中查找该词条，如果不存在，则将该词条赋予一个编码，并加入字典。由于标准ASIIC码占据了0-255，因此，字典中的编码可以从256起，逐一累加。如果该词条已存在，则用其对应的编码将该词条替换，然后再读入下一个字符进行处理，这时需要注意的是：后缀规则不变，前缀则不再是上一个读入的字符，换成了刚使用过的编码。
压缩过程注意事项：
1、由于编码是从256起，其长度大于一个字符，如256就占据了9个Bits，为了解码时能够识别，所有写入的字符长度必须保持一致，如用9位编码，所有编码长度都得用9Bits，原始ASIIC码写入时也必须扩展成9Bits。当然，9Bits所能表示的最大的数仅仅是511，在字典里很快就会被用尽，这时，可以把编码长度扩展到10Bits(1023)、11Bits(2047)、12Bits(4095)等等，但是太大也不合适，一是编码时字典将比较庞大，耗费的内存空间会比较多，查找起来也将非常耗时；二是原始ASIIC码扩展得太大，达不到压缩效果。
2、当写入一个编码时，程序是无法预知它与下一个读入的字符组成的词条是否已经存在于字典中，如果已经存在，则在写入下一个编码时须将指针退回至前一编码位置，将前一编码覆盖掉。
3、当字符串中第一次出现连续重复字符时，需谨慎处理。如处理aaa这样的字符串时，首先，a+a组成词条，因其第一次出现，字典中不存在a+a这样的词条，于是将其编入字典，假设编码为351，写入字串为aa，当处理到第3个a时，a+a组成词条，查找字典，找到该词条，取出其对应编码351，按注意事项2中的规则，将编码指针退回至前一编码位置，写入351，此时写入字串变成了a351。解码时，将无法再组成a+a这样的词条来解码，导致解码失败。因此，在出现新创建的词条紧接着就被找到的情况时，应判定为未找到，但不再创建新词条。
4、每处理一个字符，都将组成一个词条，然后去字典中查找该词条，这个查找字典的过程是整个编码过程中最耗时的部分。如果把字典设置成队列，顺序查找的时间复杂度为O（n），当然，可以考虑用二分查找算法来取代顺序查找算法，但是二分查找算法要求关键字是有序的，而事实上，作为关键字的词条是无序的，这时，可以考虑把字典设置成二叉树，把比当前节点词条大的新词条设为右子节点，小的新词条设为左子节点。这时，查找算法的时间复杂度就变成了O（ln¬¬2n）。
5、字符串压缩实例
编码过程
编码前 aababcabcdabcdeabcdef 长度 21
编码后 aab[257]c[259]d[261]e[263]f 长度 12.375
步骤前缀后缀编码是否在码表写入字符写入方式
1 - a - N a 　
2 a a 256 N a 　
3 a b 257 N b 　
4 b a 258 N a 覆盖
5 a b 257 Y 257
6 257 c 259 N c 　
7 c a 260 N a 覆盖
8 a b 257 Y 257
9 257 c 259 Y 259
10 259 d 261 N d 　
11 d a 262 N a 覆盖
12 a b 257 Y 257
13 257 c 259 Y 259
14 259 d 261 Y 261
15 261 e 263 N e 　
16 e a 264 N a 覆盖
17 a b 257 Y 257
18 257 c 259 Y 259
19 259 d 261 Y 261
20 261 e 263 Y 263
21 263 f 265 N f 　

解压过程：按压缩时写入的Bits长度为单位读取内容，比如说压缩时是按9Bits写入的，则解压时也按9Bits读取。每读入一个编码，看是否时原始ASIIC码（<256）？是则压缩成一个字节（8Bits）写入，同时按前缀+后缀的规则创建字典，若非原始ASIIC码，则在字典中找到该编码对应的词条，并将其解码为前缀+后缀，按照规则，组成词条的后缀一定是原始ASIIC码，可以直接压缩成8Bits写入，而前缀则有可能是原始ASIIC码，也有可能不是，如果不是，则把该前缀作为编码，继续在字典中查找其对应的词条，一直到前缀为原始ASCII码为止。因为解压过程中在字典中查找词条的关键字不再是词条，而是编码，按照规则，编码是逐一累加有序的，所以解压时可以把字典设置为hash表，查找算法的时间复杂度仅为O(1)。
字符串解压实例：
解码前 aab[257]c[259]d[261]e[263]f 　　
解码后 aababcabcdabcdeabcdef 　　
步骤读入字符解码为前缀后缀编码写入字符
1 a a - a - a
2 a a a a 256 a
3 b b a b 257 b
4 257 ab b a 258 ab
5 c c 257 c 259 c
6 259 abc c a 260 abc
7 d d 259 d 261 d
8 261 abcd d a 262 abcd
9 e e 261 e 263 e
10 263 abcde e a 264 abcde
11 f f 263 f 265 f

#ifndef H_LZW_ENCODE
#define H_LZW_ENCODE
class CLzwEncode
{
private:
CLzwEncode(const CLzwEncode &);
CLzwEncode & operator = (const CLzwEncode &);
private:
//构建 LZW 字典结构
typedef struct tagLzwDictionary
{
//原码前缀 + 后缀
WORD src[2];
//编码
WORD dst;
struct tagLzwDictionary * pLeft;
struct tagLzwDictionary * pRight;
}LZW, *LPLZW;
//编码解码参数
typedef struct tagCodeParam
{
//编码位数 9 - 12
BYTE bits;
//源字符串大小
long srcSize;
//已读取源字符串字符数
long srcOffset;
//目标字符串中已写入字符数
long dstOffset;
//一个字节中已使用的位
long bitsUsed;
}CODEPARAM,*LPCODEPARAM;
public:
CLzwEncode();
virtual ~CLzwEncode();
private:
//计算编码位数对应的最大数
WORD inline MaxCode(BYTE Bits)
{
return 0xFFFF >> (16 - Bits);
}
void copyCode(void * src,const void * dst);
long compareCode(const void * src,const void * dst);
LPLZW CreateNode(const LZW & lzw,WORD * pCode);
void DeleteTree(LPLZW pLzw);
//清空二叉树字典
void DestoryTree();
//压缩时创建二叉树字典
BOOL CreateTree(LZW & lzw,WORD * newCode = NULL);
//清空哈希字典
void DestoryHash();
//解压时创建哈希字典
void CreateHash(LZW & lzw);
//解码一个已编码串
long DecodeOne(LZW & lzw,char * buffer);
//将编码后的字符写入字符串
long WriteCode(BYTE bits,long * bitsUsed,WORD code,char * lpBuffer);
//从已编码的字符串中读取一个编码
long ReadCode(BYTE bits,long * bitsUsed,WORD * code,char * lpBuffer);
//按 bits 编码
void innerEncode(CODEPARAM & param,char * src,char * dst);
//按 bits 解码
void innerDecode(CODEPARAM & param,char * src,char * dst);
//
public:
long Encode(long nsize,char * src,char * dst);
long Decode(long nsize,char * src,char * dst);
private:
static const int m_sizeOfTable;
WORD m_nUsed;
LZW m_table[4096];
LPLZW m_lpHead;
};
#endif

复制代码

#include "LzwEncode.h"
const int CLzwEncode::m_sizeOfTable = 4096;
CLzwEncode::CLzwEncode()
{
m_nUsed = 256;
m_lpHead = NULL;
memset(m_table,0,sizeof(m_table));
}
CLzwEncode::~CLzwEncode()
{
DestoryTree();
}
void CLzwEncode::copyCode(void * src,const void * dst)
{
_asm
{
MOV ESI,dst
MOV EDI,src
LODSD
STOSD
}
}
long CLzwEncode::compareCode(const void * src,const void * dst)
{
long nRet = 0;
_asm
{
MOV ESI,src
LODSD
MOV ESI,dst
SUB EAX,DWORD PTR [ESI]
MOV nRet,EAX
}
return nRet;
}
void CLzwEncode::DeleteTree(LPLZW pLzw)
{
if(pLzw != NULL)
{
if(pLzw->pLeft != NULL)
{
DeleteTree(pLzw->pLeft);
}
if(pLzw->pRight != NULL)
{
DeleteTree(pLzw->pRight);
}
delete pLzw;
}
}
void CLzwEncode::DestoryTree()
{
DeleteTree(m_lpHead);
m_lpHead = NULL;
m_nUsed = 256;
}
void CLzwEncode::DestoryHash()
{
memset(m_table,0,sizeof(m_table));
m_nUsed = 256;
}
CLzwEncode::LPLZW CLzwEncode::CreateNode(const LZW & lzw,WORD * pCode)
{
LPLZW lpNode = new LZW;
lpNode->pLeft = NULL;
lpNode->pRight = NULL;
lpNode->dst = m_nUsed ++;
copyCode(lpNode->src,lzw.src);
if(pCode != NULL)
{
* pCode = lpNode->dst;
}
return lpNode;
}
BOOL CLzwEncode::CreateTree(LZW & lzw,WORD * newCode)
{
BOOL ret = FALSE;
LPLZW lpNode = NULL;
if(m_lpHead == NULL)
{
m_lpHead = CreateNode(lzw,newCode);
}
else
{
lpNode = m_lpHead;
do
{
long flag = compareCode(lpNode->src,lzw.src);
if(flag == 0)
{
//当源串第一次出现连续字符时如: aaa
//编码函数处理到前面两个aa时，为aa编码，假定为256。
//而处理到后面两个aa时，按规则，将会用256替换后面两个aa,即编码为 a256
//到解码时，解码函数将只能找个一个a,无法还原字典 aa = 256
//因此当出现连续字符时，必须特殊处理为未找到编码。
if(lpNode->dst + 1 < m_nUsed)
{
lzw.dst = lpNode->dst;
ret = TRUE;
}
break;
}
if(flag > 0)
{
if(lpNode->pRight == NULL)
{
lpNode->pRight = CreateNode(lzw,newCode);
break;
}
lpNode = lpNode->pRight;
}
else
{
if(lpNode->pLeft == NULL)
{
lpNode->pLeft = CreateNode(lzw,newCode);
break;
}
lpNode = lpNode->pLeft;
}
}while (TRUE);
}
return ret;
}
void CLzwEncode::CreateHash(LZW & lzw)
{
long i = m_nUsed - 256;
if(i == 0 || compareCode(m_table[i-1].src,lzw.src) != 0)
{
copyCode(m_table[i].src,lzw.src);
m_table[i].dst = m_nUsed ++;
}
}
long CLzwEncode::DecodeOne(LZW & lzw,char * buffer)
{
long i = m_sizeOfTable;
WORD code = lzw.src[1];
do
{
//计算编码在字典中的定位
long local = code - 256;
//字典中的与该编码对应的源码为前缀src[0]+后缀src[1]
//其中后缀一定为原始ASIIC码,将其取出
buffer[--i] = static_cast<char>(m_table[local].src[1]);
//取得源码前缀
code = m_table[local].src[0];
//如果前缀是原始ASIIC码，说明解码结束
if(code < 256)
{
buffer[--i] = TO_CHAR(code);
//以LZW.src[0]为前缀，以code为后缀，构建编码
LZW tmp = lzw;
tmp.src[1] = code;
CreateHash(tmp);
break;
}
//非原始ASIIC码则继续解码
}while(TRUE);
return i;
}
long CLzwEncode::WriteCode(BYTE bits,long * bitsUsed,WORD code,char * lpBuffer)
{
unsigned long temp = code;
//计算实际写入Bit数 = 当前字节已使用Bits + 需要写入的Bits
long writes = *bitsUsed + bits;
//当前字节已使用Bits不为0的处理
if(*bitsUsed != 0)
{
//取得当前字节，因为要做移位运算，转化成无符号字符
BYTE oldChar = lpBuffer[0];
//已使用的Bits在低位，左移将未使用的Bits清零
//右移位恢复已使用的Bits
oldChar <<= (8 - *bitsUsed);
oldChar >>= (8 - *bitsUsed);
//将需要写入的Bits左移，为当前字节已使用Bits腾出位置
temp <<= *bitsUsed;
//将当前字节已使用Bits与需要写入的Bits相结合
temp |= oldChar;
}
//写入4个字节
memcpy(lpBuffer,&temp,sizeof(long));
//计算写入后当前字节的已使用Bits
*bitsUsed = writes % 8;
//返回写入的字节数
return writes / 8 ;;
}
long CLzwEncode::ReadCode(BYTE bits,long * bitsUsed,WORD * code,char * lpBuffer)
{
unsigned long temp = 0;
//计算实际读取Bit数 = 当前字节已读取Bits + 需要读取的Bits
long reads = * bitsUsed + bits;
//读取4个字节
memcpy(&temp,lpBuffer,sizeof(long));
//右移清除掉已读取的Bits
temp >>= *bitsUsed;
//保留需要读取的Bits，将多余的Bits清0
temp <<= (32 - bits);
temp >>= (32 - bits);
//将读取的Bits转化为WORD
*code = static_cast<WORD>(temp);
//计算读取后当前字节的已读取Bits
*bitsUsed = reads % 8;
//返回读取的自己数
return (reads / 8);
}
void CLzwEncode::innerEncode(CODEPARAM & param,char * src,char * dst)
{
BOOL bFound = FALSE;
long preOff = param.dstOffset;
long offset = param.dstOffset;
long preUsed = param.bitsUsed;
long bitsUsed = param.bitsUsed;
LZW lzw = {0};
//清除字典
DestoryTree();
//读取第一个字符
lzw.src[0] = TO_BYTE(src[param.srcOffset++]);
lzw.src[1] = lzw.src[0];
lzw.dst = lzw.src[0];
//写入第一个字符
offset += WriteCode(param.bits,&bitsUsed,lzw.src[1],dst+offset);
while(param.srcSize > param.srcOffset)
{
//读取后续字符
lzw.src[1] = TO_BYTE(src[param.srcOffset++]);
lzw.src[0] = lzw.dst;
lzw.dst = lzw.src[1];
WORD code = 0;
//以src[0]为前缀，src[1]为后缀，在字典中查找编码，
//若没找到，则建立新的编码
bFound = CreateTree(lzw,&code);
//到达编码表最后一个元素
if(code == MaxCode(param.bits))
{
//写入结束标志
param.srcOffset--;
offset += WriteCode(param.bits,&bitsUsed,code,dst+offset);
break;
}
if(bFound)
{
//已编码，则将前一个写入字符覆盖写入
offset = preOff;
bitsUsed = preUsed;
offset += WriteCode(param.bits,&bitsUsed,lzw.dst,dst+offset);
}
else
{
//未编码，写入原始字符
preUsed = bitsUsed;
preOff = offset;
offset += WriteCode(param.bits,&bitsUsed,lzw.src[1],dst+offset);
}
}
param.bitsUsed = bitsUsed;
param.dstOffset = offset;
}
void CLzwEncode::innerDecode(CODEPARAM & param,char * src,char * dst)
{
long offset = param.srcOffset;
long bitsUsed = param.bitsUsed;
BOOL bFind = FALSE;
LZW lzw = {0};
DestoryHash();
//读入第一个字符
offset += ReadCode(param.bits,&bitsUsed,&lzw.src[0],src+offset);
lzw.src[1] = lzw.src[0];
dst[param.dstOffset++] = TO_CHAR(lzw.src[0]);
while(param.srcSize > offset)
{
lzw.src[0] = lzw.src[1];
//读取后续字符
offset += ReadCode(param.bits,&bitsUsed,&lzw.src[1],src+offset);
//是结束标志则退出循环
if(lzw.src[1] == MaxCode(param.bits))
{
break;
}
//是原始ASICC(0-255)字符，直接写入，并创建字典
if(lzw.src[1] < 256)
{
dst[param.dstOffset++] = TO_CHAR(lzw.src[1]);
CreateHash(lzw);
}
//非原始字符(>255)的处理
else
{
char buffer[m_sizeOfTable] = {0};
//在字典中查找其编码并返回原字符串
long local = DecodeOne(lzw,buffer);
memcpy(dst+param.dstOffset,buffer+local,m_sizeOfTable - local);
param.dstOffset += (m_sizeOfTable - local);
}
}
param.bitsUsed = bitsUsed;
param.srcOffset = offset;
}
long CLzwEncode::Encode(long nsize,char * src,char * dst)
{
CODEPARAM param = {0};
param.bits = 9;
param.srcSize = nsize;
do
{
innerEncode(param,src,dst);
if(param.srcOffset >= param.srcSize)
{
break;
}
if(param.bits < 12)
{
param.bits ++;
}
} while(TRUE);
return param.dstOffset;
}
long CLzwEncode::Decode(long nsize,char * src,char * dst)
{
CODEPARAM param = {0};
param.bits = 9;
param.srcSize = nsize;
do
{
innerDecode(param,src,dst);
if(param.srcOffset >= param.srcSize)
{
break;
}
if(param.bits < 12)
{
param.bits ++;
}
} while (TRUE);
return param.dstOffset;
}

复制代码

账号		自动登录	找回密码
密码			立即注册

[技术交流] LZW算法的实现以及注意事项

马上注册，结交更多好友，享用更多功能^_^