Huffman编码与Morse电码

Huffman编码

Huffman编码是一种无损数据压缩算法，通过使用变长编码表对源符号（如文件中的一个字母）进行编码。该变长编码表是基于符号出现的概率来构建的：出现频率高的符号使用较短的编码，而出现频率低的符号则使用较长的编码。这种方式可以有效地减少编码后的平均长度和期望值，从而实现数据的无损压缩。

例如，在英文文本中，字母e的出现频率最高，而字母z的出现频率最低。当利用Huffman编码对一篇英文文章进行压缩时，e可能用一个位元来表示，而z可能需要25个位元来表示。相较于每个字母固定占用8个位元的普通表示方法，e的编码长度大大缩短，而z的编码长度有所增加。如果能准确估算英文中各个字母的出现概率，就可以显著提高无损压缩的效率。

Huffman树

Huffman树，也称最优二叉树，是一种带权路径长度最短的二叉树。树的带权路径长度是树中所有叶结点的权值乘以其到根结点的路径长度之和。具体构建过程如下：

统计频率：计算每个字符在输入数据中的出现频率。
构建优先队列：将每个字符及其频率作为一个节点，放入优先队列（最小堆）。
生成Huffman树：重复以下步骤直到队列中只剩一个节点：
- 从队列中取出两个频率最小的节点，作为左右子节点创建一个新的父节点，其频率为两个子节点频率之和。
- 将新节点插入队列。
生成编码：从根节点开始，为每个左边路径分配0，右边路径分配1，直到达到叶节点，每个叶节点的路径就是对应字符的Huffman编码。

Huffman树的路径长度总和（WPL）是最小的，这可以通过构造过程中的贪心策略证明。

编码实现

使用Huffman算法对一组字符进行编码，并打印出每个字符的Huffman编码。

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

#define MAX_TREE_HT 100

// Huffman树节点
typedef struct HuffmanNode {
    char data;
    unsigned freq;
    struct HuffmanNode *left, *right;
} HuffmanNode;

// 优先队列节点
typedef struct MinHeapNode {
    unsigned size;
    unsigned capacity;
    HuffmanNode **array;
} MinHeap;

// 创建一个新的Huffman节点
HuffmanNode* createNode(char data, unsigned freq) {
    HuffmanNode* node = (HuffmanNode*)malloc(sizeof(HuffmanNode));
    node->data = data;
    node->freq = freq;
    node->left = node->right = NULL;
    return node;
}

// 创建一个最小堆节点
MinHeap* createMinHeap(unsigned capacity) {
    MinHeap* minHeap = (MinHeap*)malloc(sizeof(MinHeap));
    minHeap->size = 0;
    minHeap->capacity = capacity;
    minHeap->array = (HuffmanNode**)malloc(minHeap->capacity * sizeof(HuffmanNode*));
    return minHeap;
}

// 交换两个最小堆节点
void swapMinHeapNode(HuffmanNode** a, HuffmanNode** b) {
    HuffmanNode* t = *a;
    *a = *b;
    *b = t;
}

// 最小堆化
void minHeapify(MinHeap* minHeap, int idx) {
    int smallest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;

    if (left < minHeap->size && minHeap->array[left]->freq < minHeap->array[smallest]->freq)
        smallest = left;

    if (right < minHeap->size && minHeap->array[right]->freq < minHeap->array[smallest]->freq)
        smallest = right;

    if (smallest != idx) {
        swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]);
        minHeapify(minHeap, smallest);
    }
}

// 检查是否只有一个节点
int isSizeOne(MinHeap* minHeap) {
    return (minHeap->size == 1);
}

// 提取最小值节点
HuffmanNode* extractMin(MinHeap* minHeap) {
    HuffmanNode* temp = minHeap->array[0];
    minHeap->array[0] = minHeap->array[minHeap->size - 1];
    --minHeap->size;
    minHeapify(minHeap, 0);
    return temp;
}

// 插入最小堆
void insertMinHeap(MinHeap* minHeap, HuffmanNode* minHeapNode) {
    ++minHeap->size;
    int i = minHeap->size - 1;
    while (i && minHeapNode->freq < minHeap->array[(i - 1) / 2]->freq) {
        minHeap->array[i] = minHeap->array[(i - 1) / 2];
        i = (i - 1) / 2;
    }
    minHeap->array[i] = minHeapNode;
}

// 构建最小堆
void buildMinHeap(MinHeap* minHeap) {
    int n = minHeap->size - 1;
    int i;
    for (i = (n - 1) / 2; i >= 0; --i)
        minHeapify(minHeap, i);
}

// 打印数组
void printArr(int arr[], int n) {
    for (int i = 0; i < n; ++i)
        printf("%d", arr[i]);
    printf("\n");
}

// 检查是否是叶节点
int isLeaf(HuffmanNode* root) {
    return !(root->left) && !(root->right);
}

// 创建并构建最小堆
MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) {
    MinHeap* minHeap = createMinHeap(size);
    for (int i = 0; i < size; ++i)
        minHeap->array[i] = createNode(data[i], freq[i]);
    minHeap->size = size;
    buildMinHeap(minHeap);
    return minHeap;
}

// 构建Huffman树
HuffmanNode* buildHuffmanTree(char data[], int freq[], int size) {
    HuffmanNode *left, *right, *top;
    MinHeap* minHeap = createAndBuildMinHeap(data, freq, size);
    while (!isSizeOne(minHeap)) {
        left = extractMin(minHeap);
        right = extractMin(minHeap);
        top = createNode('$', left->freq + right->freq);
        top->left = left;
        top->right = right;
        insertMinHeap(minHeap, top);
    }
    return extractMin(minHeap);
}

// 打印Huffman编码
void printCodes(HuffmanNode* root, int arr[], int top) {
    if (root->left) {
        arr[top] = 0;
        printCodes(root->left, arr, top + 1);
    }
    if (root->right) {
        arr[top] = 1;
        printCodes(root->right, arr, top + 1);
    }
    if (isLeaf(root)) {
        printf("%c: ", root->data);
        printArr(arr, top);
    }
}

// 构建并打印Huffman编码
void HuffmanCodes(char data[], int freq[], int size) {
    HuffmanNode* root = buildHuffmanTree(data, freq, size);
    int arr[MAX_TREE_HT], top = 0;
    printCodes(root, arr, top);
}

int main() {
    char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f' };
    int freq[] = { 5, 9, 12, 13, 16, 45 };
    int size = sizeof(arr) / sizeof(arr[0]);
    HuffmanCodes(arr, freq, size);
    return 0;
}

注解：

频率数组和字符数组：arr[]和freq[]分别存储了字符和它们的频率。在主程序中，我们使用这些数组来构建Huffman树。
构建Huffman树：我们首先创建一个最小堆，包含所有字符。然后，我们反复从堆中取出两个频率最小的节点，创建一个新的内部节点并插入回堆中，直到堆中只有一个节点，这个节点就是Huffman树的根。
打印Huffman编码：我们从根节点开始，左边路径记作0，右边路径记作1，递归遍历树直到叶节点，每个叶节点的路径就是该字符的Huffman编码。

Morse编码

摩尔斯电码（Morse Code）是一种时通时断的信号代码，通过不同的排列顺序来表达不同的英文字母、数字和标点符号。是由美国人萨缪尔·摩尔斯在1836年发明的。

Morse电码是一种早期的数码化通信形式，但不同于现代只使用0和1两种状态的二进制代码，它的代码包括五种：

点（.）
划（-）
每个字符间短的停顿（在点和划之间的停顿）
每个词之间中等的停顿
句子之间长的停顿

通过这些基本元素的不同组合，Morse电码可以表示各种字符和符号。例如，字母A的Morse电码为".-"，字母B的Morse电码为"-..."。

编码实现

实现根据英文字母a-z的Morse码表，对输入文段进行Morse编码，并计算编码总长度和平均码长

#include <stdio.h>
#include <string.h>
#include <ctype.h>

// Morse码表
const char* morseTable[26] = {
    ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---",
    "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-",
    "..-", "...-", ".--", "-..-", "-.--", "--.."
};

// 获取字符的Morse编码
const char* getMorseCode(char c) {
    if (c >= 'a' && c <= 'z')
        return morseTable[c - 'a'];
    else if (c >= 'A' && c <= 'Z')
        return morseTable[c - 'A'];
    return "";
}

// 对指定文段进行Morse编码，并计算总长度和平均码长
void encodeMorse(const char* text) {
    int totalLength = 0;
    int charCount = 0;

    for (int i = 0; text[i] != '\0'; ++i) {
        if (text[i] == ' ')
            continue;

        const char* morseCode = getMorseCode(text[i]);
        printf("%s ", morseCode);

        totalLength += strlen(morseCode);
        charCount++;
    }

    printf("\n总编码长度: %d\n", totalLength);
    printf("平均码长: %.2f\n", (double)totalLength / charCount);
}

int main() {
    char text[1000];
    printf("请输入要编码的字符串: ");
    fgets(text, sizeof(text), stdin);
    
    // 移除fgets读取的换行符
    size_t len = strlen(text);
    if (len > 0 && text[len-1] == '\n') {
        text[len-1] = '\0';
    }
    
    encodeMorse(text);
    return 0;
}

输入任何字符串，并将其转换为Morse编码，同时计算并输出编码的总长度和平均码长。具体步骤如下：