「ハフマン符号」の版間の差分

'''ハフマン符号''' ('''Huffman coding''')とは、[[1952年]]に[[デビット・ハフマン]]によって開発された符号である。

[[コンパクト符号]]や[[エントロピー符号]]の一つ。[[JPEG]]や[[ZIP]] ([[Deflate]]) などの圧縮フォーマットで使用されている。

[[シャノン符号化]]が最適ではない場合が存在する不完全な符号であったのに対し、ハフマン符号は（整数の符号語長という制約のもとでは、）常に最適な符号を構成できる。擬似的に実数の符号語長を割り振る[[算術符号]]と比較すれば、データ[[圧縮効率]]は劣る。ただし、算術符号やその他の高効率の符号化法と異なり、特許の問題が無い。

符号化の原理上、木を構成する前に各記号の出現頻度をあらかじめ知っておく必要がある。1度目の読み込みで、データのすべての記号を調べておき、2度目に符号化を行う方法を、'''静的ハフマン符号''' ('''Static Huffman coding''') と呼ぶ。一方、記号を1つ読み込むごとに木を作り直し、1度の読み込みで符号化を行う方法を'''適応型ハフマン符号''' ('''動的ハフマン符号''', '''[[:en:Adaptive Huffman coding|Adaptive Huffman coding]]''') と呼ぶ。