贪心算法 哈夫曼编码

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。贪心算法与动态规划不同的是它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。贪心算法可以解决一些最优化问题，如:求图中的最小生成树、求哈夫曼编码等。

哈夫曼编码是一种可变字长编码(VLC)的一种，它是一种编码方式，完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。哈夫曼编码被广泛地用于数据文件压缩，其压缩率通常在20%～90%之间。

--相关问题--:
1. 贪心算法和动态规划有什么区别？
2. 哈夫曼编码的压缩率如何计算？

相关问题

贪心算法哈夫曼编码C语言

哈夫曼编码是一种基于贪心算法的压缩算法，其核心思想是将出现频率较高的字符用较短的编码表示，而出现频率较低的字符用较长的编码表示。以下是哈夫曼编码的C语言实现：

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

#define MAX_TREE_HT 100

struct MinHeapNode {
    char data;
    unsigned freq;
    struct MinHeapNode *left, *right;
};

struct MinHeap {
    unsigned size;
    unsigned capacity;
    struct MinHeapNode **array;
};

struct MinHeapNode *newNode(char data, unsigned freq) {
    struct MinHeapNode *temp = (struct MinHeapNode *)malloc(sizeof(struct MinHeapNode));
    temp->left = temp->right = NULL;
    temp->data = data;
    temp->freq = freq;
    return temp;
}

struct MinHeap *createMinHeap(unsigned capacity) {
    struct MinHeap *minHeap = (struct MinHeap *)malloc(sizeof(struct MinHeap));
    minHeap->size = 0;
    minHeap->capacity = capacity;
    minHeap->array = (struct MinHeapNode **)malloc(minHeap->capacity * sizeof(struct MinHeapNode *));
    return minHeap;
}

void swapMinHeapNode(struct MinHeapNode **a, struct MinHeapNode **b) {
    struct MinHeapNode *t = *a;
    *a = *b;
    *b = t;
}

void minHeapify(struct 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(struct MinHeap *minHeap) {
    return (minHeap->size == 1);
}

struct MinHeapNode *extractMin(struct MinHeap *minHeap) {
    struct MinHeapNode *temp = minHeap->array[0];
    minHeap->array[0] = minHeap->array[minHeap->size - 1];
    --minHeap->size;
    minHeapify(minHeap, 0);
    return temp;
}

void insertMinHeap(struct MinHeap *minHeap, struct MinHeapNode *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(struct 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) {
    int i;
    for (i = 0; i < n; ++i)
        printf("%d", arr[i]);
    printf("\n");
}

int isLeaf(struct MinHeapNode *root) {
    return !(root->left) && !(root->right);
}

struct MinHeap *createAndBuildMinHeap(char data[], int freq[], int size) {
    struct MinHeap *minHeap = createMinHeap(size);
    for (int i = 0; i < size; ++i)
        minHeap->array[i] = newNode(data[i], freq[i]);
    minHeap->size = size;
    buildMinHeap(minHeap);
    return minHeap;
}

struct MinHeapNode *buildHuffmanTree(char data[], int freq[], int size) {
    struct MinHeapNode *left, *right, *top;
    struct MinHeap *minHeap = createAndBuildMinHeap(data, freq, size);
    while (!isSizeOne(minHeap)) {
        left = extractMin(minHeap);
        right = extractMin(minHeap);
        top = newNode('$', left->freq + right->freq);
        top->left = left;
        top->right = right;
        insertMinHeap(minHeap, top);
    }
    return extractMin(minHeap);
}

void printCodes(struct MinHeapNode *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);
    }
}

void HuffmanCodes(char data[], int freq[], int size) {
    struct MinHeapNode *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;
}

以上代码实现了哈夫曼编码的生成过程，包括建立哈夫曼树、生成编码等步骤。

贪心算法哈夫曼编码java

贪心算法哈夫曼编码是一种基于贪心思想的数据压缩算法。下面是实现哈夫曼编码的Java代码：

import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Comparator;
import java.util.HashMap;

class HuffmanNode {
    char c;
    int freq;
    HuffmanNode left, right;
}

class MyComparator implements Comparator<HuffmanNode> {
    public int compare(HuffmanNode x, HuffmanNode y) {
        return x.freq - y.freq;
    }
}

public class HuffmanCode {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String text = input.nextLine().trim();
        HashMap<Character, Integer> frequency = new HashMap<>();
        for (int i = 0; i < text.length(); i++) {
            char c = text.charAt(i);
            if (frequency.containsKey(c)) {
                frequency.put(c, frequency.get(c) + 1);
            } else {
                frequency.put(c, 1);
            }
        }
        PriorityQueue<HuffmanNode> pq = new PriorityQueue<>(new MyComparator());
        for (char c : frequency.keySet()) {
            HuffmanNode node = new HuffmanNode();
            node.c = c;
            node.freq = frequency.get(c);
            node.left = null;
            node.right = null;
            pq.add(node);
        }
        while (pq.size() > 1) {
            HuffmanNode node1 = pq.poll();
            HuffmanNode node2 = pq.poll();
            HuffmanNode newNode = new HuffmanNode();
            newNode.freq = node1.freq + node2.freq;
            newNode.c = '-';
            newNode.left = node1;
            newNode.right = node2;
            pq.add(newNode);
        }
        HuffmanNode root = pq.peek();
        HashMap<Character, String> codes = new HashMap<>();
        encode(root, "", codes);
        for (char c : codes.keySet()) {
            System.out.println(c + ": " + codes.get(c));
        }
    }

    private static void encode(HuffmanNode node, String code, HashMap<Character, String> codes) {
        if (node == null) {
            return;
        }
        if (node.c != '-') {
            codes.put(node.c, code);
        }
        encode(node.left, code + "0", codes);
        encode(node.right, code + "1", codes);
    }
}

代码中使用了优先队列来存储哈夫曼树的节点，并且定义了一个比较器来按照节点权重来进行优先级排序。在主函数中，首先统计了字符串中每个字符的出现频率，然后把每个字符和对应的频率封装成节点放入优先队列中。然后通过循环，不断取出优先队列中最小的两个节点，合并成一个新节点，并且把这个新节点放入优先队列中。最终，优先队列中只剩下一个节点，这个节点就是哈夫曼树的根节点。接着，利用递归的方法，对哈夫曼树进行遍历，生成每个字符对应的编码，并存储在一个HashMap中。最后，输出每个字符和对应的编码。