lesson 51 String Algorithms · intermediate

Normalise text before you compare it

People type the same thing many ways: capitals, extra spaces, punctuation. Normalising maps every variant to one standard form, so comparisons and searches treat them as equal.

You'll be able to

Combine strip, lower and replace, keeping the new text each one returns
Build a cleaned text one character at a time: keep allowed characters, collapse repeated spaces
Reverse a text with [::-1] and test a palindrome on its normalised form

The idea

A search for night harbor should find the film stored as Night Harbor!, and a customer typing NORA garcia is the same person as Nora Garcia. == compares characters exactly, so the program has to bring both texts to one normal form first.

The usual steps are: strip() the ends, lower() the letters, replace characters that don't matter, and collapse runs of spaces into one. Strings never change in place: every method returns a new text, so keep it with text = text.strip().

Run each example to see what it prints. Running examples doesn't count toward progress.

example-1.py · One form for many spellings

def normalize(text):
    """Return text stripped, in lower case, with runs of spaces collapsed to one."""
    text = text.strip().lower()
    result = ""
    previous_space = False
    for ch in text:
        if ch == " ":
            if not previous_space:
                result = result + ch
            previous_space = True
        else:
            result = result + ch
            previous_space = False
    return result

print(normalize("  Nordic   CANDLE "))
print(normalize("nordic candle") == normalize("NORDIC  candle"))
name = "  Nora "
name.strip()
print("[" + name + "]")

Punctuation is often noise too. Instead of listing every character to remove, list the characters to keep and test each one with in. For a title search that is letters, digits and spaces; anything else is dropped.

A normalised form also makes palindromes easy to test. A slice can take a third number, the step: text[::-1] walks the whole text backwards, giving it reversed. A phrase is a palindrome if its normalised form equals its own reverse.

example-2.py · Titles without punctuation, and a palindrome

KEEP = "abcdefghijklmnopqrstuvwxyz0123456789 "

def letters_digits_spaces(text):
    """Return the lower-case text with only letters, digits and spaces kept."""
    kept = ""
    for ch in text.lower():
        if ch in KEEP:
            kept = kept + ch
    return kept

print(letters_digits_spaces("Night Harbor!") == letters_digits_spaces("night harbor"))
print(letters_digits_spaces("Wild Archive: Part 2 (Director's Cut)"))
phrase = letters_digits_spaces("Never odd, or even").replace(" ", "")
print(phrase, phrase[::-1], phrase == phrase[::-1])

When to use it: before comparing, searching, de-duplicating or counting anything a person typed. Normalise both sides the same way. Mistakes to avoid:

Calling a method without keeping its result.
Normalising only one side of a comparison.
Normalising away something that matters: C2 and c2 may be different codes in a product catalogue.

Review

Normalise both sides the same way before comparing: strip, lower, replace, collapse spaces.
Strings never change in place; keep each method's result.
Keep allowed characters one at a time; text[::-1] reverses a text.
Next: split normalised text into words and fields, and join them back.

Practise this

The shared start of several codes