mod.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Huffman Coding"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Zipfian"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7.510649703297883\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "const zipf = (n: number) => Array.from({ length: n }, (_, i) =>\n",
    "    1/(i+1)\n",
    ")\n",
    "const uniform = (n: number) => Array.from({ length: n }, _ => 1)\n",
    "\n",
    "const entropy =\n",
    "(system: number[]) => {\n",
    "    const sum = system.reduce((a, b) => a + b)\n",
    "    return -system\n",
    "            .map(n => n / sum)\n",
    "            .map(p => p * Math.log2(p))\n",
    "            .reduce((a, b) => a + b)\n",
    "}\n",
    "\n",
    "console.log(entropy(zipf(1024)))\n",
    "console.log(entropy(uniform(1024)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10     : 0\n",
      "110    : 1\n",
      "001    : 2\n",
      "1110   : 3\n",
      "0110   : 4\n",
      "0100   : 5\n",
      "0000   : 6\n",
      "11110  : 7\n",
      "01111  : 8\n",
      "01110  : 9\n",
      "01011  : 10\n",
      "01010  : 11\n",
      "00011  : 12\n",
      "00010  : 13\n",
      "111111 : 14\n",
      "111110 : 15\n"
     ]
    }
   ],
   "source": [
    "type BinTree = { sum: number } & (\n",
    "    | { key: number }\n",
    "    | {\n",
    "        left: BinTree\n",
    "        right: BinTree\n",
    "    }\n",
    ")\n",
    "\n",
    "const huffman =\n",
    "(system: number[]) => {\n",
    "    const f =\n",
    "    (trees: BinTree[]) => {\n",
    "        if (trees.length == 1) {\n",
    "            return trees[0]\n",
    "        }\n",
    "        trees.sort((a, b) => b.sum - a.sum)\n",
    "\n",
    "        const a = trees.pop()!\n",
    "        const b = trees.pop()!\n",
    "        trees.push({\n",
    "            sum: a.sum + b.sum,\n",
    "            left: a,\n",
    "            right: b,\n",
    "        })\n",
    "        return f(trees)\n",
    "    }\n",
    "\n",
    "    const read =\n",
    "    (tree: BinTree): [string, number][] => {\n",
    "        if (\"key\" in tree) {\n",
    "            return [[\"\", tree.key]]\n",
    "        }\n",
    "        return [\n",
    "            ...read(tree.left).map(([code, key]) =>\n",
    "                [0 + code, key] as [string, number]),\n",
    "            ...read(tree.right).map(([code, key]) =>\n",
    "                [1 + code, key] as [string, number]),\n",
    "        ]\n",
    "    }\n",
    "\n",
    "    const compare = <T>(a: T, b: T) => a < b ? -1 : (a > b ? 1 : 0)\n",
    "\n",
    "    return read(f(system.map((sum, key) => ({ sum, key }))))\n",
    "        .sort((a, b) => compare(a[1], b[1]))\n",
    "}\n",
    "\n",
    "console.log(huffman(zipf(16)).map(([a, b]) => a.padEnd(7) + \": \" + b).join(\"\\n\"))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Entropy: 7.510650\n",
      "Huffman: 7.536969\n",
      "Raw:    10.000000\n"
     ]
    }
   ],
   "source": [
    "const huffmanSize = (system: number[]) =>\n",
    "    huffman(system)\n",
    "        .map(([code, key]) => code.length * system[key])\n",
    "        .reduce((a, b) => a + b)\n",
    "        / system.reduce((a, b) => a + b)\n",
    "\n",
    "const n = 1024\n",
    "console.log(\"Entropy:\", entropy(zipf(n)).toFixed(6))\n",
    "console.log(\"Huffman:\", huffmanSize(zipf(n)).toFixed(6))\n",
    "console.log(\"Raw:   \", Math.log2(n).toFixed(6))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Deno",
   "language": "typescript",
   "name": "deno"
  },
  "language_info": {
   "codemirror_mode": "typescript",
   "file_extension": ".ts",
   "mimetype": "text/x.typescript",
   "name": "typescript",
   "nbconvert_exporter": "script",
   "pygments_lexer": "typescript",
   "version": "5.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}