use it elsewhere

Huffman coder

Put it on your own page with two lines, or fork it and make it yours. It is CC-BY-4.0.

Embed

The script finds its own origin, so nothing else is needed; the widget runs in a sandboxed frame and cannot touch your page. Set the controls and the two lines update; the preview beneath shows what your readers get.

<script src="https://learn.mimmsy.com/learn-widget.js"></script> <learn-widget name="huffman-coder"></learn-widget>

It is CC-BY-4.0: keep the credit line the frame shows.

Preview

Fork

A fork is a copy whose manifest names its parent and the parent's version; lineage is kept forever, and the copy is yours to change. The library is its own repository: clone it, copy huffman-coder/ to a new name (one DNS label), set forkedFrom to { "name": "huffman-coder", "version": 1 }, change what you want, run npm run check, and open a pull request. Passing the check is the whole gate. Without a checkout, submit the same files to POST /api/widgets and it is served instantly as an unreviewed draft.

Source

The whole widget is these files; the repository has their history.

widget.json

{
  "name": "huffman-coder",
  "title": "Huffman coder",
  "version": 1,
  "claim": "A Huffman code built from a text's character frequencies gives frequent characters short codewords and rare ones long codewords, and its average length always lands between the entropy H and H + 1 bits per character, never below H.",
  "summary": "Type or paste text and watch its character distribution, entropy and a live Huffman code: each codeword's length tracks −log₂ p, the average is compared with a fixed-length code, and the encoded bitstream is shown. Presets include a repetitive string and a source whose Huffman average hits the entropy exactly.",
  "topics": [
    "information/coding",
    "information/entropy"
  ],
  "aliases": [
    "Huffman coding",
    "prefix code",
    "source coding theorem",
    "lossless compression",
    "variable-length code"
  ],
  "params": {
    "text": {
      "type": "string",
      "default": "the bees and the trees by the sea seem to see the breeze",
      "label": "text to compress"
    }
  },
  "check": [
    {
      "q": "A source has entropy 2.0 bits/symbol. A lossless code that averages 1.7 bits/symbol is…",
      "options": [
        "Possible with a sufficiently good Huffman tree",
        "Impossible, because entropy is a floor on the average code length",
        "Possible if many symbols are coded as one block",
        "Standard for ZIP files"
      ],
      "answer": 1,
      "why": "The source coding theorem says no lossless code averages below H bits per symbol; coding blocks can approach 2.0 but never go under it."
    },
    {
      "q": "A text's character distribution has entropy 3.1 bits. The average code length of a Huffman code will fall…",
      "options": [
        "exactly at 3.1 bits",
        "below 3.1 bits",
        "above 8 bits",
        "between 3.1 and 4.1 bits"
      ],
      "answer": 3,
      "why": "A Huffman code's average length always lies in [H, H + 1): never below the entropy, and less than one whole bit above it."
    },
    {
      "q": "Shannon's source coding theorem says a source with entropy H…",
      "options": [
        "can always be compressed to zero with enough passes",
        "cannot be losslessly compressed below H bits/symbol on average",
        "must be transmitted at exactly H bits/symbol",
        "can be compressed below H with a large enough dictionary"
      ],
      "answer": 1,
      "why": "H is a lower bound on the average length of any lossless code, and good codes approach it arbitrarily closely."
    },
    {
      "q": "In the Huffman table, which characters get the shortest codewords?",
      "options": [
        "The rarest ones, so that surprises are cheap to send",
        "Whichever come first in the alphabet",
        "All characters get codewords of the same length",
        "The most frequent ones, whose −log₂ p is smallest"
      ],
      "answer": 3,
      "why": "Codeword length tracks the information −log₂ p, so a frequent character (large p) is assigned a short code and a rare one a long code."
    }
  ],
  "capabilities": [],
  "height": 620,
  "requires": [
    "distribution-entropy",
    "bits-as-questions"
  ],
  "forkedFrom": null,
  "authors": []
}

index.html

<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>Huffman coder</title>
<style>
  :root {
    color-scheme: light dark;
    --bg: #f7f3ea; --bg-card: #efe9da; --border: #d8cfba; --text: #211d14; --text-dim: #6e6553;
    --accent: #31597f; --accent2: #b04e1b; --hot: #a82433; --ok: #3d6b4f;
    --ink-rgb: 33, 29, 20; --paper-rgb: 247, 243, 234; --accent-rgb: 49, 89, 127;
    --accent2-rgb: 176, 78, 27; --hot-rgb: 168, 36, 51; --ok-rgb: 61, 107, 79;
    --serif: "Iowan Old Style", "Palatino Linotype", Palatino, "Book Antiqua", Georgia, serif;
    --mono: ui-monospace, "SF Mono", Menlo, Consolas, monospace;
  }
  @media (prefers-color-scheme: dark) {
    :root {
      --bg: #161410; --bg-card: #1e1b15; --border: #383225; --text: #e9e3d3; --text-dim: #9c917c;
      --accent: #8fb8e0; --accent2: #dd9355; --hot: #df7a88; --ok: #82bd97;
      --ink-rgb: 233, 227, 211; --paper-rgb: 22, 20, 16; --accent-rgb: 143, 184, 224;
      --accent2-rgb: 221, 147, 85; --hot-rgb: 223, 122, 136; --ok-rgb: 130, 189, 151;
    }
  }
  * { box-sizing: border-box; }
  html, body { margin: 0; }
  body { background: transparent; color: var(--text); font-family: var(--serif); font-size: 17px; line-height: 1.5; }
  .widget { background: var(--bg-card); border: 1px solid var(--border); border-radius: 4px; padding: 22px; }
  .chips { display: flex; flex-wrap: wrap; gap: 8px; margin-bottom: 10px; }
  .chip { font-family: var(--mono); font-size: 12.5px; color: var(--text); background: transparent; border: 1px solid var(--border); border-radius: 3px; padding: 6px 13px; cursor: pointer; transition: border-color .15s, color .15s; }
  .chip:hover { border-color: var(--accent); color: var(--accent); }
  textarea { display: block; width: 100%; height: 84px; resize: none; font-family: var(--mono); font-size: 14px; line-height: 1.4; color: var(--text); background: var(--bg); border: 1px solid var(--border); border-radius: 10px; padding: 12px 14px; outline: none; }
  textarea:focus { border-color: var(--accent); }
  .mono { font-family: var(--mono); font-variant-numeric: tabular-nums; }
  .readout-row { display: flex; gap: 36px; flex-wrap: wrap; align-items: flex-end; margin: 14px 0 6px; }
  .readout .big { display: block; font-size: 34px; font-weight: 600; color: var(--accent); line-height: 1.1; min-width: 5ch; }
  .readout.accent .big { color: var(--accent2); }
  .readout small { color: var(--text-dim); font-size: 12.5px; }
  .note { font-family: var(--mono); font-size: 12px; color: var(--text-dim); margin: 0 0 8px; white-space: nowrap; overflow: hidden; text-overflow: ellipsis; }
  .note b { color: var(--ok); font-weight: 600; }
  .table { font-family: var(--mono); font-size: 13px; }
  .row { display: grid; grid-template-columns: 30px 1fr 56px 62px minmax(96px, auto) 36px; align-items: center; gap: 12px; padding: 2px 0; height: 22px; }
  .row.head { color: var(--text-dim); font-size: 11px; border-bottom: 1px dashed var(--border); margin-bottom: 4px; }
  .row .ch { color: var(--accent); }
  .row .bar { height: 12px; background: linear-gradient(90deg, var(--accent), var(--accent2)); border-radius: 4px; min-width: 2px; }
  .row .p, .row .i, .row .len { color: var(--text-dim); text-align: right; }
  .row .code { color: var(--accent2); text-align: right; letter-spacing: 1px; }
  .row .len { color: var(--text); }
  .stream { font-family: var(--mono); font-size: 12px; color: var(--text-dim); margin: 8px 0 0; white-space: nowrap; overflow: hidden; text-overflow: ellipsis; letter-spacing: 1px; }
  .stream b { color: var(--accent2); font-weight: 600; }
  @media (max-width: 560px) { .readout .big { font-size: 27px; } .readout-row { gap: 20px; } .row { grid-template-columns: 24px 1fr 48px 52px minmax(70px, auto) 30px; gap: 8px; } }
</style>
</head>
<body>
  <div class="widget">
    <div class="chips">
      <button class="chip" data-preset="bees">the bees and the trees</button>
      <button class="chip" data-preset="aaab">aaaaaaab</button>
      <button class="chip" data-preset="abcd">A B C D at &frac12; &frac14; &#8539; &#8539;</button>
      <button class="chip" data-preset="random">random letters</button>
    </div>
    <textarea id="text" spellcheck="false" aria-label="text to compress">the bees and the trees by the sea seem to see the breeze</textarea>
    <div class="readout-row">
      <div class="readout">
        <span class="big mono" id="h">0.00</span>
        <small>entropy H &middot; bits/char</small>
      </div>
      <div class="readout">
        <span class="big mono" id="huff">0.00</span>
        <small>Huffman &middot; bits/char</small>
      </div>
      <div class="readout">
        <span class="big mono" id="fixed">0</span>
        <small>fixed code &middot; bits/char</small>
      </div>
      <div class="readout accent">
        <span class="big mono" id="save">0%</span>
        <small>smaller than fixed</small>
      </div>
    </div>
    <p class="note" id="note"></p>
    <div class="table" id="table"></div>
    <p class="stream" id="stream"></p>
  </div>
  <script src="/w/_sdk/host.js?v=1"></script>
  <script src="/w/_lib/info.js?v=1"></script>
  <script src="widget.js?v=1"></script>
</body>
</html>

widget.js

/* Huffman coder: character statistics of the typed text, its entropy, and a live Huffman code beside a fixed-length one. */
(() => {
  'use strict';
  const $ = (id) => document.getElementById(id);
  const { entropy, huffman } = window.Info;
  const MAX_ROWS = 12;
  const PRESETS = {
    bees: 'the bees and the trees by the sea seem to see the breeze',
    aaab: 'aaaaaaab',
    abcd: 'AAAABBCDAAAABBCDAAAABBCD',
    random: () => {
      let s = '';
      for (let i = 0; i < 56; i++) s += String.fromCharCode(97 + Math.floor(Math.random() * 26));
      return s;
    },
  };
  let host = null;

  const showChar = (ch) => (ch === ' ' ? '␣' : ch === '\n' ? '⏎' : ch === '\t' ? '⇥' : ch);
  const esc = (s) => s.replace(/&/g, '&amp;').replace(/</g, '&lt;').replace(/>/g, '&gt;');

  function render() {
    const text = $('text').value;
    const chars = [...text];
    const freq = new Map();
    for (const ch of chars) freq.set(ch, (freq.get(ch) || 0) + 1);
    const total = chars.length;

    if (total === 0) {
      $('h').textContent = '0.00';
      $('huff').textContent = '0.00';
      $('fixed').textContent = '0';
      $('save').textContent = '0%';
      $('note').textContent = 'type something above';
      $('table').innerHTML = '';
      $('stream').textContent = '';
      return;
    }

    const probs = [...freq.values()].map((c) => c / total);
    const H = entropy(probs);
    const codes = huffman(freq);
    let huffBits = 0;
    for (const [ch, count] of freq) huffBits += codes.get(ch).length * count;
    const huffAvg = huffBits / total;
    const fixed = Math.max(1, Math.ceil(Math.log2(freq.size)));
    const save = 1 - huffAvg / fixed;

    $('h').textContent = H.toFixed(2);
    $('huff').textContent = huffAvg.toFixed(2);
    $('fixed').textContent = fixed;
    $('save').textContent = Math.round(save * 100) + '%';
    $('note').innerHTML =
      total + ' chars · ' + freq.size + ' distinct · Huffman ' + huffBits + ' bits · fixed ' + fixed * total +
      ' bits · ASCII ' + 8 * total + ' bits · <b>H ≤ Huffman &lt; H + 1</b>';

    const rows = [...freq.entries()].sort((a, b) => b[1] - a[1]).slice(0, MAX_ROWS);
    const maxCount = rows[0][1];
    $('table').innerHTML =
      '<div class="row head"><span>char</span><span>count' + (freq.size > MAX_ROWS ? ' · top ' + MAX_ROWS + ' of ' + freq.size : '') + '</span><span class="p">p</span><span class="i">−log₂ p</span><span class="code">code</span><span class="len">bits</span></div>' +
      rows.map(([ch, count]) => {
        const p = count / total;
        const code = codes.get(ch);
        return '<div class="row">' +
          '<span class="ch">' + esc(showChar(ch)) + '</span>' +
          '<span class="bar" style="width:' + (count / maxCount) * 100 + '%"></span>' +
          '<span class="p">' + (p * 100).toFixed(1) + '%</span>' +
          '<span class="i">' + (-Math.log2(p)).toFixed(2) + '</span>' +
          '<span class="code">' + code + '</span>' +
          '<span class="len">' + code.length + '</span>' +
          '</div>';
      }).join('');

    let bits = '';
    for (const ch of chars) { bits += codes.get(ch); if (bits.length > 160) break; }
    $('stream').innerHTML = 'encoded: <b>' + bits.slice(0, 160) + '</b>' + (huffBits > 160 ? ' …' : '');
  }

  const ping = (data) => { if (host && host.signal) host.signal('interaction', data); };

  $('text').addEventListener('input', () => { render(); ping({ length: $('text').value.length }); });
  document.querySelectorAll('.chip').forEach((chip) => {
    chip.addEventListener('click', () => {
      const p = PRESETS[chip.dataset.preset];
      $('text').value = typeof p === 'function' ? p() : p;
      render();
      ping({ preset: chip.dataset.preset });
    });
  });

  render();

  LearnWidget.connect().then((h) => {
    host = h;
    if (typeof h.params.text === 'string' && h.params.text.length) { $('text').value = h.params.text; render(); }
    h.on('params.changed', (np) => { if (typeof np.text === 'string') { $('text').value = np.text; render(); } });
  });
})();