从头开始构建顺序霍夫曼树

Question

给定一些文本文件，我需要读取每个字母数字字符并使用 Huffman's algorithm.

对其进行编码

解决了读取字符、存储概率和创建节点以及使用指针创建霍夫曼特里树的问题。

但是，我需要使用二叉树的顺序表示来创建和初始化哈夫曼树，而无需任何指针。

这可以通过使用指针创建常规树然后将其读入数组来完成，但我的目标是直接用节点填充数组。

我考虑创建更小的树并将它们合并在一起，但选择了矩阵表示，我将从二叉堆中收集具有最小概率的元素并将它们存储到矩阵的行中，矩阵的行代表节点应该在二叉树中的级别，顺序相反。

E.g. Given characters and their probabilities as char[int] pairs.

a[1], b[1], c[2], d[1], e[3], f[11], g[2]

I aim to create matrix that looks like 
____________________________________
    a   |    b   |    d   |    g   |
____________________________________
   ab   |    c   |   dg   |    e   |
____________________________________
   abc  |   deg  |        |        |
____________________________________ 
 abcdeg |    f   |        |        |  
____________________________________
abcdefg |        |        |        |
____________________________________

Where levels of a, b, c, d, e & f would be rows of a matrix.

目前，我一直在研究如何在 "parent" 移动时递归增加元素的级别（如果我将来自不同级别的两个节点 ['ab' 和 'c'], 我很容易将 c 的级别与 ab 相等并解决问题，但是如果 'c' 和 'd' 都在第二行）以及如何创建完整的二叉树（如果它有左儿子，它需要有右儿子）只有终端节点的级别。

事先，我知道这个问题不是很具体，很高兴听到是否有另一种方法来解决这个问题，而不是仅仅解决上述问题。

Answer 1

这是作业的人为问题吗？我问是因为不使用 links 的树表示需要 O(2^h) space 来存储高度为 h 的树。这是因为他们假设树是完整的，允许索引计算来代替指针。由于对于大小为 m 的字母表，哈夫曼树的高度可以为 h=m-1，因此最坏情况下数组的大小可能会非常大。大部分都不会被使用。

但是如果你放弃link必须是指针的想法，允许它是数组索引，那你就没事了。很久以前——在动态内存分配器变得普遍之前——这是标准的。这个问题对这个方法特别好，因为你总是提前知道树中的节点数：比字母表大小的两倍少一个。在 C 中你可能会做这样的事情

typedef struct {
  char ch;
  int f;
  int left, right; // Indices of children. If both -1, this is leaf for char ch.
} NODE;

#define ALPHABET_SIZE 7
NODE nodes[2 * ALPHABET_SIZE - 1] = {
  { 'a', 1, , -1, -1}, 
  { 'b', 1, -1, -1 }, 
  { 'c', 2, -1, -1 }, 
  { 'd', 1, -1, -1 }, 
  { 'e', 3, -1, -1 },
  { 'f', 11, -1, -1 }, 
  { 'g', 2, -1, -1 },
  // Rest of array for internal nodes
};
int n_nodes = ALPHABET_SIZE;

int add_internal_node(int f, int left, int right) {
  // Allocate a new node in the array and fill in its values.
  int i = n_nodes++;
  nodes[i] = (NODE) { .f = f, .left = left, .right = right };
  return i;
}

现在您将像这样使用标准的树构建算法：

int build_huffman_tree(void) {
  // Add the indices of the leaf nodes to the priority queue.
  for (int i = 0; i < ALPHABET_SIZE; ++i)
    add_to_frequency_priority_queue(i);
  while (priority_queue_size() > 1) {
    int a = remove_min_frequency(); // Removes index of lowest freq node from the queue.
    int b = remove_min_frequency();
    int p = add_internal_node(nodes[a].f + nodes[b].f, a, b);
    add_to_frequency_priority_queue(p);
  }
  // Last node is huffman tree root.
  return remove_min_frequency();
}

解码算法将像这样使用根的索引：

char decode(BIT bits[], int huffman_tree_root_index) {
  int i = 0, p = huffman_tree_root_index;
  while (node[p].left != -1 || node[p].right != -1) // while not a leaf
    p = bits[i++] ? nodes[p].right : nodes[p].left;
  return nodes[p].ch;
}

当然这不会return消耗了多少位，这是真正的解码器需要做的。真正的解码器也不会在数组中获取它的位。最后，对于 encoding，除了子索引之外，您还需要父索引。解决这些问题应该很有趣。祝你好运。

从头开始构建顺序霍夫曼树

Constructing sequential Huffman Tree From Scratch

c

algorithm

binary-tree

huffman-code

data-structures