标签：编码 elements return 哈夫曼 33 char str

一、什么是哈夫曼编码

我们可以用哈夫曼树得到哈夫曼编码，即字符集中每个字符作为一个叶子节点，各个字符出现的频率作为节点的权值，根据上述方法构造哈夫曼树。因为哈夫曼树不唯一，因此哈夫曼编码也不唯一。哈夫曼编码广泛用于数据文件的压缩，其压缩效率通常在 20%~90% 之间。哈夫曼码是可变字长编码（VLC）的一种。哈夫曼编码也被称为最佳编码。

二、哈夫曼编码的原理

统计字符串中的各个字符出现的次数；
按照上面出现的次数构建一颗哈夫曼树，次数作为权值；
根据哈夫曼树，给各个字符规定编码（前缀编码），向左的路径为 0，向右的路径为 1；
根据上面的哈夫曼编码对字符串进行变长编码；

三、最小堆的相关操作

3.1、最小堆的表示

typedef struct HeapStruct *MinHeap;
typedef struct HeapStruct *Heap;
typedef struct TreeNode *HuffmanTree;
typedef HuffmanTree Position;
typedef struct TreeNode ElementType;

struct HeapStruct
{
    ElementType *elements;      // 存储堆元素的数组
    int size;                   // 堆的当前元素个数
    int capacity;               // 堆的最大容量
};

struct TreeNode
{
    char value;                 // 字符
    int weight;                 // 节点权值
    Position left;              // 指向左子节点
    Position right;             // 指向右子节点
};

3.2、最小堆的建立

/**
 * @brief 最小堆的创建
 * 
 * @param maxSize 堆的最大容量
 * @return MinHeap 返回指向最小堆的指针
 */
MinHeap CreateMinHeap(int maxSize)
{
    MinHeap H = malloc(sizeof(struct HeapStruct));
    if(H == NULL)
    {
        printf("分配内存失败！\n");
        return NULL;
    }

    H->elements = calloc((maxSize+1),sizeof(ElementType));
    if(H->elements == NULL)
    {
        printf("分配内存失败！\n");
        return NULL;
    }
  
    H->size = 0;
    H->capacity = maxSize;
    // 定义哨兵为小于堆中所有可能元素的值，便于以后更快操作
    H->elements[0].value = '\0';
    H->elements[0].weight = MinData;
    H->elements[0].left = NULL;
    H->elements[0].right = NULL;

    return H;
}

3.3、最小堆的插入

/**
 * @brief 最小堆的插入
 * 
 * @param H 待操作的最小堆
 * @param item 待插入的元素
 */
void Insert(MinHeap H,ElementType *item)
{
    int i;

    if(H->size == H->capacity)
    {
        printf("最小堆已满\n");
        return;
    }

    i = ++H->size;                                              // i指向插入后堆中的最后一个元素的位置
    for(; H->elements[i/2].weight > item->weight; i /= 2)       // 向下过滤结点
    {
        H->elements[i] = H->elements[i/2];
    }
  
    H->elements[i] = *item;                                     // 将item插入
}

3.4、最小堆的删除

/**
 * @brief 最小堆的删除
 * 
 * @param H 待操作的最小堆
 * @return ElementType 返回要删除的元素（根节点）
 */
ElementType * DeleteMin(MinHeap H)
{
    int parent,child;
    ElementType *minItem = malloc(sizeof(ElementType));
    ElementType temp;

    if(H->size == 0)
    {
        printf("最小堆已经空了\n");
        return NULL;
    }

    // 取出根结点最小值
    minItem->weight = H->elements[1].weight;
    minItem->value = H->elements[1].value;
    minItem->left = H->elements[1].left;
    minItem->right = H->elements[1].right;

    temp = H->elements[H->size--];                                          // 用最小堆中最后一个元素从根节点开始向上过滤下层结点
  
    for(parent = 1; parent*2 <= H->size; parent = child)                    // parent*2 <= H->size判别该节点是否有左孩子
    {
        child = parent * 2;                                                 // child指向左孩子
        if((child != H->size) &&                                            // child==H->size意味着左儿子是最后一个元素
            (H->elements[child].weight > H->elements[child+1].weight))      // 如果左孩子比右孩子大
        {
            child++;                                                        // child指向指向右孩子
        }
        if(temp.weight <= H->elements[child].weight)                        // temp元素比左右儿子都小
        {
            break;
        }
        else                                                                // 移动temp元素到下一层
        {
            H->elements[parent] = H->elements[child];                       // 把左右儿子中小的那个拷贝到parent上
        }
    }
    H->elements[parent] = temp;
  
    return minItem;
}

3.5、最小堆的调整

/**
 * @brief 将一个堆转换为小顶堆
 *
 * @param Heap 待操作的堆
 */
MinHeap BuildMinHeap(Heap H)
{
    int i = 0, j = 0;
    int temp = 0;

    for(i = H->size/2; i >= 1; i--)
    {
        AdjustHeap(H,i,H->size);
    }

    return H;
}

/**
 * @brief 将以i对应的非叶子节点的树调整为小顶堆
 * 
 * @param array 待调整的数组
 * @param i 表示非叶子节点在数组中的索引
 * @param n 待调整的数据的元素的个数
 */
void AdjustHeap(Heap H,int i,int n)
{
    ElementType temp = H->elements[i];
    int k = 0;
    // k=i*2，k是i节点的左子节点
    for(k = i*2; k <= n; k = k*2)
    {
        if(k+1 <= n && H->elements[k].weight > H->elements[k+1].weight)     // 左子节点的值大于右子节点的值
        {
            k++;                                                            // k指向右子节点
        }
        if(H->elements[k].weight < temp.weight)                             // 如果子节点小于父节点
        {
            H->elements[i] = H->elements[k];                                // 把较大的值赋值给当前节点
            i = k;                                                          // i指向k，继续循环比较
        }
        else
        {
            break;
        }
    }
    // 当for循环结束后，已经将以i为父节点的树的最小值，放在了最顶上，即局部小顶堆
    H->elements[i] = temp;                                                  //将temp放在调整后的位置
}

四、字符编码

4.1、字符编码的表示

typedef struct CodingMap *CodeMap;
typedef struct Maping *Map;

struct CodingMap
{
    Map map;                    // 键值对，用于存储字符编码的键值对
    int count;                  // 用于存储键值对的个数
};

struct Maping
{
    char key;                   // 用于存放字符本身
    int value;                  // 用于存储字符出现的次数
};

4.2、生成字符编码

统计字符串中的各个字符出现的次数；

/**
 * @brief 获取字符编码函数
 * 
 * @param str 待编码的字符串
 * @return CodeMap 返回字符编码的键值对 
 */
CodeMap GetCodeMap(char str[])
{
    int length = strlen(str);
    int i = 0;
    char chCode[128] = {0};

    CodeMap codeMap = malloc(sizeof(struct CodingMap));
    if(codeMap == NULL)
    {
        printf("分配内存失败！\n");
        return NULL;
    }

    codeMap->map = calloc(128,sizeof(struct Maping));
    if(codeMap->map == NULL)
    {
        printf("分配内存失败！\n");
        return 0;
    }

    codeMap->count = 0;

    for(i = 0; i < length; i++)
    {
        chCode[str[i]]++;                           // 统计字符个数
    }

    for(i = 0; i < 128; i++)
    {
        if(chCode[i] != 0)
        {
            codeMap->map[codeMap->count].key = i;
            codeMap->map[codeMap->count].value = chCode[i];
            codeMap->count++;
        }
    }

    return codeMap;
}

五、哈夫曼树的构建

按照字符出现的次数构建一颗哈夫曼树，次数作为权值；

/**
 * @brief 哈夫曼树的构造
 * 
 * @param H 根据结点创建最小堆
 * @return HuffmanTree 返回执行树根的指针
 */
HuffmanTree CreateHuffmanTree(CodeMap codeMap)
{
    // 假设H->size个权值已经存在H->elements[]里
    int i;
    HuffmanTree T;

    MinHeap H = CreateMinHeap(MinSize);
    for(i = 0; i < codeMap->count; i++)
    {
        H->elements[i+1].value = codeMap->map[i].key;
        H->elements[i+1].weight = codeMap->map[i].value;
        H->elements[i+1].left = NULL;
        H->elements[i+1].right = NULL;
        H->size++;
    }

    H = BuildMinHeap(H);                                    // 将H->elements[]按权值调整为最小堆

    while(H->size > 1)                                      // 做H->size-1次合并
    {
        T = malloc(sizeof(ElementType));                    // 建立新节点
        if(T == NULL)
        {
            printf("分配内存失败！\n");
            return NULL;
        }

        T->left = DeleteMin(H);
        T->right = DeleteMin(H);
        T->value = '\0';
        T->weight = T->left->weight + T->right->weight;     // 计算新权值

        Insert(H,T);                                        // 将新T插入最小堆
    }

    T = DeleteMin(H);

    return T;
}

六、哈夫曼编码

6.1、哈夫曼编码的表示

typedef struct HuffmanCodingMap *HuffmanCodeMap;
typedef struct HuffmanMapping *HuffmanMap;

struct HuffmanCodingMap
{
    HuffmanMap map;             // 键值对，用于存储哈夫曼编码的键值对
    int count;                  // 用于存储键值对的个数
};

struct HuffmanMapping
{
    char key;                   // 用于存放字符本身
    char *value;                // 用于存储哈夫曼编码
};

6.2、生成哈夫曼编码表

根据哈夫曼树，给各个字符规定编码（前缀编码），向左的路径为 0，向右的路径为 1；

/**
 * @brief 获取哈夫曼编码表
 * 
 * @param tree 待操作的哈夫曼树
 * @return HuffmanCodeMap 返回哈夫曼编码表
 */
HuffmanCodeMap GetHuffmanEncode(HuffmanTree tree)
{
    char str[100] = {0};

    if(tree == NULL)
    {
        printf("哈夫曼树为空！\n");
        return NULL;
    }
    GetHuffmanCodeMap(tree->left,"0",str);
    GetHuffmanCodeMap(tree->right,"1",str);

    return huffmanCodeMap;
}

/**
 * @brief 哈夫曼编码表的核心算法
 * 
 * @param tree 待操作的哈夫曼树
 * @param code 哈夫曼树的左路径为 0，右路径为 1
 * @param str 递归生成哈夫曼编码
 */
void GetHuffmanCodeMap(HuffmanTree tree,char code[],char str[])
{
    static int num = 0;
    char string[100];

    strcpy(string,str);
    strcat(string,code);

    if(tree != NULL)
    {
        // 判断当前节点是叶子节点还是非叶子节点
        if(tree->value == '\0')                                     // 非叶子节点
        {
            // 递归处理
            GetHuffmanCodeMap(tree->left,"0",string);              // 向左递归
            GetHuffmanCodeMap(tree->right,"1",string);             // 向右递归
        }
        else                                                        // 叶子节点
        {
            huffmanCodeMap->map[num].key = tree->value;
            huffmanCodeMap->map[num].value = malloc(sizeof(strlen(string)));
            strcpy(huffmanCodeMap->map[num].value,string);
            num++;
        }
    }
}

七、数据压缩

typedef struct HuffmanEncoding *HuffmanEncode;

struct HuffmanEncoding
{
    int length;
    char *HuffmanCodeByte;
    int lastBit;
};

/**
 * @brief 哈夫曼压缩函数
 * 
 * @param str 原始字符串
 * @return HuffmanEncode 返回编码后的字符数组
 */
HuffmanEncode HuffmanZip(char *str)
{
    int i = 0;

    CodeMap codeMap = GetCodeMap(str);                                          // 获取字符编码

    HuffmanTree tree = CreateHuffmanTree(codeMap);                              // 获取哈夫曼树

    huffmanCodeMap = malloc(sizeof(struct HuffmanCodingMap));
    if(huffmanCodeMap == NULL)
    {
        printf("分配内存失败！\n");
        return 0;
    }
    huffmanCodeMap->count = codeMap->count;
    huffmanCodeMap->map = calloc(huffmanCodeMap->count,sizeof(struct HuffmanMapping));
    if(huffmanCodeMap->map == NULL)
    {
        printf("分配内存失败！\n");
        return 0;
    }

    huffmanCodeMap = GetHuffmanEncode(tree);                                    // 根据哈夫曼树获取哈夫曼编码

    HuffmanEncode huffmanEncode = Zip(str,huffmanCodeMap);                      // 根据哈夫曼编码对原始字符串进行压缩

    return huffmanEncode;
}

/**
 * @brief 将字符串进行编码
 * 
 * @param src 原始的字符串
 * @param huffmanCode 哈夫曼编码表
 * @return HuffmanEncode 返回编码后的字符数组
 */
HuffmanEncode Zip(char * src,HuffmanCodeMap huffmanCode)
{
    int i = 0, j = 0;
    char str[1024] = {0};                               // 哈夫曼编码对应的字符串

    // 利用哈夫曼编码表将原始字符串转换成哈夫曼编码对应的字符串
    for(i = 0; i < strlen(src); i++)                    // 遍历源数组
    {
        for(j = 0; j < huffmanCode->count; j++)
        {
            if(src[i] == huffmanCode->map[j].key)
            {
                strcat(str,huffmanCode->map[j].value);
                break;
            }
        }
    }

    int len = (strlen(str) + 7) / 8;                    // 统计返回哈夫曼编码的长度
    int index = 0;                                      // 记录第一个byte

    HuffmanEncode huffmanEncode = malloc(sizeof(struct HuffmanEncoding));
    if(huffmanEncode == NULL)
    {
        printf("分配内存失败！\n");
        return NULL;
    }
    huffmanEncode->length = len;
    huffmanEncode->lastBit = strlen(str) % 8 ? strlen(str) % 8 : 8;
    huffmanEncode->HuffmanCodeByte = calloc(huffmanEncode->length,sizeof(char));

    // 将字符串转换为字节数组，每8位对应一个byte，所以步长为8
    for(i = 0; i < strlen(str); i += 8)
    {
        huffmanEncode->HuffmanCodeByte[index] = 0;

        char strByte[9] = {0};
        if(i+8 > strlen(str))                           // 不够8位
        {
            strcpy(strByte,str+i);
        }
        else
        {
            strncpy(strByte,str+i,8);
        }
      

        for(j = 0; j < strlen(strByte); j++)
        {
            if(strByte[j] == '1')
            {
                huffmanEncode->HuffmanCodeByte[index] += (int)pow(2,strlen(strByte)-j-1);
            }
        }
        index++;
    }
  
    return huffmanEncode;
}

八、数据的解压

数据解压的思路：

将哈夫曼字节数组 huffmanEncode 先转成哈夫曼编码对应的二进制字符串。
将哈夫曼编码对应的二进制字符串对照哈夫曼编码表重新转成字符串；

/**
 * @brief 根据哈夫曼编码进行解码
 * 
 * @param huffmanCode 哈夫曼编码表
 * @param huffmanEncode 压缩后的字节数组
 * @param encodeStr 解压后的字符串
 * @return char* 返回指向解压后的字符串的首地址
 */
char * Unzip(HuffmanCodeMap huffmanCode,HuffmanEncode huffmanEncode,char encodeStr[])
{
    int i = 0, j = 0;
    char str[9] = {0};
    char binStr[huffmanEncode->length * 8];
    int num = 0;

    // 先得到huffmanEncode对应的二进制字符串
    // 循环处理前length-1个编码的字节数组
    for(i = 0; i < huffmanEncode->length - 1; i++)
    {
        memset(str,0,9);
        byteToBitString(huffmanEncode->HuffmanCodeByte[i],8,str);
        strcat(binStr,str);
    }
    // 处理最后一个编码的字节数组
    memset(str,0,9);
    byteToBitString(huffmanEncode->HuffmanCodeByte[i],huffmanEncode->lastBit,str);
    strcat(binStr,str);

    // 把二进制字符串按照哈夫曼编码表进行解码
    for(i = 0; i < strlen(binStr);)
    {
        char count = 1;
        char flag = 1;
        char b = 0;

        while(flag)
        {
            char key[100] = {0};
            strncpy(key,binStr+i,count);                            // i不动，count移动，指定匹配一个字符
            for(j = 0; j < huffmanCode->count; j++)
            {
                if(strcmp(key,huffmanCode->map[j].value) == 0)      // 如果匹配到
                {
                    b = huffmanCode->map[j].key;
                    // printf("%s:%c\n",key,b);
                    flag = 0;
                    break;
                }
            }
            if(flag)                                                // 如果没有匹配到
            {
                count++;
            }
        
        }

        encodeStr[num++] = b;
        i += count;
    }

    // 当for循环结束后，encodeStr[]存放了所有的字符
    return encodeStr;
}

/**
 * @brief 将一个字节数组转换为对应的二进制字符串
 * 
 * @param byte 待操作的字节数组
 * @param bit 字节中的位数
 * @param str 转换的二进制字符串
 * @return char* 返回执行二进制字符串的首地址
 */
char * byteToBitString(char byte,char bit,char str[])
{
    int i = 0;

    for(i = 0; i < bit; i++)
    {
        str[i] = ((byte >> (bit - 1 - i)) & 1) + '0';
    }

    return str;
}

九、测试程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

HuffmanCodeMap huffmanCodeMap;

int main(void)
{
    char str[] = "The past belongs to death, and that the future belongs to yourself.";                    // 原始字符串
    int i = 0;
    char encodeStr[100];

    HuffmanEncode huffmanEncode = HuffmanZip(str);                              // 根据哈夫曼编码对原始字符串进行压缩

    Unzip(huffmanCodeMap,huffmanEncode,encodeStr);
    printf("%s\n",encodeStr);

    return 0;
}

标签：编码,elements,return,哈夫曼,33,char,str
From： https://www.cnblogs.com/kurome/p/17491844.html

33. 哈夫曼编码