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

Question

我在Python中创建了一个愚蠢的霍夫曼压缩器，因此我可以压缩图像/声音数据以应用于我的Tandy彩色计算机项目。解压缩器写在 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

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