assembly - 我应该如何表示要在彩色计算机程序中使用的霍夫曼树？

Question

我用 Python 创建了一个愚蠢的霍夫曼压缩器，因此我可以压缩图像/声音数据以应用于我的 Tandy Color 计算机项目。解压器是用6809汇编编写的。 我找不到存储哈夫曼树的方法，因此我生成了走进树并获取正确的未压缩数据的汇编代码。这是一个例子:

DECOMP_HUFFMAN:        PSHS    A,B,X,Y,U
                       LDB     #8
                       STB     $2100
                       pshs    x
                       ldx     $2102
                       stx     $2106
                       puls    x                       
                       LDB     ,X+
                       JMP     inicio
prox_bit:              LSLB
                       PSHS    CC
                       DEC     $2100
                       BNE     S_P_B
                       LDB     #8
                       STB     $2100
                       LDB       ,X+
S_P_B:                 PULS    CC
                       RTS
armazena:              STA       ,U+
                       LEAY    -1,Y
                       BNE      inicio
                       PULS   U,Y,X,B,A
                       RTS


inicio:     jsr prox_bit
            tfr  cc,a
            anda #1
            sta  $2104
            lda ($2102)
            bne  n1
            lda $2104
n0:         pshs x
            ldx  $2102
            leax 1,x
            lda  a,x            
            puls x
            bsr  armazena
            pshs x
            ldx  $2106
            stx  $2102
            puls x
            bra inicio


n1:         cmpa #1
            bne  n2
            lda  $2104
            bne  n0
            bra  n4

n2:         cmpa #2
            bne  n3
            lda  $2104
            beq  n0

n3:         lda  $2104
n4:         pshs x
            ldx   $2102
            leax  1,x
            lda   a,x
            leax  a,x            
            stx   $2102
            puls x
            bra   inicio

我想使用真正的霍夫曼树，而不是创建汇编代码来完成它。

感谢您的宝贵时间。

Answer 1

您只需发送每个符号的代码长度即可传输霍夫曼代码。您不需要发送一棵树。代码长度为零表示该符号未出现。

您发送的内容可能类似于:

A: 2
B: 0
C: 0
D: 3
E: 1
F: 0
G: 0
H: 0
I: 3
J: 0

如果您只发送数字 - 符号的分配是按符号顺序进行的。

两端均采用规范的霍夫曼代码，其中代码值按从最短代码长度到最长代码长度的顺序分配。在位长度内，代码按顺序递增地分配给符号。例如(符号:代码长度-代码):

E: 1 - 0
A: 2 - 10
D: 3 - 110
I: 3 - 111

现在解码器只需将低位与每个位长度之间的截止处的整数值进行比较(存储上面的位反转)，从最短的开始。在每个位长度内，从开头开始的索引提供了符号查找表中的偏移量。