cs110_pcw_14_1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before you turn this problem in, make sure everything runs as expected. First, **restart the kernel** (in the menubar, select Kernel$\\rightarrow$Restart) and then **run all cells** (in the menubar, select Cell$\\rightarrow$Run All).\n",
    "\n",
    "Make sure you fill in any place that says `YOUR CODE HERE` or \"YOUR ANSWER HERE\", as well as your name and collaborators below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "NAME = \"Evan\"\n",
    "COLLABORATORS = \"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "66e4a5cae0e361c97d6c83e84754f7bb",
     "grade": false,
     "grade_id": "cell-aedfb9351c4dd419",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "# CS110 Pre-class Work 14.1\n",
    "\n",
    "In this Pre-class work we will apply Huffman's algorithm in file compression. \n",
    "## Question 1.\n",
    "Below is the utility function for downloading a text file from a URL. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "b4cfc6776ba647ea042e50771b3d8483",
     "grade": false,
     "grade_id": "cell-b84ee6c499c87372",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "outputs": [],
   "source": [
    "from urllib.request import urlopen\n",
    "import shutil\n",
    "import gzip\n",
    "import os\n",
    "\n",
    "\n",
    "# Download the file if need be:\n",
    "def download_file(url, filename):\n",
    "    if not os.path.exists(filename):\n",
    "        response = urlopen(url + filename)\n",
    "        shutil.copyfileobj(\n",
    "            gzip.GzipFile(fileobj=response), open(filename+'.txt', 'wb'))\n",
    "\n",
    "url = \"http://www.gutenberg.org/ebooks/\"\n",
    "filename = \"100.txt.utf-8\"\n",
    "\n",
    "download_file(url, filename) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "8a077d16d8c9d48ba47b01467d9fd9c2",
     "grade": false,
     "grade_id": "cell-c2e379e275938e68",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "Your tasks:\n",
    "\n",
    "1. Run the cell so that the file \"100.txt.utf-8\" is downloaded to your local machine. Please allow some time for the code to complete.\n",
    "2. Check that the file \"100.txt.utf-8\" has been downloaded to your computer.\n",
    "3. Open and view the file with your favorite text editor. \n",
    "4. In the cell below, write down the size of the downloaded file (for example, 1.2GB)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "f18750524ace65719b91a60e8d9a43b8",
     "grade": true,
     "grade_id": "cell-b83cd656878410be",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "5.9 MB"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "80849f8ac566ae2fe64a35cc8c8e882d",
     "grade": false,
     "grade_id": "cell-5ffca685c11b6b4d",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 2. \n",
    "Now, as a bit of an interlude, we will get familiar with the `bitarray` Python library, which is helpful for completing this pre-class work. Go to this [link](https://pypi.org/project/bitarray/) and read the examples in the first three cell of section **Using the module**. Once you complete the reading task, please complete the function `get_bit_array` in the cell below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "ec3c2a880c1c14e2d359fac0dada1c28",
     "grade": false,
     "grade_id": "cell-7ba9ec08bcd38455",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "from bitarray import bitarray\n",
    "class Node(object):\n",
    "    \"\"\"A node in a binary tree that represents a prefix code.\"\"\"\n",
    "    def __init__(self, freq, symb, parent = None, lchild = None, rchild = None):\n",
    "        \"\"\"\n",
    "        - freq: float, frequency of the character\n",
    "        - symb: string, a character in the file \n",
    "        - parent: a node, parent of the current node in the tree\n",
    "        - lchild, rchild: left child node and right child node of the current node \n",
    "        in the tree.\n",
    "        \"\"\"\n",
    "        self.freq = freq\n",
    "        self.symb = symb\n",
    "        self.parent = parent\n",
    "        self.lchild = lchild\n",
    "        self.rchild = rchild\n",
    "    \n",
    "    def __lt__(self, other):\n",
    "        \"\"\"\n",
    "        nodeA < nodeB returns True if nodeA.freq < nodeB.freq. This enables\n",
    "        us to use the module heapq on nodes. In other words, with this function,\n",
    "        we can now push/insert a node into a heap as well as extract/pop the \n",
    "        minimum node from a heap. We studied the module heapq before. You can brush\n",
    "        up your memory by visiting this link: \n",
    "        https://docs.python.org/3.0/library/heapq.html\n",
    "        \n",
    "        \"\"\"\n",
    "        return self.freq < other.freq\n",
    "    \n",
    "def get_bitarray(node):\n",
    "    \"\"\"\n",
    "    Given a node in the tree, determines the corresponding codeword for character\n",
    "    node.symb, using the rule in Cormen et al.: the binary codeword for a character \n",
    "    is the simple path from the root to that character, where 0 means “go to the \n",
    "    left child” and 1 means “go to the right child.\n",
    "    \n",
    "    Inputs:\n",
    "    - node: a node, whose codeword represented by the tree is of interest\n",
    "    \n",
    "    Outputs:\n",
    "    - a: a bit array that represents the codeword. For example, if the codeword is \n",
    "    01001, then a is bitarray('01001')\n",
    "    \n",
    "    \"\"\"\n",
    "    # YOUR CODE HERE\n",
    "    \n",
    "    a = bitarray()\n",
    "    while node.parent:\n",
    "        if node.parent.lchild == node:\n",
    "            a.append(0)\n",
    "\n",
    "        elif node.parent.rchild == node:           \n",
    "            a.append(1)\n",
    "        node=node.parent\n",
    "            \n",
    "    a = reversed(a)\n",
    "    return a\n",
    "    \n",
    "    \n",
    "    \n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "2fe3268d072490748502ac5657baf039",
     "grade": false,
     "grade_id": "cell-30c0c74327992b26",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 3. \n",
    "Complete the following function that builds a Huffman code, making use of `get_bitarray` and the module `heapq`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "ff946fc33af51c13fefcf767c4f91292",
     "grade": false,
     "grade_id": "cell-a99a125161e64aac",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "import heapq\n",
    "def encode(symb2freq):\n",
    "    \"\"\"\n",
    "    Huffman encode the given dict mapping symbols to weights. \n",
    "    \n",
    "    Inputs:\n",
    "    - symb2freq: a dictionary that maps a symbol/character to\n",
    "    the probability frequency in the text file. For example,\n",
    "    {'a': .3, 'b':.6, 'c': .1}. This example symb2freq means \n",
    "    that symbol 'a' appears with frequency 30%, symbol 'b' 60%, \n",
    "    and symbol 'c' 10%.\n",
    "    \n",
    "    Outputs:\n",
    "    - out: a dictionary that maps a symbol/charcater to a bitarray\n",
    "    that represents the codeword for that symbol. For example,\n",
    "    out = {'a': bitarray('01'), 'b': bitarray('11'), 'c': bitarray('101')}.\n",
    "    \"\"\"\n",
    "    # YOUR CODE HERE\n",
    "    heap = []\n",
    "    symb2dict = {}\n",
    "    for sym in symb2freq:\n",
    "        heapq.heappush(heap,Node(freq=symb2freq[sym],symb = sym))\n",
    "    \n",
    "    symb2bitarray = { }\n",
    "    for heaps in heap:\n",
    "        symb2bitarray[heaps.symb] = get_bitarray(heaps)\n",
    "                       \n",
    "    return  symb2bitarray                 \n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a 0.3\n",
      "b 0.6\n",
      "c 0.1\n"
     ]
    }
   ],
   "source": [
    "dictt = {'a': .3, 'b':.6, 'c': .1}\n",
    "\n",
    "for sym in dictt:\n",
    "    print(sym,dictt[sym])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "cfdc434c6f29f0186e0bcadcec736d83",
     "grade": false,
     "grade_id": "cell-fa651be15a7f3559",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "# Question 4. \n",
    "Below you are given three functions to 1) build a frequency table for a file, 2) compress a file, and 3) decompress a file. Make use of these functions to do the following:\n",
    "\n",
    "1. Create a compressed version of file `100.txt.utf-8.txt` that is named `100.txt.utf-8.txt.huff`.\n",
    "2. Decompress `100.txt.utf-8.txt.huff` to file `100.txt.utf-8.txt.huff.dehuff.txt`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "f1a7d2cdc3ec444c75a311ce72630ee3",
     "grade": false,
     "grade_id": "cell-7c911f3552280b25",
     "locked": false,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "bitarray expected for dict value",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-12-60f54d8760fa>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m     51\u001b[0m \u001b[0mcompress\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mfilename\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m'100.txt.utf-8.txt'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mencoding\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mencodng\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mcompressed_name\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;32mNone\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     52\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 53\u001b[0;31m \u001b[0mdecompress\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mfilename\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m'100.txt.utf-8.txt.huff'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdecompressed_name\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;32mNone\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     54\u001b[0m \u001b[0;31m#raise NotImplementedError()\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-12-60f54d8760fa>\u001b[0m in \u001b[0;36mdecompress\u001b[0;34m(filename, decompressed_name)\u001b[0m\n\u001b[1;32m     39\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     40\u001b[0m     \u001b[0;31m# Totally cheating here and using a builtin method:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 41\u001b[0;31m     \u001b[0moutput\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mbits\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mdecode\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mencoding\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     42\u001b[0m     \u001b[0;32mwith\u001b[0m \u001b[0mopen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mdecompressed_name\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m'wb'\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mas\u001b[0m \u001b[0mf\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     43\u001b[0m         \u001b[0mf\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mwrite\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mbytes\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0moutput\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mTypeError\u001b[0m: bitarray expected for dict value"
     ]
    }
   ],
   "source": [
    "from collections import defaultdict \n",
    "import pickle\n",
    "# build a frequency table:\n",
    "def build_freq(filename):\n",
    "    freq = defaultdict(int)\n",
    "    with open(filename, 'rb') as f:\n",
    "        for line in f:\n",
    "            for char in line:\n",
    "                freq[char] += 1\n",
    "    total = float(sum(freq.values()))\n",
    "    return {char: count / total for (char, count) in freq.items()}\n",
    "\n",
    "# Now compress the file:\n",
    "def compress(filename, encoding, compressed_name=None):\n",
    "    if compressed_name is None:\n",
    "        compressed_name = filename + \".huff\"\n",
    "    output = bitarray()\n",
    "    with open(filename, 'rb') as f:\n",
    "        for line in f:\n",
    "            for char in line:\n",
    "                output.extend(encoding[char])\n",
    "    N = len(output)\n",
    "    with open(compressed_name, 'wb') as f:\n",
    "        pickle.dump(N, f)\n",
    "        pickle.dump(encoding, f)\n",
    "        output.tofile(f)\n",
    "\n",
    "\n",
    "# Now decompress the file:\n",
    "def decompress(filename, decompressed_name=None):\n",
    "    if decompressed_name is None:\n",
    "        decompressed_name = filename + \".dehuff.txt\"\n",
    "    with open(filename, 'rb') as f:\n",
    "        N = pickle.load(f)\n",
    "        encoding = pickle.load(f)\n",
    "        bits = bitarray()\n",
    "        bits.fromfile(f)\n",
    "        bits = bits[:N]\n",
    "\n",
    "    # Totally cheating here and using a builtin method:\n",
    "    output = bits.decode(encoding)\n",
    "    with open(decompressed_name, 'wb') as f:\n",
    "        f.write(bytes(output))\n",
    "        \n",
    "# YOUR CODE HERE\n",
    "\n",
    "freq_table = build_freq(filename = '100.txt.utf-8.txt')\n",
    "\n",
    "encodng = encode(freq_table)\n",
    "\n",
    "compress(filename = '100.txt.utf-8.txt', encoding = encodng, compressed_name=None)\n",
    "\n",
    "decompress(filename = '100.txt.utf-8.txt.huff', decompressed_name=None)\n",
    "#raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "4df4ea196f6952f4b7e15d7ed2ea9430",
     "grade": false,
     "grade_id": "cell-b564d21e754a0461",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 5. \n",
    "Give your answer in the cell below:\n",
    "1. Report the size of the compressed file and the decompressed file in the cell below.\n",
    "2. How does the size of the decompressed file compare to the size of the original file (`100.txt.utf-8.txt`)?\n",
    "3. Visually skim the decompressed file and the original file. Do they appear identical?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "4c171a626010799721ff7c9e3ac9a22a",
     "grade": true,
     "grade_id": "cell-b5988d6026475a88",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "YOUR ANSWER HERE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "499835f219f42c8fb92f0ac6136707a4",
     "grade": false,
     "grade_id": "cell-b9ea500bebcac4dd",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Question 6.\n",
    "Compute and print out:\n",
    "1. The percentage of 1’s in the compressed version\n",
    "2. The percentage of 1’s in the uncompressed version"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "e1287afdf6be4303ec9293e1894b9643",
     "grade": true,
     "grade_id": "cell-a1f9f58458cf80d5",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "# YOUR CODE HERE\n",
    "raise NotImplementedError()"
   ]
  }
 ],
 "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}