Study material generated by AI from this openly licensed book (CC BY-NC 3.0). Not affiliated with or endorsed by the publisher.
Think Python, 2nd Edition, by Allen B. Downey, Green Tea Press, licensed under CC BY-NC 3.0. Read the original free
Chapter 13 · pp. 147–158
This chapter uses a few text-processing projects to practice choosing the right data structure for a job. You will count the words in a book, find the most common ones, pick random words, and generate new text with Markov analysis. Along the way you will also learn about random numbers, optional parameters, and a set of debugging strategies.
To study word frequency, a program reads a file one line at a time and splits each line into words. Raw words are messy, though. "The", "the" and "the," would be counted as three different words. So each word is stripped of whitespace and punctuation and converted to lowercase before it is counted. The string module helps here: string.punctuation holds the punctuation characters and string.whitespace holds spaces, tabs, newlines and similar characters. Both can be passed to strip. Methods such as replace and translate are other options. (pp. 147–149)
Strings are immutable, so strip and lower do not change the original word. They return new strings. The sample program also replaces hyphens with spaces before splitting, so that hyphenated words become separate words. (p. 149)
Building a histogram. A histogram here is a dictionary that maps each word to how many times it appears. The dictionary works as an accumulator. For each word, the program runs hist[word] = hist.get(word, 0) + 1. If the word is new, get returns 0, so the entry starts at 1. If the word has been seen, its count goes up by one. Two helper functions split the work: process_file loops over the lines, and process_line cleans and counts the words in one line. (p. 149)
Totals. The values are the counts, so sum(hist.values()) gives the total number of words. Each key is one distinct word, so len(hist) gives the vocabulary size. For the novel Emma, this gives 161,080 words in total and 7,214 different words. (pp. 149–150)
A dictionary cannot be sorted by its values directly. The fix is to build a list of (frequency, word) tuples. Python compares tuples starting with the first item, so putting the frequency first makes the sort go by frequency. Calling t.sort(reverse=True) puts the largest counts first, and t[:10] is the top ten. In Emma the leaders are "to", "the" and "and". (p. 150)
A function can give a parameter a default value in its definition. In print_most_common(hist, num=10), the num parameter is optional. Calling print_most_common(hist) uses 10. Calling print_most_common(hist, 20) overrides the default with 20. Required parameters must be listed before optional ones. (pp. 151, 156)
Suppose you want the words in a book that are missing from a word list. This is set subtraction: take the items in one collection that are not in another. The function subtract(d1, d2) loops over d1 and adds each key that is not in d2 to a new dictionary. The values do not matter, so they are set to None. For Emma, the leftover words include names, possessives, rare words like "rencontre", and a few ordinary words the list should have contained. (pp. 151–152)
Because only the words matter, Python's built-in set type does the same job with less code. Convert the book's words and the word list to sets and subtract one from the other. This is the idea behind Exercise 13.6. (p. 152)
A program is deterministic if it gives the same output every time for the same inputs. This is usually what we want from a calculation. Games and simulations are exceptions, because there we want unpredictable behavior. (pp. 148, 156)
A computer has trouble being truly nondeterministic. Instead it uses pseudorandom numbers. These come from a deterministic formula, but they look random to anyone who inspects them. Each call to random.random() returns the next number in a long series. (p. 148)
The random module has three basic tools:
random.random() returns a float from 0.0 up to, but not including, 1.0.random.randint(low, high) returns an integer that can equal either end, so random.randint(5, 10) may give 5 or 10.random.choice(seq) returns one random element of a sequence, such as random.choice([1, 2, 3]).(p. 148)
Suppose a word should be picked with probability proportional to how often it appears. The simple method builds a list with freq copies of each word and calls random.choice on it. This works, but it rebuilds a list as large as the whole book for every pick. Building it once helps, but the list is still huge. (p. 152)
A better method uses a cumulative sum and bisection search:
For example, with counts 2 and 1 for a and b, the cumulative list is [2, 3]. A random number of 1 or 2 lands at index 0 (a), and 3 lands at index 1 (b). That matches the probabilities 2/3 and 1/3. (p. 152)
Words picked at random from a book show the vocabulary but do not form sentences, because successive words are unrelated. A real sentence has structure. For instance, "the" is usually followed by a noun or adjective. (pp. 152–153)
Markov analysis captures this by mapping each prefix (a short sequence of words) to the suffixes (words that can follow it). In the song "Eric, the Half a Bee", the prefix "half the" is always followed by "bee". The prefix "the bee" is followed by either "has" or "is". The prefix can be any length, not just two. (p. 153)
Generating text. Start with a prefix and choose a random suffix for it. Then build the next prefix from the end of the old prefix plus the new word, and repeat. From the prefix "Half a", the next word must be "bee", so the new prefix is "a bee". That prefix can be followed by several words. The result is almost correct in grammar but not in meaning. Longer prefixes limit the choices more, so the text tends to make more sense. (pp. 153–154)
The Markov project needs three decisions: how to store prefixes, how to store the suffixes, and how to map one to the other. A dictionary is the obvious mapping. (p. 154)
shift(prefix, word) returns prefix[1:] + (word,).(p. 154)
When weighing options, consider four things: which operations are needed, how easy the code is to write, run time, and storage space. If you cannot tell which version is faster, you can implement both and compare them, which is called benchmarking. A practical alternative is to write the simplest version first and optimize only if it is too slow. The profile module can then show which parts take the most time. Saving space can sometimes speed a program up, but run time is often the bigger concern. (pp. 154–155)
There are five things to try on a hard bug: reading, running, ruminating, rubberducking and retreating. (p. 155)
If you get stuck on one strategy, try the others. (p. 156)
hist.get(word, 0) + 1 do the first time a word appears?most_common written as (frequency, word) rather than (word, frequency)?