Algorithms Exercise 1

Imports



In [14]:

    
%matplotlib inline
from matplotlib import pyplot as plt
import numpy as np

Word counting

Write a function tokenize that takes a string of English text returns a list of words. It should also remove stop words, which are common short words that are often removed before natural language processing. Your function should have the following logic:

Split the string into lines using splitlines.
Split each line into a list of words and merge the lists for each line.
Use Python's builtin filter function to remove all punctuation.
If stop_words is a list, remove all occurences of the words in the list.
If stop_words is a space delimeted string of words, split them and remove them.
Remove any remaining empty words.
Make all words lowercase.



In [20]:

    
def tokenize(s, stop_words=None, punctuation='`~!@#$%^&*()_-+={[}]|\:;"<,>.?/}\t'):
    """Split a string into a list of words, removing punctuation and stop words."""
    s = s.replace("\n", " ")
    for i in range(len(punctuation)):
        s = s.replace(punctuation[i], " ")
    #clean = ''.join([c.lower() for c in s if c not in punctuation])
    clean = s.split(" ")
    
    # Check if stop_words is a string
    if stop_words != None:
        if (isinstance(stop_words, str)):
            stop_lst = stop_words.split(" ")
            go_words = [w.lower() for w in clean if w not in stop_lst and len(w) > 0]
        else:
            go_words = [w.lower() for w in clean if w not in stop_words and len(w) > 0]
    else:
        go_words = [w.lower() for w in clean if len(w) > 0]
      
    return(go_words)
    
    
    #raise NotImplementedError()



In [21]:

    
assert tokenize("This, is the way; that things will end", stop_words=['the', 'is']) == \
    ['this', 'way', 'that', 'things', 'will', 'end']
wasteland = """
APRIL is the cruellest month, breeding
Lilacs out of the dead land, mixing
Memory and desire, stirring
Dull roots with spring rain.
"""

assert tokenize(wasteland, stop_words='is the of and') == \
    ['april','cruellest','month','breeding','lilacs','out','dead','land',
     'mixing','memory','desire','stirring','dull','roots','with','spring',
     'rain']

Write a function count_words that takes a list of words and returns a dictionary where the keys in the dictionary are the unique words in the list and the values are the word counts.



In [22]:

    
def count_words(data):
    """Return a word count dictionary from the list of words in data."""
    data.sort()
    word_dict = {}
    for i in range(len(data)):
        if i == 0 or (data[i] != data[i-1]):
            word_dict[data[i]] = 1
        else:
            word_dict[data[i]] += 1
    return(word_dict)  
    
    #raise NotImplementedError()



In [23]:

    
assert count_words(tokenize('this and the this from and a a a')) == \
    {'a': 3, 'and': 2, 'from': 1, 'the': 1, 'this': 2}

Write a function sort_word_counts that return a list of sorted word counts:

Each element of the list should be a (word, count) tuple.
The list should be sorted by the word counts, with the higest counts coming first.
To perform this sort, look at using the sorted function with a custom key and reverse argument.



In [24]:

    
def sort_word_counts(wc):
    """Return a list of 2-tuples of (word, count), sorted by count descending."""
    word_tups = [(key, wc[key]) for key in wc]
    res = sorted(word_tups, key = lambda word: word[1], reverse = True)
    return(res)
    #raise NotImplementedError()



In [25]:

    
assert sort_word_counts(count_words(tokenize('this and a the this this and a a a'))) == \
    [('a', 4), ('this', 3), ('and', 2), ('the', 1)]

Perform a word count analysis on Chapter 1 of Moby Dick, whose text can be found in the file mobydick_chapter1.txt:

Read the file into a string.
Tokenize with stop words of 'the of and a to in is it that as'.
Perform a word count, the sort and save the result in a variable named swc.



In [28]:

    
file = open('mobydick_chapter1.txt', 'r')
data = file.read()
file.close()

swc = sort_word_counts(count_words(tokenize(data, 'the of and a to in is it that as')))
print(len(swc))
print(swc)
#raise NotImplementedError()









    



849
[('i', 43), ('me', 25), ('you', 23), ('all', 23), ('this', 17), ('there', 16), ('for', 16), ('but', 15), ('my', 14), ('with', 13), ('sea', 13), ('they', 12), ('go', 12), ('on', 12), ('from', 11), ('not', 11), ('some', 11), ('one', 10), ('or', 10), ('his', 10), ('he', 10), ('what', 9), ('upon', 9), ('be', 9), ('into', 9), ('if', 9), ('have', 8), ('was', 8), ('water', 8), ('by', 8), ('do', 8), ('about', 7), ('part', 7), ('were', 7), ('though', 7), ('and', 7), ('why', 7), ('more', 6), ('will', 6), ('like', 6), ('land', 6), ('no', 6), ('your', 6), ('down', 6), ('it', 6), ('get', 6), ('take', 6), ('see', 6), ('way', 6), ('voyage', 6), ('can', 6), ('old', 6), ('time', 6), ('did', 5), ('at', 5), ('now', 5), ('the', 5), ('when', 5), ('ever', 5), ('who', 5), ('whenever', 5), ('sailor', 5), ('other', 5), ('them', 5), ('are', 5), ('stand', 5), ('such', 5), ('here', 5), ('never', 5), ('whaling', 5), ('then', 5), ('same', 5), ('most', 5), ('passenger', 4), ('first', 4), ('which', 4), ('because', 4), ('things', 4), ('must', 4), ('little', 4), ('than', 4), ('those', 4), ('yet', 4), ('would', 4), ('being', 4), ('an', 4), ('up', 4), ('two', 4), ('high', 4), ('going', 4), ('these', 4), ('much', 4), ('so', 4), ('head', 4), ('tell', 4), ('men', 4), ('am', 4), ('world', 4), ('their', 4), ('money', 4), ('every', 4), ('may', 3), ('great', 3), ('miles', 3), ('without', 3), ('hand', 3), ('myself', 3), ('broiled', 3), ('we', 3), ('winds', 3), ('how', 3), ('still', 3), ('passengers', 3), ('ships', 3), ('soul', 3), ('set', 3), ('image', 3), ('grand', 3), ('paying', 3), ('almost', 3), ('nothing', 3), ('him', 3), ('say', 3), ('whale', 3), ('sort', 3), ('right', 3), ('purse', 3), ('out', 3), ('ship', 3), ('something', 3), ('cook', 3), ('parts', 3), ('before', 3), ('man', 3), ('off', 3), ('come', 3), ('should', 3), ('crowds', 2), ('among', 2), ('order', 2), ('thing', 2), ('fates', 2), ('thump', 2), ('plunged', 2), ('leaders', 2), ('motives', 2), ('any', 2), ('however', 2), ('particular', 2), ('unless', 2), ('robust', 2), ('between', 2), ('could', 2), ('phantom', 2), ('better', 2), ('magic', 2), ('aloft', 2), ("shepherd's", 2), ('in', 2), ('long', 2), ('just', 2), ('make', 2), ('spar', 2), ('let', 2), ('captain', 2), ('metaphysical', 2), ('distant', 2), ('besides', 2), ('begin', 2), ('hunks', 2), ('perhaps', 2), ('respectfully', 2), ('lead', 2), ('own', 2), ('themselves', 2), ('look', 2), ('ourselves', 2), ('strong', 2), ('over', 2), ('having', 2), ('grow', 2), ('chief', 2), ('care', 2), ('officer', 2), ('ishmael', 2), ('mast', 2), ('always', 2), ('where', 2), ('hill', 2), ('else', 2), ('air', 2), ('scores', 2), ('round', 2), ('mean', 2), ('requires', 2), ('meadow', 2), ('ocean', 2), ('previous', 2), ('wild', 2), ('meaning', 2), ('once', 2), ('fixed', 2), ('well', 2), ('commodore', 2), ('under', 2), ('yonder', 2), ('pay', 2), ('account', 2), ('city', 2), ('glory', 2), ('paid', 2), ('point', 2), ('content', 2), ('seas', 2), ('cannot', 2), ('think', 2), ('schoolmaster', 2), ('each', 2), ('does', 2), ('sleep', 2), ('sight', 2), ('thinks', 2), ('thousand', 2), ('streets', 2), ('country', 2), ('warehouses', 2), ('find', 2), ('its', 2), ('reveries', 2), ('himself', 2), ('leaves', 2), ('forecastle', 2), ('sail', 2), ('deep', 2), ('healthy', 2), ('thousands', 2), ('been', 2), ('ago', 2), ('deck', 2), ('stream', 2), ('exactly', 2), ('breezes', 1), ('whether', 1), ('looking', 1), ('perils', 1), ('heaven', 1), ('oceans', 1), ('swung', 1), ('urbane', 1), ('sighs', 1), ('ignoring', 1), ('feel', 1), ('new', 1), ('boy', 1), ('inferred', 1), ('true', 1), ('making', 1), ('trouble', 1), ('experiment', 1), ('needles', 1), ('exercise', 1), ('leagues', 1), ('trunk', 1), ('vain', 1), ('cataract', 1), ('thought', 1), ('somehow', 1), ('wherefore', 1), ('stoics', 1), ('goes', 1), ('call', 1), ('inducements', 1), ('forbidden', 1), ('dreamy', 1), ('unbiased', 1), ('came', 1), ('judgmatically', 1), ('uncomfortable', 1), ('amount', 1), ('satisfaction', 1), ('watery', 1), ('nights', 1), ('extremest', 1), ('dotings', 1), ('soon', 1), ('knows', 1), ('seaward', 1), ('fountain', 1), ('precisely', 1), ('archangel', 1), ('infallibly', 1), ('involuntarily', 1), ('enough', 1), ('pier', 1), ('story', 1), ('needed', 1), ('instance', 1), ('coral', 1), ('farces', 1), ('virtue', 1), ('degree', 1), ('abandon', 1), ('suddenly', 1), ('undeliverable', 1), ('insular', 1), ('penny', 1), ('fields', 1), ('easy', 1), ('monster', 1), ('scales', 1), ('corlears', 1), ('bound', 1), ('within', 1), ('abominate', 1), ('bathed', 1), ('thieves', 1), ('philosophical', 1), ('west', 1), ('gone', 1), ('hats', 1), ('judgment', 1), ('hook', 1), ('root', 1), ('plaster', 1), ('landsmen', 1), ('second', 1), ('really', 1), ('rear', 1), ('love', 1), ('prevent', 1), ('putting', 1), ('rigging', 1), ('marvellous', 1), ('mole', 1), ('heard', 1), ('gets', 1), ('disguises', 1), ('van', 1), ('others', 1), ('eye', 1), ('buy', 1), ('feelings', 1), ('downtown', 1), ('various', 1), ('manhattoes', 1), ('inmost', 1), ('isles', 1), ('smelt', 1), ('drawn', 1), ('mysterious', 1), ('extreme', 1), ('royal', 1), ('romantic', 1), ('infliction', 1), ('roasted', 1), ('astern', 1), ('presented', 1), ('solo', 1), ('spleen', 1), ('wonder', 1), ('lilies', 1), ('falling', 1), ('us', 1), ('compare', 1), ('invisible', 1), ('lies', 1), ('life', 1), ('enter', 1), ('absent', 1), ('sailors', 1), ('mystical', 1), ('deepest', 1), ('street', 1), ('answer', 1), ('idolatrous', 1), ('since', 1), ('stage', 1), ('desires', 1), ('processions', 1), ('sentinels', 1), ('professor', 1), ('stepping', 1), ('lath', 1), ('silver', 1), ('wedded', 1), ('perceive', 1), ('cheerfully', 1), ('sick', 1), ('unite', 1), ('influences', 1), ('breathes', 1), ('transition', 1), ('resulting', 1), ('magnetic', 1), ('fancied', 1), ('single', 1), ('legs', 1), ('enable', 1), ('bake', 1), ('wade', 1), ('creatures', 1), ('obey', 1), ('wish', 1), ('captains', 1), ('cottage', 1), ('drizzly', 1), ('itch', 1), ('mid', 1), ('repeatedly', 1), ('throws', 1), ('has', 1), ('days', 1), ('trees', 1), ('pythagorean', 1), ('induced', 1), ('loitering', 1), ('surveillance', 1), ("ain't", 1), ('principle', 1), ('testament', 1), ('keen', 1), ('wears', 1), ('meet', 1), ('woodlands', 1), ('perdition', 1), ('yes', 1), ('shoulder', 1), ('secretly', 1), ('suspect', 1), ('brief', 1), ('methodically', 1), ('rub', 1), ('green', 1), ('conceits', 1), ('silent', 1), ('sights', 1), ('circumambulate', 1), ('suffice', 1), ('side', 1), ('cato', 1), ('saco', 1), ('simple', 1), ('hooded', 1), ('surely', 1), ('performing', 1), ('grim', 1), ('tallest', 1), ('visit', 1), ('jolly', 1), ('formed', 1), ('rolled', 1), ('general', 1), ('providence', 1), ('hypos', 1), ('nigh', 1), ('purpose', 1), ('difference', 1), ('confess', 1), ('family', 1), ('sleepy', 1), ('prevalent', 1), ('particularly', 1), ('desks', 1), ('striving', 1), ('seemingly', 1), ('left', 1), ('shabby', 1), ('waterward', 1), ('curiosity', 1), ('passed', 1), ('assure', 1), ('washed', 1), ('east', 1), ('ah', 1), ('heads', 1), ('friendly', 1), ('place', 1), ('valley', 1), ('fowls', 1), ('quick', 1), ('again', 1), ('feet', 1), ('damp', 1), ('patagonian', 1), ('affghanistan', 1), ('hermit', 1), ('peep', 1), ('genteel', 1), ('overlapping', 1), ('sand', 1), ('floated', 1), ('horror', 1), ('regulating', 1), ('growing', 1), ('ills', 1), ('constant', 1), ('gabriel', 1), ('hours', 1), ('recall', 1), ('swayed', 1), ('police', 1), ('commerce', 1), ('drop', 1), ('pedestrian', 1), ('plumb', 1), ('knew', 1), ('reverentially', 1), ('short', 1), ('orchard', 1), ('desert', 1), ('less', 1), ('rivers', 1), ('hardicanutes', 1), ('knocking', 1), ('salted', 1), ('lungs', 1), ('thence', 1), ('tragedies', 1), ('extensive', 1), ('cunningly', 1), ('sway', 1), ('rag', 1), ('straight', 1), ("people's", 1), ('tribulations', 1), ('niagara', 1), ('tormented', 1), ('driving', 1), ('bulwarks', 1), ('persians', 1), ('established', 1), ('shady', 1), ('around', 1), ('sword', 1), ('earnestly', 1), ('upper', 1), ('magnificent', 1), ('sadly', 1), ('mummies', 1), ('served', 1), ('election', 1), ('orders', 1), ('november', 1), ('years', 1), ('receives', 1), ('counters', 1), ('merchant', 1), ('believe', 1), ('trip', 1), ('poet', 1), ('lanes', 1), ('please', 1), ('northward', 1), ('distinction', 1), ('broom', 1), ('physical', 1), ('rather', 1), ('very', 1), ('american', 1), ('mouth', 1), ('atmosphere', 1), ('good', 1), ('roused', 1), ('remote', 1), ('carries', 1), ('flood', 1), ('rensselaers', 1), ('earthly', 1), ('wanting', 1), ('mortal', 1), ('leaning', 1), ('hands', 1), ('after', 1), ('beach', 1), ('quietest', 1), ('dogs', 1), ('unaccountable', 1), ('circumstances', 1), ('far', 1), ('hazy', 1), ('coffin', 1), ('buttered', 1), ('judiciously', 1), ('hollow', 1), ('wholesome', 1), ('programme', 1), ('trials', 1), ('tree', 1), ('compasses', 1), ('drowned', 1), ('region', 1), ('greeks', 1), ('dive', 1), ('reaching', 1), ('nameless', 1), ('whereas', 1), ('inmates', 1), ('fore', 1), ('inlanders', 1), ('overwhelming', 1), ('cooled', 1), ('brigs', 1), ('waves', 1), ('pacing', 1), ('spiles', 1), ('deliberately', 1), ('open', 1), ('lording', 1), ('south', 1), ('grin', 1), ('key', 1), ('noble', 1), ("don't", 1), ('eyes', 1), ('grasp', 1), ('quietly', 1), ('commonalty', 1), ('battery', 1), ('bloody', 1), ('many', 1), ('either', 1), ('moral', 1), ('nor', 1), ('comedies', 1), ('june', 1), ('interlude', 1), ('happen', 1), ('shore', 1), ('managers', 1), ('week', 1), ('gates', 1), ('kind', 1), ('reason', 1), ('activity', 1), ('few', 1), ('slave', 1), ('alleys', 1), ('tennessee', 1), ('handfuls', 1), ('substitute', 1), ('against', 1), ('lodges', 1), ('presidency', 1), ('picture', 1), ('hold', 1), ('island', 1), ("one's", 1), ('unpleasant', 1), ('town', 1), ('dale', 1), ('fowl', 1), ("other's", 1), ('indignity', 1), ('ball', 1), ('pool', 1), ('wharves', 1), ('narcissus', 1), ('bit', 1), ('benches', 1), ('limit', 1), ('pent', 1), ('quarrelsome', 1), ('artist', 1), ('employs', 1), ('ungraspable', 1), ('lee', 1), ('terms', 1), ('circulation', 1), ('bear', 1), ('shadiest', 1), ('give', 1), ('choice', 1), ('funeral', 1), ('blue', 1), ('nearly', 1), ('bill', 1), ('contested', 1), ('egyptians', 1), ('vibration', 1), ('peppered', 1), ('north', 1), ('surf', 1), ('seneca', 1), ('violate', 1), ('pine', 1), ('decoction', 1), ('path', 1), ('whatsoever', 1), ('weighed', 1), ('try', 1), ('conscious', 1), ('even', 1), ('finally', 1), ('coat', 1), ('horse', 1), ('meditation', 1), ('snow', 1), ('doubtless', 1), ('pausing', 1), ('surrounds', 1), ('of', 1), ('run', 1), ('prairies', 1), ('spurs', 1), ('enjoy', 1), ('holy', 1), ('honour', 1), ('ibis', 1), ('tiger', 1), ('athirst', 1), ('thus', 1), ('grasshopper', 1), ('receiving', 1), ('jove', 1), ('thither', 1), ('tied', 1), ('blades', 1), ('everlasting', 1), ('awe', 1), ('lakes', 1), ('touches', 1), ('bulk', 1), ('pure', 1), ('mazy', 1), ('travel', 1), ('smoke', 1), ('invest', 1), ('avenues', 1), ('needs', 1), ('mild', 1), ('act', 1), ('maxim', 1), ('anything', 1), ('portentous', 1), ('poor', 1), ('towards', 1), ('honourable', 1), ('quarter', 1), ('toils', 1), ('sleeps', 1), ('belted', 1), ('shakes', 1), ('interest', 1), ('houses', 1), ('sounds', 1), ('told', 1), ('springs', 1), ('social', 1), ('element', 1), ('possibly', 1), ('yourself', 1), ('states', 1), ('pyramids', 1), ('taking', 1), ('respectable', 1), ('consign', 1), ('crazy', 1), ('river', 1), ('clinched', 1), ('huge', 1), ('landscape', 1), ('especially', 1), ('reefs', 1), ('view', 1), ('welcome', 1), ('nailed', 1), ('universal', 1), ('punch', 1), ('china', 1), ('monied', 1), ('sweep', 1), ('tormenting', 1), ('schooners', 1), ('crucifix', 1), ('strange', 1), ('idea', 1), ('charm', 1), ('caravan', 1), ('united', 1), ('afternoon', 1), ('boys', 1), ('delusion', 1), ('bringing', 1), ('promptly', 1), ('deeper', 1), ('seated', 1), ('considerable', 1), ('pot', 1), ('battle', 1), ('rockaway', 1), ('pistol', 1), ('deliberate', 1), ('habit', 1), ('separate', 1), ('mind', 1), ('saw', 1), ('her', 1), ('tranced', 1), ('whitehall', 1), ('everybody', 1), ('slip', 1), ('speak', 1), ('cajoling', 1), ('gazers', 1), ('attract', 1), ('freewill', 1), ('castle', 1), ('mountains', 1), ('enchanting', 1), ('salt', 1), ('posted', 1), ('performances', 1), ('minded', 1), ('considering', 1), ('paint', 1), ('ten', 1), ('coasts', 1), ('discriminating', 1), ('barques', 1), ('decks', 1), ('attending', 1), ('deity', 1), ('helped', 1), ('jump', 1), ('put', 1), ('sense', 1), ('flourish', 1), ('indian', 1), ('supplied', 1), ('endless', 1), ('randolphs', 1), ('offices', 1), ('brother', 1), ('cherish', 1), ('entailed', 1), ('coenties', 1), ('broiling', 1), ('cattle', 1), ('board', 1), ('quite', 1), ('barbarous', 1), ('surprising', 1), ('knowing', 1), ('sabbath', 1), ('dreamiest', 1), ('marvels', 1), ('contrary', 1), ('tar', 1), ('knee', 1)]






    



---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-28-cb83e0b6fa4f> in <module>()
      6 print(len(swc))
      7 print(swc)
----> 8 swc['shepherd']
      9 #raise NotImplementedError()

TypeError: list indices must be integers, not str



In [9]:

    
assert swc[0]==('i',43)
assert len(swc)==848









    



---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-9-79f30673d9f4> in <module>()
      1 assert swc[0]==('i',43)
----> 2 assert len(swc)==848

AssertionError:

Create a "Cleveland Style" dotplot of the counts of the top 50 words using Matplotlib. If you don't know what a dotplot is, you will have to do some research...



In [ ]:

    
# YOUR CODE HERE
raise NotImplementedError()



In [ ]:

    
assert True # use this for grading the dotplot