压缩文件程序

Question

我想建立一个压缩文件的程序。我使用的是Huffman算法，我用视频：https://www.youtube.com/watch?v=dM6us854Jk0&t=436s研究了它

我试着在比特上使用同样的方式--首先，我在Nibbles上尝试过:我每咬一次(16次)就给它一个随机的频率，后来我构建了一棵二叉树，按照Nibbles的频率排序，就像视频中的那样。

到目前为止，我成功地将22K位压缩成18K。然后我在Bytes (256选项)上试了一下，但它没有工作--一开始它有13M位，压缩后得到89M。

我有一张图片，它显示了Nibble示例的二叉树：

​

​

还有两个exel文件，用于指定Nibbles树和Bytes树的计算：

• 咬嘴：https://drive.google.com/file/d/1X2clucNxr51li61ASdTVdeZHRtISMS4x/view
• 字节：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;
}

每个人都说Huffman算法是压缩文件的最佳算法，所以我在这里遗漏了什么？我在做什么？

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，等等。

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

你应该知道(从编码理论上)一些文本不能被压缩。对于给定的压缩算法，始终存在至少一个不能被压缩的文本。一般来说，无论您尝试使用哪种算法，都至少有一个文本不能被压缩。所有这些都需要更多的理论解释，但这大概是理论可以说的。