PLS INDENT THE CODE :)

N-grams Overview An n-gram in the context of parsing natural languages such as English- -is a sequence of n consecutive tokens (which we might define as characters separated by whitespace) from some passage of text. Based on the following passage I really really like cake We have the following 2-grams [('I, 'really'), (really, 'really), (really,like', 'like', "cake. 1 And the following 3-grams [('I, 'really, 'really'), (really', 'really', 'like (really', 'likecake.')] (l omit a 1-gram listing because it would merely be a list of all tokens in the original text.) Among other things, n-grams are useful for describing the vocabulary of and statistical correlation between tokens in a sample body of text (e.g., as taken from a book). We can use an n-gram model to determine the likelihood of finding a particular sequence of words after another. This information, in turn, can be used to generate passages of text that statistically mimic the sample We can convert the above 3-gram list into the following lookup structure (i.e., a dictionary mapping strings to lists of 2-tuples , where the first token of each n- gram maps to all sequences that follow it in the text: ('I': really,"really, really''really, 'like', like, 'cake. '] We can now generate passages of text using the following method 1. Select a random key and use it as the start token of the passage. It will also serve as the current token for the next step 2. Select a random tuple from the list associated with the current token and append the sequence to the passage. The last token of the selected sequence will be the new current token. 3 If the current token is a key in the dictionary then simply repeat step 2, otherwise select another random key from the dictionary as the current token and append it to the passage before repeating step 2 Eg. , we might start by selecting T in step (1), which gives us ( ' really 'really' ) as our only choice in (2). The second ' really' in that tuple is the new current token (which is a valid key), which takes us back to (2) and gives us a choice between two tuples. If we choose ('like, 'cake.', then we have 'cake.' as our new current token it is not a key in the map, however, so we'd have to choose a new random key if we wanted to generate a longer passage. Either way, the passage we've generated thus far is 'I really really like cake. ' (which also happens to be the original passage) Here's a lengthier passage that could be generated from the 3-gram dictionary abovenote that for clarity lI've added 's every time a new random key is selected (i.e., when the previous token isn't a key in the dictionary) really like cake. * really really really like really like cake. "I really really really like really This gets more interesting when we build n-gram dictionaries from lengthier bodies of text. For instance, the following text was generated (with a little programmed embellishment for prettier capitalization and punctuation) from a 3-gram dictionary extracted from Romeo's famous balcony monologue Lamp her eyes were there they in their spheres till they in her eyes in all the fairest stars in all the heaven having some business do wear it is my love! O it is envious her cheek would through the heaven having some business do entreat her eyes were there they in their spheres till they in her eyes to For reference, here is the dictionary entry for the token 'her used to generate the above her [ (maid', 'art'), maid', 'since, ('vestal', 'livery'), 'eyes', to ('eyes', 'were, 'head?, The' ) ('cheek', 'would') 'eyes, 'in'), ('cheek', upon, ('hand! , 0' If you haven't already guessed it, your assignment is to implement a function that constructs an n-gram dictionary from a list of strings (tokens), and another that returns a passage of text generated from a given n-gram dictionary And now for some simple tests In from unittest import TestCase tc-TestCase () simple toks-t.lower) fortin 'I really really like cake. .split()] compute ngrams (simple toks) tc.assertEqual (compute_ngrams (simple_toks), ('i': [('really ,, like: ( cake.',), really'really',, 'like,]) tc.assertEqual (compute_ngrams (simple_toks, n-3), ('i': 'really,"really really 'really,'like, ('like cake. ')])) romeo-toks [t. lower() for t in ROMEO-SOLILOQUY. split()] = dct compute_ngrams (romeo_toks, n-4) dctI 'but' ] tc.assertEqual (dct 'but'l, [ sick'and'green''fools' do''wear)) tc.assertEqual (dct['it', [ ('is',"the, "east,', off.', 'it', is ('is', "mylady,) (is', 'my,'love! (were', "not', 'night. "1) I've also placed the entire text of Peter Pan (courtesy of Project Gutenberg) on the server, to be used to stress test your function just a bit. The following code reads the passage of the file (f you're not working on the course server this won't work for you) PETER_PAN_FILENAME /srv/cs331/peterpan.txt' with open (PETER_PAN_FILENAME) as infile: In pp text infile.read() print (pp_text[1361:1949]) Time for some larger test cases! In [ tcTestCase() pp-toks = [t, lower() for t in pp-text, split()] dct compute_ngrams (pptoks, n-3) tc.assertEqual (dct['crocodile', (passes ('that', 'happened' uld', 'have ('was in'), ('passed ('is','about'), ("climbing, it., ('that, 'was), "pass', 'by'), ("and, "let', ('was, among), ('was, 'waiting')]) tc.assertEqual (len (dct[ 'wendy'1), 202) tc.assertEqual(len (dct 'peter.(,243 Random selection One more thing before you start work on generating passages from an n-gram dictionary: we need a way to choose a random item from a sequence The random.choice function provides just this functionality. Consider (and feel free to play with) the following examplesyou should, at the very least, evaluate the cell a few separate times to see the results In import random print (random.choice('lions, "tigers "bears' ])) print (random.choice (range (100))) print (random.choice( 'really'like', (like'cake')])) Note that a separate tutorial on random number generators (and other random module APIs) will be posted separately, but for now just understanding how to use random.choice should be sufficient for this assignment. gen passage Finally, you're ready to implement gen_passage, which will take an n-gram dictionary and a length for the passage to generate (as a token count) As described earlier, it will work as follows 1. Select a random key from the dictionary and use it as the start token of the passage. It will also serve as the current token for the next step 2. Select a random tuple from the list associated with the current token and append the sequence to the passage. The last token of the selected sequence will be the new current token. 3 lf the current token is a key in the dictionary then simply repeat step 2, otherwise select another random key from the map as the current token and append it to the passage before repeating step 2 You will use random.choice whenever a random selection needs to be made. In order for your results to be reproduceable, it is vital that when selecting a random key from the ngram dictionary you do so using the following bit of code (assuming ngram dict is the dictionary) random.choice(sorted (ngram dict.keys))) In def gen_passage (ngram_dict, length-100): YOUR CODE HERE raise NotImplementedError() For the following test cases to work, it is critical that you do not invoke random.choice more than is absolutely necessary, and only as prescribed in the steps described above! Note that in addition to the automated test cases, we'll also be manually grading your code above. In [ ]: tc = TestCase() random.seed (1234) simple_ toks[t.lower) for t in 'I really really like cake.".split()] tc.assertEqual (gen_passage (compute_ngrams (simple_toks), 10), like cake. i really really really really like cake. i') random. seed (1234) romeo-toks = [t. lower() for t in ROMEO-SOLILOQUY, split()] tc.assertEqual(gen_passage (compute_ngrams (romeo_toks), 10), too bold, \tis not night. see, how she leans her')