Building Lookup Tables
Dictionaries outperform lists and variables for character counting because they only allocate space for characters that actually appear, not for every possible character.
From Text to Tallies
Suppose you want to analyze a word and discover which letters appear most frequently. For the word brontosaurus, the letters r, o, s, and u each appear twice, while b, n, t, and a each appear once. This task is called frequency counting. The collection of counters that records these frequencies is called a histogram. In computing, the histogram does not need to be a graph: a dictionary containing the character counts is already the histogram.
What do you think happens?
After processing every character in brontosaurus, what will the dictionary contain?
Reveal answer
Answer: {'b': 1, 'r': 2, 'o': 2, 'n': 1, 't': 1, 's': 2, 'a': 1, 'u': 2}
Each character is counted when it appears. The first appearance creates an entry with count 1. A later appearance finds the existing entry and increments its count.
Three Storage Strategies
There are three main strategies for storing character frequencies. The first uses a separate variable for each possible character. The second uses a list with one position for each possible character, converting a character into an index with ord(). Both approaches require you to decide in advance which characters may appear. The third uses a dictionary, which creates entries as characters are encountered.
| Approach | How counts are stored | Main limitation |
|---|---|---|
| Separate variables | A counter is assigned to each character | The possible characters must be decided in advance |
| List | A character is converted to an index, such as with ord() | The full range of possible characters and their numeric codes must be known |
| Dictionary | A character is a key and its frequency is the value | The source emphasizes its advantages rather than a comparable fixed-range limitation |
The dictionary approach is more flexible because it does not require advance knowledge of which letters will occur. It can create entries for digits, punctuation, or Unicode symbols when those characters appear. A list approach would require knowledge of the full possible range and its numeric codes, while separate variables would require additional named counters.
The First-Encounter Decision
counts = {} for c in text: if c not in counts: counts[c] = 1 else: counts[c] = counts[c] + 1
A lookup table connects a key to information about that key. In this frequency-counting pattern, each character is a key and its current frequency is the associated value. The dictionary itself contains the complete histogram.
Processing Each Character
Tracing brontosaurus
Build a frequency dictionary for the word brontosaurus.
Read b: The dictionary does not contain b, so add b with count 1.
Read r: The dictionary does not contain r, so add r with count 1.
Read o: The dictionary does not contain o, so add o with count 1.
Read n: The dictionary does not contain n, so add n with count 1.
Read t: The dictionary does not contain t, so add t with count 1.
Read o again: The key o already exists with count 1, so increment its count to 2.
Read s: The dictionary does not contain s, so add s with count 1.
Read a: The dictionary does not contain a, so add a with count 1.
Read u: The dictionary does not contain u, so add u with count 1.
Read r again: The key r already exists with count 1, so increment its count to 2.
Read u again: The key u already exists with count 1, so increment its count to 2.
Read s again: The key s already exists with count 1, so increment its count to 2.
The 12-character word has 8 unique letters. The resulting histogram is {'b': 1, 'r': 2, 'o': 2, 'n': 1, 't': 1, 's': 2, 'a': 1, 'u': 2}.
Why Sparse Storage Helps
A dictionary creates entries only for characters that actually appear. This is sparse storage: the table contains the observed characters and their counts, rather than reserved counters for every possible character. By contrast, using 26 variables or a 26-element list reserves room for every letter of the alphabet, including letters absent from the input.
Prefer the dictionary pattern when the possible characters are unknown, when the input may contain digits or punctuation, or when the same counting idea may later be applied to words or text in multiple languages. The source identifies this adaptability as the dictionary approach's decisive advantage.
Mistakes in Frequency Tables
Treating every character as new
Repeated characters need their existing count increased. Treating them as new prevents the dictionary from recording the true frequency.
Fix:
Check whether the key exists. Initialize a missing key to 1; otherwise increment its current value.Incrementing before creating a missing key
The first encounter has no existing count to update.
Fix:
Use the new-character branch first and assign the initial count of 1.Assuming the input must be limited to English letters
The input may include digits, punctuation, or Unicode symbols.
Fix:
Use dictionary keys for the characters that actually arrive.Confusing a histogram with a graph only
In computing, a histogram can simply be a collection of counters.
Fix:
Recognize the dictionary of character counts as the histogram.
Practice the Decision
Trace the dictionary for the input letter. Write the dictionary after each character is processed, then identify which steps create a new key and which steps increment an existing value.
Hints
- Start with an empty dictionary.
- The first l creates a new entry.
- The second l updates the existing l entry.
- The second e updates the existing e entry.
Practice answer
Count the characters in letter.
Read l: Create l with count 1.
Read e: Create e with count 1.
Read t: Create t with count 1.
Read t again: Increment t from 1 to 2.
Read e again: Increment e from 1 to 2.
Read r: Create r with count 1.
{'l': 1, 'e': 2, 't': 2, 'r': 1}
The Reusable Pattern
- Character counting can use separate variables, a list, or a dictionary.
- Variables and lists require advance knowledge of the characters that may appear.
- A dictionary creates entries only for characters that actually occur.
- The central pattern is: if the key is missing, initialize it to 1; otherwise increment its value.
- The resulting dictionary is a histogram because it stores the complete collection of frequency counters.
Key Takeaways
- A frequency count records how often each character appears.
- Three approaches are separate variables, an indexed list, and a dictionary.
- The dictionary approach adapts to characters discovered during processing and stores entries only for characters that appear.
- The if c not in d pattern separates first encounters from repeated encounters.
- A dictionary of counts is a histogram in computing.