In-memory-url-compression.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "83497fcd",
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "import random\n",
    "\n",
    "import pandas as pd\n",
    "\n",
    "from tqdm.notebook import tqdm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "c7a2436b",
   "metadata": {},
   "outputs": [],
   "source": [
    "# node structure\n",
    "class node :\n",
    "    # common prefix\n",
    "    #  different url\n",
    "    # address of parent\n",
    "    # address of left child\n",
    "    # address of right child\n",
    "    def __init__(self, i) :\n",
    "        self.cp = 0\n",
    "        self.id = i\n",
    "        self.parent = None\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.height = 1\n",
    "        self.diffUrl = None\n",
    "\n",
    "class avl:\n",
    "    # Calculate height of the avl tree\n",
    "    def  height(self, N) :\n",
    "        if (N == None) :\n",
    "            return  0\n",
    "        return  N.height\n",
    "    # calculate balance of the node\n",
    "    def  getBalance(self, N) :\n",
    "        if (N == None) :\n",
    "            return  0\n",
    "        return  self.height(N.left) - self.height(N.right)\n",
    "    # function to find common prefix length between two strings\n",
    "    def  getprefix(self, A,  B) :\n",
    "        la = len(A)\n",
    "        lb = len(B)\n",
    "        c = min(la,lb)\n",
    "        i = 0\n",
    "        while (i < c) :\n",
    "            if (A[i] != B[i]) :\n",
    "                return  i\n",
    "            i += 1\n",
    "        return  c\n",
    "    #  INSERTION\n",
    "    def  insert(self, root,  a,  URL) :\n",
    "        # WHEN ROOT==NULL\n",
    "        if (root == None) :\n",
    "            a.diffUrl = URL[a.cp:]\n",
    "            return  a\n",
    "        # CALLING RETRIEVE()\n",
    "        rURL = self.retrieve(root)\n",
    "        # WHEN NODE IS ALREADY PRESENT\n",
    "        if (rURL == URL) :\n",
    "            return  root\n",
    "        a.cp = self.getprefix(rURL, URL)\n",
    "        a.parent = root\n",
    "        if (rURL < URL) : #  GO right\n",
    "            root.right = self.insert(root.right, a, URL)\n",
    "        else :#  GO left\n",
    "            root.left = self.insert(root.left, a, URL)\n",
    "        root.height = 1 + max(self.height(root.left),self.height(root.right))\n",
    "        balance = self.getBalance(root)\n",
    "        rlurl = self.retrieve(root.left)\n",
    "        rrurl = self.retrieve(root.right)\n",
    "        #  Left Left Case\n",
    "        # if (balance > 1 && key < root.left.key)\n",
    "        if (balance > 1 and (URL < rlurl)) :\n",
    "            return  self.rightRotate(root)\n",
    "        #  Right Right Case\n",
    "        # if (balance < -1 && key > root.right.key)\n",
    "        if (balance < -1 and (URL > rrurl)) :\n",
    "            return  self.leftRotate(root)\n",
    "        #  Left Right Case\n",
    "        #  if (balance > 1 && key > root.left.key)\n",
    "        if (balance > 1 and (URL > rlurl)) :\n",
    "            root.left = self.leftRotate(root.left)\n",
    "            return  self.rightRotate(root)\n",
    "        #  Right Left Case\n",
    "        # if (balance < -1 && key < root.right.key)\n",
    "        if (balance < -1 and (URL < rrurl)) :\n",
    "            root.right = self.rightRotate(root.right)\n",
    "            return  self.leftRotate(root)\n",
    "        return  root\n",
    "    # LEFT_ROTATION\n",
    "    def  leftRotate(self, x) :\n",
    "        xurl = self.retrieve(x)\n",
    "        y = x.right\n",
    "        yurl = self.retrieve(y)\n",
    "        y.parent = x.parent\n",
    "        x.parent = y\n",
    "        x.right = y.left\n",
    "        y.left = x\n",
    "        # CALCULATE HEIGHT\n",
    "        x.height = max(self.height(x.left),self.height(x.right)) + 1\n",
    "        y.height = max(self.height(y.left),self.height(y.right)) + 1\n",
    "        # CALL RECALC() FOR Y AND X\n",
    "        y = self.recalc(y, yurl)\n",
    "        x = self.recalc(x, xurl)\n",
    "        return  y\n",
    "    # RIGHT_ROTATION\n",
    "    def  rightRotate(self, x) :\n",
    "        xurl = self.retrieve(x)\n",
    "        y = x.left\n",
    "        yurl = self.retrieve(y)\n",
    "        y.parent = x.parent\n",
    "        x.parent = y\n",
    "        x.left = y.right\n",
    "        y.right = x\n",
    "        # CALCULATE HEIGHT\n",
    "        x.height = max(self.height(x.left),self.height(x.right)) + 1\n",
    "        y.height = max(self.height(y.left),self.height(y.right)) + 1\n",
    "        # CALL RECALC() FOR Y AND X\n",
    "        y = self.recalc(y, yurl)\n",
    "        x = self.recalc(x, xurl)\n",
    "        return  y\n",
    "    # RECALCULATE COMMON PREFIX AND DIFFERENT URL\n",
    "    def  recalc(self, a,  url) :\n",
    "        purl = self.retrieve(a.parent)\n",
    "        a.cp = self.getprefix(purl, url)\n",
    "        a.diffUrl = url[a.cp:]\n",
    "        return  a\n",
    "    # SEARCHING\n",
    "    def  search(self, root,  URL) :\n",
    "        if (root == None) :\n",
    "            return  None\n",
    "        temp = self.retrieve(root)\n",
    "        if (temp == URL) :\n",
    "            return  root\n",
    "        if (temp < URL) : # go right\n",
    "            return  self.search(root.right, URL)\n",
    "        # go left\n",
    "        return  self.search(root.left, URL)\n",
    "    # RETREIVING\n",
    "    def  retrieve(self, a) :\n",
    "        if (a == None) :\n",
    "            return  \"\"\n",
    "        if (a.cp == 0) :\n",
    "            return  a.diffUrl\n",
    "        t = (self.retrieve(a.parent))[0:a.cp] + a.diffUrl\n",
    "        return  t\n",
    "\n",
    "    \n",
    "    def preOrder(self, root):\n",
    " \n",
    "        if not root:\n",
    "            return\n",
    " \n",
    "        print(\"{0} \".format(root.diffUrl), end=\"\")\n",
    "        self.preOrder(root.left)\n",
    "        self.preOrder(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "4205f6db",
   "metadata": {},
   "outputs": [],
   "source": [
    "#dataset containing urls from bbc.com website\n",
    "df = pd.read_csv('../../osama/Downloads/bbc_sitemaps.csv')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "2ed97f7f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0          https://www.bbc.com/arabic/middleeast/2009/06/...\n",
       "1          https://www.bbc.com/arabic/middleeast/2009/06/...\n",
       "2          https://www.bbc.com/arabic/business/2009/06/09...\n",
       "3          https://www.bbc.com/arabic/multimedia/2009/06/...\n",
       "4          https://www.bbc.com/arabic/business/2009/06/09...\n",
       "                                 ...                        \n",
       "3995807    https://www.bbc.com/persian/tv-and-radio-52114329\n",
       "3995808           https://www.bbc.com/burmese/burma-52116369\n",
       "3995809           https://www.bbc.com/persian/sport-52099005\n",
       "3995810    https://www.bbc.com/zhongwen/trad/multimedia/2...\n",
       "3995811        https://www.bbc.com/vietnamese/world-52102027\n",
       "Name: loc, Length: 3995812, dtype: object"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#check number of urls (~4 million urls)\n",
    "df['loc']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "a1b0d231",
   "metadata": {},
   "outputs": [],
   "source": [
    "urls = list(df['loc'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cc3f9341",
   "metadata": {},
   "outputs": [],
   "source": [
    "avl_tree = avl()\n",
    "root = None\n",
    "indexes = []\n",
    "id = 0\n",
    "\n",
    "for u in tqdm(urls):\n",
    "    a = node(id)\n",
    "    indexes.append(a)\n",
    "    id = id + 1\n",
    "    root = avl_tree.insert(root, a, u)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "3a25a66a",
   "metadata": {},
   "outputs": [],
   "source": [
    "total_size_uncompressed = 0\n",
    "for s in urls:\n",
    "    total_size_uncompressed = total_size_uncompressed + sys.getsizeof(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "8fe6d94e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Total size before compression: 405.66 MB\n"
     ]
    }
   ],
   "source": [
    "uncompressed_size_in_mb = total_size_uncompressed / 1024**2\n",
    "print(f'Total size before compression: {round(uncompressed_size_in_mb, 2)} MB')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "c51f9993",
   "metadata": {},
   "outputs": [],
   "source": [
    "total_size_avl_compressed = 0\n",
    "for s in indexes:\n",
    "    total_size_avl_compressed = total_size_avl_compressed + sys.getsizeof(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "15377946",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Total size after compression: 182.91 MB\n"
     ]
    }
   ],
   "source": [
    "total_size_compressed = total_size_avl_compressed / 1024**2\n",
    "print(f'Total size after compression: {round(total_size_compressed, 2)} MB')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "58b76df2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "54.91 % sapce saving\n"
     ]
    }
   ],
   "source": [
    "sapce_saving = (1 - total_size_avl_compressed/total_size_uncompressed) * 100\n",
    "print(str(round(sapce_saving, 2)) + \" % sapce saving\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "15739704",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "'https://www.bbc.com/news/world-africa-12421747' STORED_AS '1747'\n",
      "'https://www.bbc.com/turkce/haberler/2012/05/120508_end_austerity' STORED_AS 'end_austerity'\n",
      "'https://www.bbc.com/ukrainian/news_in_brief/2014/11/141111_vs_poroshenko_biden' STORED_AS '1_vs_poroshenko_biden'\n"
     ]
    }
   ],
   "source": [
    "#See how a random url is stored\n",
    "random_urls = random.sample(urls, 3)\n",
    "for url in random_urls:\n",
    "    node = avl_tree.search(root, url)\n",
    "    print(f'\\'{url}\\' STORED_AS \\'{node.diffUrl}\\'')"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}