2

我在 Python 中创建了一个愚蠢的 Huffman 压缩器，因此我可以压缩图像/声音数据以应用于我的 Tandy Color Computer Projects。解压器是用 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

我想使用真正的霍夫曼树，而不是创建汇编代码来做到这一点。

感谢您的时间。

4

1 回答 1

3

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

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

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

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

于 2012-04-22T01:50:14.347 回答