The torn phone book: quantifiers

When you get in this morning, the director has yesterday's number plate pattern up on the screen. "Instead of writing \d four times, there's a way to just say 'four times'. That's today." Just then the door opens and the florist from down the alley walks in, holding a soggy wad of paper. "My regulars' phone book got soaked in the rain. I scanned it and turned it into text, but it's a mess."

Here is the list the OCR produced. Every number uses a different separator, and the last line looks off somehow.

kim   010-0000-1234   04542
lee   010 0000 9876   04545
park  02-0000-5678    04538
choi  010.0000.4321   04539
yoon  1234-5678-9012

The syntax that says how many times something repeats is called a quantifier. Today you'll use quantifiers to sort out this list.

3-1. Exactly how many: {m} and {m,n} (7 min)

A quantifier sets how many times the single piece right before it repeats. \d{4} is the same as \d\d\d\d. Let's shorten the number plate pattern from Lesson 2.

re.findall(r"\d{2}[가-힣]\d{4}", "12가3457 123가4567")   # ['12가3457', '23가4567']

It's shorter, but there's a problem. The newer plates issued since 2019 have three digits up front. From 123가4567 the pattern dropped the leading 1 and cut out just 23가4567.

{m,n} means at least m and at most n times. Change the front to \d{2,3} and it takes both two and three digits.

re.findall(r"\d{2,3}[가-힣]\d{4}", "12가3457 123가4567")   # ['12가3457', '123가4567']

• No spaces around the comma, as in {2,3}. Put a space in and it stops being a quantifier (see Dot's tip below).
• A postcode is five digits, so it's written \d{5}.

3-2. At least, at most: {m,} and {,n} (6 min)

You can leave one side of {m,n} empty.

• {m,} : m times or more, with no upper limit
• {,n} : anywhere from 0 to n times. Since 0 counts, it also matches a spot with no characters at all

re.findall(r"a{2,}", "a aa aaaa")   # ['aa', 'aaaa']
re.findall(r"\d{3,}", "1 22 333 4444")   # ['333', '4444']
re.findall(r"\d{,2}", "123")        # ['12', '3', '']

The '' at the end of the last result is a match at the very end of the string, where there are zero digits. You'll look at these empty matches closely in 3-6.

If a { isn't shaped like a quantifier, it's treated as a plain character. a{x} looks for the four characters a, {, x, }.

re.findall(r"a{x}", "a{x} ax")      # ['a{x}']
re.findall(r"a{2, 3}", "aa a{2, 3}")   # ['a{2, 3}']

3-3. The everyday three: * + ? (8 min)

The most common counts get one-character names.

re.findall(r"ab*", "a ab abbb")      # ['a', 'ab', 'abbb']
re.findall(r"ab+", "a ab abbb")      # ['ab', 'abbb']
re.findall(r"ab?", "a ab abbb")      # ['a', 'ab', 'ab']
re.findall(r"colou?r", "color colour colouur")   # ['color', 'colour']

? is a perfect fit for "a character that may or may not be there". The mobile numbers in the list use a hyphen, a space or a period as separator, depending on the line. Write the separator spot as [-. ]? and it accepts one of the three, or none at all.

re.findall(r"010[-. ]?\d{4}[-. ]?\d{4}", phonebook)
# ['010-0000-1234', '010 0000 9876', '010.0000.4321']

As you learned in Lesson 2, a . inside brackets is a real period, and the - is at the very front, so it's a literal character.

3-4. A quantifier applies only to the piece right before it (5 min)

A quantifier attaches only to the single piece right before it. A piece is one character, one bracketed class, or one shorthand like \d. So ab+ doesn't mean "ab, several times" but "a, followed by b several times".

re.findall(r"ab+", "abbb abab")      # ['abbb', 'ab', 'ab']
re.fullmatch(r"ab+", "abab")         # None
re.fullmatch(r"(ab)+", "abab")       # <re.Match object; span=(0, 4), match='abab'>

To repeat several characters together, wrap them in parentheses to make one piece. (ab)+ is "ab, one or more times". Parentheses have another important job besides grouping, and you'll learn it in Lesson 5.

re.fullmatch matches only when the whole string fits the pattern. Lesson 4 covers the differences in detail.

3-5. Quantifiers are greedy (4 min)

By default, quantifiers are greedy. Within the allowed range, they take as much as they possibly can.

re.search(r"\d+", "tel 0100000")     # <re.Match object; span=(4, 11), match='0100000'>
re.search(r"\d{2,4}", "123456")      # <re.Match object; span=(0, 4), match='1234'>
re.findall(r"\d{2,4}", "123456")     # ['1234', '56']

\d{2,4} would settle for two digits, but it grabs four first. Only if the rest of the pattern fails does it give them back, one at a time. This "give one back and try again" is called backtracking, and in Lesson 8 it's what brings the agency to a standstill. You'll also learn the lazy quantifier +?, which takes as little as possible, at that point.

3-6. Finding them all: findall and finditer (10 min)

Now let's gather everything found in the whole list. Say the list above is stored in a string called phonebook.

re.findall returns the matched text as a list of strings. That's how it behaves when the pattern has no parentheses; with parentheses, see Lesson 5.

re.findall(r"\d{5}", phonebook)     # ['04542', '04545', '04538', '04539']

re.finditer returns an iterator that hands you Match objects one at a time. Use it when you need the positions (span) too.

for m in re.finditer(r"\d{5}", phonebook):
    print(m.group(), m.span())
# 04542 (22, 27)
# 04545 (50, 55)
# 04538 (78, 83)
# 04539 (106, 111)

• An iterator finds matches one at a time as you ask for them, so it saves memory even on very long strings.
• Once an iterator is used up, it's done. To loop again, call re.finditer again.

The thing to watch out for here is empty matches. *, ? and {,n} allow zero repetitions, so they succeed even at a spot with no characters at all. findall puts those empty matches into the result as ''.

re.findall(r"\d*", "a12b")    # ['', '12', '', '']
re.findall(r"\d+", "a12b")    # ['12']

One empty match before a, then 12, one empty match before b, and one at the end of the string. When you're collecting something, use + or {1,}, which don't allow zero.

Cracking the case (10 min)

A phone number is an area code or prefix of 2–3 digits, a middle of 3–4 digits, and a final 4 digits. The separators may or may not be there. A postcode is five digits.

phones = re.findall(r"\d{2,3}[-. ]?\d{3,4}[-. ]?\d{4}", phonebook)
print(phones)
# ['010-0000-1234', '010 0000 9876', '02-0000-5678', '010.0000.4321', '234-5678-9012']

postcodes = re.findall(r"\d{5}", phonebook)
print(postcodes)   # ['04542', '04545', '04538', '04539']

Four phone numbers and four postcodes, collected. But what is the fifth phone number, 234-5678-9012? The florist looks at the screen and shakes her head. "That's not a phone number. That's a note of my card number."

re.search(r"\d{2,3}[-. ]?\d{3,4}[-. ]?\d{4}", "yoon  1234-5678-9012")
# <re.Match object; span=(7, 20), match='234-5678-9012'>

The pattern skipped the first character 1 of 1234 and started matching at position 7, right in the middle of a number. It's the same accident as 23가4567 in 3-1.

The director stares at the last line for a long time. "It started in the middle of a number. This pattern doesn't know where a number begins or ends." In the next lesson you'll learn to write those boundaries into a pattern.

Exercises

1. Predict what \d{2,3}[-. ]?\d{3,4}[-. ]?\d{4} finds in 01000001234 (a number with no separators), then run it.
2. Predict the result of re.findall(r"\d?", "a1"). How many empty strings are there?
3. Use re.finditer to find the phone numbers in the list, and print each number with its start position, one per line.