L5 - Compression.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introduction\n",
    "\n",
    "In this notebook, we experiment with various compression methods for postings lists. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from math import log\n",
    "\n",
    "DEBUG = True\n",
    "#DEBUG = False\n",
    "\n",
    "def p(msg):\n",
    "    if DEBUG:\n",
    "        print('.. {}'.format(msg))\n",
    "\n",
    "def ilog2(x):\n",
    "    return int(log(x, 2.0))\n",
    "\n",
    "def encode_unary(vals):\n",
    "    out = \"\"\n",
    "\n",
    "    vs = [vals] if type(vals) == int else vals\n",
    "    for v in vs:\n",
    "        out = out + \"1\" * v\n",
    "        out = out + \"0\"\n",
    "\n",
    "    return out\n",
    "\n",
    "def encode_binary(vals, width):\n",
    "    out = \"\"\n",
    "\n",
    "    vs = [vals] if type(vals) == int else vals\n",
    "    for v in vs:\n",
    "        for i in range(width, 0, -1):\n",
    "            bit = v >> (i-1) & 0x0001\n",
    "            if bit > 0:\n",
    "                out = out + \"1\"\n",
    "            else:\n",
    "              out = out + \"0\"\n",
    "\n",
    "    return out\n",
    "\n",
    "\n",
    "# should check if input val is within the coding range (e.g., >0)\n",
    "def encode_gamma(vals):\n",
    "    out_code = []\n",
    "    for v in vals:\n",
    "        k_d = ilog2(v)\n",
    "        k_r = v - (1 << k_d)\n",
    "        p('val = {}, k_d = {}, k_r = {}'.format(v, k_d, k_r))\n",
    "        out1 = encode_unary(k_d)\n",
    "        out2 = encode_binary(k_r, k_d)\n",
    "        out_code.append([out1, out2])\n",
    "    return out_code\n",
    "\n",
    "# out_list is a list of encodings for each value, where each encoding is a list of component\n",
    "def pp_binary(out_list, width=8, as_string=True):\n",
    "    if as_string:\n",
    "        # print as strings of width-byte chunks\n",
    "        # first, flatten the list\n",
    "        l = [\"\".join(v) for v in out_list]\n",
    "        str = \"\".join(l)\n",
    "        n = len(str)\n",
    "        s = 0\n",
    "        while s < n:\n",
    "            e = min(s + width, n)\n",
    "            print(\"{} \".format(str[s:e]), end=\"\")\n",
    "            s += width\n",
    "        print()\n",
    "    else:\n",
    "        for component in out_list:\n",
    "            print(component)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def test_gamma(values):\n",
    "    out = encode_gamma(values)\n",
    "    #print(out)\n",
    "    pp_binary(out, as_string=False)\n",
    "    pp_binary(out)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]\n"
     ]
    }
   ],
   "source": [
    "print([x for x in range(1,16)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ".. val = 1, k_d = 0, k_r = 0\n",
      ".. val = 2, k_d = 1, k_r = 0\n",
      ".. val = 3, k_d = 1, k_r = 1\n",
      ".. val = 4, k_d = 2, k_r = 0\n",
      ".. val = 5, k_d = 2, k_r = 1\n",
      ".. val = 6, k_d = 2, k_r = 2\n",
      ".. val = 7, k_d = 2, k_r = 3\n",
      ".. val = 8, k_d = 3, k_r = 0\n",
      ".. val = 9, k_d = 3, k_r = 1\n",
      ".. val = 10, k_d = 3, k_r = 2\n",
      ".. val = 11, k_d = 3, k_r = 3\n",
      ".. val = 12, k_d = 3, k_r = 4\n",
      ".. val = 13, k_d = 3, k_r = 5\n",
      ".. val = 14, k_d = 3, k_r = 6\n",
      ".. val = 15, k_d = 3, k_r = 7\n",
      "['0', '']\n",
      "['10', '0']\n",
      "['10', '1']\n",
      "['110', '00']\n",
      "['110', '01']\n",
      "['110', '10']\n",
      "['110', '11']\n",
      "['1110', '000']\n",
      "['1110', '001']\n",
      "['1110', '010']\n",
      "['1110', '011']\n",
      "['1110', '100']\n",
      "['1110', '101']\n",
      "['1110', '110']\n",
      "['1110', '111']\n",
      "01001011 10001100 11101011 01111100 00111000 11110010 11100111 11010011 10101111 01101110 111 \n"
     ]
    }
   ],
   "source": [
    "test_gamma(range(1,16))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise\n",
    "\n",
    "1. Implement a method `decode_gamma` that takes a gamma-encoded binary string and decode it into a list of integers. \n",
    "2. Implement the encoding and decoding methods for delta, rice, and variable byte methods. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.4.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}