Toy implementation and showcase for simple Huffman encoding

huffman_creation.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Grundlagen\n",
    "\n",
    "Aus [Wikipedia](https://de.wikipedia.org/wiki/Huffman-Kodierung):\n",
    "\n",
    "> Die Huffman-Kodierung ist eine Form der Entropiekodierung, die 1952 von David A. Huffman entwickelt und in der Abhandlung \"A Method for the Construction of Minimum-Redundancy Codes\" publiziert wurde. Sie ordnet einer festen Anzahl an Quellsymbolen jeweils Codewörter mit variabler Länge zu. In der Informationstechnik ist sie ein Präfix-Code, die üblicherweise für verlustfreie Kompression benutzt wird. Ähnlich anderer Entropiekodierungen werden häufiger auftauchende Zeichen mit weniger Bits repräsentiert als seltener auftauchende.\n",
    "\n",
    "> Um Daten möglichst redundanzfrei darzustellen, müssen die Quellsymbole mit Codewörtern unterschiedlicher Wortlängen kodiert werden. Die Länge der Codewörter entspricht dabei idealerweise ihrem Informationsgehalt. Um einen Code auch wieder eindeutig dekodieren zu können, muss er die Kraftsche Ungleichung erfüllen und zusätzlich noch präfixfrei sein, d. h. kein Codewort darf der Beginn eines anderen sein.\n",
    "\n",
    "> Die Grundidee ist, einen k-nären Wurzelbaum (ein Baum mit jeweils k Kindern je Knoten) für die Darstellung des Codes zu verwenden. In diesem sog. Huffman-Baum stehen die Blätter für die zu kodierenden Zeichen, während der Pfad von der Wurzel zum Blatt das Codesymbol bestimmt. Im Gegensatz zur Shannon-Fano-Kodierung wird der Baum dabei von den Blättern zur Wurzel (englisch bottom-up) erstellt.\n",
    "\n",
    "> Im Unterschied zum Morse-Code benötigt man bei einer Huffman-Codierung keine Trennzeichen. Eine Trennung der Codewörter ist nicht notwendig, da die Codierung präfixfrei ist. Dadurch ist kein Codewort Anfang eines anderen Codewortes.\n",
    "\n",
    "> Der bei der Huffman-Kodierung gewonnene Baum liefert garantiert eine optimale und präfixfreie Kodierung. D. h. es existiert kein symbolbezogenes Kodierverfahren, das einen kürzeren Code generieren könnte, wenn die Auftrittswahrscheinlichkeiten der Symbole bekannt sind."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Implementierung"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import string\n",
    "from heapq import heappush, heappop, heapify\n",
    "from collections import Counter, OrderedDict"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Code zur Generierung eines Dictionaries, das die Codes enthält.  Der Input ist ein Dictionary mit dem Mapping von Symbolen (ie. Buchstaben) auf ihre Häufigkeit."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# source: http://rosettacode.org/wiki/Huffman_coding#Python\n",
    "def generate_code(symb2freq):\n",
    "    \"\"\"Huffman encode the given dict mapping symbols to weights\"\"\"\n",
    "    heap = [[wt, [sym, \"\"]] for sym, wt in symb2freq.items()]\n",
    "    heapify(heap)\n",
    "    while len(heap) > 1:\n",
    "        lo = heappop(heap)\n",
    "        hi = heappop(heap)\n",
    "        for pair in lo[1:]:\n",
    "            pair[1] = '0' + pair[1]\n",
    "        for pair in hi[1:]:\n",
    "            pair[1] = '1' + pair[1]\n",
    "        heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])\n",
    "    return sorted(heappop(heap)[1:], key = lambda p: (len(p[-1]), p))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Zuerst berechnen wir die Häufigkeiten in einem Text, den wir Codieren wollen, in diesem Fall Faust I:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "frequencies = Counter()\n",
    "\n",
    "with open('faust.txt', 'r') as f:\n",
    "    for line in f:\n",
    "        frequencies += Counter(l for l in line.lower() if l in string.ascii_lowercase)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Jetzt können wir die Funktion mit dieser Häufigkeitsinformation füttern:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Counter({'e': 24746, 'n': 15125, 'i': 13408, 'r': 10994, 't': 10716, 's': 10503, 'h': 10044, 'a': 8246, 'd': 7618, 'u': 6430, 'c': 6314, 'l': 6273, 'm': 5044, 'o': 4525, 'g': 4477, 'b': 3004, 'w': 2984, 'f': 2958, 'p': 1781, 'k': 1766, 'z': 1528, 'v': 1051, 'j': 373, 'y': 367, 'x': 79, 'q': 66})\n",
      "[['e', '110'], ['n', '001'], ['a', '0101'], ['d', '0001'], ['h', '0111'], ['i', '1111'], ['r', '1010'], ['s', '1000'], ['t', '1001'], ['u', '0000'], ['c', '11101'], ['g', '01001'], ['l', '10111'], ['m', '01101'], ['o', '01100'], ['b', '111000'], ['f', '101100'], ['p', '010000'], ['w', '101101'], ['k', '1110011'], ['v', '0100011'], ['z', '1110010'], ['j', '01000100'], ['y', '010001011'], ['q', '0100010100'], ['x', '0100010101']]\n"
     ]
    }
   ],
   "source": [
    "huff = OrderedDict(sorted(generate_code(frequencies), \n",
    "                          key = lambda t: frequencies[t[0]], \n",
    "                          reverse = True))\n",
    "#print(huff)\n",
    "print(frequencies)\n",
    "print(generate_code(frequencies))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Oben sieht man das Häufigkeits-Dictionary sowie den resultierenden Code.  Übersichtlicher ist das Ganze in tabellarischer Form:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Symbol\tWeight\tHuffman-Code\n",
      "e\t24746\t110\n",
      "n\t15125\t001\n",
      "i\t13408\t1111\n",
      "r\t10994\t1010\n",
      "t\t10716\t1001\n",
      "s\t10503\t1000\n",
      "h\t10044\t0111\n",
      "a\t8246\t0101\n",
      "d\t7618\t0001\n",
      "u\t6430\t0000\n",
      "c\t6314\t11101\n",
      "l\t6273\t10111\n",
      "m\t5044\t01101\n",
      "o\t4525\t01100\n",
      "g\t4477\t01001\n",
      "b\t3004\t111000\n",
      "w\t2984\t101101\n",
      "f\t2958\t101100\n",
      "p\t1781\t010000\n",
      "k\t1766\t1110011\n",
      "z\t1528\t1110010\n",
      "v\t1051\t0100011\n",
      "j\t373\t01000100\n",
      "y\t367\t010001011\n",
      "x\t79\t0100010101\n",
      "q\t66\t0100010100\n"
     ]
    }
   ],
   "source": [
    "print(\"Symbol\\tWeight\\tHuffman-Code\")\n",
    "for p in huff.items():\n",
    "    print(\"{}\\t{}\\t{}\".format(p[0], frequencies[p[0]], p[1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Mit diesem optimalen Code können wir jetzt eine Codierungsfunktion bauen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def encode_huffman(text):\n",
    "    return ' '.join(huff[c] for c in text)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Und auf Beispiele anwenden:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "110 1111 110 1010\n",
      "1110010 010001011 1001 01100 10111 01100 01001 1111 110\n"
     ]
    }
   ],
   "source": [
    "print(encode_huffman('eier'))\n",
    "print(encode_huffman('zytologie'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Zum Vergleich, die \"rohen\" Bytes in ASCII:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "01100101 01101001 01100101 01110010\n",
      "01111010 01111001 01110100 01101111 01101100 01101111 01100111 01101001 01100101\n"
     ]
    }
   ],
   "source": [
    "def encode_ascii(text):\n",
    "    return ' '.join('{0:08b}'.format(ord(c)) for c in text)\n",
    "\n",
    "print(encode_ascii('eier'))\n",
    "print(encode_ascii('zytologie'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die Decodierung ist hier nicht gezeigt, aber sowohl verlustfrei als auch eindeutig und effizient möglich."
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [default]",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}