Huffman

哈夫曼树的学习

【oi-wiki】霍夫曼树

![[Huffman.png]]

基本概念#

树的带权路径长度#

设二叉树具有 n 个带权叶结点，从根结点到各叶结点的路径长度与相应叶节点权值的乘积之和称为

树的带权路径长度（Weighted Path Length of Tree，WPL）。

结构#

对于给定一组具有确定权值的叶结点，可以构造出不同的二叉树，其中，WPL 最小的二叉树 称为 霍夫曼树（Huffman Tree）。

程序逆向#

馒头

听说你数据结构与算法学的很好？

出题人：@Ea5y

题目文 件链接{:download="mt.exe"}

64位的，扔进ida里面分析

main#

huffmanTree HT; // [rsp+28h] [rbp-8h] BYREF

initHuffmanTree(&HT);
creatHuffmanTree(&HT, 24);
if ( check_flag(HT, 47) )
    printf("yes");
return 0;

initHuffmanTree#

*HT = (huffmanTree)malloc(0x3C0ui64);
for ( i = 1; i <= 47; ++i )
{
    v1 = &(*HT)[i];
    v1->rch = -1;
    v2 = &(*HT)[i];
    v2->lch = v1->rch;
    (*HT)[i].parent = v2->lch;
}
puts("please input flag:");
for ( i_0 = 1; i_0 <= 24; ++i_0 )
{
    a = getchar();
    (*HT)[i_0].data = i_0;                      // 下标
    (*HT)[i_0].weight = a;                      // 权重为ascii
}
return 1;

creatHuffmanTree#

if ( n > 1 )
{
    for ( i = n + 1; i < 2 * n; ++i )           // n = 24, for i in range(25, 48)
    {
    min1 = 0x7FFF;                            // 32767
    lnode = -1;
    min2 = 0x7FFF;                            // 32767
    rnode = -1;
    for ( j = 1; i > j; ++j )                 // j < i, 找到权重最小的两个下标，分别放在lnode和rnode
    {
        if ( min1 > (*HT)[j].weight && (*HT)[j].parent == -1 )// 如果权重小于min1，且没有父节点
        {
            min2 = min1;                          // 把原来的最小存到min2
            rnode = lnode;                        // 右变左
            min1 = (*HT)[j].weight;               // 把min1设置成j的权重
            lnode = j;                            // 左节点设成j
        }
        else if ( min2 > (*HT)[j].weight && (*HT)[j].parent == -1 )// 如果权重小于min2，且没有父节点
        {
            min2 = (*HT)[j].weight;
            rnode = j;                            // 右节点设置为j
        }
    }
    v2 = &(*HT)[rnode];
    v2->parent = i;                           // 提升，rnode和lnode的父节点设置成i
    (*HT)[lnode].parent = v2->parent;
    (*HT)[i].lch = lnode;                     // i的lch和rch设置成lnode和rnode，权重为l r 权重之和
    (*HT)[i].rch = rnode;
    (*HT)[i].weight = (*HT)[lnode].weight + (*HT)[rnode].weight;
    }
}

上面的代码就生成了哈夫曼树，根节点在 HT[47]

check_flag#

int __cdecl check_flag(huffmanTree HT, int i)
{
    int data; // ecx
    int v3; // eax
    int result; // eax
    int weight; // ecx
    int v6; // eax
    int v7; // ecx
    int v8; // eax

    if ( i <= 24 )
    {
        data = HT[i].data;
        v3 = index++;
        if ( data != ans1[v3] )
        return 0;
    }
    if ( i <= 24 )
        goto LABEL_11;
    weight = HT[i].weight;
    v6 = index++;
    if ( weight != ans1[v6] )
        return 0;
    if ( HT[HT[i].lch].data <= 24 && HT[HT[i].lch].data > 0 )// 如果左节点是第一部分初始化的节点
                                                    // 即如果有数据，那就检查，然后在下一次迭代中检查data
                                                    // 如果没数据，就在下一次迭代中检查
    {
        v7 = HT[HT[i].lch].weight;
        v8 = index++;
        if ( v7 != ans1[v8] )
        return 0;
    }
    LABEL_11:
    if ( HT[i].lch <= 0 )                         // 如果左节点没了，就返回true
        return 1;
    result = check_flag(HT, HT[i].lch) && check_flag(HT, HT[i].rch);// 如果还有，就检查左节点和右节点
    if ( (_BYTE)result )
        return 1;
    return result;
}

其中 ans1 中的数据即下面 EXP 的 data

这里是按照 先序遍历 节点的 权重/data ，然后依次比较 ans1 中的值（【oi-wiki】先序遍历）

• 左叶节点的权重和data都会被比较

• 右叶节点只有data会被比较

在 initHuffmanTree 中得知，data为下标，对应的权重为ascii码

又因为只要有左节点，一定会有右节点——如果没有找到，说明就是右叶节点

EXP#

递归 类似先序遍历

data = [0x8de,0x395,0x1be,0xd9,0x6a,0x33,0x14,0xf,0x11,0xe5,0x72,0x10,0xb,0x1d7,0xe9,0x74,0xe,0xd,0xee,0x76,0xc,0x7,0x549,0x22d,0xf8,0x7b,0x6,0x18,0x135,0x89,0x43,0x3,0x5,0xac,0x54,0x4,0x1,0x31c,0x17f,0xba,0x59,0x2,0x8,0xc5,0x61,0x30,0x17,0xa,0x15,0x19d,0xcb,0x65,0x16,0x9,0xd2,0x68,0x13,0x12]

result = {}

def getSub(current_data: list[int]):
    current_v = current_data[0]
    next_v = current_data[1]
    
    if len(current_data) == 2:
        result[current_data[1]] = current_data[0]
        return

    sub = current_v - next_v # 
    if sub in current_data:
        rnode_i = current_data.index(sub)

        getSub(current_data[1:rnode_i])
        getSub(current_data[rnode_i:])
    else:
        # 如果没有，尾巴的元素就是data值
        # sub就是右节点的权重
        result[current_data[-1]] = sub
        getSub(current_data[1:-1])

getSub(data)
print(''.join(chr(result[i]) for i in range(1, 25)))