3a0674818cbd0ec051babab5876102a6
数据压缩算法

1 前言

数据压缩是指在不丢失有用信息的前提下,缩减数据量以减少存储空间,提高其传输、存储和处理效率,或按照一定的算法对数据进行重新组织,减少数据的冗余和存储的空间的一种技术方法。

2 霍夫曼编码

霍夫曼编码是一种基于最小冗余编码的压缩算法。最小冗余编码是指,如果知道一组数据中符号出现的频率,就可以用一种特殊的方式来表示符号从而减少数据需要的存储空间。
霍夫曼编码流程如下:

2.1 统计字符频率

例如有如下字符串:
A A C B C A A D D B B A D D A A B B

得到各个字符频率如下表:

字符 频率
A 7
B 5
C 2
D 4

2.2 构造霍夫曼树

2.2.1 定义

给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。结合2.1的字符串,将字符串出现频率作为权值。

2.2.2 构造过程

(1)选取权值最小和次小的节点作为左右子树,构造一棵二叉树。
(2)将步骤1构造的二叉树的根节点的权值设置为,左右子树之和。
(3)去除步骤1中已经选过的节点,将新的二叉树的根节点加入至待选集合
(4)继续重复步骤1,直至仅剩一个元素未选中。

2.2.3 图解过程

通过构造的霍夫曼树可以看出,权值越大的节点距离根节点越近,其深度越小,权值越小的节点,距离根节点越远,其深度越大。

2.3 编码

在构造出霍夫曼树后,将向左子树路径标记为0,向右子树的路径标记为1。则标记后的霍夫曼树为:

图2.3

图2.3

按照图2.3进行霍夫曼编码为:

数据 编码
A 0
B 10
C 111
D 110

A A C B C A A D D B B A D D A A B B 编码后的数据长度为:
0 0 111 10 111 0 0 110 110 10 10 0 110 110 0 0 10 10 编码长度为35。

若采用等长编码为:

数据 编码
A 00
B 01
C 10
D 11

则A A C B C A A D D B B A D D A A B B对应编码为:
00 00 10 01 10 00 00 11 11 01 01 00 11 11 00 00 01 01
长度为36。可以看出使用霍夫曼编码可以缩短数据编码长度,达到数据压缩的效果。

2.4 代码实现

#include<iostream>  
#include<string>  
using namespace std;

struct Node
{
    double weight;  //存储权值
    string ch;  //存储字符
    string code; //编码
    int lchild, rchild, parent;//分别存储左孩子、右孩子、父节点位置
};

void Select(Node huffTree[], int *a, int *b, int n)//找权值最小的两个a和b  
{
    int i;
    double weight = 0; //找最小的数
    for (i = 0; i <n; i++)
    {
        if (huffTree[i].parent != -1)     //判断节点是否已经选过
            continue;
        else
        {
            if (weight == 0)
            {
                weight = huffTree[i].weight;
                *a = i;
            }
            else
            {
                if (huffTree[i].weight < weight)
                {
                    weight = huffTree[i].weight;
                    *a = i;
                }
            }
        }
    }
    weight = 0; //找第二小的数
    for (i = 0; i < n; i++)
    {
        if (huffTree[i].parent != -1 || (i == *a))//排除已选过的数
            continue;
        else
        {
            if (weight == 0)
            {
                weight = huffTree[i].weight;
                *b = i;
            }
            else
            {
                if (huffTree[i].weight  < weight)
                {
                    weight = huffTree[i].weight;
                    *b = i;
                }
            }
        }
    }
    int temp;
    if (huffTree[*a].lchild < huffTree[*b].lchild)  //小的数放左边
    {
        temp = *a;
        *a = *b;
        *b = temp;
    }
}

void Huff_Tree(Node huffTree[], int w[], string ch[], int n)
{
    for (int i = 0; i < 2 * n - 1; i++) //初始过程
    {
        huffTree[i].parent = -1;    
        huffTree[i].lchild = -1;    
        huffTree[i].rchild = -1;  
        huffTree[i].code = "";
    }
    for (int i = 0; i < n; i++)       
    {
        huffTree[i].weight = w[i];  
        huffTree[i].ch = ch[i];     
    }
    for (int k = n; k < 2 * n - 1; k++)
    {
        int i1 = 0;
        int i2 = 0;
        Select(huffTree, &i1, &i2, k); //将i1,i2节点合成节点k
        huffTree[i1].parent = k;   
        huffTree[i2].parent = k;
        huffTree[k].weight = huffTree[i1].weight + huffTree[i2].weight;
        huffTree[k].lchild = i1;
        huffTree[k].rchild = i2;
    }
}

void Huff_Code(Node huffTree[], int n)
{
    int i, j, k;
    string s = "";
    for (i = 0; i < n; i++)  
    {
        s = "";         
        j = i;                
        while (huffTree[j].parent != -1) //从叶子往上找到根节点
        {
            k = huffTree[j].parent;
            if (j == huffTree[k].lchild) //如果是根的左孩子,则记为0
            {
                s = s + "0";
            }
            else               
            {
                s = s + "1";
            }
            j = huffTree[j].parent; 
        }
        cout << "字符 " << huffTree[i].ch << " 的编码:";
        for (int l = s.size() - 1; l >= 0; l--)    
        {
            cout << s[l];
            huffTree[i].code += s[l]; //保存编码
        }
        cout << endl;
    }
}

string Huff_Decode(Node huffTree[], int n,string s)
{
    cout << "解码后为:";
    string temp = "",str="";//保存解码后的字符串
    for (int i = 0; i < s.size(); i++)
    {
        temp = temp + s[i];
        for (int j = 0; j < n; j++)
        {    
            if (temp == huffTree[j].code)
            {
                str=str+ huffTree[j].ch;
                temp = "";
                break;
            }    
            else if (i == s.size()-1&&j==n-1&&temp!="")//全部遍历后没有
            {
                str= "解码错误!";
            }
        }
    }
    return str;
}

3 LZ77压缩算法

3.1 概述

Ziv和Lempel于1977年发表题为“顺序数据压缩的一个通用算法(A Universal Algorithm for Sequential Data Compression )”的论文,论文中描述的算法被后人称为LZ77算法。值得说的是,LZ77严格意义上来说不是一种算法,而是一种编码理论。

3.2 重点概念

3.2.1 前向缓冲区

前向缓冲区为待编码区的一段编码。例如待编码数据为ABBCA,选取前向缓冲区数据大小为4,则开始编码时的前向缓冲区中的数据为ABBC。

3.2.2 滑动窗口

滑动窗口是个历史缓冲器,它被用来存放输入流的前n个字节的有关信息。在每一次匹配之后,滑动窗口需要向前滑动。滑动的距离根据匹配的结果决定。

3.3 实现过程

(1)设置编码位置为输入流的开始
(2)在滑窗的待编码区查找搜索区中的最大匹配字符串
(3)如果找到字符串,输出(偏移值, 匹配长度), 窗口向前滑动“匹配长度”
(4)如果没有找到,输出待编码区的第一个字符,窗口向前滑动一个单位
(5)如果待编码区不为空,回到步骤2

通过语言描述算法过程过于晦涩,下面将通过实例说明其实现过程:

例如有字符串:ABABCBABABCAD。设置滑动窗口大小为8,前向缓冲区大小为4。

编码过程:




解码过程:



top Created with Sketch.