DOSEIの日記

技術メモ+日常ログ

ファノ符号化

ファノ符号化は、常に最適な符号化、ではない。たとえば、出現頻度が 20, 19, 17 16, 14, 13 の6文字を符号化すると、

20    00
19    010
17    011
16    10
14    110
13    111

と符号化され、「出現頻度が大きいほど短い符号」にはならない。
また、分割の際、2通りの分割が出来る場合がある。つまり、ある記号の出現頻度を除いて上下の出現頻度の和が等しい場合である。この場合、どちらかを選ぶかで異なった符号語がえられる。ただし、圧縮率は変わらない(平均符号長は変わる)。…ぽい変わらない。計算間違ってた(笑)