テクノロジ
ハフマン符号とは
読み方：ハフマンふごう
ひとことで言うと：出現頻度に応じて符号長を変え、平均データ長を短くする可変長符号化方式。
意味をわかりやすく解説
ハフマン符号は、出現頻度の高い記号に短いビット列、低い記号に長いビット列を割り当てて平均符号長を短くする可変長符号です。
頻度の小さい二つを順にまとめて二分木を作ります。得られる符号は、ある符号が別の符号の先頭部分にならない接頭語条件を満たすため、区切り記号なしで復号できます。
具体例
Aが50%、Bが25%、CとDが各12.5%なら、Aに1ビット、低頻度の記号により長い符号を割り当てることで固定長より平均長を短くできます。
似た用語との違い
固定長符号
固定長符号は全記号が同じ長さです。ハフマン符号は頻度に応じて長さを変えて圧縮します。
ランレングス符号
ランレングスは同じ値の連続回数を圧縮します。ハフマンは各記号の出現頻度を利用します。
覚え方
よく出る記号ほど短く、まれな記号ほど長く。
基本情報技術者試験の試験ポイント
頻度からハフマン木を作る手順、可変長でも一意に復号できる理由、平均符号長の計算を押さえます。
CHECK QUESTION
ハフマン符号で、出現頻度が高い記号には一般に長い符号と短い符号のどちらを割り当てますか。
答えを見る
短い符号です。頻出記号を短くすることで平均符号長を小さくします。
この説明は分かりやすかったですか？
基本情報技術者試験を勉強中ですか？
この用語を含む重要用語を、単語帳や4択テストで学習できます。