Yan`s Notepad

--- My Notepad......Articles, tools and etc.
LZ78算法原理与实现
LZ78算法是一个很简单的动态字典压缩算法。比较有名的LZW压缩算法便是基于LZ78的。相比于LZ77,它维护一个动态字典,并不断在最靠前的输入流中找到最长匹配。以压缩字符串“ASAASASA”为例子,此时,会有三种情况:
1. str没有任何一个匹配的, 则编码为(0, str[0]), 然后移动输入流一个长度:
···图片正在加载···
images/lz78/step1.png
编码情况1
图中的蓝色字对应了每一次的操作,右下角为字典,左下角为输出,而最顶上则是需要编码的字符串str和编码位置。之后的图都以此表示。程序继续运行,遇到了字符S,它依然在字典中没有任何匹配。因此和A的编码结果一样的。在此之后,编码到'A'的位置,发现字典中有最长匹配'A'。那么就是第二种情况:
2. 在字典中找到了最长匹配word,它的编号为id,则编码为(id, last_char):
···图片正在加载···
images/lz78/step2.png
编码情况2
上图中,绿色框表示在词典中找到的最长匹配:字串"A",然后,编码器查找原始字串中,该最长匹配的后一个字符:'A'(图中的蓝色区域),并输出(1, A),且将最长匹配与它的后一个字符合并,作为一个新的词(图中的红色区域)插入字典。最后,才将待编码字串的位置移动到最长匹配的后一个字符的后面。继续运行,之后的字符串"SA"也是一样的情况。再往下,字符串"SA"存在着最长匹配,但是它的后面已经没有字符串了,这个特殊处理,即第三种情况:
3. 最后的一个被匹配的字串,编码为(id,):
···图片正在加载···
images/lz78/step3.png
编码情况3
同样的,绿色框内表示匹配到的最长字串。至此,整套编码程序就运行结束了。在左下角,我们得到了整个输出。将字典抛弃掉,保存输出,完成编码:(0, A), (0, S), (1, A), (2, A), (4, )
下面来处理解码问题。和编码过程相反,通过读取上面的输出内容,我们将重新恢复出整个字典。对于每个编码输入(preIndex, lastChar),将大体分为两种情况:
1. preIndex == 0,说明该编码数据并没有在字典中对应任何的词条,输出lastChar,直接向字典中插入lastChar即可:
···图片正在加载···
images/lz78/destep1.png
解码情况1
之后的(0, S)也是一样的。继续运行程序,此时preIndex > 0了。则情况二如下。
2. 否则,在字典中找到id是preIndex的字串word,放入输出。如果有lastChar,就将lastChar放入输出,并且字典中插入word+lastChar:
···图片正在加载···
images/lz78/destep2.png
解码情况2
如此往下,处理完整个待解码流,即可得到原始字符串:
···图片正在加载···
images/lz78/destep3.png
解码情况2+
下面我们来考虑实现。
在实现整个lz78之前,我们需要先完成一个字典。字典有一种高效的实现方案——Tire树。不过这时我们只是希望完成LZ78,而不是将它置于实际中去。因此,我决定使用链表那样的线性方案,它会多花费O(N)的时间去查找重复项。定义LZ78编码输出和单条的字典数据:
#define  MAX_WORDLENGTH         2048
typedef struct _WordBlock
{
    int        id;
    int        len;
    char       str[MAX_WORDLENGTH];
}WordBlock;
typedef struct _LZ78Data
{
    int        id;
    char       ch;
}LZ78Data;
std::list<WordBlock>      dictionary;
std::list<LZ78Data>       lz78_data;
int                       g_id;
如上面的代码那样,我们在全局变量中引入字典和LZ78数据输出的链表。先考虑字典的实现。LZ78中需要实现的字典操作包含:按词条无重复插入(这是为了避免带来过多的冗余)、按词条id取回、按词条进行最长匹配。由于词条编码需要一个唯一的id,因此我们还需要引入一个全局变量来记录调用次数,返回唯一的ID。在不考虑任何错误的情况下,可以很容易的得到:
// 取得唯一的ID
int getID()
{
    g_id++;
    return g_id;
}
// 用mstr完全匹配str前面的n个char,返回n, 失败返回-1
int wordMatching(const char *str, const char *mstr)
{
    const char *p = mstr;
    while (*str && *p && *str == *p)
    {
        str++;
        p++;
    }
    if (*p != 0)
        return -1;
    return strlen(mstr);
}
// 匹配一个最长字串, 成功返回字串的ID, 失败返回-1
int matchingMaxLengWord(const char *str, int *retLeng)
{
    int        curid = -1;
    int        curleng = 0;
    *retLeng = -1;
    for (auto i = dictionary.begin(); i != dictionary.end(); i++)
    {
        int  leng;
        leng = wordMatching(str, i->str);
        if (leng > curleng)                                 // 匹配失败就会返回-1, -1 < 0, 因此是可以的
        {
            curid = i->id;
            curleng = leng;                                 // 记录当前的最长长度
            *retLeng = i->len;
        }
    }
    return curid;
}
// 按照某个id, 往词典中插入单词
// word插入前面leng部分, 如果word不够长, 那么就插入word的全部
void insertWordWithID(const char* word, int leng, int id)
{
    WordBlock   w;
    char* p;
    const char* s = word;
    w.id = id;
    p = w.str;
    for (auto i = dictionary.begin(); i != dictionary.end(); i++)
    {
        if (i->id == id || strcmp(i->str, word) == 0)
        {
            return;                                         // 有重复的, 不插入
        }
    }
    while (*s && s - word < leng)
    {
        *p = *s;
        s++;
        p++;
    }
    *p = 0;
    w.len = leng;
    dictionary.push_back(w);
}
// 往词典里面插入单词
void insertWord(const char *word, int leng)
{
    insertWordWithID(word, leng, getID());
}
// 字符串拼接, 带尾部
void strcpyWithEnd(char *dst, const char *src, char end)
{
    while (*src)
    {
        *dst = *src;
        dst++;
        src++;
    }
    *dst++ = end;
    *dst++ = 0;
}
// 取回某id的词典单词, 返回len, word应该初始化为全0
int getWordWithChar(char *word, int id, int endchar)
{
    for (auto i = dictionary.begin(); i != dictionary.end(); i++)
    {
        if (i->id == id)
        {
            strcpyWithEnd(word, i->str, endchar);
            return strlen(word);                            // word后面肯定是空的...strlen算了
        }
    }
    return 0;
}
最后,我们完成lz78的编解码实现。思路在上文已经提到:
// lz78压缩, 输出在lz78_data中
void lz78Encode(const char* s)
{
    LZ78Data      dat;
    int           id, len, count = 0;
    const char*  str;
    str = s;
    lz78_data.clear();                                      // 清空上次的输出
    while (*str)                                            // 持续编码直到字符串结束
    {
        id = matchingMaxLengWord(str, &len);                // 找到最长匹配
        if (id == -1)                                       // 没有最长匹配
        {
            dat.id = 0;
            dat.ch = *str;
            insertWord(str, 1);                             // 插入这个字符
            str++;                                          // 只需要移动一个缓冲区位置, 因为一个字符长度为1.....
        }
        else {
            insertWord(str, len + 1);                       // len + 1, len是最长匹配字串的长度, 1是它后面接的那个字符(如果有的话)
            str += len;
            dat.id = id;
            if (*str != 0)                                  // 字符串还没有结束
            {
                dat.ch = *str;
                str++;                                      // 移动一下, 跳过它后面的那个字符
            }
            else {
                dat.ch = 0;                                 // 注, 其实字符串是以0结尾的, 之所以把dat.ch = *str分开写, 是为了凸显算法
            }
        }
        lz78_data.push_back(dat);                           // 放入数据
    }
}
// lz78解压
void lz78Decode(char* s)
{
    char* p = s;
    for (auto i = lz78_data.begin(); i != lz78_data.end(); i++)
    {
        if (i->id == 0)
        {
            *p = i->ch;
            insertWord(p, 1);                               // 插入这个词
            p++;
        }
        else {
            char  tmp[MAX_WORDLENGTH] = { 0 };
            int   len;
            len = getWordWithChar(tmp, i->id, i->ch);       // 找到词典中的对应项, 并补上尾部(如果有的话, 没有就是0, 无影响)
            insertWord(tmp, len);                           // 插入新词
            strcpy(p, tmp);
            p += len;
        }
    }
    *p = 0;
}

int main()
{
    const char encode[25] = { "ASAASASA" };
    char       decode[25] = { 0 };

    printf("压缩: \n");
    g_id = 0;                                               // 重置全局id
    lz78Encode(encode);
    for (auto i = lz78_data.begin(); i != lz78_data.end(); i++)
    {
        printf("    (%d, %c)\n", i->id, i->ch);
    }
    printf("词典: \n");
    for (auto i = dictionary.begin(); i != dictionary.end(); i++)
    {
        printf("    id = %d:%s\n", i->id, i->str);
    }
    dictionary.clear();


    g_id = 0;                                               // 重置全局id
    lz78Decode(decode);
    printf("解压:\n    %s\n", decode);
    printf("词典: \n");
    for (auto i = dictionary.begin(); i != dictionary.end(); i++)
    {
        printf("    id = %d:%s\n", i->id, i->str);
    }

    lz78_data.clear();
    dictionary.clear();
    return 0;
}