Huffman.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Github: aahmadnejad**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary tree:\n",
    "### (based on huffman's binary tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node(object):\n",
    "        def __init__(self , value):\n",
    "            self.value = value\n",
    "            self.left = None\n",
    "            self.right = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BinaryTree(object):\n",
    "    def __init__(self , root):\n",
    "        self.root = Node(root)\n",
    "        \n",
    "    def print_tree(self):\n",
    "        return self.preorder(tree.root , \"\" , [])\n",
    "    \n",
    "    def preorder(self , start , htx ,hashed):\n",
    "        if start:\n",
    "            left = htx + '0'\n",
    "            right = htx + '1'\n",
    "            if start.left is None and start.right is None:\n",
    "                k = [start.value , htx]\n",
    "                hashed.append(k)\n",
    "            self.preorder(start.left , left , hashed)\n",
    "            self.preorder(start.right , right , hashed)\n",
    "        return hashed"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Huffman encrypting:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### input text and counting the characters:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "enter your text :aaaabababaaaaaacccccbcbabbafff\n"
     ]
    }
   ],
   "source": [
    "text = str( input('enter your text :') )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "temp_count = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "for chaar in text:\n",
    "    touple = [ chaar , text.count(chaar)]\n",
    "    if touple not in temp_count: \n",
    "        temp_count.append(touple)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### sort characters less repeat to highest repeat:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "temp_count.sort(key=lambda tup: tup[1], reverse=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "we create an empty array. this array finally became our final **huffman tree** for calculate hashed version of our input:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "trees = []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## building our tree and a Road map for it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[['f', 3], ['c', 6], ['b', 7], ['a', 14]]\n",
      "char f and c:\n",
      "[['b', 7], ['fc', 9], ['a', 14]]\n",
      "char b and fc:\n",
      "[['a', 14], ['bfc', 16]]\n",
      "char a and bfc:\n",
      "[['abfc', 30]]\n"
     ]
    }
   ],
   "source": [
    "while len(temp_count) != 1 :\n",
    "    print(temp_count)\n",
    "    \n",
    "    two_less = temp_count[0:2]\n",
    "    name = str(two_less[0][0] + two_less[1][0])\n",
    "    head = two_less[0][1] + two_less[1][1]\n",
    "    \n",
    "    \"\"\"\n",
    "    This part is the important part for ceating our tree, as you know in huffman tree creation we have 3\n",
    "    situations:\n",
    "    \n",
    "    two characters\n",
    "    one character and one tree\n",
    "    two trees\n",
    "    \n",
    "    -if they are two characters we save their trees in 'trees' Array for next use as a touple [tree , name].\n",
    "    \n",
    "    -if they are one character and one tree we search for that touple and use the tree. finaly we delete the tree\n",
    "    and save our new tree.\n",
    "    \n",
    "    -if they are two trees we search for each of them and use them. finaly we delete our trees and save our new tree.\n",
    "    \"\"\"\n",
    "    if len(two_less[0][0]) == 1:\n",
    "        if len(two_less[1][0]) ==1:\n",
    "            \n",
    "            tree = BinaryTree(str(head))\n",
    "            tree.root.left = Node(two_less[0][0])\n",
    "            tree.root.right = Node(two_less[1][0])       \n",
    "            trees.append([name , tree])\n",
    "            \n",
    "        elif len(two_less[1][0]) > 1:\n",
    "            for index, item in enumerate(trees[:]):\n",
    "                for index2, item2 in enumerate(item[:]):\n",
    "                    if item2 == two_less[1][0]:\n",
    "                        add = index\n",
    "            \n",
    "            tr = trees[add][1]\n",
    "            del trees[add]\n",
    "            tree = BinaryTree(str(head))\n",
    "            tree.root.left = Node(two_less[0][0])\n",
    "            tree.root.right = (tr.root)\n",
    "            trees.append([name , tree])\n",
    "            \n",
    "    elif len(two_less[0][0]) > 1:\n",
    "        if len(two_less[1][0]) == 1:\n",
    "            for index, item in enumerate(trees[:]):\n",
    "                for index2, item2 in enumerate(item[:]):\n",
    "                    if item2 == two_less[1][0]:\n",
    "                        add = index\n",
    "            \n",
    "            tr = trees[add][1]\n",
    "            del trees[add]\n",
    "            tree = BinaryTree(str(head))\n",
    "            tree.root.left = (tr.root)\n",
    "            tree.root.right = Node(two_less[1][0])\n",
    "            trees.append([name , tree])\n",
    "            \n",
    "        else:\n",
    "            for index, item in enumerate(trees[:]):\n",
    "                for index2, item2 in enumerate(item[:]):\n",
    "                    if item2 == two_less[1][0]:\n",
    "                        add = index\n",
    "                        \n",
    "            for index, item in enumerate(trees[:]):\n",
    "                for index2, item2 in enumerate(item[:]):\n",
    "                    if item2 == two_less[1][0]:\n",
    "                        add2 = index\n",
    "            \n",
    "            tr = trees[add][1]\n",
    "            tr2 = trees [add2][1]\n",
    "            del trees[add]\n",
    "            del trees[add2]\n",
    "            tree = BinaryTree(str(head))\n",
    "            tree.root.left = (tr.root)\n",
    "            tree.root.right = (tr2.root)\n",
    "            trees.append([name , tree])\n",
    "    \n",
    "    #######################################################################################################\n",
    "    ######### this is our road map and new array section. we have sort the array each time for find #######\n",
    "    ############################# two less repeating char's in text #######################################\n",
    "    #######################################################################################################\n",
    "    print(f'char {two_less[0][0]} and {two_less[1][0]}:')\n",
    "    val = int(two_less[0][1] + two_less[1][1])\n",
    "    del temp_count[0:2]\n",
    "    temp_count.append([name , val])\n",
    "    temp_count.sort(key=lambda tup: tup[1], reverse=False)\n",
    "print(temp_count)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## This is our final keys for each character:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['a', '0'], ['b', '10'], ['f', '110'], ['c', '111']]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "h_char = trees[0][1].print_tree()\n",
    "h_char"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "hashed = text"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### now we are ready for hashing our text"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "for ch in h_char:\n",
    "    hashed = hashed.replace(ch[0] , ch[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'0000100100100000001111111111111111011110010100110110110'"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hashed"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "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.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}