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
{'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 |
All three approaches count frequencies, but they differ in how they handle characters that were not known ahead of time.
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- 1The dictionary begins with no frequency entries.
- 2The loop considers each character in the input.
- 3The condition distinguishes a first encounter from a repeated encounter.
- 4A first encounter adds the character with a count of 1.
- 5A repeated encounter updates the existing count by increasing it.
- Start with an empty dictionary.
- Process one character at a time.
- Check whether the current character is already a key.
- Create a new key with count 1 when the character is new.
- Increment the existing count when the character has appeared before.
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.
- 1Read b
The dictionary does not contain b, so add b with count 1.
- 2Read r
The dictionary does not contain r, so add r with count 1.
- 3Read o
The dictionary does not contain o, so add o with count 1.
- 4Read n
The dictionary does not contain n, so add n with count 1.
- 5Read t
The dictionary does not contain t, so add t with count 1.
- 6Read o again
The key o already exists with count 1, so increment its count to 2.
- 7Read s
The dictionary does not contain s, so add s with count 1.
- 8Read a
The dictionary does not contain a, so add a with count 1.
- 9Read u
The dictionary does not contain u, so add u with count 1.
- 10Read r again
The key r already exists with count 1, so increment its count to 2.
- 11Read u again
The key u already exists with count 1, so increment its count to 2.
- 12Read 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
Common mistake Treating every character as new
What it looks likeAdding a fresh entry whenever a character is read, even when that character is already a key
Why it failsRepeated characters need their existing count increased. Treating them as new prevents the dictionary from recording the true frequency.
Do this insteadCheck whether the key exists. Initialize a missing key to 1; otherwise increment its current value.
Common mistake Incrementing before creating a missing key
What it looks likeTrying to increase the count of a character that is not yet in the dictionary
Why it failsThe first encounter has no existing count to update.
Do this insteadUse the new-character branch first and assign the initial count of 1.
Common mistake Assuming the input must be limited to English letters
What it looks likeDesigning the counter only around the 26 letters of the alphabet
Why it failsThe input may include digits, punctuation, or Unicode symbols.
Do this insteadUse dictionary keys for the characters that actually arrive.
Common mistake Confusing a histogram with a graph only
What it looks likeThinking that frequency information becomes a histogram only after drawing bars
Why it failsIn computing, a histogram can simply be a collection of counters.
Do this insteadRecognize 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.
- 1Read l
Create l with count 1.
- 2Read e
Create e with count 1.
- 3Read t
Create t with count 1.
- 4Read t again
Increment t from 1 to 2.
- 5Read e again
Increment e from 1 to 2.
- 6Read r
Create r with count 1.
{'l': 1, 'e': 2, 't': 2, 'r': 1}
The Reusable Pattern
- 1Character counting can use separate variables, a list, or a dictionary.
- 2Variables and lists require advance knowledge of the characters that may appear.
- 3A dictionary creates entries only for characters that actually occur.
- 4The central pattern is: if the key is missing, initialize it to 1; otherwise increment its value.
- 5The 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.