chapter_4.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 348,
   "id": "43f4aab3",
   "metadata": {},
   "outputs": [],
   "source": [
    "import nltk\n",
    "import re\n",
    "from collections import Counter, defaultdict\n",
    "from copy import deepcopy\n",
    "import numpy as np\n",
    "from nltk.book import *\n",
    "import string\n",
    "import random\n",
    "from operator import itemgetter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "87ad7589",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['hi', 'word', 'hello', 'language', 'a_vey_long_word']"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list1 = [\"hello\", \"word\", \"language\", \"a_vey_long_word\", \"hi\"]\n",
    "sorted(list1, key = lambda x: len(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fa347d7b",
   "metadata": {},
   "source": [
    "__◑ Create a list of words and store it in a variable sent1. Now assign sent2 = sent1. Modify one of the items in sent1 and verify that sent2 has changed.__\n",
    "\n",
    "__Now try the same exercise but instead assign sent2 = sent1[:]. Modify sent1 again and see what happens to sent2. Explain.\n",
    "Now define text1 to be a list of lists of strings (e.g. to represent a text consisting of multiple sentences. Now assign text2 = text1[:], assign a new value to one of the words, e.g. text1[1][1] = 'Monty'. Check what this did to text2. Explain.\n",
    "Load Python's deepcopy() function (i.e. from copy import deepcopy), consult its documentation, and test that it makes a fresh copy of any object.__\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "464d5470",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sentence 2 now is  ['that', 'is', 'the', 'first', 'sentence']\n",
      "Sentence 1 now is  ['that', 'is', 'the', 'first', 'sentence']\n",
      "Are sents equal?  True\n"
     ]
    }
   ],
   "source": [
    "sent1 = [\"this\", \"is\", \"the\", \"first\", \"sentence\"]\n",
    "sent2 = sent1\n",
    "sent1[0] = \"that\"\n",
    "print(\"Sentence 2 now is \", sent2)\n",
    "print(\"Sentence 1 now is \", sent1)\n",
    "print(\"Are sents equal? \", sent1==sent2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "35a4d8f7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sentence 3 now is  ['that', 'is', 'the', 'first', 'sentence']\n",
      "Sentence 1 now is  ['that', 'was', 'the', 'first', 'sentence']\n",
      "Are sents equal?  False\n"
     ]
    }
   ],
   "source": [
    "sent3 = sent1[:]\n",
    "sent1[1] = \"was\"\n",
    "print(\"Sentence 3 now is \", sent3)\n",
    "print(\"Sentence 1 now is \", sent1)\n",
    "print(\"Are sents equal? \", sent1==sent3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "4ba3686a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sentence 4 now is  ['that', 'was', 'the', 'first', 'sentence']\n",
      "Sentence 1 now is  ['sent1', 'was', 'the', 'first', 'sentence']\n",
      "Are sents equal?  False\n"
     ]
    }
   ],
   "source": [
    "sent4 = deepcopy(sent1)\n",
    "sent1[0] = \"sent1\"\n",
    "print(\"Sentence 4 now is \", sent4)\n",
    "print(\"Sentence 1 now is \", sent1)\n",
    "print(\"Are sents equal? \", sent1==sent4)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ed56a3e2",
   "metadata": {},
   "source": [
    "__◑ Initialize an n-by-m list of lists of empty strings using list multiplication, e.g. word_table = [[''] * n] * m. What happens when you set one of its values, e.g. word_table[1][2] = \"hello\"? Explain why this happens. Now write an expression using range() to construct a list of lists, and show that it does not have this problem.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "19dbcd85",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[['', '', 'hello'], ['', '', 'hello'], ['', '', 'hello']]\n"
     ]
    }
   ],
   "source": [
    "word_table = [[''] * 3] * 3\n",
    "word_table[0][2] = \"hello\"\n",
    "print(word_table)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "66e04575",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[['', '', 'hello'], ['', '', ''], ['', '', '']]\n"
     ]
    }
   ],
   "source": [
    "word_table_2 = [[\"\" for _ in range(3)] for _ in range(3)]\n",
    "word_table_2[0][2] = \"hello\"\n",
    "print(word_table_2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d7a0ab6b",
   "metadata": {},
   "source": [
    "__◑ Write code to initialize a two-dimensional array of sets called word_vowels and process a list of words, adding each word to word_vowels[l][v] where l is the length of the word and v is the number of vowels it contains.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "bb1876da",
   "metadata": {},
   "outputs": [],
   "source": [
    "word_vowels = [[]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "80f5c9e6",
   "metadata": {},
   "outputs": [],
   "source": [
    "list_of_words = [\"here\", \"is\", \"a\", \"list\", \"of\", \"words\", \"of\", 'different', \"lengths\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "cc56a291",
   "metadata": {},
   "outputs": [],
   "source": [
    "for word in list_of_words:\n",
    "    if len(word) > len(word_vowels):\n",
    "        for idx in range(len(word_vowels), len(word)):\n",
    "            word_vowels.append(list())\n",
    "    num_vowels = len(re.findall(r'[aeiou]', word.lower()))\n",
    "    if num_vowels > len(word_vowels[len(word)]):\n",
    "        for idx in range(len(word_vowels[len(word)]), num_vowels):\n",
    "            word_vowels[len(word)].append(set())\n",
    "    word_vowels[len(word)][num_vowels].add(word)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "74e98c32",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[],\n",
       " [set(), {'a'}],\n",
       " [set(), {'is', 'of'}],\n",
       " [],\n",
       " [set(), {'list'}, {'here'}],\n",
       " [set(), {'words'}],\n",
       " [],\n",
       " [set(), {'lengths'}],\n",
       " [],\n",
       " [set(), set(), set(), {'different'}]]"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "word_vowels"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "801695ff",
   "metadata": {},
   "source": [
    "__◑ Write a function novel10(text) that prints any word that appeared in the last 10% of a text that had not been encountered earlier.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 186,
   "id": "173fb365",
   "metadata": {},
   "outputs": [],
   "source": [
    "def novel10(text):\n",
    "    if type(text) == str:\n",
    "        text = nltk.word_tokenize(text)\n",
    "        \n",
    "    length = len(text)\n",
    "    first_90 = text[:int(0.9*length)]\n",
    "    last_10 = text[int(0.9*length):]\n",
    "    novels = [word for word in last_10 if word not in first_90]\n",
    "    \n",
    "    return set(novels)        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 187,
   "id": "2f3bd315",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "shuffling finds restraints Sally EDWARD scorn cutting enjoyments subsisting vigour calculate tricking 48 dogs astray invent management embellishment completion meals burnt worry privately wronged supplanted quivered surviving Instead THREE option conforming university flourish inspect WHAT outgrown repining Mansion resented bribing failure disagreement misled listener innumerable howsever stating dilatoriness superintend acquaintances inconsolable prosecution echoed commonly protestations incessant jumbled provident comment minuteness rendering adopted errors 50 Willing imitate couples indolent regulated strains intruder afterward LESS crowned unitedly doubly Precious Inn unsettle insulted affirmative merited delays economical unpardoned similarity postponing pasturage Selfish philosophic Considering comparisons treasured FERRARS sedateness workmen jealousy Which crossness labor patron inattentive unconquerable frugality honourably sweep Please replace obligations professed project frequency sheath standard deserts tablecloth mound Rather conspired abridge inexperience start intuitively Hanger ranked virtuous composition lessening unmoved excuses 49 humbled trembled appropriate chosen enormously stammered Sincerely transgressed compared indolence footsteps plead disquiet suffers 47 dryness disinherited utterance fairly manager interests unsteady policy mediation warmest thoughtless failing transport hussy repentance autumn destruction weaknesses solely comer practices nominal enlightened halves whiter plighted injure unembarrassed invalid sober nerve relent Unaccountable scrape patroness spoiling renounced appetites Being pecuniary TIME ALWAYS instigation observable entanglement fluctuating Burgess amended wrought expediency experiencing grounded contracted path unsubdued sobered destroy stopping compare economy untried Reflection reconciliation FAITH boyish fickle slowly substance genial unite unguarded jilting appointed ungraciously exceed panting scrawls disagreements interviews puzzle fretful publication retrenched nobleman unbroken retreated deserted continually profiting shaken articulate New crept worlds representation unknowingly constitutional expensiveness hazarding facts fearing voluntary residue dessert dreading studies shamefully glebe crime resuscitation messages exercising disordered augmenting haughty reproving maxims unnatural wisher > amiss useless SIR unblemished contriving THE unspeakable unbounded assiduous pages reckons poorly breed hazard adhering unbiased tidings familiarized repaid unintelligible tale unquiet rumour enumeration clemency submitting religion safeguard conjecturing decree worked disproportion penitent producing gates flowing slighter ruling incitement stupified consequently prophecies wont discussions murmurings penetrate submission Between confederacy recognised Comparisons habitual retailed bide lurking sacred END borrowed henceforth lingered annihilation thrill sensitive obstructed birth westward swell closely control minds justifying necessitous fled LUCY unfulfilled enrich doubtingly\n"
     ]
    }
   ],
   "source": [
    "print(*novel10(text2))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e9056ad0",
   "metadata": {},
   "source": [
    "__◑ Write a program that takes a sentence expressed as a single string, splits it and counts up the words. Get it to print out each word and the word's frequency, one per line, in alphabetical order.__\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "id": "619600a2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def freq_alphabetic(text):\n",
    "    \n",
    "    text = nltk.word_tokenize(text.lower())\n",
    "    freq = nltk.FreqDist(text)\n",
    "    \n",
    "    return sorted(freq, key = lambda x: x[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "id": "8c799e17",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['and', 'alphabetically', 'be', 'split', 'sorted', 'this', 'text', 'will']"
      ]
     },
     "execution_count": 112,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sent = \"This text will be split and alphabetically sorted\"\n",
    "freq_alphabetic(sent)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aba6720f",
   "metadata": {},
   "source": [
    "__◑ Read up on Gematria, a method for assigning numbers to words, and for mapping between words having the same number to discover the hidden meaning of texts (http://en.wikipedia.org/wiki/Gematria, http://essenes.net/gemcal.htm).__\n",
    "\n",
    "Write a function gematria() that sums the numerical values of the letters of a word, according to the letter values in letter_vals:\n",
    "\n",
    "Process a corpus (e.g. nltk.corpus.state_union) and for each document, count how many of its words have the number 666.\n",
    "\n",
    "Write a function decode() to process a text, randomly replacing words with their Gematria equivalents, in order to discover the \"hidden meaning\" of the text."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "dee279de",
   "metadata": {},
   "outputs": [],
   "source": [
    "letter_vals = {'a':1, 'b':2, 'c':3, 'd':4, 'e':5, 'f':80, 'g':3, 'h':8,\n",
    "                'i':10, 'j':10, 'k':20, 'l':30, 'm':40, 'n':50, 'o':70, 'p':80, 'q':100,\n",
    "                'r':200, 's':300, 't':400, 'u':6, 'v':6, 'w':800, 'x':60, 'y':10, 'z':7} "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "1aac5db0",
   "metadata": {},
   "outputs": [],
   "source": [
    "def gematria(text):\n",
    "     \n",
    "    gem_dict = defaultdict(set)\n",
    "    for w in text:\n",
    "        w = re.sub(r'[\\d.,?!%$&*\\\\\\/\\[\\\\(\\)\\]\\'\\\":;_-]', \"\", w) # since there is not number id for punctutation and digits\n",
    "        gems = 0\n",
    "        \n",
    "        for char in w.lower():\n",
    "            gems += letter_vals[char]\n",
    "        gem_dict[gems].add(w)\n",
    "    \n",
    "    return gem_dict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "7f5ac4ba",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'eloquent', 'outlook'}"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gem_state = gematria(nltk.corpus.state_union.words(\"1945-Truman.txt\"))\n",
    "gem_state[666]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 172,
   "id": "b82556f0",
   "metadata": {},
   "outputs": [],
   "source": [
    "def decode(text, N=100):\n",
    "    \"\"\"\n",
    "    Processes a text and randomly replaces words with their Gematria equivalents\n",
    "    \n",
    "    text - list of tokens\n",
    "    N - number of words to be replaced with gematria idx\n",
    "    \n",
    "    \"\"\"\n",
    "    if N > len(text):\n",
    "        raise Exception(\"N cannot be greater than the length of the text tokens\")\n",
    "    ids = []  # collect all ids so that new random is not the same as the previous one\n",
    "    count = 0 # how many words were replaced\n",
    "    text = [re.sub(r'[\\d\\W]', \"\", w) for w in text]\n",
    "    text = [w.lower() for w in text if w] # getting rid of empty str\n",
    "    while count < N:\n",
    "        idx = random.randint(0, len(text)-1)\n",
    "        if idx not in ids:\n",
    "            ids.append(idx)\n",
    "            text[idx] = str(sum([letter_vals[char] for char in text[idx]]))\n",
    "            count += 1\n",
    "    return text"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 184,
   "id": "81e3e1cc",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1054 harry 300 697 s 814 before a 540 session 150 the 931 april mr 611 mr president members of the congress it is with a heavy heart that i stand before you my friends and colleagues in the congress of 413 united states 160 yesterday 805 laid to rest the mortal remains of 276 beloved president franklin 160 roosevelt at a 455 like this 1374 are inadequate the most eloquent 1023 910 7 1 871 403 yet in this decisive 284 when world events are moving 370 rapidly our silence 461 be misunderstood and might give 863 to our enemies in his 615 wisdom almighty 77 has seen fit to 426 390 us a 609 man who loved and was beloved 12 all 525 no 91 could possibly fill the tremendous 90 left 12 the passing of that noble 406 no words can ease the aching hearts of untold millions 150 226 race creed and color the world knows it 309 800 a heroic champion of 734 and 404 tragic 486 has 1314 upon us 215 responsibilities we must carry on our departed 245 never looked backward he looked forward and moved forward that is what he would want us to 74 that is 1209 america will do so 57 176 has already been shed for the ideals which we cherish and for which 441 delano roosevelt lived and died that 805 210 520 735 even a 816 pause 60 the hard fight for victory today the entire world 310 looking to america for enlightened leadership 470 peace and 1158 such 1 leadership requires vision 288 55 tolerance it 54 be provided only by a united nation deeply devoted to the highest ideals 1218 great humility i call upon all americans 470 help 45 keep our nation united in defense of 783 ideals which have been so eloquently proclaimed by franklin roosevelt i want in 656 to assure my fellow 610 55 all of those who 111 peace 55 657 throughout the world 809 i will support 55 defend those ideals with all my strength and 61 50 heart 809 is my duty and 10 shall not shirk 410 so that there can be 120 797 1433 both 309 and japan 54 be certain beyond any shadow of a 482 that america will continue the fight 350 freedom until no vestige of resistance remains 805 are deeply conscious 150 the fact that much hard 564 is still ahead of us having 470 pay 317 a heavy price 470 make complete 699 certain america will 266 become 1 party to any plan for partial 699 to 1140 for merely another temporary respite would 551 jeopardize\n"
     ]
    }
   ],
   "source": [
    "print(*decode(nltk.corpus.state_union.words(\"1945-Truman.txt\")[:500], 100))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "114415be",
   "metadata": {},
   "source": [
    "__◑ Write a function shorten(text, n) to process a text, omitting the n most frequently occurring words of the text. How readable is it?__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 176,
   "id": "a866b833",
   "metadata": {},
   "outputs": [],
   "source": [
    "def shorten(text, n=50):\n",
    "    \n",
    "    most_commons = [word for word, freq in nltk.FreqDist(text).most_common(n)]\n",
    "    for i in range(len(text)):\n",
    "        if text[i] in most_commons:\n",
    "            text[i] = ''\n",
    "    return text"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 183,
   "id": "ba967036",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[  by Jane Austen 1816 ] VOLUME  CHAPTER   Woodhouse  handsome  clever   rich    comfortable home  happy disposition  seemed  unite some   best blessings  existence    lived nearly twenty - one years   world   little  distress or vex   She   youngest   two daughters   most affectionate  indulgent father      consequence   sister   marriage   mistress   house from   early period  Her mother  died too long ago     more than an indistinct remembrance   caresses    place   supplied by an excellent woman  governess  who  fallen little short   mother  affection  Sixteen years   Taylor     Woodhouse   family  less   governess than  friend   fond  both daughters   particularly    Between _them_   more  intimacy  sisters  Even before  Taylor  ceased  hold  nominal office  governess   mildness   temper  hardly allowed   impose  restraint    shadow  authority being now long passed away  they   living together  friend  friend  mutually attached    doing just what  liked  highly esteeming  Taylor   judgment   directed chiefly by  own  The real evils  indeed      situation   power  having rather too much  own way    disposition  think  little too well  herself  these   disadvantages which threatened alloy   many enjoyments  The danger  however    present  unperceived   they did  by  means rank  misfortunes    Sorrow came   gentle sorrow        shape   disagreeable consciousness   Taylor married  It   Taylor   loss which first brought grief  It    wedding - day  this beloved friend   first sat  mournful thought   continuance  The wedding over    bride - people gone   father  herself  left  dine together    prospect   third  cheer  long evening  Her father composed himself  sleep after dinner   usual     then only  sit  think  what   lost  The event  every promise  happiness   friend    Weston   man  unexceptionable character  easy fortune  suitable age   pleasant manners   there  some satisfaction  considering  what self - denying  generous friendship   always wished \n"
     ]
    }
   ],
   "source": [
    "txt = list(gutenberg.words(\"austen-emma.txt\"))\n",
    "print(*shorten(txt)[:500])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aa9222d7",
   "metadata": {},
   "source": [
    "__◑ Write code to print out an index for a lexicon, allowing someone to look up words according to their meanings (or pronunciations; whatever properties are contained in lexical entries).__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e4f6b279",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "f0ef4843",
   "metadata": {},
   "source": [
    "__◑ Write a list comprehension that sorts a list of WordNet synsets for proximity to a given synset. For example, given the synsets minke_whale.n.01, orca.n.01, novel.n.01, and tortoise.n.01, sort them according to their shortest_path_distance() from right_whale.n.01.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 229,
   "id": "b202b113",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(Synset('lesser_rorqual.n.01'), 0.25),\n",
       " (Synset('killer_whale.n.01'), 0.16666666666666666),\n",
       " (Synset('tortoise.n.01'), 0.07692307692307693),\n",
       " (Synset('novel.n.01'), 0.043478260869565216)]"
      ]
     },
     "execution_count": 229,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list_of_sn = [wordnet.synset(\"minke_whale.n.01\"), wordnet.synset(\"orca.n.01\"), wordnet.synset(\"novel.n.01\"), wordnet.synset(\"tortoise.n.01\")]\n",
    "sorted([(sn, wordnet.synset(\"right_whale.n.01\").path_similarity(sn)) for sn in list_of_sn], key = itemgetter(1), reverse = True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 228,
   "id": "341a3202",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(Synset('lesser_rorqual.n.01'), 0.25),\n",
       " (Synset('killer_whale.n.01'), 0.16666666666666666),\n",
       " (Synset('tortoise.n.01'), 0.07692307692307693),\n",
       " (Synset('novel.n.01'), 0.043478260869565216)]"
      ]
     },
     "execution_count": 228,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def synset_sort_by_similarity(synset, list_of_synsets):\n",
    "    return sorted([(sn, synset.path_similarity(sn)) for sn in list_of_synsets], key = itemgetter(1), reverse = True)\n",
    "\n",
    "synset_sort_by_similarity(wordnet.synset(\"right_whale.n.01\"), list_of_sn)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bcf6ba36",
   "metadata": {},
   "source": [
    "__◑ Write a function that takes a list of words (containing duplicates) and returns a list of words (with no duplicates) sorted by decreasing frequency. E.g. if the input list contained 10 instances of the word table and 9 instances of the word chair, then table would appear before chair in the output list.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 210,
   "id": "a3db76d2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "dict_keys(['table', 'sun', 'chair', 'desk', 'a'])"
      ]
     },
     "execution_count": 210,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list_dup = [\"table\",\"sun\",\"table\",\"table\",\"table\",\"table\",\"table\",\"table\",\"chair\",\"chair\",\"chair\",\"chair\",\"desk\",\"desk\",\"a\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 227,
   "id": "e733a3d4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('table', 7), ('chair', 4), ('desk', 2), ('sun', 1), ('a', 1)]"
      ]
     },
     "execution_count": 227,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted(Counter(list_dup).items(), key = itemgetter(1), reverse = True)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "82a36e2b",
   "metadata": {},
   "source": [
    "__◑ Write a function that takes a text and a vocabulary as its arguments and returns the set of words that appear in the text but not in the vocabulary. Both arguments can be represented as lists of strings. Can you do this in a single line, using set.difference()?__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 221,
   "id": "6e205561",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{2, 5, 6}"
      ]
     },
     "execution_count": 221,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "set_text = {1,2,3,4,5,6}\n",
    "set_vocab = {1,7,8,0,4,3}\n",
    "set_text.difference(set_vocab)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "290a53ee",
   "metadata": {},
   "source": [
    "__◑ Import the itemgetter() function from the operator module in Python's standard library (i.e. from operator import itemgetter). Create a list words containing several words. Now try calling: sorted(words, key=itemgetter(1)), and sorted(words, key=itemgetter(-1)). Explain what itemgetter() is doing.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 226,
   "id": "ccb38577",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('of', 0), ('this', 1), ('words', 2), ('a', 6), ('is', 9), ('list', 100)]"
      ]
     },
     "execution_count": 226,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "words = [(\"this\", 1), (\"is\", 9), (\"a\", 6), (\"list\", 100), (\"of\", 0), (\"words\",2)]\n",
    "sorted(words, key=itemgetter(1))  # sorts by the second element in the tuple"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8777629d",
   "metadata": {},
   "source": [
    "__◑ Write a recursive function lookup(trie, key) that looks up a key in a trie, and returns the value it finds. Extend the function to return a word when it is uniquely determined by its prefix (e.g. vanguard is the only word that starts with vang-, so lookup(trie, 'vang') should return the same thing as lookup(trie, 'vanguard')).__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 230,
   "id": "0529e321",
   "metadata": {},
   "outputs": [],
   "source": [
    "def insert(trie, key, value):\n",
    "    if key:\n",
    "        first, rest = key[0], key[1:]\n",
    "        if first not in trie:\n",
    "            trie[first] = {}\n",
    "        insert(trie[first], rest, value)\n",
    "    else:\n",
    "        trie['value'] = value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 231,
   "id": "f64ef22d",
   "metadata": {},
   "outputs": [],
   "source": [
    "trie = {}\n",
    "insert(trie, 'chat', 'cat')\n",
    "insert(trie, 'chien', 'dog')\n",
    "insert(trie, 'chair', 'flesh')\n",
    "insert(trie, 'chic', 'stylish')\n",
    "insert(trie, 'maison', 'house')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 244,
   "id": "9b3c130b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'h': {'a': {'i': {'r': {'value': 'flesh'}}, 't': {'value': 'cat'}},\n",
      "       'i': {'c': {'value': 'stylish'}, 'e': {'n': {'value': 'dog'}}}}}\n"
     ]
    }
   ],
   "source": [
    "import pprint\n",
    "pprint.pprint(trie[\"c\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 275,
   "id": "80ff016a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 275,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(trie)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 281,
   "id": "4ed2ef13",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "dog\n"
     ]
    }
   ],
   "source": [
    "def lookup(trie, key):\n",
    "    if len(key) == 0:\n",
    "        if 'value' in trie:\n",
    "            result = trie['value']\n",
    "            return result\n",
    "        elif (len(trie) == 1):\n",
    "            key = list(trie.keys())\n",
    "            return lookup(trie[key[0]], '')\n",
    "        else:\n",
    "            return 'no value found'\n",
    "    else:\n",
    "        if (key[0] in trie):\n",
    "            return lookup(trie[key[0]], key[1:])\n",
    "        else:\n",
    "            return 'no value found'\n",
    "\n",
    "print(lookup(trie, 'chie'))    "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a801b8cc",
   "metadata": {},
   "source": [
    "__◑ Read up on \"keyword linkage\" (chapter 5 of (Scott & Tribble, 2006)). Extract keywords from NLTK's Shakespeare Corpus and using the NetworkX package, plot keyword linkage networks.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b6aae746",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1c60e3b8",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "78b135b6",
   "metadata": {},
   "source": [
    "__◑ Read about string edit distance and the Levenshtein Algorithm. Try the implementation provided in nltk.edit_distance(). In what way is this using dynamic programming? Does it use the bottom-up or top-down approach? [See also http://norvig.com/spell-correct.html]__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 282,
   "id": "1c405b4c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 282,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nltk.edit_distance(\"deer\", \"dear\") # switch one letter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 283,
   "id": "f5bab043",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 283,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nltk.edit_distance(\"rainbow\", \"rain\") # delete 3 letters"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d9eb3eef",
   "metadata": {},
   "source": [
    "__◑ The Catalan numbers arise in many applications of combinatorial mathematics, including the counting of parse trees (6). The series can be defined as follows: C0 = 1, and Cn+1 = Σ0..n (CiCn-i).__\n",
    "\n",
    "Write a recursive function to compute nth Catalan number Cn.\n",
    "\n",
    "Now write another function that does this computation using dynamic programming.\n",
    "\n",
    "Use the timeit module to compare the performance of these functions as n increases."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 323,
   "id": "5435b013",
   "metadata": {},
   "outputs": [],
   "source": [
    "def catalan(num):\n",
    "    if num <= 1:\n",
    "        return 1\n",
    "\n",
    "    result = 0\n",
    "    for i in range(num):\n",
    "        result += catalan(i) * catalan(num-i-1)\n",
    " \n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 324,
   "id": "42594fa4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 324,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "catalan(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e9f463cf",
   "metadata": {},
   "outputs": [],
   "source": [
    "def catalan(n):\n",
    "    if num <= 1:\n",
    "        return 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d5fe00ea",
   "metadata": {},
   "source": [
    "__★ Reproduce some of the results of (Zhao & Zobel, 2007) concerning authorship identification.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d46d7f59",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "6713b8ef",
   "metadata": {},
   "source": [
    "__★ Study gender-specific lexical choice, and see if you can reproduce some of the results of http://www.clintoneast.com/articles/words.php__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a003250f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# could not get access to the website"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e3f4cfc2",
   "metadata": {},
   "source": [
    "__★ Write a recursive function that pretty prints a trie in alphabetically sorted order__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 334,
   "id": "3bf89720",
   "metadata": {},
   "outputs": [],
   "source": [
    "def pprint_trie(trie, line=''):\n",
    "    if 'value' in trie:\n",
    "        print(line + ': \\'' + trie['value'] + '\\'')\n",
    "        \n",
    "    for index, key in enumerate(sorted(trie.keys())):\n",
    "        if (index == 0):\n",
    "            pprint_trie(trie[key], line + key)\n",
    "        else:\n",
    "            pprint_trie(trie[key], ('-' * len(line)) + key)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "86702abf",
   "metadata": {},
   "outputs": [],
   "source": [
    "#COME BACK TO THIS ONE"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b76068a9",
   "metadata": {},
   "source": [
    "__★ With the help of the trie data structure, write a recursive function that processes text, locating the uniqueness point in each word, and discarding the remainder of each word. How much compression does this give? How readable is the resulting text?__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9b9cf52b",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "78e78673",
   "metadata": {},
   "source": [
    "__★ Obtain some raw text, in the form of a single, long string. Use Python's textwrap module to break it up into multiple lines. Now write code to add extra spaces between words, in order to justify the output. Each line must have the same width, and spaces must be approximately evenly distributed across each line. No line can begin or end with a space.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 456,
   "id": "08a2ae2e",
   "metadata": {},
   "outputs": [],
   "source": [
    "import textwrap\n",
    "\n",
    "sample_text = \"\"\"This function wraps the input paragraph such that each line in the paragraph is at most \\\n",
    "width characters long. The wrap method returns a list of output lines. The returned list is empty if \\\n",
    "the wrapped output has no contents\"\"\"\n",
    "\n",
    "def wrap_text(text, width = 50):\n",
    "    wrapper = textwrap.TextWrapper(width=width)\n",
    "    wrapped = wrapper.wrap(text)\n",
    "    lengths = [len(line) for line in wrapper.wrap(text)]\n",
    "    space_needed = [50 - l for l in lengths]\n",
    "    \n",
    "    wrapped_new = []\n",
    "    \n",
    "    for idx, line in enumerate(wrapped):\n",
    "        if space_needed[idx] != 0:\n",
    "            add = space_needed[idx] // (len(line.split())-1)\n",
    "            extra = space_needed[idx] % (len(line.split())-1)\n",
    "            line = re.sub(\"\\s\", \" \"*(add + 1), line)\n",
    "            if extra != 0: line = re.subn(\"\\s\", \"  \", line, extra)[0]\n",
    "            wrapped_new.append(line)\n",
    "    return wrapped_new"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 427,
   "id": "31fc05b6",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "This  function wraps the input paragraph such that\n",
      "each  line  in  the  paragraph  is  at  most width\n",
      "output  lines.  The  returned list is empty if the\n",
      "wrapped      output      has      no      contents\n"
     ]
    }
   ],
   "source": [
    "for line in wrap_text(sample_text):\n",
    "    print(line)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c0e2e706",
   "metadata": {},
   "source": [
    "__★ Develop a simple extractive summarization tool, that prints the sentences of a document which contain the highest total word frequency. Use FreqDist() to count word frequencies, and use sum to sum the frequencies of the words in each sentence. Rank the sentences according to their score. Finally, print the n highest-scoring sentences in document order. Carefully review the design of your program, especially your approach to this double sorting. Make sure the program is written as clearly as possible.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 445,
   "id": "0d9703d3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sort_sent_by_freq(text, N):\n",
    "    \n",
    "    freq = nltk.FreqDist(nltk.word_tokenize(text))\n",
    "    # sorted_freq = sorted(freq.items(), itemgetter[1], reverse = True)\n",
    "    sents = nltk.sent_tokenize(text)\n",
    "    \n",
    "    sent_fd = 0\n",
    "    sents_with_fd = []\n",
    "    \n",
    "    for sent in sents:\n",
    "        sent_fd = sum([freq[w] for w in sent])\n",
    "        sents_with_fd.append((sent, sent_fd))\n",
    "    \n",
    "    return(sorted(sents_with_fd, key = itemgetter(1), reverse=True))[:N]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 457,
   "id": "09246599",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('This function wraps the input paragraph such that each line in the paragraph is at most width characters long.',\n",
       "  14),\n",
       " ('The wrap method returns a list of output lines.', 4)]"
      ]
     },
     "execution_count": 457,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sort_sent_by_freq(sample_text, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "01809b11",
   "metadata": {},
   "source": [
    "__★ Read the following article on semantic orientation of adjectives. Use the NetworkX package to visualize a network of adjectives with edges to indicate same vs different semantic orientation. http://www.aclweb.org/anthology/P97-1023__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0f5cb925",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "170d6435",
   "metadata": {},
   "source": [
    "__★ Design an algorithm to find the \"statistically improbable phrases\" of a document collection. http://www.amazon.com/gp/search-inside/sipshelp.html__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f53096bc",
   "metadata": {},
   "outputs": [],
   "source": [
    "# I did not get what is expected, and the page does not exist anymore. So, I will skip this one"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "12a4c751",
   "metadata": {},
   "source": [
    "__★ Write a program to implement a brute-force algorithm for discovering word squares, a kind of n × n crossword in which the entry in the nth row is the same as the entry in the nth column. For discussion, see http://itre.cis.upenn.edu/~myl/languagelog/archives/002679.html__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 459,
   "id": "c80909c5",
   "metadata": {},
   "outputs": [],
   "source": [
    "vocab = nltk.corpus.words.words()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 462,
   "id": "a4bf550a",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sator(vocab, size):\n",
    "    \n",
    "    \n",
    "    word = [[]] * (size + 1)\n",
    "    while True:\n",
    "        word[1][1] = random.choice(words)\n",
    "        for n in range(2, size):\n",
    "            word[1][n] = [w for w in words if w.startswith(word[1][1])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 563,
   "id": "83a20935",
   "metadata": {},
   "outputs": [],
   "source": [
    "def word_square(n):\n",
    "    \n",
    "    words = [w.lower() for w in vocab if len(w) ==  n]\n",
    "    square = []\n",
    "    skipWords = [[] for i in range(n)] # cache for words that have already been tested at position i\n",
    "    \n",
    "    def check_against_square(word): # checks if current state of square would allow to add word to it\n",
    "        if word in square:\n",
    "            return False\n",
    "        for (index, square_word) in enumerate(square):\n",
    "            if (word[index] != square_word[len(square)]):\n",
    "                return False\n",
    "        return True\n",
    "    \n",
    "    def add_word():\n",
    "        for word in words:\n",
    "            if len(square) == n:\n",
    "                return True\n",
    "            elif (word not in skipWords[len(square)]) and check_against_square(word):\n",
    "                square.append(word)\n",
    "                add_word()\n",
    "        if len(square) != n and len(square) != 0:   \n",
    "            skipWords[len(square) - 1].append(square.pop()) # add word to cache\n",
    "            for i in range(len(square) + 1, n): # reset the following parts of the cache\n",
    "                skipWords[i] = []\n",
    "            add_word()\n",
    "        return False\n",
    "            \n",
    "        \n",
    "    if add_word():\n",
    "        for word in square:\n",
    "            print(word)\n",
    "    else:\n",
    "        print('No square found :/')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 574,
   "id": "87c793fd",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "aalii\n",
      "abash\n",
      "lazar\n",
      "isawa\n",
      "ihram\n"
     ]
    }
   ],
   "source": [
    "word_square(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 585,
   "id": "0f6166ce",
   "metadata": {},
   "outputs": [],
   "source": [
    "def check_against_square(word): # checks if current state of square would allow to add word to it\n",
    "    if word in square:\n",
    "        return False\n",
    "    for (index, square_word) in enumerate(square):\n",
    "        if (word[index] != square_word[len(square)]):\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 587,
   "id": "24ad9171",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 589,
   "id": "fb7eb274",
   "metadata": {},
   "outputs": [],
   "source": [
    "square = [\"baba\", \"alma\", \"bmit\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 595,
   "id": "b1eafdde",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 595,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "check_against_square(\"appy\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 594,
   "id": "1f1cbbcc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 594,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"appy\"[2] == \"bmit\"[3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "51a47234",
   "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.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}