压缩文件程序

Question

我正在尝试构建一个用于压缩文件的程序。我正在使用霍夫曼算法，并通过视频对其进行了研究:https://www.youtube.com/watch?v=dM6us854Jk0&t=436s

我尝试在位上使用相同的方式 - 首先我在 Nibbles 上尝试过:我取了每个 Nibble(16 个选项)并给它一个随机频率，后来我构建了一个二叉树，按照视频中的 Nibbles 的频率排序。

我成功将22K位压缩成18K位，到此为止。然后我在 Bytes(256 选项)上尝试了它，但它没有用 - 一开始它有 13M 位，压缩后它有 89M。

我有一张图片展示了 Nibble 示例的二叉树:

还有两个 exel 文件指定了 Nibbles 树和 Bytes 树的计算:

• 半字节:https://drive.google.com/file/d/1X2clucNxr51li61ASdTVdeZHRtISMS4x/view
• 字节数:https://drive.google.com/file/d/1Hn0sSRAaNoSzxgbaBzFejtCnaO_9M4Kv/view

我用C语言实现了算法，这里是部分函数:

typedef struct INFO
{
    unsigned char binary;   //Binary number
    int amount; //Frequency
} INFO;

typedef struct TREE
{
    INFO info;
    struct TREE *prev;
    struct TREE *left;
    struct TREE *right;
} TREE;



/** Function that allocates memory and creates a tree node and initializes it */
TREE * treeNodeMalloc()
{
    TREE *p;
    p = (TREE *)malloc(sizeof(TREE));
    if (!p)
        return NULL;
    p->prev = p->left = p->right = NULL;
    return p;
}


/** Function that builds the first sub-root node consist of two binary numbers */
TREE * firstNode(INFO first, INFO second)
{
    TREE *head, *p;
    int i;
    head = treeNodeMalloc();
    if (!head) return 0;
    for (i = 1; i <= 2; i++)
    {
        p = treeNodeMalloc();
        if (!p) { freeTree(head); return 0; }
        p->prev = head;
        if (i % 2)
        {
            p->info.amount = first.amount;
            p->info.binary = first.binary;
            head->left = p;
        }
        else
        {
            p->info.amount = second.amount;
            p->info.binary = second.binary;
            head->right = p;
        }
    }
    head->info.amount = head->left->info.amount + head->right->info.amount;
    return head;
}


/** Function that builds a sub-root node that consist of a node of binary number and a sub-root of two previous binary numbers */
TREE * continuanceNode(TREE *p1, INFO info)
{
    TREE *h, *p2;
    h = treeNodeMalloc();
    if (!h) { freeTree(p1); return 0; }
    p2 = treeNodeMalloc();
    if (!p2) { free(h); freeTree(p1); return 0; }
    p2->info.amount = info.amount;
    p2->info.binary = info.binary;
    p1->prev = p2->prev = h;
    h->left = p1;
    h->right = p2;
    h->info.amount = h->left->info.amount + h->right->info.amount;
    return h;
}


/** Function that builds the last node of the tree - the main root */
TREE * LastNode(TREE *p1, TREE *p2)
{
    TREE *p3;
    p3 = treeNodeMalloc();
    if (!p3)
    {
        freeTree(p1);
        freeTree(p2);
        return NULL;
    }
    p3->left = p1;
    p3->right = p2;
    p1->prev = p2->prev = p3;
    p3->info.amount = p3->left->info.amount + p3->right->info.amount;
    return p3;
}



/** Function that builds the binary tree from the array of INFO (binary numbers and their frequencies),
The function builds the tree from bottum to the top (reverse build) */
TREE * dataToTree(INFO arr[], int size)
{
    int i;
    TREE *h, *p, *t=NULL;
    p = firstNode(arr[0], arr[1]);
    if (!p) return 0;
    for (i = 2; i < size; i++)
    {
        if (p->info.amount > arr[size - 1].amount)
            if (!t)
            {
                t = firstNode(arr[i], arr[i + 1]); 
                i++;
                if (!t) { freeTree(p); return NULL; }
            }
            else
                if (p->info.amount < t->info.amount)
                {
                    p = continuanceNode(p, arr[i]);
                    if (!p) { freeTree(t); return 0; }
                }
                else
                {
                    t = continuanceNode(t, arr[i]);
                    if (!t) { freeTree(p); return 0; }
                }
        else
        {
            p = continuanceNode(p, arr[i]);
            if (!p) { freeTree(t); return 0; }
        }
    }
    h = LastNode(p, t);
    return h;
}

每个人都说霍夫曼算法是压缩文件的最佳算法，那么我在这里缺少什么？我在做什么？

Answer 1

你构建的霍夫曼树是错误的。在每一步中，您都需要融合所有可用根节点中频率最低的两个节点。所以首先将 9 和 14 融合在一起，它给你:

  21
 /  \
9   14

下一步是融合 21 和 20

    41
   /  \
  21  20
 /  \
9   14

然后是 41 和 50

      91
     /  \
    41  50
   /  \
  21  20
 /  \
9   14

但是这一步最低的两个是70和80，所以分开融合

      91     150
     /  \   /  \
    41  50 70  80
   /  \
  21  20
 /  \
9   14

然后你必须融合最低的两个，91 和 100，等等。

然后树会更“平衡”，结果可能会更好。

你应该知道(从编码理论)有些文本是不能压缩的。对于给定的压缩算法，总是存在至少一个无法压缩的文本。通常，无论您尝试使用任何算法，都至少存在一个无法压缩的文本。所有这些都需要一些更多的理论解释，但大致是理论可以说的。