CompressionAlgorithm.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "orInput = '''Chapter 10\n",
    "\n",
    "      The day passed much as the day before had done. Mrs. Hurst and\n",
    "      Miss Bingley had spent some hours of the morning with the\n",
    "      invalid, who continued, though slowly, to mend; and in the\n",
    "      evening Elizabeth joined their party in the drawing-room. The\n",
    "      loo-table, however, did not appear. Mr. Darcy was writing, and\n",
    "      Miss Bingley, seated near him, was watching the progress of his\n",
    "      letter and repeatedly calling off his attention by messages to\n",
    "      his sister. Mr. Hurst and Mr. Bingley were at piquet, and Mrs.\n",
    "      Hurst was observing their game.\n",
    "\n",
    "      Elizabeth took up some needlework, and was sufficiently amused in\n",
    "      attending to what passed between Darcy and his companion. The\n",
    "      perpetual commendations of the lady, either on his handwriting,\n",
    "      or on the evenness of his lines, or on the length of his letter,\n",
    "      with the perfect unconcern with which her praises were received,\n",
    "      formed a curious dialogue, and was exactly in union with her\n",
    "      opinion of each.\n",
    "\n",
    "      “How delighted Miss Darcy will be to receive such a letter!”\n",
    "\n",
    "      He made no answer.\n",
    "\n",
    "      “You write uncommonly fast.”\n",
    "\n",
    "      “You are mistaken. I write rather slowly.”\n",
    "\n",
    "      “How many letters you must have occasion to write in the course\n",
    "      of a year! Letters of business, too! How odious I should think\n",
    "      them!”\n",
    "\n",
    "      “It is fortunate, then, that they fall to my lot instead of\n",
    "      yours.”\n",
    "\n",
    "      “Pray tell your sister that I long to see her.”\n",
    "\n",
    "      “I have already told her so once, by your desire.”\n",
    "\n",
    "      “I am afraid you do not like your pen. Let me mend it for you. I\n",
    "      mend pens remarkably well.”\n",
    "\n",
    "      “Thank you—but I always mend my own.”\n",
    "\n",
    "      “How can you contrive to write so even?”\n",
    "\n",
    "      He was silent.\n",
    "\n",
    "      “Tell your sister I am delighted to hear of her improvement on\n",
    "      the harp; and pray let her know that I am quite in raptures with\n",
    "      her beautiful little design for a table, and I think it\n",
    "      infinitely superior to Miss Grantley’s.”\n",
    "\n",
    "      “Will you give me leave to defer your raptures till I write\n",
    "      again? At present I have not room to do them justice.”\n",
    "\n",
    "      “Oh! it is of no consequence. I shall see her in January. But do\n",
    "      you always write such charming long letters to her, Mr. Darcy?”\n",
    "\n",
    "      “They are generally long; but whether always charming it is not\n",
    "      for me to determine.”\n",
    "\n",
    "      “It is a rule with me, that a person who can write a long letter\n",
    "      with ease, cannot write ill.”\n",
    "\n",
    "      “That will not do for a compliment to Darcy, Caroline,” cried her\n",
    "      brother, “because he does _not_ write with ease. He studies too\n",
    "      much for words of four syllables. Do not you, Darcy?”\n",
    "\n",
    "      “My style of writing is very different from yours.”\n",
    "\n",
    "      “Oh!” cried Miss Bingley, “Charles writes in the most careless\n",
    "      way imaginable. He leaves out half his words, and blots the\n",
    "      rest.”\n",
    "\n",
    "      “My ideas flow so rapidly that I have not time to express them—by\n",
    "      which means my letters sometimes convey no ideas at all to my\n",
    "      correspondents.”\n",
    "\n",
    "      “Your humility, Mr. Bingley,” said Elizabeth, “must disarm\n",
    "      reproof.”\n",
    "\n",
    "      “Nothing is more deceitful,” said Darcy, “than the appearance of\n",
    "      humility. It is often only carelessness of opinion, and sometimes\n",
    "      an indirect boast.”\n",
    "\n",
    "      “And which of the two do you call _my_ little recent piece of\n",
    "      modesty?”\n",
    "\n",
    "      “The indirect boast; for you are really proud of your defects in\n",
    "      writing, because you consider them as proceeding from a rapidity\n",
    "      of thought and carelessness of execution, which, if not\n",
    "      estimable, you think at least highly interesting. The power of\n",
    "      doing anything with quickness is always prized much by the\n",
    "      possessor, and often without any attention to the imperfection of\n",
    "      the performance. When you told Mrs. Bennet this morning that if\n",
    "      you ever resolved upon quitting Netherfield you should be gone in\n",
    "      five minutes, you meant it to be a sort of panegyric, of\n",
    "      compliment to yourself—and yet what is there so very laudable in\n",
    "      a precipitance which must leave very necessary business undone,\n",
    "      and can be of no real advantage to yourself or anyone else?”\n",
    "\n",
    "      “Nay,” cried Bingley, “this is too much, to remember at night all\n",
    "      the foolish things that were said in the morning. And yet, upon\n",
    "      my honour, I believe what I said of myself to be true, and I\n",
    "      believe it at this moment. At least, therefore, I did not assume\n",
    "      the character of needless precipitance merely to show off before\n",
    "      the ladies.”\n",
    "\n",
    "      “I dare say you believed it; but I am by no means convinced that\n",
    "      you would be gone with such celerity. Your conduct would be quite\n",
    "      as dependent on chance as that of any man I know; and if, as you\n",
    "      were mounting your horse, a friend were to say, ‘Bingley, you had\n",
    "      better stay till next week,’ you would probably do it, you would\n",
    "      probably not go—and at another word, might stay a month.”\n",
    "\n",
    "      “You have only proved by this,” cried Elizabeth, “that Mr.\n",
    "      Bingley did not do justice to his own disposition. You have shown\n",
    "      him off now much more than he did himself.”\n",
    "\n",
    "      “I am exceedingly gratified,” said Bingley, “by your converting\n",
    "      what my friend says into a compliment on the sweetness of my\n",
    "      temper. But I am afraid you are giving it a turn which that\n",
    "      gentleman did by no means intend; for he would certainly think\n",
    "      better of me, if under such a circumstance I were to give a flat\n",
    "      denial, and ride off as fast as I could.”\n",
    "\n",
    "      “Would Mr. Darcy then consider the rashness of your original\n",
    "      intentions as atoned for by your obstinacy in adhering to it?”\n",
    "\n",
    "      “Upon my word, I cannot exactly explain the matter; Darcy must\n",
    "      speak for himself.”\n",
    "\n",
    "      “You expect me to account for opinions which you choose to call\n",
    "      mine, but which I have never acknowledged. Allowing the case,\n",
    "      however, to stand according to your representation, you must\n",
    "      remember, Miss Bennet, that the friend who is supposed to desire\n",
    "      his return to the house, and the delay of his plan, has merely\n",
    "      desired it, asked it without offering one argument in favour of\n",
    "      its propriety.”\n",
    "\n",
    "      “To yield readily—easily—to the _persuasion_ of a friend is no\n",
    "      merit with you.”\n",
    "\n",
    "      “To yield without conviction is no compliment to the\n",
    "      understanding of either.”\n",
    "\n",
    "      “You appear to me, Mr. Darcy, to allow nothing for the influence\n",
    "      of friendship and affection. A regard for the requester would\n",
    "      often make one readily yield to a request, without waiting for\n",
    "      arguments to reason one into it. I am not particularly speaking\n",
    "      of such a case as you have supposed about Mr. Bingley. We may as\n",
    "      well wait, perhaps, till the circumstance occurs before we\n",
    "      discuss the discretion of his behaviour thereupon. But in general\n",
    "      and ordinary cases between friend and friend, where one of them\n",
    "      is desired by the other to change a resolution of no very great\n",
    "      moment, should you think ill of that person for complying with\n",
    "      the desire, without waiting to be argued into it?”\n",
    "\n",
    "      “Will it not be advisable, before we proceed on this subject, to\n",
    "      arrange with rather more precision the degree of importance which\n",
    "      is to appertain to this request, as well as the degree of\n",
    "      intimacy subsisting between the parties?”\n",
    "\n",
    "      “By all means,” cried Bingley; “let us hear all the particulars,\n",
    "      not forgetting their comparative height and size; for that will\n",
    "      have more weight in the argument, Miss Bennet, than you may be\n",
    "      aware of. I assure you, that if Darcy were not such a great tall\n",
    "      fellow, in comparison with myself, I should not pay him half so\n",
    "      much deference. I declare I do not know a more awful object than\n",
    "      Darcy, on particular occasions, and in particular places; at his\n",
    "      own house especially, and of a Sunday evening, when he has\n",
    "      nothing to do.”\n",
    "\n",
    "      Mr. Darcy smiled; but Elizabeth thought she could perceive that\n",
    "      he was rather offended, and therefore checked her laugh. Miss\n",
    "      Bingley warmly resented the indignity he had received, in an\n",
    "      expostulation with her brother for talking such nonsense.\n",
    "\n",
    "      “I see your design, Bingley,” said his friend. “You dislike an\n",
    "      argument, and want to silence this.”\n",
    "\n",
    "      “Perhaps I do. Arguments are too much like disputes. If you and\n",
    "      Miss Bennet will defer yours till I am out of the room, I shall\n",
    "      be very thankful; and then you may say whatever you like of me.”\n",
    "\n",
    "      “What you ask,” said Elizabeth, “is no sacrifice on my side; and\n",
    "      Mr. Darcy had much better finish his letter.”\n",
    "\n",
    "      Mr. Darcy took her advice, and did finish his letter.\n",
    "\n",
    "      When that business was over, he applied to Miss Bingley and\n",
    "      Elizabeth for an indulgence of some music. Miss Bingley moved\n",
    "      with some alacrity to the pianoforte; and, after a polite request\n",
    "      that Elizabeth would lead the way which the other as politely and\n",
    "      more earnestly negatived, she seated herself.\n",
    "\n",
    "      Mrs. Hurst sang with her sister, and while they were thus\n",
    "      employed, Elizabeth could not help observing, as she turned over\n",
    "      some music-books that lay on the instrument, how frequently Mr.\n",
    "      Darcy’s eyes were fixed on her. She hardly knew how to suppose\n",
    "      that she could be an object of admiration to so great a man; and\n",
    "      yet that he should look at her because he disliked her, was still\n",
    "      more strange. She could only imagine, however, at last that she\n",
    "      drew his notice because there was something more wrong and\n",
    "      reprehensible, according to his ideas of right, than in any other\n",
    "      person present. The supposition did not pain her. She liked him\n",
    "      too little to care for his approbation.\n",
    "\n",
    "      After playing some Italian songs, Miss Bingley varied the charm\n",
    "      by a lively Scotch air; and soon afterwards Mr. Darcy, drawing\n",
    "      near Elizabeth, said to her:\n",
    "\n",
    "      “Do not you feel a great inclination, Miss Bennet, to seize such\n",
    "      an opportunity of dancing a reel?”\n",
    "\n",
    "      She smiled, but made no answer. He repeated the question, with\n",
    "      some surprise at her silence.\n",
    "\n",
    "      “Oh!” said she, “I heard you before, but I could not immediately\n",
    "      determine what to say in reply. You wanted me, I know, to say\n",
    "      ‘Yes,’ that you might have the pleasure of despising my taste;\n",
    "      but I always delight in overthrowing those kind of schemes, and\n",
    "      cheating a person of their premeditated contempt. I have,\n",
    "      therefore, made up my mind to tell you, that I do not want to\n",
    "      dance a reel at all—and now despise me if you dare.”\n",
    "\n",
    "      “Indeed I do not dare.”\n",
    "\n",
    "      Elizabeth, having rather expected to affront him, was amazed at\n",
    "      his gallantry; but there was a mixture of sweetness and archness\n",
    "      in her manner which made it difficult for her to affront anybody;\n",
    "      and Darcy had never been so bewitched by any woman as he was by\n",
    "      her. He really believed, that were it not for the inferiority of\n",
    "      her connections, he should be in some danger.\n",
    "\n",
    "      Miss Bingley saw, or suspected enough to be jealous; and her\n",
    "      great anxiety for the recovery of her dear friend Jane received\n",
    "      some assistance from her desire of getting rid of Elizabeth.\n",
    "\n",
    "      She often tried to provoke Darcy into disliking her guest, by\n",
    "      talking of their supposed marriage, and planning his happiness in\n",
    "      such an alliance.\n",
    "\n",
    "      “I hope,” said she, as they were walking together in the\n",
    "      shrubbery the next day, “you will give your mother-in-law a few\n",
    "      hints, when this desirable event takes place, as to the advantage\n",
    "      of holding her tongue; and if you can compass it, do cure the\n",
    "      younger girls of running after officers. And, if I may mention so\n",
    "      delicate a subject, endeavour to check that little something,\n",
    "      bordering on conceit and impertinence, which your lady\n",
    "      possesses.”\n",
    "\n",
    "      “Have you anything else to propose for my domestic felicity?”\n",
    "\n",
    "      “Oh! yes. Do let the portraits of your uncle and aunt Phillips be\n",
    "      placed in the gallery at Pemberley. Put them next to your\n",
    "      great-uncle the judge. They are in the same profession, you know,\n",
    "      only in different lines. As for your Elizabeth’s picture, you\n",
    "      must not have it taken, for what painter could do justice to\n",
    "      those beautiful eyes?”\n",
    "\n",
    "      “It would not be easy, indeed, to catch their expression, but\n",
    "      their colour and shape, and the eyelashes, so remarkably fine,\n",
    "      might be copied.”\n",
    "\n",
    "      At that moment they were met from another walk by Mrs. Hurst and\n",
    "      Elizabeth herself.\n",
    "\n",
    "      “I did not know that you intended to walk,” said Miss Bingley, in\n",
    "      some confusion, lest they had been overheard.\n",
    "\n",
    "      “You used us abominably ill,” answered Mrs. Hurst, “running away\n",
    "      without telling us that you were coming out.”\n",
    "\n",
    "      Then taking the disengaged arm of Mr. Darcy, she left Elizabeth\n",
    "      to walk by herself. The path just admitted three. Mr. Darcy felt\n",
    "      their rudeness, and immediately said:\n",
    "\n",
    "      “This walk is not wide enough for our party. We had better go\n",
    "      into the avenue.”\n",
    "\n",
    "      But Elizabeth, who had not the least inclination to remain with\n",
    "      them, laughingly answered:\n",
    "\n",
    "      “No, no; stay where you are. You are charmingly grouped, and\n",
    "      appear to uncommon advantage. The picturesque would be spoilt by\n",
    "      admitting a fourth. Good-bye.”\n",
    "\n",
    "      She then ran gaily off, rejoicing as she rambled about, in the\n",
    "      hope of being at home again in a day or two. Jane was already so\n",
    "      much recovered as to intend leaving her room for a couple of\n",
    "      hours that evening.'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "globalAlphabet = sorted([x for x in set(orInput)])\n",
    "alphabet = [x for x in globalAlphabet]\n",
    "inputString = [x for x in orInput]\n",
    "lenInputString = len(inputString)\n",
    "\n",
    "#Suggested Transformation\n",
    "rotationMatrix = []\n",
    "#rotate right or left\n",
    "#rotate left\n",
    "for i in range(0, len(inputString)):\n",
    "    newString = inputString[i:] + inputString[:i]\n",
    "    rotationMatrix.append(newString)\n",
    "\n",
    "rotationMatrix = sorted(rotationMatrix)\n",
    "index = rotationMatrix.index(inputString)\n",
    "lString = []\n",
    "for r in rotationMatrix:\n",
    "    lString.append(r[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "#move to front encoding\n",
    "\n",
    "numString = []\n",
    "for x in lString:\n",
    "    i = alphabet.index(x)\n",
    "    numString.append(i)\n",
    "    alphabet = [alphabet[i]] + alphabet[:i] + alphabet[i+1:]\n",
    "\n",
    "#create dictionary for numString\n",
    "numDict = dict()\n",
    "for x in numString:\n",
    "    if x in numDict:\n",
    "        numDict[x] += 1\n",
    "    else:\n",
    "        numDict[x] = 1\n",
    "\n",
    "#huffman coding\n",
    "\n",
    "import heapq\n",
    "minHeap = []\n",
    "\n",
    "#create a tree\n",
    "class node:\n",
    "    def __init__(self, val, weight):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.val = val\n",
    "        self.weight = weight\n",
    "        \n",
    "    def __lt__(self, other):\n",
    "        return(self)\n",
    "        \n",
    "    def __rt__(self, other):\n",
    "        return(self)\n",
    "        \n",
    "for x in numDict:\n",
    "    currentNode = node(x, numDict[x])\n",
    "    heapq.heappush(minHeap, (currentNode.weight, currentNode))\n",
    "    \n",
    "        \n",
    "while(len(minHeap)>1):\n",
    "    node1 = heapq.heappop(minHeap)[1]\n",
    "    node2 = heapq.heappop(minHeap)[1]\n",
    "    parent = node(None, node1.weight+node2.weight)\n",
    "    parent.left = node1\n",
    "    parent.right = node2\n",
    "    heapq.heappush(minHeap, (parent.weight, parent))\n",
    "    \n",
    "root = minHeap[-1][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "codeDict = dict()\n",
    "\n",
    "def makeCode(soFar, node):\n",
    "    if (node.left==None and node.right==None):\n",
    "        codeDict[node.val] = soFar\n",
    "    else:\n",
    "        if node.left:\n",
    "            makeCode(soFar+\"1\", node.left)\n",
    "        if node.right:\n",
    "            makeCode(soFar+\"0\", node.right)\n",
    "            \n",
    "makeCode(\"\", root)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Size coded string:  42723\n",
      "bits / character:  3.090271247739602\n"
     ]
    }
   ],
   "source": [
    "codedString = []\n",
    "for x in numString:\n",
    "    codedString.append(codeDict[x])\n",
    "\n",
    "#Size coded string\n",
    "size = 0\n",
    "for x in codedString:\n",
    "    size += len(x)\n",
    "    \n",
    "print(\"Size coded string: \", size)\n",
    "print(\"bits / character: \", size/lenInputString)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Successfully uncompressed.\n"
     ]
    }
   ],
   "source": [
    "#decode the coding\n",
    "\n",
    "#Step 1\n",
    "#Decode huffman coding\n",
    "decodeNumString = []\n",
    "\n",
    "decodeDict = {codeDict[x]:x for x in codeDict}\n",
    "\n",
    "for x in codedString:\n",
    "    decodeNumString.append(decodeDict[x])\n",
    "\n",
    "#Step 2\n",
    "#Decode move to front coding\n",
    "alphabet = [x for x in globalAlphabet]\n",
    "\n",
    "decodeLString = []\n",
    "\n",
    "for x in decodeNumString:\n",
    "    decodeLString.append(alphabet[x])\n",
    "    alphabet = [alphabet[x]] + alphabet[:x] + alphabet[x+1:]\n",
    "\n",
    "#Step 3\n",
    "#Decode\n",
    "F = sorted(decodeLString)\n",
    "\n",
    "L = decodeLString\n",
    "P = dict()\n",
    "C = dict()\n",
    "\n",
    "#First pass\n",
    "\n",
    "for i in range(len(L)):\n",
    "    if L[i] not in C:\n",
    "        C[L[i]] = 0\n",
    "    P[i] = C[L[i]]\n",
    "    C[L[i]] = C[L[i]] + 1\n",
    "\n",
    "s = 0;\n",
    "for ch in sorted(C):\n",
    "    s = s + C[ch]\n",
    "    C[ch] = s - C[ch]\n",
    "\n",
    "#second pass\n",
    "\n",
    "S = [0]* len(L)\n",
    "i = index\n",
    "for j in range(len(L)-1, -1, -1):\n",
    "    S[j] = L[i];\n",
    "    i = P[i] + C[L[i]]\n",
    "    \n",
    "if S==inputString:\n",
    "    print(\"Successfully uncompressed.\")\n",
    "else:\n",
    "    print(\"String mismatch\")"
   ]
  },
  {
   "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}