03-homework.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from math import factorial\n",
    "import io, requests, sys, urllib.request\n",
    "sys.setrecursionlimit(3000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this homework, you will implement *two more compression algorithms*:\n",
    "\n",
    "1. a \"universal\" compression algorithm for binary pictures (which is essentially the one discussed in the tutorials), and\n",
    "2. the Lempel-Ziv algorithm discussed in the lecture (we will use it to compress the same Hamlet text as on the previous homework).\n",
    "\n",
    "The two problems can be solved independently from each other, so **feel free to start with the one that seems easiest!**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1. \"Universal\" Compression of Bitstrings and Binary Pictures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Enumerating Bitstrings\n",
    "\n",
    "Before we start, let us agree how to order $B(N, k)$ -- the set of *all* bitstrings of length $N$ with $k$ ones and (hence) $N-k$ zeros.\n",
    "We will use the *lexicographic order* discussed in the exercise class, which is just the order in which the bitstrings would appear in a dictionary.\n",
    "For example, $B(4,2)$ is sorted as follows:\n",
    "```\n",
    "0011\n",
    "0101\n",
    "0110\n",
    "1001\n",
    "1010\n",
    "1100\n",
    "```\n",
    "The following function computes $B(N,k)$ in lexicographic order:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[0, 0, 1, 1],\n",
       " [0, 1, 0, 1],\n",
       " [0, 1, 1, 0],\n",
       " [1, 0, 0, 1],\n",
       " [1, 0, 1, 0],\n",
       " [1, 1, 0, 0]]"
      ]
     },
     "execution_count": null,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def B(N, k):\n",
    "    if N == 0:\n",
    "        return [[]] if k == 0 else []\n",
    "\n",
    "    return [[0] + y for y in B(N - 1, k)] + [[1] + y for y in B(N - 1, k - 1)]\n",
    "\n",
    "\n",
    "B(4, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For simplicity, we represent bitstrings by Python lists, which is very inefficient. In a real implementation you would use a more compact representation.\n",
    "\n",
    "The size of the list $B(n,k)$ is given by the binomial coefficient $\\binom N k$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": null,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def binomial(N, k):\n",
    "    if 0 <= k <= N:\n",
    "        return factorial(N) // factorial(k) // factorial(N - k)\n",
    "    return 0\n",
    "\n",
    "\n",
    "binomial(4, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here comes your first task.\n",
    "Consider the following two functions.\n",
    "The first function, `bitstring_to_index`, determines the index of a given bitstring of length $N$ with $k$ ones in the list $B(N,k)$.\n",
    "The second function, `index_to_bitstring`, looks up the bitstring for a given index.\n",
    "While correct, these functions are completely impractical since they both create the entire list $B(N,k)$ even though we are only interested in a single element.\n",
    "For example, $B(64, 8)$ contains $\\approx 2^{32}$ elements, which requires multiple GB!\n",
    "\n",
    "**Your task is to do better and re-implement the two functions `bitstring_to_index` and `index_to_bitstring` in an efficient way (in the tutorials you discussed how this can be done)!**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def index_to_bitstring(N, k, index):\n",
    "    # TODO: CAN YOU MAKE THIS FASTER?\n",
    "    return B(N, k)[index]\n",
    "\n",
    "\n",
    "def bitstring_to_index(x):\n",
    "    # TODO: CAN YOU MAKE THIS FASTER?\n",
    "    N = len(x)\n",
    "    k = list(x).count(1)\n",
    "    return B(N, k).index(x)\n",
    "\n",
    "\n",
    "# a simple test\n",
    "assert bitstring_to_index([1, 0, 1, 0]) == 4\n",
    "assert index_to_bitstring(4, 2, 4) == [1, 0, 1, 0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is a more elaborate test to make sure that your implementation works fine:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for N in range(11):\n",
    "    for k in range(N + 1):\n",
    "        for index, x in enumerate(B(N, k)):\n",
    "            assert bitstring_to_index(x) == index\n",
    "            assert index_to_bitstring(N, k, index) == x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following test will fail unless you re-implemented the two functions more efficiently:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert bitstring_to_index(index_to_bitstring(64, 8, 986860893)) == 986860893"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Compressing and Decompressing Images\n",
    "\n",
    "We will now implement the \"universal\" compression algorithm discussed in the tutorials to compress images.\n",
    "Consider a binary image of height $h$ and width $w$.\n",
    "Any such image can be converted into a bitstring by listing the pixel values (0=black pixel, 1=white pixel) row by row, starting with the top row.\n",
    "Let $N$ denote the length of the bitstring, $k$ the number of ones, and $p$ its index in the lexicographically ordered list $B(N,k)$.\n",
    "Then the quadruple $(h,w,k,p)$ defines the **compression** of the bitstring.\n",
    "\n",
    "For example, consider the following $2\\times2$ image:\n",
    "\n",
    "![](https://github.com/qi-rub/iit21-homework/raw/main/material/two_by_two.png)\n",
    "\n",
    "It corresponds the bitstring `0010`, so $N=4$ and $k=1$.\n",
    "There are four strings in $B(4, 1)$.\n",
    "In lexicographic order, they are: `0001`, `0010`, `0100`, `1000`.\n",
    "The index of our bitstring in this list is $p=1$ (remember that indices start at 0).\n",
    "Thus, the compression of this image is $(2,2,1,1)$.\n",
    "\n",
    "**Your task is to program both the compressor and the decompressor.\n",
    "For this, please complete the following two functions.\n",
    "As usual, images are represented by two-dimensional NumPy arrays.\n",
    "Don't worry about converting $(w,h,k,p)$ to bitstrings -- you can keep them as integers.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def compress(image):\n",
    "    # TODO: FINISH THIS FUNCTION\n",
    "    h, w = image.shape\n",
    "    x = list(image.reshape(h * w))\n",
    "    k = ...\n",
    "    p = ...\n",
    "    return h, w, k, p\n",
    "\n",
    "\n",
    "def decompress(h, w, k, p):\n",
    "    # TODO: FINISH THIS FUNCTION\n",
    "    x = ...\n",
    "    return np.array(x).reshape(h, w)\n",
    "\n",
    "\n",
    "# make sure the code works for the 2x2 example described above\n",
    "TEST_IMAGE = np.array([[0, 0], [1, 0]])\n",
    "assert compress(TEST_IMAGE) == (2, 2, 1, 1)\n",
    "assert np.all(decompress(2, 2, 1, 1) == TEST_IMAGE)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is a more interesting test.\n",
    "Does your code decompress the following image correctly? (You will recognize when it does.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# decompress an 8x8 image\n",
    "image = decompress(8, 8, 8, 986860893)\n",
    "\n",
    "# show it\n",
    "plt.imshow(image, cmap=plt.get_cmap(\"binary\"), interpolation=\"none\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, you may evaluate your compressor on the donkey image from the first homework. The following code downloads the image and downscales it to 34x40 pixels (to avoid any potential performance problems):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAA8QAAAM6CAYAAABHNIqeAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjcuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/bCgiHAAAACXBIWXMAAB7CAAAewgFu0HU+AABFQklEQVR4nO3de5BV5Zkv/mdLh7uKE0SFRlFIiyaOoRSOxAviBct4wYaSxJkEIRI0Go+mLMdMSBE1Myk1IeLhZM5IRImTiWYkjkYcE40HURElJOQcJ16Qm6Ghx9BEReXasH5/cNi/RugL0Kt3734/n6quWt1r7Xc/e7373d3fftelkGVZFgAAAJCYg0pdAAAAAJSCQAwAAECSBGIAAACSJBADAACQJIEYAACAJAnEAAAAJEkgBgAAIEkCMQAAAEkSiAEAAEiSQAwAAECSBGIAAACSJBADAACQJIEYAACAJAnEAAAAJEkgBgAAIEkCMQAAAEmqKHUB5WDz5s3x6quvRkTE4YcfHhUVdhsAAEBbqq+vj3Xr1kVExEknnRRdu3Y94DYluxZ49dVXY9iwYaUuAwAAgIhYtGhRDB069IDbccg0AAAASTJD3AKHH354cXnRokVx1FFHlbAaAACA9NTW1haP3G2Y0Q5E2QXit99+O/7H//gf8eSTT8bq1aujS5cuMXDgwBg3blxcd9110b1791Z/zobnDB911FFRWVnZ6s8BAABAy7TWdZ3KKhA/8cQT8aUvfSk2bNhQ/NnGjRtj8eLFsXjx4rjvvvviySefjEGDBpWwSgAAAMpB2ZxDvGTJkvjCF74QGzZsiJ49e8Y//uM/xksvvRTPPvtsfPWrX42IiKVLl8ZFF10UH3zwQYmrBQAAoL0rmxniG264ITZt2hQVFRXx9NNPx/Dhw4vrzjnnnPjUpz4Vf/d3fxdLly6NadOmxa233lq6YgEAAGj3ymKGeNGiRfHCCy9ERMRVV121Wxje5aabbooTTjghIiLuueee2LZtW5vWCAAAQHkpi0D82GOPFZcnTpy4120OOuigGD9+fEREvPfeezFv3ry2KA0AAIAyVRaB+MUXX4yIiB49esQpp5zS6HYjRowoLi9YsCD3ugAAAChfZXEO8euvvx4REYMGDWry8tqDBw/e4zEtUVNT0+T62traFrcFAABAeWj3gXjz5s1RV1cXEdHs/X8PO+yw6NGjR3z00UexevXqFj9H//79D6hGAAAAyk+7P2S64S2Uevbs2ez2PXr0iIiIDz/8MLeaAAAAKH9lMUO8S+fOnZvdvkuXLhERsWnTphY/R3OzybW1tTFs2LAWtwcAAED71+4DcdeuXYvLW7dubXb7LVu2REREt27dWvwczR2KDQAAQMfT7g+ZPvjgg4vLLTkM+qOPPoqIlh1eDQAAQLrafSDu2rVrfPKTn4yI5q8G/e677xYDsQtlAQAA0JR2H4gjIk488cSIiFi2bFnU19c3ut0bb7xRXD7hhBNyrwsAAIDyVRaB+IwzzoiInYdD/+53v2t0u/nz5xeXTz/99NzrAgAAoHyVRSC+7LLLissPPPDAXrfZsWNHPPjggxER0atXrxg5cmRblAYAAECZKotAPGzYsDjzzDMjImLWrFmxcOHCPbaZNm1avP766xERccMNN8QnPvGJNq0RAACA8tLub7u0yz333BOnn356bNq0KUaNGhXf+ta3YuTIkbFp06Z4+OGHY+bMmRERUVVVFTfddFOJqwUAAKC9K5tAPGTIkPj5z38eX/rSl2LDhg3xrW99a49tqqqq4sknn9ztVk0AAACwN2VxyPQul1xySfzf//t/4xvf+EZUVVVF9+7do1evXnHqqafGnXfeGUuWLIlBgwaVukwAAADKQCHLsqzURbR3NTU1xfsar169OiorK0tcEQAAQFryyGVlNUMMAAAArUUgBgAAIEkCMQAAAEkSiAEAAEiSQAwAAECSBGIAAACSJBADAACQJIEYAACAJAnEAAAAJEkgBgAAIEkCMQAAAEkSiAEAAEiSQAwAAECSBGIAAACSJBADAACQJIEYAACAJAnEAAAAJEkgBgAAIEkCMQAAAEmqKHUBAFDOCoVCLu1mWZZLuwDA/88MMQAAAEkSiAEAAEiSQAwAAECSBGIAAACSJBADAACQJIEYAACAJAnEAAAAJEkgBgAAIEkCMQAAAEkSiAEAAEiSQAwAAECSBGIAAACSJBADAACQJIEYAACAJAnEAAAAJEkgBgAAIEkCMQAAAEkSiAEAAEiSQAwAAECSBGIAAACSJBADAACQpIpSFwAA5SzLslzaLRQKubSbV73k12flxPsLKDdmiAEAAEiSQAwAAECSBGIAAACSJBADAACQJIEYAACAJAnEAAAAJEkgBgAAIEkCMQAAAEkSiAEAAEiSQAwAAECSBGIAAACSJBADAACQJIEYAACAJAnEAAAAJEkgBgAAIEkCMQAAAEkSiAEAAEiSQAwAAECSBGIAAACSJBADAACQJIEYAACAJFWUugAAYE9ZlpW6hJIrFAqlLgGADs4MMQAAAEkSiAEAAEiSQAwAAECSBGIAAACSJBADAACQJIEYAACAJAnEAAAAJEkgBgAAIEkCMQAAAEkSiAEAAEiSQAwAAECSBGIAAACSJBADAACQJIEYAACAJAnEAAAAJEkgBgAAIEkCMQAAAEkSiAEAAEiSQAwAAECSBGIAAACSJBADAACQpIpSFwAAtJ1CoVDqEthHWZa1epveBwA7mSEGAAAgSWURiAuFQou+zj777FKXCgAAQJkoi0AMAAAAra2sziH+2te+Ftdee22j63v06NGG1QAAAFDOyioQ9+nTJz7zmc+UugwAAAA6AIdMAwAAkCSBGAAAgCQJxAAAACSprM4hfuSRR+Lf/u3fYtWqVdGpU6c48sgj43Of+1xMmDAhRo4cud/t1tTUNLm+trZ2v9sGAACgfSpkWZaVuojmFAqFZre57LLLYvbs2XHooYfm0v4uq1evjsrKyn1+DgBoD/bldx7tQx5/quX1PiiDPyuBMlZTUxP9+/ePiNbLZWUxQ9y9e/e49NJL49xzz43BgwdHz549Y926dTF//vz453/+51i/fn089thjMXr06HjmmWfiE5/4RKlLBgAAoJ0rixni9957L3r16rXXde+8805ceOGFsWTJkoiIuOeee+K///f/vk/tt+SQ6WHDhkWEGWIAypsZ4vJjhhhgpzxmiMsiEDdnxYoVMXjw4Ni2bVsMGjQo3nrrrVZtP48dDwClIBCXH4EYYKc8clmHuMr0cccdF+eff35ERCxbtizWrl1b4ooAAABo7zpEII6IOPHEE4vLa9asKWElAAAAlIMOE4gdAgYAAMC+6DCB+LXXXisu9+3bt4SVAAAAUA46RCBeuXJlPPPMMxERMXDgwOjXr1+JKwIAAKC9a/eB+Iknnoj6+vpG17/zzjsxduzY2Lp1a0REXHvttW1VGgAAAGWsotQFNOf666+Pbdu2xdixY2P48OExYMCA6NatW9TV1cVzzz0X9957b9TV1UVExBlnnBHXXXddiSsGAACgHLT7QBwRsXbt2pgxY0bMmDGj0W3Gjh0b9913X3Tp0qUNKwMAAKBctftA/JOf/CTmz58fCxcujBUrVkRdXV1s2LAhevbsGf3794/Pfe5zceWVV8bw4cNLXSoAtBp3TwCA/LX7QDxixIgYMWJEqcsAAACgg2n3F9UCAACAPAjEAAAAJEkgBgAAIEkCMQAAAEkSiAEAAEiSQAwAAECSBGIAAACSJBADAACQJIEYAACAJAnEAAAAJEkgBgAAIEkCMQAAAEkSiAEAAEiSQAwAAECSBGIAAACSJBADAACQJIEYAACAJAnEAAAAJEkgBgAAIEkVpS4AAKAjyLKs1CUAsI/MEAMAAJAkgRgAAIAkCcQAAAAkSSAGAAAgSQIxAAAASRKIAQAASJJADAAAQJIEYgAAAJIkEAMAAJAkgRgAAIAkCcQAAAAkSSAGAAAgSQIxAAAASRKIAQAASJJADAAAQJIEYgAAAJIkEAMAAJAkgRgAAIAkCcQAAAAkSSAGAAAgSQIxAAAASaoodQEAUM4KhUKpS+iwsiwrdQntQh7vMfsWYCczxAAAACRJIAYAACBJAjEAAABJEogBAABIkkAMAABAkgRiAAAAkiQQAwAAkCSBGAAAgCQJxAAAACRJIAYAACBJAjEAAABJEogBAABIkkAMAABAkgRiAAAAkiQQAwAAkCSBGAAAgCQJxAAAACRJIAYAACBJAjEAAABJEogBAABIkkAMAABAkipKXQAAtJVCoVDqEjqsLMtKXUKLldv7oJz2LUC5MUMMAABAkgRiAAAAkiQQAwAAkCSBGAAAgCQJxAAAACRJIAYAACBJAjEAAABJEogBAABIkkAMAABAkgRiAAAAkiQQAwAAkCSBGAAAgCQJxAAAACRJIAYAACBJAjEAAABJEogBAABIkkAMAABAkgRiAAAAkiQQAwAAkCSBGAAAgCQJxAAAACSpotQFQJ4KhUKrt5llWau3CbSNchq/eXx+5amc6i2n9wEA+cp1hvjPf/5zzJ07N6ZOnRoXXnhh9O7dOwqFQhQKhZgwYcI+t/fUU09FdXV1VFZWRpcuXaKysjKqq6vjqaeeav3iAQAA6NBynSE+4ogjWqWdHTt2xOTJk2PWrFm7/XzNmjWxZs2aeOyxx2LSpElx7733xkEHOQocAACA5rVZejz66KNj1KhR+/XYKVOmFMPwkCFD4qGHHopFixbFQw89FEOGDImIiPvuuy++/e1vt1q9AAAAdGy5zhBPnTo1hg4dGkOHDo0jjjgiVq1aFccee+w+tbF06dL4wQ9+EBERp556ajz//PPRrVu3iIgYOnRoXHrppTFixIhYvHhxfP/734+vfOUrMWjQoFZ/LQAAAHQsuc4Q33bbbXHxxRcf0KHT06dPj/r6+oiImDFjRjEM79K9e/eYMWNGRETU19fH3Xffvf8FAwAAkIx2fcJtlmXx+OOPR0TE4MGD47TTTtvrdqeddlocf/zxERHx+OOPu3okAAAAzWrXgXjlypWxdu3aiIgYMWJEk9vuWr9mzZpYtWpV3qUBAABQ5tp1IH7ttdeKy4MHD25y24brX3/99dxqAgAAoGPI9aJaB6qmpqa4XFlZ2eS2/fv3Ly6vXr16v59nb2pra/epPQAAANq/dh2IP/jgg+Jyz549m9y2R48exeUPP/xwn56nYZgGAAAgDe36kOnNmzcXlzt37tzktl26dCkub9q0KbeaAAAA6Bja9Qxx165di8tbt25tctstW7YUlz9+a6bmNHeIdW1tbQwbNmyf2gQAAKB9a9eB+OCDDy4uN3cY9EcffVRcbu7w6o9r7vxkAAAAOp52fch0w6Da3IWvGs7yOicYAACA5rTrQHziiScWl994440mt224/oQTTsitJgAAADqGdh2Ijz322Ojbt29ERMyfP7/JbZ9//vmIiOjXr18MGDAg79IAAAAoc+06EBcKhRg9enRE7JwBfvnll/e63csvv1ycIR49enQUCoU2qxEAAIDy1K4DcUTEjTfeGJ06dYqIiOuvv36PWypt2rQprr/++oiIqKioiBtvvLGtSwQAAKAM5XqV6RdffDGWLVtW/L6urq64vGzZspg9e/Zu20+YMGGPNqqqquLmm2+OO+64IxYvXhynn3563HLLLTFw4MBYvnx53HnnnbFkyZKIiLj55pvjU5/6VC6vBQAAgI6lkGVZllfjEyZMiJ/85Cct3r6xUnbs2BFf/epX4/7772/0sVdddVXMnDkzDjqo9Se9a2pqileuXr16tds0lZE8Dp/PccgAFDn9Jz8+xwHKUx65rF3fh3iXgw46KGbNmhVjx46NmTNnxm9/+9uoq6uL3r17x9ChQ+Pqq6+OCy+8sNRlcgDy+sPPHz3kyfuWPHkf+KcAAPnLdYa4ozBDnD/BgnLkfQv5MsYAaCiPXNbuL6oFAAAAeRCIAQAASJJADAAAQJIEYgAAAJIkEAMAAJAkgRgAAIAkCcQAAAAkSSAGAAAgSQIxAAAASRKIAQAASJJADAAAQJIEYgAAAJIkEAMAAJAkgRgAAIAkCcQAAAAkSSAGAAAgSQIxAAAASRKIAQAASJJADAAAQJIEYgAAAJJUUeoCoNwUCoVc2s2yLJd2yY8+AwAob2aIAQAASJJADAAAQJIEYgAAAJIkEAMAAJAkgRgAAIAkCcQAAAAkSSAGAAAgSQIxAAAASRKIAQAASJJADAAAQJIEYgAAAJIkEAMAAJAkgRgAAIAkCcQAAAAkSSAGAAAgSQIxAAAASRKIAQAASJJADAAAQJIEYgAAAJIkEAMAAJAkgRgAAIAkVZS6ACg3WZaVuoR9UigUcmk3j/1QTrUCu8tj/OY1dn3WALCLGWIAAACSJBADAACQJIEYAACAJAnEAAAAJEkgBgAAIEkCMQAAAEkSiAEAAEiSQAwAAECSBGIAAACSJBADAACQJIEYAACAJAnEAAAAJEkgBgAAIEkCMQAAAEkSiAEAAEiSQAwAAECSBGIAAACSJBADAACQJIEYAACAJAnEAAAAJEkgBgAAIEkVpS4A2KlQKJS6hH1SbvXmIa99kGVZLu1CnsrpfZtXrT4TAMqPGWIAAACSJBADAACQJIEYAACAJAnEAAAAJEkgBgAAIEkCMQAAAEkSiAEAAEiSQAwAAECSBGIAAACSJBADAACQJIEYAACAJAnEAAAAJEkgBgAAIEkCMQAAAEkSiAEAAEiSQAwAAECSBGIAAACSJBADAACQJIEYAACAJAnEAAAAJKmi1AVARESWZbm0WygUWr3NvGrNq13yeR/kqZzet5SfvMaD95jfZZSncvsdmYdyGrt5SfkzwQwxAAAASco1EP/5z3+OuXPnxtSpU+PCCy+M3r17R6FQiEKhEBMmTGhRG7Nnzy4+prmv2bNn5/lyAAAA6EByPWT6iCOOyLN5AAAA2G9tdg7x0UcfHYMHD46nn356v9v49a9/HX379m10fWVl5X63DQAAQFpyDcRTp06NoUOHxtChQ+OII46IVatWxbHHHrvf7VVVVcWAAQNar0AAAACSlWsgvu222/JsHgAAAPabq0wDAACQJIEYAACAJLXZRbVaw8SJE+PNN9+Murq6OOSQQ2LQoEFx3nnnxde+9rXo16/ffrdbU1PT5Pra2tr9bhsAAID2qawC8XPPPVdcXr9+faxfvz5eeeWVmDZtWkyfPj2uvvrq/Wq3f//+rVQhAAAA5aIsAvFxxx0XY8aMieHDhxfD64oVK+IXv/hFzJkzJzZv3hzXXHNNFAqFmDx5comrBQAAoBy0+0BcXV0dV155ZRQKhd1+PnTo0PjCF74Qc+fOjTFjxsS2bdviG9/4Rlx66aVx5JFH7tNzrF69usn1tbW1MWzYsH2uHQAAgPar3V9U69BDD90jDDd08cUXx9SpUyMiYuPGjTFr1qx9fo7Kysomv4466qj9rh8AAID2qd0H4paYPHlyMTTPnz+/xNUAAABQDjpEIO7Tp0988pOfjIiINWvWlLgaAAAAykGHCMQR0eRh1QAAAPBxHSIQr1u3Lurq6iIiom/fviWuBgAAgHLQIQLxzJkzI8uyiIgYMWJEiasBAACgHLTrQLxq1apYsmRJk9vMnTs3br/99oiI6NatW0ycOLEtSgMAAKDM5Xof4hdffDGWLVtW/H7XYc0REcuWLYvZs2fvtv2ECRN2+37VqlUxcuTIGD58eFxyySVx8sknR58+fSIiYsWKFTFnzpyYM2dOcXb4Bz/4QfTr1y+fFwMAAECHkmsgvu++++InP/nJXtctWLAgFixYsNvPPh6Id1m4cGEsXLiw0efp3r173H333TF58uT9rhUAAIC05BqID9Qpp5wSP/3pT2PhwoWxePHiqK2tjbq6uqivr4/DDjssPv3pT8e5554bkyZNKs4cQ0O7jh4gbeX2Psjjqvl5XYm/3PZtOSm3PsujXu+vnfLYD+X2/ion7nxSfsqtz3wmtK5CVg5VllhNTU30798/IiJWr14dlZWVJa4I6MjK6RezXyH5Kbc/TgTi8lJu769yUk6f4ZSnlANxHrmsXV9UCwAAAPIiEAMAAJAkgRgAAIAkCcQAAAAkSSAGAAAgSQIxAAAASRKIAQAASJJADAAAQJIEYgAAAJIkEAMAAJAkgRgAAIAkCcQAAAAkSSAGAAAgSQIxAAAASRKIAQAASJJADAAAQJIEYgAAAJIkEAMAAJAkgRgAAIAkCcQAAAAkqaLUBQD5KhQKpS6hxbIsK3UJ7UI57Ydyen+Vm3J6H5Cvchpn5VRrufGZkJ+83rf6rDyYIQYAACBJAjEAAABJEogBAABIkkAMAABAkgRiAAAAkiQQAwAAkCSBGAAAgCQJxAAAACRJIAYAACBJAjEAAABJEogBAABIkkAMAABAkgRiAAAAkiQQAwAAkCSBGAAAgCQJxAAAACRJIAYAACBJAjEAAABJEogBAABIkkAMAABAkgRiAAAAklRR6gIgIqJQKJS6hA4ry7Jc2tVn5SWv/srr/QX8/4yz8uL3I3nzHmtdZogBAABIkkAMAABAkgRiAAAAkiQQAwAAkCSBGAAAgCQJxAAAACRJIAYAACBJAjEAAABJEogBAABIkkAMAABAkgRiAAAAkiQQAwAAkCSBGAAAgCQJxAAAACRJIAYAACBJAjEAAABJEogBAABIkkAMAABAkgRiAAAAkiQQAwAAkKSKUhdAeSkUCqUugX2kz4iIyLKs1CXsk3J635bbvgVgd+X2OV5u9bZ3ZogBAABIkkAMAABAkgRiAAAAkiQQAwAAkCSBGAAAgCQJxAAAACRJIAYAACBJAjEAAABJEogBAABIkkAMAABAkgRiAAAAkiQQAwAAkCSBGAAAgCQJxAAAACRJIAYAACBJAjEAAABJEogBAABIkkAMAABAkgRiAAAAkiQQAwAAkCSBGAAAgCRVlLoAykuWZaUugXaiUCiUuoQOK499W25jt9zqJR/l9jnjfZtfn9m3QF7MEAMAAJCkXAPx4sWL4/bbb49Ro0ZFZWVldOnSJXr27BlVVVUxceLEePHFF/epvaeeeiqqq6uLbVVWVkZ1dXU89dRTOb0CAAAAOqpCltMxKGeddVa88MILzW43fvz4+PGPfxydO3dudJsdO3bE5MmTY9asWY1uM2nSpLj33nvjoINaP+PX1NRE//79IyJi9erVUVlZ2erPAeXGYb35sW8pR+V2eHMejDOHTEfYB5CnPHJZbjPEa9eujYiIvn37xg033BBz5syJRYsWxcKFC+OHP/xh9OvXLyIiHnzwwZgwYUKTbU2ZMqUYhocMGRIPPfRQLFq0KB566KEYMmRIRETcd9998e1vfzuvlwMAAEAHk9sM8cUXXxzjx4+PsWPHRqdOnfZYX1dXF6effnosXbo0IiLmz58fZ5111h7bLV26ND796U9HfX19nHrqqfH8889Ht27dius3btwYI0aMiMWLF0dFRUW8/vrrMWjQoFZ9LWaIYU9mMfNj31KOzBAbZxFmRyPsA8hTWc0Qz507N8aNG7fXMBwR0bt375g2bVrx+zlz5ux1u+nTp0d9fX1ERMyYMWO3MBwR0b1795gxY0ZERNTX18fdd9/dGuUDAADQwZX0KtMjR44sLi9fvnyP9VmWxeOPPx4REYMHD47TTjttr+2cdtppcfzxx0dExOOPP+4/aAAAADSrpIF4y5YtxeW9zSSvXLmyeC7yiBEjmmxr1/o1a9bEqlWrWq9IAAAAOqSKUj75/Pnzi8snnHDCHutfe+214vLgwYObbKvh+tdffz2OPfbYFtdRU1PT5Pra2toWtwUAAEB5KFkg3rFjR9xxxx3F78eNG7fHNg2DanMnTO86uTpi5wnW+6LhYwEAAEhDyQ6Zvvvuu2PRokURETFmzJg45ZRT9tjmgw8+KC737NmzyfZ69OhRXP7www9bqUoAAAA6qpLMEM+fPz+++c1vRkREnz594n/9r/+11+02b95cXO7cuXOTbXbp0qW4vGnTpn2qp7kZ5dra2hg2bNg+tQkAAED71uaB+I9//GNUV1dHfX19dO3aNR555JHo06fPXrft2rVrcXnr1q1NttvwAl0fvzVTc9xXGAAAID1tesj0ypUrY9SoUfHuu+9Gp06d4uGHH46zzjqr0e0PPvjg4nJzh0F/9NFHxeXmDq8GAACANgvEa9eujfPOOy/Wrl0bhUIh7r///hg9enSTj2k4c9vclaAbHvbsIlkAAAA0p00CcV1dXZx//vmxYsWKiIiYMWNGjB8/vtnHnXjiicXlN954o8ltG67f2y2cAAAAoKHcA/H7778fF1xwQfGewnfccUdcd911LXrsscceG3379o2I3e9ZvDfPP/98RET069cvBgwYsP8FAwAAkIRcA/HGjRvjoosuit///vcRETFlypS45ZZbWvz4QqFQPKz6jTfeiJdffnmv27388svFGeLRo0dHoVA4wMoBAADo6HILxFu3bo3q6upYsGBBRETccMMN8Q//8A/73M6NN94YnTp1ioiI66+/fo9bKm3atCmuv/76iIioqKiIG2+88cAKBwAAIAm53XbpiiuuiKeffjoiIs4555y46qqr4j//8z8b3b5z585RVVW1x8+rqqri5ptvjjvuuCMWL14cp59+etxyyy0xcODAWL58edx5552xZMmSiIi4+eab41Of+lQ+LwgAAIAOpZBlWZZLw/t42PIxxxwTq1at2uu6HTt2xFe/+tW4//77G338VVddFTNnzoyDDmr9Se+amprilatXr17tvsUQ+z7GWyKnj6OyY99SjpyuZJxF5Pc+KKd9ax9AfvLIZbnNELemgw46KGbNmhVjx46NmTNnxm9/+9uoq6uL3r17x9ChQ+Pqq6+OCy+8sNRlAgfIH9Q7+aOnvPjjNz/2QfnRZ0C5yS0Q5/GB+PnPfz4+//nPt3q7AAAApKdN7kMMAAAA7Y1ADAAAQJIEYgAAAJIkEAMAAJAkgRgAAIAkCcQAAAAkSSAGAAAgSQIxAAAASRKIAQAASJJADAAAQJIEYgAAAJIkEAMAAJAkgRgAAIAkCcQAAAAkSSAGAAAgSQIxAAAASRKIAQAASJJADAAAQJIEYgAAAJIkEAMAAJCkilIXAOSrUCjk0m6WZbm0W07y2rd58D7YKY/9YB8AQPkyQwwAAECSBGIAAACSJBADAACQJIEYAACAJAnEAAAAJEkgBgAAIEkCMQAAAEkSiAEAAEiSQAwAAECSBGIAAACSJBADAACQJIEYAACAJAnEAAAAJEkgBgAAIEkCMQAAAEkSiAEAAEiSQAwAAECSBGIAAACSJBADAACQJIEYAACAJAnEAAAAJKmi1AVAREShUMil3SzLWr3Ncqo1z3bJb9/m8R7zPtjJZ4L3QjnymVB+4wwoH2aIAQAASJJADAAAQJIEYgAAAJIkEAMAAJAkgRgAAIAkCcQAAAAkSSAGAAAgSQIxAAAASRKIAQAASJJADAAAQJIEYgAAAJIkEAMAAJAkgRgAAIAkCcQAAAAkSSAGAAAgSQIxAAAASRKIAQAASJJADAAAQJIEYgAAAJIkEAMAAJCkilIXQHkpFAqlLqHksiwrdQl0cHm8x/Iau8ZD+e0D7wXKUV7vL3/XAGaIAQAASJJADAAAQJIEYgAAAJIkEAMAAJAkgRgAAIAkCcQAAAAkSSAGAAAgSQIxAAAASRKIAQAASJJADAAAQJIEYgAAAJIkEAMAAJAkgRgAAIAkCcQAAAAkSSAGAAAgSQIxAAAASRKIAQAASJJADAAAQJIEYgAAAJIkEAMAAJAkgRgAAIAkVZS6AMpLlmWlLgGAA5DX53ihUGj1Nv3O2cl+yE8e+zaPsQDkxwwxAAAASco1EC9evDhuv/32GDVqVFRWVkaXLl2iZ8+eUVVVFRMnTowXX3yx2TZmz54dhUKhRV+zZ8/O8+UAAADQgeR2yPRZZ50VL7zwwh4/37p1a7z11lvx1ltvxezZs2P8+PHx4x//ODp37pxXKQAAALCH3ALx2rVrIyKib9++cfnll8eZZ54ZRx99dGzfvj0WLlwY06ZNizVr1sSDDz4Y27Zti5/97GfNtvnrX/86+vbt2+j6ysrKVqsfAACAji23QDx48OD43ve+F2PHjo1OnTrttu60006LL3/5y3H66afH0qVL46GHHoprrrkmzjrrrCbbrKqqigEDBuRVMgAAAAnJ7RziuXPnxrhx4/YIw7v07t07pk2bVvx+zpw5eZUCAAAAeyjpVaZHjhxZXF6+fHkJKwEAACA1JQ3EW7ZsKS43NpMMAAAAecjtHOKWmD9/fnH5hBNOaHb7iRMnxptvvhl1dXVxyCGHxKBBg+K8886Lr33ta9GvX7/9rqOmpqbJ9bW1tfvdNgAAAO1TyQLxjh074o477ih+P27cuGYf89xzzxWX169fH+vXr49XXnklpk2bFtOnT4+rr756v2rp37//fj0OAACA8lWyQHz33XfHokWLIiJizJgxccoppzS67XHHHRdjxoyJ4cOHF8PrihUr4he/+EXMmTMnNm/eHNdcc00UCoWYPHlym9QPAABAeStkWZa19ZPOnz8/zjvvvKivr48+ffrEq6++Gn369Nnrtu+//34ccsghUSgU9rp+7ty5MWbMmNi2bVt07949li9fHkceeeQ+1dOSQ6aHDRsWERGrV692v2Og7DT2GXqgSvArhHYqj/eY9xflyOct5KempqY4QdpauazNL6r1xz/+Maqrq6O+vj66du0ajzzySKNhOCLi0EMPbfKD5eKLL46pU6dGRMTGjRtj1qxZ+1xTZWVlk19HHXXUPrcJAABA+9amgXjlypUxatSoePfdd6NTp07x8MMPx1lnnXXA7U6ePLkYmhteqAsAAAAa02aBeO3atXHeeefF2rVro1AoxP333x+jR49ulbb79OkTn/zkJyMiYs2aNa3SJgAAAB1bmwTiurq6OP/882PFihURETFjxowYP358qz5HXudrAAAA0DHlHojff//9uOCCC+K1116LiIg77rgjrrvuulZ9jnXr1kVdXV1ERPTt27dV2wYAAKBjyjUQb9y4MS666KL4/e9/HxERU6ZMiVtuuaXVn2fmzJnFK++NGDGi1dsHAACg48ktEG/dujWqq6tjwYIFERFxww03xD/8wz/sUxurVq2KJUuWNLnN3Llz4/bbb4+IiG7dusXEiRP3r2AAAACSUpFXw1dccUU8/fTTERFxzjnnxFVXXRX/+Z//2ej2nTt3jqqqqt1+tmrVqhg5cmQMHz48Lrnkkjj55JOLt2hasWJFzJkzJ+bMmVOcHf7BD34Q/fr1y+kVAQAA0JHkFogfffTR4vL//t//O/76r/+6ye2POeaYWLVq1V7XLVy4MBYuXNjoY7t37x533313TJ48eb9qBQAAID25BeLWcMopp8RPf/rTWLhwYSxevDhqa2ujrq4u6uvr47DDDotPf/rTce6558akSZOKM8cAtJ28rvC/68gfykcefVZud5DI631bTvvB2AXKTW6BuDU+EA8++OD427/92/jbv/3bVqgIAAAA/n9tch9iAAAAaG8EYgAAAJIkEAMAAJAkgRgAAIAkCcQAAAAkSSAGAAAgSQIxAAAASRKIAQAASJJADAAAQJIEYgAAAJIkEAMAAJAkgRgAAIAkCcQAAAAkSSAGAAAgSQIxAAAASRKIAQAASJJADAAAQJIEYgAAAJIkEAMAAJAkgRgAAIAkVZS6AADKV5ZlubRbKBRyaTePesup1jzltR/KiX1QfvugnMaZzxrIhxliAAAAkiQQAwAAkCSBGAAAgCQJxAAAACRJIAYAACBJAjEAAABJEogBAABIkkAMAABAkgRiAAAAkiQQAwAAkCSBGAAAgCQJxAAAACRJIAYAACBJAjEAAABJEogBAABIkkAMAABAkgRiAAAAkiQQAwAAkCSBGAAAgCQJxAAAACSpotQFAFC+CoVCLu1mWZZLu3nUm1et5cZ+gHyV0+dihM8EyocZYgAAAJIkEAMAAJAkgRgAAIAkCcQAAAAkSSAGAAAgSQIxAAAASRKIAQAASJJADAAAQJIEYgAAAJIkEAMAAJAkgRgAAIAkCcQAAAAkSSAGAAAgSQIxAAAASRKIAQAASJJADAAAQJIEYgAAAJIkEAMAAJAkgRgAAIAkCcQAAAAkSSAGAAAgSRWlLgCA8pVlWS7tFgqFXNrNQ161ltu+zateiPC+LUd59Jn+Ig9miAEAAEiSQAwAAECSBGIAAACSJBADAACQJIEYAACAJAnEAAAAJEkgBgAAIEkCMQAAAEkSiAEAAEiSQAwAAECSBGIAAACSJBADAACQJIEYAACAJAnEAAAAJEkgBgAAIEkCMQAAAEkSiAEAAEiSQAwAAECSBGIAAACSJBADAACQJIEYAACAJFWUugAA+Lgsy0pdQosVCoWyahfKUTl9JgDlJbcZ4g0bNsTDDz8cN910U4wYMSIGDRoUhx56aHTu3Dn69OkTZ599dtx1112xfv36FrX30ksvxZe+9KU45phjomvXrnHkkUfGBRdcEA899FBeLwEAAIAOrJDl9C+33/zmN3H++ec3u13v3r3jpz/9aVxwwQWNbnPrrbfGd7/73dixY8de11900UUxZ86c6Nq1637X25Sampro379/RESsXr06Kisrc3kegLzkNdto1sZM7i7eC7BTuX3eltNnmM8Z8shluZ5D3L9//xg/fnzcc8898eijj8bChQtjwYIF8fOf/zwuv/zy6NSpU9TV1cWll14a/+f//J+9tnHvvffGbbfdFjt27IiBAwfGrFmzYtGiRfHYY4/FyJEjIyLiySefjK985St5vhQAAAA6mNxmiLdv3x6dOnVqcpvHHnssqqurIyKiuro6Hn300d3W/+Uvf4njjjsu3n///Tj66KPjd7/7XfTu3Xu356iuro4nnngiIiLmzZsXZ599duu+kDBDDJS/cpuxKCflNLuSJ+8F2KncPm/L6TPM5wxlNUPcXBiOiLjsssvi+OOPj4iIF154YY/19913X7z//vsREXHnnXfuFoZ3Pcc//dM/FZ/r+9///oGWDQAAQCJKftulgw8+OCIiNm/evMe6xx57LCIiDjnkkBgzZsxeH19ZWRnnnXdeREQ8++yz8cEHH+RTKAAAAB1KSQPxm2++GX/4wx8iImLw4MG7rdu6dWssWrQoIiKGDx8enTt3brSdESNGRETEli1bYvHixfkUCwAAQIfS5vch3rhxY6xZsyaeeOKJuOuuu6K+vj4iIm688cbdtlu6dGls3749IvYMyx/XcP3rr79evNhWS9XU1DS5vra2dp/aAwAAoP1rk0A8e/bsmDhxYqPrv/nNb8bf/M3f7PazhiG1uZOld51YHbHz5Op91fDxAAAApKHNZ4gb+uxnPxszZ86MoUOH7rGu4bnAPXv2bLKdHj16FJc//PDD1isQAACADqtNAvFll10Wp556akREbNq0KZYvXx7/9m//Fv/+7/8eV1xxRUyfPj0uvvji3R7T8CJbTZ0/HBHRpUuX4vKmTZv2ub7mZpVra2tj2LBh+9wuAAAA7VebBOJevXpFr169it8PHTo0vvjFL8a//Mu/xJVXXhmjR4+OWbNmxYQJE4rbdO3atbi8devWJtvfsmVLcblbt277XJ/7CgMAAKSnpFeZ/vKXvxyXX3557NixI77+9a/HX/7yl+K6Xbdjimj+MOiPPvqouNzc4dUAAAAQ0Q7uQzx69OiI2Blqf/WrXxV/3nDWtrmrQDc85NkFsgAAAGiJkgfiww8/vLj89ttvF5erqqqiU6dOERHxxhtvNNlGw/UnnHBCK1cIAABAR1TyQLxmzZricsPDnTt37ly8kNXChQubPI94/vz5EbHz4lq7Lt4FAAAATSl5IH7kkUeKyyeddNJu6y677LKIiNiwYUM8+uije318TU1N/OY3v4mIiHPPPXe3c48BAACgMbkF4tmzZ+9266S9ufvuu+M//uM/IiLi2GOPjTPPPHO39ZMmTYpDDz00IiK++c1vxvr163dbv3379rj22mtj+/btERFx8803t1b5AAAAdHC53Xbp1ltvjZtuuinGjh0bZ5xxRgwcODB69uwZH3zwQbz66qvxr//6r7FgwYKI2Hl49MyZM4vnDO/yV3/1V3HnnXfGNddcE2+//Xb8t//232LKlClx0kknxdq1a2P69Okxb968iIi44oor4uyzz87r5QAAANDBFLIsy/JoeMCAAbtdJKsxlZWVcf/998f555/f6Dbf+c534rvf/W40VurnP//5+MUvfrHbvYtbU01NTfHq1atXr3bfYqDsFAqFXNrN6VdIWclr35Yb7wXYqdw+b8vpM8znDHnkstxmiH/961/Hk08+GQsWLIhly5bFO++8E+vXr49u3bpFnz594rOf/WxcfPHFMW7cuOjevXuTbd12221xwQUXxI9+9KN44YUX4p133olevXrFySefHBMnTowrrrgir5cBAABAB5XbDHFHYoYYaEvl9N/6vPjVVH6zTFCOyunzttzGbh77ttz2Aa0vj1xW8qtMAwAAQCkIxAAAACRJIAYAACBJAjEAAABJEogBAABIkkAMAABAkgRiAAAAkiQQAwAAkCSBGAAAgCQJxAAAACRJIAYAACBJAjEAAABJEogBAABIkkAMAABAkgRiAAAAkiQQAwAAkCSBGAAAgCQJxAAAACRJIAYAACBJAjEAAABJqih1AQDAnrIsK3UJ0G4UCoVSl9Bixu5O9gPlwgwxAAAASRKIAQAASJJADAAAQJIEYgAAAJIkEAMAAJAkgRgAAIAkCcQAAAAkSSAGAAAgSQIxAAAASRKIAQAASJJADAAAQJIEYgAAAJIkEAMAAJAkgRgAAIAkCcQAAAAkSSAGAAAgSQIxAAAASRKIAQAASJJADAAAQJIEYgAAAJIkEAMAAJCkilIXAMDusiwrdQkA7YrPRSAvZogBAABIkkAMAABAkgRiAAAAkiQQAwAAkCSBGAAAgCQJxAAAACRJIAYAACBJAjEAAABJEogBAABIkkAMAABAkgRiAAAAkiQQAwAAkCSBGAAAgCQJxAAAACRJIAYAACBJAjEAAABJEogBAABIkkAMAABAkgRiAAAAklRR6gLKQX19fXG5tra2hJUAAACkqWEWa5jRDoRA3ALr1q0rLg8bNqyElQAAALBu3boYMGDAAbfjkGkAAACSVMiyLCt1Ee3d5s2b49VXX42IiMMPPzwqKhqfWK+trS3OIi9atCiOOuqoNqmR/afPyov+Kj/6rPzos/Kiv8qPPis/+qx9qK+vLx69e9JJJ0XXrl0PuE2HTLdA165dY+jQofv8uKOOOioqKytzqIi86LPyor/Kjz4rP/qsvOiv8qPPyo8+K63WOEy6IYdMAwAAkCSBGAAAgCQJxAAAACRJIAYAACBJAjEAAABJEogBAABIkkAMAABAkgpZlmWlLgIAAADamhliAAAAkiQQAwAAkCSBGAAAgCQJxAAAACRJIAYAACBJAjEAAABJEogBAABIkkAMAABAkgRiAAAAkiQQAwAAkCSBuBW9/fbbcdNNN8XgwYOjR48e8Vd/9VcxdOjQ+P73vx8bN24sdXn8P4VCoUVfZ599dqlLTcKf//znmDt3bkydOjUuvPDC6N27d7EPJkyYsM/tPfXUU1FdXR2VlZXRpUuXqKysjOrq6njqqadav/gEtUZ/zZ49u8XjcPbs2bm+nhQsXrw4br/99hg1alRxXPTs2TOqqqpi4sSJ8eKLL+5Te8ZY/lqjz4yztrFhw4Z4+OGH46abbooRI0bEoEGD4tBDD43OnTtHnz594uyzz4677ror1q9f36L2XnrppfjSl74UxxxzTHTt2jWOPPLIuOCCC+Khhx7K+ZWkozX67Lnnnmvx+Lr11lvb7sWxfzJaxS9/+cvskEMOySJir19VVVXZW2+9VeoyybJG++jjXyNGjCh1qUloqg+uvPLKFrezffv27KqrrmqyvUmTJmXbt2/P78UkoDX664EHHmjxOHzggQdyfT0d3Zlnntmi/Tx+/Phsy5YtTbZljLWN1uoz46xtPPPMMy3ax717985+9atfNdnWd77zneyggw5qtI2LLroo27RpUxu9so6rNfps3rx5LR5f3/nOd9r2BbLPKoIDtmTJkvjCF74QmzZtip49e8bf//3fx8iRI2PTpk3x8MMPx49//ONYunRpXHTRRbF48eI4+OCDS10yEfG1r30trr322kbX9+jRow2rISLi6KOPjsGDB8fTTz+9z4+dMmVKzJo1KyIihgwZEn/3d38XAwcOjOXLl8ddd90VS5Ysifvuuy8OP/zw+N73vtfapSfpQPprl1//+tfRt2/fRtdXVlbud9tErF27NiIi+vbtG5dffnmceeaZcfTRR8f27dtj4cKFMW3atFizZk08+OCDsW3btvjZz37WaFvGWNtozT7bxTjLV//+/WPkyJFxyimnRP/+/eOoo46KHTt2RE1NTcyZMyceffTRqKuri0svvTQWLVoUJ5988h5t3HvvvXHbbbdFRMTAgQPjW9/6Vpx00kmxdu3auOeee2LevHnx5JNPxle+8pUW9TlNa40+2+X++++PoUOHNrq+T58+ebwEWlOpE3lHsOu/uRUVFdlLL720x/q77rrLf4naEX3RvkydOjV74oknsv/6r//KsizLVq5cuc8zjm+++WZWUVGRRUR26qmnZhs3btxt/UcffZSdeuqpxXHqaI391xr91XDmauXKlfkVS3bRRRdlP//5z7P6+vq9rl+3bl1WVVVV7I/58+fvdTtjrO20Vp8ZZ22jsX5q6N///d+LfVFdXb3H+vXr12eHHnpoFhHZ0Ucfna1bt26P57jkkkuKbcybN6+1yk9Sa/RZwxli/VH+nEN8gBYtWhQvvPBCRERcddVVMXz48D22uemmm+KEE06IiIh77rkntm3b1qY1Qnt22223xcUXXxxHHHHEfrcxffr0qK+vj4iIGTNmRLdu3XZb371795gxY0ZERNTX18fdd9+9/wUnrjX6i7Yzd+7cGDduXHTq1Gmv63v37h3Tpk0rfj9nzpy9bmeMtZ3W6jPaRmP91NBll10Wxx9/fERE8W/Ghu677754//33IyLizjvvjN69e+/xHP/0T/9UfK7vf//7B1p20lqjz+hYBOID9NhjjxWXJ06cuNdtDjrooBg/fnxERLz33nsxb968tigNkpBlWTz++OMRETF48OA47bTT9rrdaaedVvzl9vjjj0eWZW1WI7RnI0eOLC4vX758j/XGWPvTXJ/R/uw6XW7z5s17rNv1t+QhhxwSY8aM2evjKysr47zzzouIiGeffTY++OCDfAqlqKk+o2MRiA/Qris99ujRI0455ZRGtxsxYkRxecGCBbnXBalYuXJl8Zy7huNsb3atX7NmTaxatSrv0qAsbNmypbi8t5kTY6z9aa7PaF/efPPN+MMf/hARO/+p1NDWrVtj0aJFERExfPjw6Ny5c6Pt7BpfW7ZsicWLF+dTLBHRdJ/R8QjEB+j111+PiIhBgwZFRUXj1yhrOJh2PYbSeuSRR+LEE0+M7t27x8EHHxyf+tSn4sorrzSDX2Zee+214nJzv7SMw/Zn4sSJ0bdv3+jcuXP07t07TjvttPj2t78da9asKXVpyZg/f35xedfpPQ0ZY+1Pc332ccZZ29u4cWO89dZb8cMf/jBGjBhRPOXgxhtv3G27pUuXxvbt2yPC+Cq1lvbZx02ZMiWOOeaY6NKlSxx22GExZMiQ+MY3vhFLly5tg6ppDQLxAdi8eXPU1dVFRPNXaDzssMOKVy1evXp17rXRvNdeey1ef/312LRpU3z44YexbNmyePDBB+Occ86J6urq4vk8tG81NTXF5ebGYf/+/YvLxmH78Nxzz0VtbW1s27Yt1q9fH6+88kr84z/+YwwaNCjuvffeUpfX4e3YsSPuuOOO4vfjxo3bYxtjrH1pSZ99nHHWNhre+7lHjx5RVVUVN910U7zzzjsREfHNb34z/uZv/ma3xxhfpbU/ffZxL730UvzpT3+KrVu3xnvvvRd/+MMfYvr06XHCCSfErbfe6vSRMuC2Sweg4fkbPXv2bHb7Hj16xEcffRQffvhhnmXRjO7du8ell14a5557bgwePDh69uwZ69ati/nz58c///M/x/r16+Oxxx6L0aNHxzPPPBOf+MQnSl0yTdiXcdjwVlrGYWkdd9xxMWbMmBg+fHjxj7wVK1bEL37xi5gzZ05s3rw5rrnmmigUCjF58uQSV9tx3X333cXDNceMGbPXU3+MsfalJX22i3HWPnz2s5+NmTNn7vXWPMZX+9RUn+1y1FFHxZgxY+KMM86I4447LioqKuJPf/pTzJ07t3hbtNtuuy22bt3qVnTtXUmvcV3m/vSnPxUvuf7lL3+52e379++fRUQ2cODANqiOxrz77ruNrvuv//qvbMiQIcV+veeee9quMLIs2/fb+Nx+++3F7Z999tkmt3322WeL2373u99tpYrTtj+3XXrvvfeyHTt2NLr+iSeeyD7xiU9kEZF17949q62tbaVqaei5554r3kqpT58+2TvvvLPX7Yyx9qOlfZZlxlkpvPvuu9mrr76avfrqq9miRYuyhx56KKuuri7+7ffEE0/s8ZgHH3ywOGZmzZrVZPvLly8vbnvVVVfl9TKSsj99lmVZ9uGHH2Zbt25ttN1XXnmleCutQqGQ/eEPf8jrJdAKHDJ9ALp27Vpc3rp1a7Pb77oIxsdvV0Hb6tWrV6PrjjjiiJgzZ05xVnjXbURov/ZlHDa8EI1xWDqHHnpoFAqFRtdffPHFMXXq1IjYeU7XrFmz2qq0ZPzxj3+M6urqqK+vj65du8YjjzwSffr02eu2xlj7sC99FmGclUKvXr3iM5/5THzmM5+JoUOHxhe/+MV49NFH48EHH4wVK1bE6NGjY/bs2bs9xvgqrf3ps4ids/VNHUE4bNiw+J//839GxM4r9e9apn0SiA/ArsuxR7Ts0JWPPvooIlp2eDWlc9xxx8X5558fERHLli0rXl2V9mlfxuGuMRhhHLZ3kydPLv4x3/ACQhy4lStXxqhRo+Ldd9+NTp06xcMPPxxnnXVWo9sbY6W3r33WUsZZ2/jyl78cl19+eezYsSO+/vWvx1/+8pfiOuOrfWqqz1rqi1/8YhxyyCERYXy1dwLxAejatWt88pOfjIjdL4qwN++++27xg6zhRRFon0488cTisqtwtm8NL0LS3DhseBES47B969OnT/Hz1RhsPWvXro3zzjsv1q5dG4VCIe6///4YPXp0k48xxkprf/qspYyztrOrzz766KP41a9+Vfy58dV+NdZnLVVRURFVVVURYXy1dwLxAdoVnJYtW1a8PPvevPHGG8XlltwigdJq6jAz2peG/7xoOM72xjgsL8Zh66qrq4vzzz8/VqxYERE7TwkZP358s48zxkpnf/tsXxhnbePwww8vLr/99tvF5aqqquK9pI2v9qWxPtsXxld5EIgP0BlnnBERO/979Lvf/a7R7RoeKnH66afnXhcHpuF9N/v27VvCSmjOscceW+yj5g5Jev755yMiol+/fjFgwIC8S+MArFu3rnhbO2PwwL3//vtxwQUXFD/b7rjjjrjuuuta9FhjrDQOpM9ayjhrOw1nCBse7ty5c+cYNmxYREQsXLiwyfOId42/Ll26xKmnnppTpezSWJ+1VH19ffFexMZX+yYQH6DLLrusuPzAAw/sdZsdO3bEgw8+GBE7T94fOXJkW5TGflq5cmU888wzERExcODA6NevX4kroimFQqF4WNMbb7wRL7/88l63e/nll4v/XR89erT/2rZzM2fOLN67ccSIESWuprxt3LgxLrroovj9738fERFTpkyJW265pcWPN8ba3oH2WUsZZ23nkUceKS6fdNJJu63b9bfkhg0b4tFHH93r42tqauI3v/lNRESce+65u517TD6a6rOW+PnPfx7vv/9+RBhf7V6Jr3LdIZx55plZRGQVFRXZSy+9tMf6u+66q3iZ/O985zttXyBFv/zlL7Nt27Y1uv7jt12aNm1aG1ZHlu3fbXzefPPNrFOnTllEZKeeemq2cePG3dZv3LgxO/XUU4vjdOnSpTlUnqZ97a+VK1dmv//975vc5oknnsg6d+6cRUTWrVu3rKamppWqTc+WLVuyUaNGFfvohhtu2K92jLG20xp9Zpy1nQceeCDbtGlTk9v88Ic/LPbnsccem9XX1++2fv369cVb9BxzzDFZXV3dbuvr6+uzSy65pNjGvHnzWvtlJOVA++wvf/lLs33wyiuvZL169Sredmnx4sWtUTo5KWTZ//vXIPttyZIlcfrpp8emTZuiZ8+e8a1vfStGjhwZmzZtiocffjhmzpwZETvPE1m8eLH/6pXQgAEDYtu2bTF27NgYPnx4DBgwILp16xZ1dXXx3HPPxb333ls8fOyMM86I3/zmN9GlS5cSV92xvfjii7Fs2bLi93V1dXHzzTdHxM7TCyZNmrTb9hMmTNhrO3//938fd9xxR0REDBkyJG655ZYYOHBgLF++PO68885YsmRJcbvvfe97ObySNBxofz333HMxcuTIGD58eFxyySVx8sknF28ds2LFipgzZ07MmTOnOGv1ox/9KK699tocX1HHNnbs2OKM0znnnBPTp09vcua2c+fOxYvAfJwx1jZao8+Ms7YzYMCA+OCDD2Ls2LFxxhlnxMCBA6Nnz57xwQcfxKuvvhr/+q//GgsWLIiInX315JNPxnnnnbdHO/fee29cc801EbHz6LQpU6bESSedFGvXro3p06fHvHnzIiLiiiuuiJ/97Gdt9wI7oAPts1WrVsWxxx4bf/3Xfx2XXXZZnHLKKXHUUUdFp06d4k9/+lPMnTs3/uVf/qV4+PvNN98cd911V0leKy1U2jzecfzyl7/MDjnkkOJ/kz7+VVVVlb311lulLjN5xxxzTKN91PBr7Nix2bvvvlvqcpNw5ZVXtqhPdn01Zvv27dlXvvKVJh971VVXZdu3b2/DV9fxHGh/zZs3r0WP6969e3bvvfeW4BV2LPvSV/H/ZqcaY4y1jdboM+Os7bT074rKysrs6aefbrKtqVOnZoVCodE2Pv/5zzc7s0nzDrTPGh4Z1dRXp06dsltvvTXbsWNHCV4l+8IMcSt6++2345577oknn3wyampqonPnzjFo0KC4/PLL4+tf/3p079691CUmb/78+TF//vxYuHBhrFixIurq6mLDhg3Rs2fP6N+/f3zuc5+LK6+8MoYPH17qUpMxYcKE+MlPftLi7Zv7yPqP//iPmDlzZvz2t7+Nurq66N27dwwdOjSuvvrquPDCCw+03OQdaH998MEH8ctf/jIWLlwYixcvjtra2qirq4v6+vo47LDD4tOf/nSce+65MWnSpOKMFvtvX8/jPeaYY2LVqlVNbmOM5as1+sw4aztvvvlmPPnkk7FgwYJYtmxZvPPOO7F+/fro1q1b9OnTJz772c/GxRdfHOPGjWvR34EvvfRS/OhHP4oXXngh3nnnnejVq1ecfPLJMXHixLjiiiva4BV1fAfaZ1u3bi2Or0WLFsWaNWuirq4uNm/eHIceemgcf/zxcfbZZ8ekSZNcXLBMCMQAAAAkyVWmAQAASJJADAAAQJIEYgAAAJIkEAMAAJAkgRgAAIAkCcQAAAAkSSAGAAAgSQIxAAAASRKIAQAASJJADAAAQJIEYgAAAJIkEAMAAJAkgRgAAIAkCcQAAAAkSSAGAAAgSQIxAAAASRKIAQAASJJADAAAQJIEYgAAAJIkEAMAAJAkgRgAAIAkCcQAAAAkSSAGAAAgSQIxAAAASfr/ALerETU3ipJbAAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 640x480 with 1 Axes>"
      ]
     },
     "metadata": {
      "image/png": {
       "height": 413,
       "width": 482
      }
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "URL = \"https://github.com/qi-rub/it-ss23-homework/raw/main/material/donkey.png\"\n",
    "ORIGINAL = plt.imread(io.BytesIO(urllib.request.urlopen(URL).read()))\n",
    "\n",
    "# remove alpha channel\n",
    "if ORIGINAL.shape[2] == 4:\n",
    "    alpha = ORIGINAL[:, :, 3:]\n",
    "    ORIGINAL = ORIGINAL[:, :, :3] * alpha + (1 - alpha)\n",
    "\n",
    "# convert to black & white\n",
    "WHITE_THRESHOLD = 0.8\n",
    "ORIGINAL = np.where(ORIGINAL[:, :, :3].max(axis=2) > WHITE_THRESHOLD, 0, 1)\n",
    "\n",
    "# downscale by a factor 20\n",
    "ORIGINAL = ORIGINAL[::20, ::20]\n",
    "\n",
    "# show the figure\n",
    "plt.imshow(ORIGINAL, cmap=plt.get_cmap(\"binary\"), interpolation=\"none\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Run the following code that first compresses and then decompresses the image -- does it pass the test?**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "h, w, k, p = compress(ORIGINAL)\n",
    "assert np.all(ORIGINAL == decompress(h, w, k, p))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What compression rate does your code achieve on the donkey image?\n",
    "(For simplicity, we will ignore the number of bits required to represent $h$ and $w$.\n",
    "The original, uncompressed image contains $N = h \\times w$ many bits, while, after compressing, we need about $\\log(N) +\\log\\#B(N,k)$ bits to represent $k$ and $p$ in binary.\n",
    "\n",
    "**Run the following code to determine the compression rate that you achieved for the donkey image:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "N = h * w\n",
    "R = (np.log2(N) + np.log2(float(binomial(N, k)))) / N\n",
    "print(f\"Compression rate: {R:2.0%}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you are interested, you could compare this number with the compression rate that PNG or GIF achieve for the same picture..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2. Lempel-Ziv Compression\n",
    "\n",
    "Next, you will implement the Lempel-Ziv compression algorithm discussed in class.\n",
    "\n",
    "Just like on the last homework, we are going to compress Shakespear's Hamlet, so let us download it again."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "179096"
      ]
     },
     "execution_count": null,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hamlet = requests.get(\n",
    "    \"https://github.com/qi-rub/it-ss23-homework/raw/main/material/hamlet.txt\"\n",
    ").content.decode(\"ascii\", errors=\"ignore\")\n",
    "hamlet = hamlet\n",
    "len(hamlet)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Write a function that takes as input a string and as output returns the LZ compression as a list of pairs `(k,x)`. You can assume that the last symbol of the input is the symbol `EOF` defined below (in class we used $\\perp$).**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "EOF = \"\\0\"\n",
    "\n",
    "\n",
    "def lz_compress(s):\n",
    "    assert s.find(EOF) == len(s) - 1, \"String should contain EOF precisely at the end\"\n",
    "    # TODO: can you implement this?\n",
    "    return ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following code tests your function with the example discussed in class:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "compressed = lz_compress(\"ABBABAABAABABA\" + EOF)\n",
    "assert compressed == [\n",
    "    (0, \"A\"),\n",
    "    (0, \"B\"),\n",
    "    (2, \"A\"),\n",
    "    (3, \"A\"),\n",
    "    (4, \"B\"),\n",
    "    (1, \"B\"),\n",
    "    (1, EOF),\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Just like on the previous homework, we provide a decompressor for your convenience:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def lz_decompress(compressed):\n",
    "    phrases = [\"\"]\n",
    "    result = \"\"\n",
    "    for k, x in compressed:\n",
    "        phrase = phrases[k] + x\n",
    "        phrases.append(phrase)\n",
    "        result += phrase\n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's now compress Hamlet and estimate the compression rate:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "compressed = lz_compress(hamlet + EOF)\n",
    "assert lz_decompress(compressed) == hamlet + EOF\n",
    "\n",
    "compressed_bytes = np.ceil(\n",
    "    sum(np.ceil(np.log2(j)) + 8 for j in range(1, len(compressed) + 1)) / 8\n",
    ")\n",
    "R = compressed_bytes / len(hamlet + EOF)\n",
    "print(f\"Compression rate: {R:2.0%}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Bonus challenges for the LZ problem (completely optional):**\n",
    "\n",
    "0. Compare your results with `zlib`, a compression library that is shipped with Python (`import zlib; zlib.compress(...)`).\n",
    "1. Modify your compressor so that it emits a bitstring, not just a list of pairs $(k,x)$. We discussed in class how this can be done.\n",
    "2. Can you combine the LZ algorithm with Huffman compression to get an improved compression rate? Should you apply Huffman before or after the LZ step? It may be useful to use multiple Huffman codebooks for different kinds of data. Try to get below 50%!\n",
    "3. Can you tweak your implementation so that it efficient enough for the `enwik8` data set mentioned on the last homework?"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "python3",
   "language": "python",
   "name": "python3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}