|
|
> No.659[元記事へ]
ハフマン符号木の、最後尾に１つ使わない枝を設けると、その分、符号木の
枝ぶりが増え、全体のビット長も増え、圧縮コードとしては良くないですが、
反面、バイト・バインドされる画像データー中に、現れるオール１の形態(0xff)
が減って、全体のバイト数が少なくなるかもしれない。(0xff は marker コード
の先頭バイトと重なる為、画像データーの合図に 0x00 を後付する規則がある )
どちらを優先するかは、エンコーダー側の問題で、殆どは、0xff を押える方を、
優先し、符号木の枝ぶりに、犠牲を払っているようです。
だからと言って、デコーダー側が、符号木に空きが無い事を、否定する法は、
ないでしょう。
下は、ハフマン符号木を、作成する部分で、「baseline.jpg が開けない場合」に
差替えて下さい。Page-3 （そのソフトは、恐らくバグだと思います。）
!←(+1) 符号木の最下に、…の行、２つ。SE+1 を、SE に戻すと空席は無くなり、
元の状態にも、戻せます。
!-------------------
! make huffman tree
SUB TREE3
MAT Tr=ZER
FOR i=0 TO SE
LET F_(i)=S_(i,P) !数値を壊すので、コピー F_(i)で実行
NEXT i
LET F_(SE+1)=0 !← 空席用
!---minimum pair
DO
LET w=1e8
FOR i=0 TO SE+1 !←(+1) 符号木の最下に、空席を１つ作る。
IF F_(i)< w THEN
LET w=F_(i)
LET Ad1=i ! minimum1 !頻度最小の分岐アドレスAd1
END IF
NEXT i
LET w=1e8
FOR i=0 TO SE+1 !←(+1) 符号木の最下に、空席を１つ作る。
IF F_(i)< w AND i<>Ad1 THEN
LET w=F_(i)
LET Ad2=i ! minimum2 !頻度最小の分岐アドレスAd2
END IF
NEXT i
IF w=1e8 THEN EXIT DO !分岐の組が無くなるまで
!---
LET F_(Ad1)=F_(Ad1)+F_(Ad2) !次の頻度最小の組探しは、２分岐合計を１つにし、
LET F_(Ad2)=1e9 !他方を外して行なう
!---
FOR Le1=16 TO 1 STEP -1 !アドレスAd1の最上 節点レベルLe1 を探す(最初のLe1=0)
IF Tr(Le1,Ad1,1)>0 OR Tr(Le1,Ad1,3)>0 THEN EXIT FOR
NEXT Le1
FOR Le2=16 TO 1 STEP -1 !アドレスAd2の最上 節点レベルLe2 を探す(最初のLe2=0)
IF Tr(Le2,Ad2,1)>0 OR Tr(Le2,Ad2,3)>0 THEN EXIT FOR
NEXT Le2
LET Le0=MAX( Le1,Le2 )+1 !両者何れよりも１つ上の節点レベル(Le0,Ad1)に、
!---
LET Tr(Le0,Ad1,0)=Le1 !分岐先( 節点レベル,アドレス)として２組記入
LET Tr(Le0,Ad1,1)=Ad1
LET Tr(Le0,Ad1,2)=Le2
LET Tr(Le0,Ad1,3)=Ad2
LOOP
!---make DH()
LET k=0
CALL bitl(Le0,Ad1) !全アドレスの nested 段数を求める。
FOR Ad=0 TO SE !nested 段数が同じ Ad の総数を、段数毎に集計
LET DH(Tr(0,Ad,1),P)=DH(Tr(0,Ad,1),P)+1
NEXT Ad
LET DH(0,P)=Ad
END SUB
SUB bitl(Le,Ad) !最上 節点(Le0,Ad1)より全分岐を、底まで辿る
IF 0< Le THEN
LET k=k+1
CALL bitl( Tr(Le,Ad,0), Tr(Le,Ad,1) ) !分岐 nested 1
CALL bitl( Tr(Le,Ad,2), Tr(Le,Ad,3) ) !分岐 nested 2
LET k=k-1
ELSE
LET Tr(0,Ad,1)=k !最上 節点から底までの nested 段数kを書く
END IF
END SUB
|
|