Case Study: Text Processing in Everyday Apps

The Hidden String Operations in Your Daily Life

You've used a search engine, sent a text message with autocorrect, and (if you use email) probably had a spam filter save you from a Nigerian prince or two. All of these systems rely heavily on string processing — the same techniques you learned in Chapter 7, scaled up to handle millions or billions of operations per second.

This case study explores three everyday applications and shows how the string methods you now know form the foundation of systems used by billions of people.

Application 1: Autocorrect and Spelling Suggestion

When you type "teh" on your phone and it corrects it to "the," a string processing pipeline is at work.

Simplified Autocorrect Pipeline

Here's a stripped-down version of how autocorrect might work:

# A tiny dictionary for demonstration
DICTIONARY = {
    "the", "them", "then", "there", "these", "they",
    "this", "that", "than", "thank", "their",
    "hello", "help", "here", "her", "hero",
    "python", "program", "print", "process",
}


def edit_distance_one(word):
    """Generate all strings that are one edit away from `word`.

    Edits: delete a character, swap adjacent characters,
    replace a character, or insert a character.
    """
    letters = "abcdefghijklmnopqrstuvwxyz"
    results = set()

    # Deletions: remove one character
    for i in range(len(word)):
        candidate = word[:i] + word[i+1:]
        results.add(candidate)

    # Transpositions: swap adjacent characters
    for i in range(len(word) - 1):
        candidate = word[:i] + word[i+1] + word[i] + word[i+2:]
        results.add(candidate)

    # Replacements: change one character
    for i in range(len(word)):
        for c in letters:
            candidate = word[:i] + c + word[i+1:]
            results.add(candidate)

    # Insertions: add one character
    for i in range(len(word) + 1):
        for c in letters:
            candidate = word[:i] + c + word[i:]
            results.add(candidate)

    return results


def suggest(word):
    """Suggest corrections for a misspelled word."""
    word = word.lower().strip()

    # If it's already correct, no suggestion needed
    if word in DICTIONARY:
        return [word]

    # Find dictionary words that are one edit away
    candidates = edit_distance_one(word)
    suggestions = [w for w in candidates if w in DICTIONARY]

    return sorted(suggestions) if suggestions else [f"(no suggestion for '{word}')"]


# Test with common typos
test_words = ["teh", "helo", "pythn", "ther", "prgram"]
for typo in test_words:
    corrections = suggest(typo)
    print(f"  '{typo}' -> {corrections}")

Output:
  'teh' -> ['the']
  'helo' -> ['hello', 'help', 'hero']
  'pythn' -> ['python']
  'ther' -> ['the', 'them', 'then', 'there', 'they']
  'prgram' -> ['program']

String Operations at Work

Notice the string techniques in edit_distance_one: - Slicing (word[:i], word[i+1:]) to split words at every position - Concatenation (word[:i] + c + word[i+1:]) to build candidate words - lower() to normalize input - strip() to clean whitespace - The in operator to check dictionary membership

Real autocorrect systems (like those on your phone) use more sophisticated algorithms — learned language models, keyboard proximity data, and personal usage patterns — but the core operation is still string manipulation: generating candidates and checking them against a dictionary.

Application 2: Search Engine Query Processing

When you type a search query, the search engine doesn't just look for your exact text. It processes your query through several string transformation steps before matching it against its index.

Query Processing Pipeline

# Common English stop words (words too common to be useful for search)
STOP_WORDS = {
    "a", "an", "the", "is", "it", "in", "on", "at", "to", "for",
    "of", "and", "or", "but", "not", "with", "this", "that", "from",
    "by", "as", "are", "was", "were", "be", "been", "being",
    "have", "has", "had", "do", "does", "did", "will", "would",
    "can", "could", "should", "may", "might",
}


def simple_stem(word):
    """Very simplified stemming: remove common suffixes.

    Real stemmers (like Porter or Snowball) are much more sophisticated.
    """
    suffixes = ["ing", "tion", "sion", "ed", "ly", "er", "est", "ness", "ment", "s"]
    for suffix in sorted(suffixes, key=len, reverse=True):
        if word.endswith(suffix) and len(word) - len(suffix) >= 3:
            return word[:-len(suffix)]
    return word


def process_query(raw_query):
    """Process a search query through a simplified pipeline."""
    steps = {}

    # Step 1: Normalize case
    step1 = raw_query.lower()
    steps["1. Lowercase"] = step1

    # Step 2: Strip whitespace
    step2 = step1.strip()
    steps["2. Stripped"] = step2

    # Step 3: Tokenize (split into words)
    tokens = step2.split()
    steps["3. Tokenized"] = str(tokens)

    # Step 4: Remove punctuation from each token
    clean_tokens = []
    for token in tokens:
        cleaned = token.strip(".,!?;:'\"()-")
        if cleaned:
            clean_tokens.append(cleaned)
    steps["4. Cleaned"] = str(clean_tokens)

    # Step 5: Remove stop words
    meaningful = [t for t in clean_tokens if t not in STOP_WORDS]
    steps["5. Stop words removed"] = str(meaningful)

    # Step 6: Stem words (simplified)
    stemmed = [simple_stem(t) for t in meaningful]
    steps["6. Stemmed"] = str(stemmed)

    return steps, stemmed


# Process some example queries
queries = [
    "  What is the best programming language for beginners?  ",
    "How to fix Python indentation errors",
    "The History of Computing in the 20th Century",
]

for query in queries:
    print(f"\nQuery: {query!r}")
    steps, result = process_query(query)
    for step_name, value in steps.items():
        print(f"  {step_name}: {value}")
    print(f"  Final search terms: {result}")

Output:
Query: '  What is the best programming language for beginners?  '
  1. Lowercase: what is the best programming language for beginners?
  2. Stripped: what is the best programming language for beginners?
  3. Tokenized: ['what', 'is', 'the', 'best', 'programming', 'language', 'for', 'beginners?']
  4. Cleaned: ['what', 'is', 'the', 'best', 'programming', 'language', 'for', 'beginners']
  5. Stop words removed: ['what', 'best', 'programming', 'language', 'beginners']
  6. Stemmed: ['what', 'best', 'programm', 'languag', 'beginn']
  Final search terms: ['what', 'best', 'programm', 'languag', 'beginn']

Query: 'How to fix Python indentation errors'
  1. Lowercase: how to fix python indentation errors
  2. Stripped: how to fix python indentation errors
  3. Tokenized: ['how', 'to', 'fix', 'python', 'indentation', 'errors']
  4. Cleaned: ['how', 'to', 'fix', 'python', 'indentation', 'errors']
  5. Stop words removed: ['how', 'fix', 'python', 'indentation', 'errors']
  6. Stemmed: ['how', 'fix', 'python', 'indentat', 'error']
  Final search terms: ['how', 'fix', 'python', 'indentat', 'error']

Query: 'The History of Computing in the 20th Century'
  1. Lowercase: the history of computing in the 20th century
  2. Stripped: the history of computing in the 20th century
  3. Tokenized: ['the', 'history', 'of', 'computing', 'in', 'the', '20th', 'century']
  4. Cleaned: ['the', 'history', 'of', 'computing', 'in', 'the', '20th', 'century']
  5. Stop words removed: ['history', 'computing', '20th', 'century']
  6. Stemmed: ['history', 'comput', '20th', 'century']
  Final search terms: ['history', 'comput', '20th', 'century']

The critical insight: a 15-word query reduces to 4-5 meaningful terms. This is how search engines match your intent rather than your exact words — by normalizing, cleaning, and reducing text to its core semantic content, all through string operations.

Application 3: Spam Filter (Naive Keyword Approach)

Email spam filters use many techniques, but one foundational layer is keyword-based text analysis. Here's a simplified version:

# Spam indicators: words/phrases and their "spam scores"
SPAM_SIGNALS = {
    "free money": 5,
    "click here": 4,
    "limited time": 4,
    "act now": 4,
    "congratulations": 3,
    "winner": 3,
    "urgent": 3,
    "no obligation": 3,
    "100% free": 5,
    "dear friend": 3,
    "nigerian prince": 5,
    "wire transfer": 4,
    "unsubscribe": 1,
    "buy now": 3,
    "special offer": 3,
}

# Legitimate indicators
HAM_SIGNALS = {
    "meeting": -2,
    "attached": -2,
    "invoice": -1,
    "project": -2,
    "schedule": -2,
    "deadline": -2,
    "regards": -1,
    "team": -2,
}


def analyze_email(subject, body):
    """Analyze an email for spam indicators.

    Returns a score (higher = more likely spam) and matched signals.
    """
    # Combine and normalize
    full_text = (subject + " " + body).lower().strip()

    score = 0
    matched = []

    # Check for spam signals
    for phrase, points in SPAM_SIGNALS.items():
        count = full_text.count(phrase)
        if count > 0:
            score += points * count
            matched.append(f"+{points * count}: '{phrase}' (x{count})")

    # Check for legitimate signals
    for phrase, points in HAM_SIGNALS.items():
        count = full_text.count(phrase)
        if count > 0:
            score += points * count
            matched.append(f"{points * count}: '{phrase}' (x{count})")

    # Additional heuristics
    exclamation_count = full_text.count("!")
    if exclamation_count > 3:
        bonus = exclamation_count - 3
        score += bonus
        matched.append(f"+{bonus}: excessive exclamation marks ({exclamation_count})")

    all_caps_words = sum(1 for word in body.split() if word.isupper() and len(word) > 2)
    if all_caps_words > 2:
        score += all_caps_words
        matched.append(f"+{all_caps_words}: ALL CAPS words ({all_caps_words})")

    # Classify
    if score >= 8:
        verdict = "SPAM"
    elif score >= 4:
        verdict = "SUSPICIOUS"
    else:
        verdict = "LIKELY LEGITIMATE"

    return verdict, score, matched


# Test emails
emails = [
    {
        "subject": "Congratulations! You are a winner!",
        "body": "Click here to claim your free money. "
                "Act now, this is a limited time offer."
    },
    {
        "subject": "Friday standup notes",
        "body": "Hi team, the deadline has been moved to Friday. "
                "I've attached the updated schedule. "
                "Please review and confirm. Regards, Sarah"
    },
    {
        "subject": "New deals this week",
        "body": "Dear friend, check out our latest products. "
                "Buy now and save before the sale ends."
    },
]

for email in emails:
    print(f"\n{'='*60}")
    print(f"Subject: {email['subject']}")
    print(f"{'='*60}")
    verdict, score, matches = analyze_email(email["subject"], email["body"])

    print(f"  Verdict: {verdict} (score: {score})")
    print(f"  Signals detected:")
    for match in matches:
        print(f"    {match}")

Output:
============================================================
Subject: Congratulations! You are a winner!
============================================================
  Verdict: SPAM (score: 23)
  Signals detected:
    +5: 'free money' (x1)
    +4: 'click here' (x1)
    +4: 'limited time' (x1)
    +4: 'act now' (x1)
    +3: 'congratulations' (x1)
    +3: 'winner' (x1)

============================================================
Subject: Friday standup notes
============================================================
  Verdict: LIKELY LEGITIMATE (score: -9)
  Signals detected:
    -2: 'attached' (x1)
    -2: 'schedule' (x1)
    -2: 'deadline' (x1)
    -1: 'regards' (x1)
    -2: 'team' (x1)

============================================================
Subject: New deals this week
============================================================
  Verdict: SUSPICIOUS (score: 6)
  Signals detected:
    +3: 'dear friend' (x1)
    +3: 'buy now' (x1)

String Operations at Work

This spam filter uses: - lower() to normalize case (spammers mix CAPS to evade detection) - strip() to clean input - count() to find how many times a phrase appears - split() to break text into words - isupper() to detect ALL CAPS words - + concatenation to combine subject and body - The in operator implicitly through count()

The Bigger Picture

These three applications — autocorrect, search, and spam filtering — process billions of strings per day across the world's computing infrastructure. And they all rely on the same fundamental operations you learned in Chapter 7:

The techniques scale from a homework assignment to a global service. The algorithms get more sophisticated, but the building blocks are the same.

Discussion Questions

1. Autocorrect trade-offs: The edit_distance_one function generates thousands of candidates for a single word. Why might this be acceptable for a phone keyboard but problematic for a search engine processing millions of queries per second? What trade-off is being made?

2. Stop words and meaning: Look at the search query processing example. "The History of Computing" reduces to ['history', 'comput', '20th', 'century']. Can you think of a query where removing stop words would change the meaning? (Example: "to be or not to be" — a Shakespeare search.)

3. Spam evolution: The keyword-based spam filter is easily fooled by misspellings ("fr3e m0ney") or character substitutions. How would you extend the filter to handle these evasion techniques, using only string methods you know?

4. Case sensitivity matters: Why do all three applications immediately convert text to lowercase? Can you think of a situation where preserving case would be important?

5. Connect to immutability: Each step in the search pipeline creates new strings rather than modifying the original query. How does this relate to the immutability concept from Section 7.4? Is there a practical advantage to keeping the original query unchanged?