Dictionaries and the telegraph

The last chapter stopped halfway. Python needed a fraction of a second to say how many times the word “war” occurs in War and Peace: 292. But counting every word of the novel didn’t work out. Two parallel lists, of words and of their counters, ran slower the longer the text grew: to find a word’s counter, the program had to go through all the known words from the beginning. On the whole novel that takes about ten seconds; on a library, hours.

We need something that goes from a word straight to its counter, like a reference book you open at the right letter. Python has it, and it is called a dictionary. We’ll learn it in a fitting place: a telegraph office, where every word cost money and the length of a letter was measured in dots. The office takes orders from the editors of a magazine who are preparing an issue about Tolstoy’s novel. They read it, as most readers of this page do, in English, in the translation by Louise and Aylmer Maude. Here is the first order.

STOP is not an order to stop. Telegrams were paid for by the word, which is where telegraphese comes from, a style without a single word to spare. Punctuation was spelled out too: a period became the word STOP, paid for like any other word. Answering this telegram will take us half the chapter. We begin with the telegraph itself, whose history had a dictionary long before Python did.

Morristown, 1838: the dictionary that was thrown away

Vail counted letters in order to hand out codes. We’ll do the same with War and Peace and check whether the short codes went to the frequent letters. But first, the code itself: the same kind of dictionary, only for letters.

The code table

Morse code is a table: each letter has its code. A telegraphist needs to find a letter’s code quickly. You could keep such a table as a list of pairs, like ELIZA’s rules in the last chapter, but then every letter would have to be searched for by going through the list. For tables of “what goes with what” Python has a structure of its own:

Curly braces, and inside them pairs separated by commas: to the left of the colon is what we look up, to the right what we find. Such a structure is called a dictionary; the left part of a pair is the key, the right part the value. The expression code["o"] looks like a list index, except that inside the square brackets, in place of a position, is the key itself. len counts the pairs, and in asks whether there is such a key. Keys only, though: "---" in code gives False, because in doesn’t look at the values.

A dictionary can be added to and corrected as you go.

Assigning to a new key adds an entry, and assigning to an old one replaces the value: a dictionary never holds two entries with the same key. Entries are kept in the order they were added. Asking for a key that isn’t there ends in a KeyError, and the traceback names the key. When a missing key is an ordinary event, you ask with the method get: it returns the value if the key is there, and its second argument if it isn’t.

Here is the whole alphabet, the International Morse code for the 26 letters of English, and a function that turns a telegram into dots and dashes. Letters in the code are separated by spaces, words by a slash.

Dots and dashes differ in how long they last. Their length is measured in units: a dot sounds for one unit, a dash for three, the pause between signals inside a letter lasts one unit, the pause between letters three, between words seven. Type a telegram of your own into the machine below and compare how many units “e” and “q” cost.

The reverse dictionary, code → letter, is made from the forward one: go through the pairs and swap the key and the value in each. It is one of the tasks at the end of the chapter.

The type case

Our type case is the novel itself: 3.2 million characters in the Maudes’ translation. But first a bet, about the Russian original.

We’ll count with a dictionary: the key is a letter, the value is how many times it has occurred. Here is the technique on a short word. Press “Steps” and watch the dictionary grow: a new letter gets an entry with the counter 1, a familiar one gets one added.

All the work happens in the line counts[ch] = counts.get(ch, 0) + 1. On the right, get fetches the letter’s old counter, or zero if the letter hasn’t occurred yet; on the left, the result goes back under the same key. This line is worth remembering, because it counts anything: letters, words, visitors to a website, errors in a server log. Now for the whole novel. The course module cs.texts hands it over as one string.

Two and a half million letters in less than half a second. A telegraph knows no capital letters, which is why the text goes to lower case first. All that’s left is to put the letters in order of frequency. A dictionary can’t sort itself, but you can go through it: the method items() hands out the “key, value” pairs, and the loop unpacks each pair into two variables, like a tuple in Chapter 6. We put the pairs into a list the other way round, number first and letter second, and sort it in decreasing order: tuples are compared by their first item first.

We have hidden the table MORSE in the course module cs.morse, along with the function duration, which counts the units of a code: one for each dot, three for each dash, plus the pauses between them. The surprise is in the fourth row. O, the fourth most frequent letter of the novel, is sent as three dashes, 11 units: only three letters take longer, and each of them makes up less than 2% of the text. E and T are short, as frequent letters should be. O was unlucky. The table is International Morse, which differs from Vail’s code. When the code was adapted for European lines, first by the German telegraph engineer Friedrich Clemens Gerke in 1848 and then at an international telegraph conference in Paris in 1865, codes with gaps inside them were done away with, and O, which had been a dot, a pause and a dot, became three dashes. In Russian, O fared worse still: in the Russian alphabet of 1856 Russian letters took the codes of similar Latin ones, and O, the most frequent letter of Tolstoy’s text, got the same three dashes.

To see what that bad luck costs, take the same 26 codes, sort them by duration and hand them out to the letters by frequency, the shortest code to the most frequent letter. Then compare how many units the whole novel takes.

The method values() hands out only the values of a dictionary, without the keys; its sibling keys() hands out only the keys. In an f-string, :, splits a number into groups of three digits, and :.0% shows a fraction as a percentage.

The same 26 codes, handed out by Vail’s rule, would send the novel only 4% faster: for all of O’s bad luck, the International code still keeps close to the order of English letter frequencies. Go back to the machine, flip the switch to “by frequency” and type your telegram again. The best possible code for given frequencies is built from scratch by Huffman’s algorithm. We’ll build it in Chapter 23, in Chapter 47 it becomes part of ZIP, and “Mathematics, the Queen of the Sciences” has a detailed account of why no code can do better.

Why a dictionary is fast

We counted two and a half million letters in less than half a second, while the parallel lists of the last chapter took most of a second over eighty thousand words. The difference lies in how the counter is found. Picture two clerks. The first keeps a ledger: row after row of “word, how many times.” To add one to a word, he runs his finger down the ledger from the top until he finds the word’s row. The second keeps a card index: every word has a drawer of its own with a label, and he opens the right drawer at once. Give them the same text, the famous sky over Austerlitz.

The card index needs one look for each word, while the ledger takes longer to search the more rows it has. On a passage of 128 words the ledger needs almost thirty times as many looks. On the whole novel the first clerk would look through about 950 million rows, some 1,700 for every word, and the second would open 562,000 drawers, one per word. How a dictionary knows where the drawer is without searching the others is a story for Chapter 16: inside it is a hash table. For now one fact is enough: looking up a key in a dictionary takes about the same time however many entries it holds.

The answer to the editors

Now we can answer the first telegram. The novel is cut into words by the function from the end of the last chapter; it lives in the course module under the name words: lower case, punctuation trimmed off the ends.

Hundredths of a second instead of ten seconds: the same technique as with the letters, only the keys are now words. “War” occurs 292 times, “peace” 108 and “Natasha” 1,091, plus more than a hundred times as “Natasha’s,” which our function counts as a word of its own. This edition also sets its dashes without spaces, so for our function “him—he” is a single word, and nearly two thousand such glued pairs have crept in among the 20,478. What counts as a word is the programmer’s decision, and the answers depend on it; the search engines of Chapter 48 spend a good deal of effort on that question.

All that remains is to find the most frequent words. That is the familiar sorting of pairs.

At the top is the glue of the language: “the,” “and,” “to,” “of,” “a.” The first word with a meaning of its own is “said,” in 26th place: much of the novel is conversation. “Prince” stands in 39th place, Pierre in 41st, Natasha in 61st, and “war” only in the third hundred. Its exact place is a matter of chance: three words occur exactly 292 times, “war,” “toward” and “position,” and the sort decides the order among equals. The last loop finds a word’s place by going through the list. For five words that’s bearable; for a thousand it would be wiser to set up one more dictionary, word → place.

Zipf’s law

Before answering, go back to the numbers in Reply No. 1. “The” occurs 34,388 times, “and” 22,075, “to” 16,631, half as often as “the.” Frequency falls as the rank grows, and roughly in step with it: the word in place $r$ occurs about $r$ times less often than the first. The French stenographer Jean-Baptiste Estoup noticed the pattern early in the twentieth century, and the American linguist George Kingsley Zipf, who wrote several books about it in the 1930s and 1940s, made it famous. It is called Zipf’s law: the frequency of a word is roughly inversely proportional to its rank,

The law is easiest to check by eye on a plot with logarithmic scales: on them the power law $C/r$ turns into a straight line with slope $-1$. Matplotlib draws such a plot on the server.

From about the tenth place to the thousandth, across two orders of magnitude, the points hug a straight line. The very first places lie below it (“the” occurs half as often as the dashed line promises), and past the two-thousandth place the points sag below the line and break into steps: the frequencies there are small whole numbers, 3, 2, 1. For Tolstoy’s original the dashed line would be $45\,000 / r$. The translation has more words in all and fewer different ones, so each word repeats more often, and our line runs higher: it is drawn by [65000 / r for r in ranks], which builds a list from an expression for every $r$. Such list comprehensions are the subject of Chapter 10.

The last line answers the editors: 8,451 words out of 20,478, two in every five, occur only once, and nearly two thousand of them are the glued pairs like “him—he.” This too follows from Zipf’s law: in the long tail every word is rare, but together they make up a large part of the vocabulary. Similar laws turn up outside language, in the populations of cities, for example: a country’s second-largest city is often about half the size of the largest, although for cities the law holds far from everywhere. There is no single agreed explanation of why this happens, but the consequence is very practical: any text will contain plenty of words you have never seen before. Search engines, compression programs and language models all have to reckon with it.

Grouping: anagrams for a crossword

Anagrams are words made of the same letters: “listen” and “silent,” “stone” and “notes.” Checking every pair of twenty thousand words means more than two hundred million pairs. There’s a better way: give every word a key that all its anagrams share. Put a word’s letters in alphabetical order, and anagrams come out the same: sorted("listen") and sorted("silent") both give the list ['e', 'i', 'l', 'n', 's', 't'], and "".join(...) glues it into the string "eilnst". All that remains is a dictionary whose key is such a string and whose value is the list of all words with that key.

This is grouping, the second main use of a dictionary after counting. The scheme is the same: work out a key for every item, then either add to a counter or append to a list. If the key isn’t there yet, start an empty list for it first. The construction set(...) removes repeated words; there is more about sets below. And the string method isalpha tells you whether a string consists of letters only.

“Post, pots, spot, stop, tops,” with the telegraph’s own STOP among them; “evil, live, veil, vile”; “danger, garden, ranged”; and further down the list of 66 groups, “Andrew, wander, warned” and even “Amstetten, statement, testament,” after an Austrian town of the novel’s 1805 campaign. The editors will have plenty to choose from. You can think up a different key, too, and get a different grouping altogether. Try it in the sorting office below.

What follows a word

You can group by something other than a property of the word itself. Group every word of the novel by the word in front of it, and the result is a dictionary of “word → the list of all the words that followed it in the novel.” For “prince” the list holds “andrew” 976 times, “vasili” 196 times and hundreds of other words. A dictionary like this can make up sentences. Start with the word “prince,” pick a random “successor” from its list, then a successor of the successor, and so on fifteen times.

Run it a few times. It isn’t Tolstoy, but it has a Tolstoyan air: every two neighboring words did stand side by side in the novel, though the whole makes no sense. The function random.choice picks a random item of a list, and since “andrew” is in the list 976 times, it comes up more often than the rest. This is the simplest language model: all it knows is which word followed which. Large language models take thousands of preceding words into account, and in place of a dictionary they have a trained network; that is the subject of Chapter 63 and of the Sprout course on this site. But they too started from the idea of counting what follows what.

Sets

Sometimes there’s nothing to count, and it’s enough to know which words are there. For that Python has the set, a dictionary without values, keys alone. Its items don’t repeat and have no order, and the in test is instant, like a key lookup. A set is built by the function set from any list, or written in braces without colons: {"war", "peace"}. An empty set can only be written set(), because {} is an empty dictionary.

Sets can do everything they do in school math: the intersection a & b (what is in both), the union a | b (what is in at least one), the difference a - b (what is in the first but not the second) and the symmetric difference a ^ b (what is in exactly one). Try them on two short texts.

Now we can answer the editors: compare the vocabulary of the opening books with that of the epilogues and find the words that appear nowhere in the novel before the epilogues.

The first three books, all set in 1805 and making up the first volume in Russian editions, are salons, armies and Kutuzov, who doesn’t appear in the epilogues even once. The epilogues are family and philosophy. “Rulers,” “deity,” “astronomy” and “electricity” appear for the first time on the last pages; “power,” mentioned 16 times in the first three books, comes up 106 times in the epilogues, and “history” goes from 3 to 107. The second epilogue is Tolstoy’s essay on what moves history, and the frequency dictionary sees it without reading a line. Even the word at the top of the new ones, “rulers,” comes from it: the essay keeps asking how much power rulers have over the movements of nations.

Sets have one more virtue: speed. The test x in list goes through the list; x in set looks straight into the right drawer.

The word “computer” isn’t in the novel, and to make sure of that the list goes through all 562,000 words. The set needs one look: the difference is tens of thousands of times. How such differences are worked out and written as formulas is the subject of Chapter 13.

Why a key can’t be a list

Now we have to count pairs of words, and the key has to be a pair. The first thing that comes to mind is a list of two words.

The tuple is accepted as a key, but on the list Python stops with the error TypeError: unhashable type: 'list'. The reason is that lists can change. In Chapter 6 two names pointed at one list, and a change made through one name showed through the other. A dictionary files its entries in drawers according to what the key is at the moment of writing. If a list could be a key, it could later be changed through another name, by append or sort, and the entry would stay in the drawer labeled with the old key: you couldn’t find it by the new key or by the old one. So a key can only be an immutable value: a number, a string, a tuple of immutable values. For the same reason the items of a set can’t be lists. What the word unhashable means and how the drawers work is explained in Chapter 16.

The words that most often stand side by side in the novel are “of the,” 4,032 times, followed by “to the” and “in the”: the glue of the language again, and all of the top eight are made of it. The first pair with a meaning of its own is “prince andrew,” 976 times, in ninth place, while “princess mary,” 464 times, comes thirty-seventh. The line for n, (a, b) in top[:10] unpacks every item, a tuple of a number and a tuple of words, into three names at once; the parentheses show how the parts are nested.

Ready-made tools

Counting and grouping are needed so often that Python’s standard library has ready-made dictionaries with special abilities for them. They live in the module collections.

Counter counts whatever it is given, and the method most_common(k) hands out the k most frequent pairs, which is what we did by hand with sorting. For a missing key Counter answers zero, where an ordinary dictionary would raise an error. defaultdict is a dictionary that creates the entry for a new key by itself: defaultdict(list) puts an empty list there, defaultdict(int) a zero. The list in the parentheses has no parentheses of its own: we pass not a list but the function that knows how to make one, and the dictionary calls it when needed. A function as an argument of another function is the subject of Chapter 10.

Writing the manual versions wasn’t wasted effort. Now you know what happens inside, and you can write a count where Counter won’t do, for instance when each word should add its length to the counter rather than one.

Dictionaries inside dictionaries

A value in a dictionary can be anything: a number, a string, a list or another dictionary. The results of our work fit nicely into one nested structure.

report["characters"]["Natasha"] reads from left to right: in the report, take the characters; among the characters, take Natasha. That’s how you get down to any depth. The function json.dumps turns a dictionary into text in the JSON format: ensure_ascii=False leaves letters outside English, such as the é of “café,” as they are instead of turning them into escape codes, and indent=2 lays out the indentation. The output is almost indistinguishable from a Python dictionary. JSON was born in JavaScript but long ago became the common language for exchanging data, from websites to phone apps. When a weather app shows you the temperature, it has almost certainly received JSON from a server.

The reverse function, json.loads, turns JSON text into Python dictionaries and lists. That’s how data comes from the website of the United States Geological Survey, the source of the earthquake catalog of Chapter 6. Here is the strongest quake of that night, in the form the server sends it, only shortened.

The time in the JSON is a number: milliseconds since January 1, 1970, a common way for computers to store moments in time. The coordinates come in an unexpected order, longitude first and latitude second. That is the convention of the GeoJSON format, and it pays to remember it: mix them up, and the program will try to put a point at latitude 160°, which doesn’t exist. Reading unfamiliar JSON is everyday work for a programmer: you study the nesting and walk down the keys.

Telegrams to take home

Four tasks. The tests call your functions and compare what they return with what is expected.

What next

The last request looks simple. A folder is a dictionary: a file name → its size in kilobytes, the name of a folder inside → a dictionary of its contents.

On the first level a loop, on the second a loop inside a loop, and on the third we gave up: “old” sits inside “volume 2,” and “older still” inside “old.” To go down to any depth, we would have to know in advance how many loops to nest, but folders on a disk, like JSON from a server, can be nested as deep as you like. Consider the task once more: the size of a folder is the sum of the sizes of its files plus the sizes of the folders inside it. Inside the task sits the same task, only smaller. How to solve tasks like that, and why the same idea gives the Tower of Hanoi, a snowflake and the tree from Chapter 0, is the subject of Chapter 9.