ForHosting KIT · 開発者向けツール

ハフマン符号長計算

頻度5、9、12、13、16、45を入力すると、最適なハフマン符号長は4、4、3、3、3、1で、合計224ビット、1記号あたり平均2.24ビットです。比較用のエントロピーも分かります。ブラウザで無料で使えます。

  • 無料
  • ブラウザで動作
  • 登録不要
  • データは端末の外に出ません
ご利用方法 ウェブAPIメールTelegramアプリ 近日
入力した場合
頻度
5, 9, 12, 13, 16, 45
結果
シンボル数
6
長さ
4, 4, 3, 3, 3, 1
合計頻度
100
総ビット数
224

ハフマン符号化は、ZIP、PNG、DEFLATE、JPEG、そして数多くの教材ラボで使われる古典的な最小冗長二進プレフィックス符号です。各記号の出現頻度に応じて、アルゴリズムは頻出記号に短いビット列を、稀な記号に長いビット列を割り当て、どの符号も他の符号の接頭辞にならないようにします。このハフマン符号長計算機は、厳密に正の頻度のリストを受け取り、決定的なタイブレーク付きで最適ハフマン木を構築し、各記号の符号長、記号多重集合の総符号化ビット数、平均長、比較用のシャノンエントロピー(ビット)、冗長性、クラフト和を返します。記号が1つのアルファベットには長さ0(空符号)が割り当てられ、それでもプレフィックス性質を満たします。

最適ハフマン長の意味と木の構築方法

二進プレフィックス符号は、アルファベットの各記号をビット列に写像し、どの符号も他の符号の真の接頭辞にならないようにします。この性質により、デコーダは区切りなしで連結ビット列を解析できます。構築は単純かつ厳密です。

各記号を頻度をキーとする優先度キューに入れ、最も軽い2ノードを繰り返し取り出し、重みがその和である親を作り、根が1つになるまで再挿入します。葉の符号長はその木における深さです。2ノードが同じ重みを共有する場合、本実装は安定した挿入識別子でタイを解決し、同一入力がランタイム間で常に同じ長ベクトルを生むようにします。

記号が1つのとき最適長は0です。空符号はビットを使わず、単一アルファベットでも有効なプレフィックス符号です。2記号以上では各長は少なくとも1です。

各長の2のマイナス乗のクラフト和は完全なプレフィックス符号で高々1であり、木を自分で再構築せずにクラフト不等式を確認できるよう報告されます。

ハフマン符号長の用途と制限

情報理論の講義やコーディング面接では、ハフマン符号長計算機を使い、学生が頻度表ごとに手描きで木を作らずに最適深さと総ビットを確認します。圧縮エンジニアは、ヘッダ設計、静的/動的表の選択、DEFLATE 系符号がエントロピー境界に近い理由の説明で、ハフマン平均長とシャノンエントロピーを比較します。検証失敗は残高を消費しません。

アルファベットは公開上限内に収め、特別扱いが要るゼロを混ぜず厳密に正の計数だけを送り、返却 lengths 配列をテストに固定してください。

授業と面接の演習

学生が正の記号頻度を貼り付け、手描きの木と照合して最適ハフマン長・総ビット・平均長を確認します。

圧縮設計の確認

エンジニアが経験ヒストグラム上でハフマン平均長とシャノンエントロピーを比較し、静的表や固定符号を選ぶ前に確認します。

記号が1つのときの長さは?

長さ0です。 最小冗長プレフィックス符号では1記号アルファベットにビットは不要で、空符号は有効かつ最適です。

実際の 0/1 ビット列も返しますか?

いいえ。 最適長と集計(総ビット、平均長、エントロピー、クラフト和)のみです。それらの深さを守る任意の左右ラベル付けを割り当てられます。

平均符号長がエントロピーを上回るのはなぜですか?

シャノンのエントロピーは、曖昧さなく復号できるどんな符号でも平均の長さの下限になるためです。冗長度は平均符号長からエントロピーを引いた値なので、負になることはありません。

クラフト和から何が分かりますか?

各符号長について、2のマイナス符号長乗を足した値です。完全な接頭符号なら1以下になり、例ではちょうど1なので、木を作り直さずにクラフトの不等式を確かめられます。

同じ頻度があると結果は変わりますか?

変わりません。同じ重みは挿入順で安定して決めるので、同じ頻度を入力すれば、どの環境でも毎回同じ符号長が返ります。

このページの機能はすべてAPIからも利用できます。自社システムに組み込みたいチーム向けのセクションです。それ以外の方は上のツールをそのままお使いください。

POSThttps://api.kit.forhosting.com/dev/huffman-code-length

Bearerトークンで認証し、POST1回でタスクをキューに登録します。結果はWebhookまたは署名付きリンクで受け取れます。

curl -X POST https://api.kit.forhosting.com/dev/huffman-code-length \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"frequencies":[5,9,12,13,16,45]}'
{
  "frequencies": [
    5,
    9,
    12,
    13,
    16,
    45
  ]
}
{
  "task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
  "type": "dev.huffman_code_length",
  "status": "queued",
  "_links": {
    "result": "/tasks/tsk_…/result"
  }
}

非同期APIです。task_idは即時に返ります。ポーリングは1秒あたり1リクエストまでです。

1リクエストあたり$0.002

単価はすべて公開しています。トークン換算や独自クレジットはありません。失敗したタスクは課金されません。

HTTPコード意味
401unauthorizedAPIキーが無効か、指定されていません。Authorizationヘッダーを確認してください。
402insufficient_balance残高が不足しています。チャージ後に再度お試しください。
404unknown_type指定されたタスクタイプは存在しません。タイプ名を確認してください。
429rate_limitedリクエストが多すぎます。しばらく待ってから再度お試しください。

無料のブラウザ経路と前払いAPIは同一の純解析モジュールを共有するため、課題用オラクルと本番パイプラインで符号長が食い違うことはありません。検証失敗は invalid_input を起こし、課金されません。

最適ハフマン長の意味と木の構築方法

あらゆる二進プレフィックス符号の中で、ハフマン符号は与えられた正の頻度ベクトルに対して重み付き経路長 Σ frequency_i × length_i を最小化します。返却される total_bits は頻度×長の和であり、頻度に一致する多重集合を符号化する厳密なビットコストです。平均長は total_bits を総頻度で割った値です。ビット単位のシャノンエントロピーは一意復号可能な任意の符号の平均長の下界なので、redundancy_bits は平均長からエントロピーを引いた値で、浮動小数精度の範囲で常に非負です。

入力契約、応答フィールド、エイリアス、エラー挙動

明示的な 0/1 符号が必要な場合は、返却された長に合わせてご自身でビット列を割り当ててください。frequencies を厳密に正の有限数の空でない配列として含む JSON 本体を POST してください。エイリアス freqs、weights、counts、freq も受け付け、カンマまたは空白区切り文字列は簡易テキストフォームで使えます。任意の labels(エイリアス symbols、names、alphabet)は、同じ長さの空でない文字列の並列配列として人間可読な行を付けられます。ゼロ・負・欠落・空・非有限の頻度は、不正インデックスを示す invalid_input で失敗します。4096を超える記号は Worker とブラウザ経路を高速に保つため拒否されます。成功時、本体には symbol_count、整形済み frequencies、同じ順の lengths、total_frequency、total_bits、average_length、min_length と max_length、shannon_entropy_bits、redundancy_bits、kraft_sum、method が huffman_optimal_lengths、深さ規則を要約する formula、提供時の labels、各記号の index・frequency・length・bits・任意 label を持つ symbol_rows が含まれます。教科書の古典頻度 5、9、12、13、16、45 はこの決定的結合順で total_bits 224、平均長 2.24 ビット/記号を与えます。本エンドポイントは長と集計のみを返し、枝の左0・右0といった特定のラベル付けは返しません。

ハフマン長 API の用途、料金、制限

データパイプラインの著者は、スキーマ変更が記号ヒストグラムを変えうるときに lengths と total_bits を CI フィクスチャへ固定する決定的オラクルを必要とします。実装は純 parse ティア A のため、成功した各呼び出しはモデルトークンも外部ネットもなく公開ベース価格 $0.002 です。

コーデック試験用 CI オラクル

パイプラインが決定的な total_bits と lengths 配列を固定し、ヒストグラムやアルファベットの変更でテストが即座に失敗するようにします。

頻度からハフマン符号長をどう計算しますか?

厳密に正の頻度の空でない配列を送ってください。API は最適ハフマン木を構築し、各葉の深さを lengths として返し、total_bits = Σ frequency × length も返します。

頻度ゼロは許可されますか?

いいえ。ゼロまたは負の項目は invalid_input で失敗します。未使用記号を省くか、厳密に正の計数だけを送ってください。

ハフマン符号長計算機の料金は?

ブラウザツールは無料です。API リクエストは成功呼び出しごとに前払い KIT 残高から $0.002 です。無効入力は課金されません。

KITの完全なドキュメントを見る →