Overview

In earlier lessons, we introduced the idea of tokens and discussed some of their attributes. We devised some informal descriptions of the clues that signal token boundaries (ex. whitespace, contractions, etc.). In this lesson, we'll how to use regexes to tokenize text.

Outcomes

After completing this lesson, you'll be able to …

• describe token boundaries in terms of regular expressions
• write a simple regex tokenizer
• describe a rule cascade and how it can be used

Prerequisites

Before you start, read this description of SpaCy's rule-based tokenizer:

• https://spacy.io/usage/linguistic-features#tokenization

Tokenization

Tokenization is the process of segmenting text into tokens.

text = "I do not eat giraffes."
 
text = ["I", "do" "not", "eat", "giraffes", "."]

Given how machine learning has come to dominate most approaches in natural language processing (tagging, parsing, sentiment analysis, classification, etc.), you may be surprised to learn that tokenization is still frequently handled using regexes. This is an approach taken not just in English, but in many natural languages.

For example, SpaCy is a popular NLP library used in industry which supports a growing number of natural languages.

SpaCy handles tokenization using a prioritized series or cascade of rules:

Each rule (ex. regex) defines a token boundary.

Finding token boundaries using re.split

If we want to take a rule-based approach to tokenization, our regexes (rules) need to define token boundaries. In other words, our regex should match the position within a string where we want to split it into tokens. If we're using Python, the re module contains a function to do exactly this: re.split().

As an example, we have the follow string and want to split it whenever we see a y:

text = "yxxyxxxxxyxxxx"

The pattern in this case is very simple: y

import re
 
text = "yxxyxxxxxyxxxx"
tokens = re.split("y", text)
print(tokens)

["", "xx", "xxxxx", "xxxx"]

That worked, but we have one empty string as a token. Let's filter that out:

print([tok for tok in tokens if tok])

["xx", "xxxxx", "xxxx"]

What if instead tokens in this language all started with a y? In this case, we'd want to split immediately before any y without losing any existing characters.

For this, we can use a lookahead:

import re
 
text = "yxxyxxxxxyxxxx"
# we'll filter out any empty tokens as well
tokens = [tok for tok in re.split("(?=y)", text) if tok]
print(tokens)

["yxx", "yxxxxx", "yxxxx"]

What if our language included puncuation and we wanted that punctuation to constitute separate tokens only if it is preceded by a certain number of x characters?

We could extend our regex by adding disjunctions (i.e., $p_{1} \; \text{OR} \; p_{2} \; \text{OR} \; p_{3} \; \text{OR} \; \ldots$), but as that regex grows in complexity, it also becomes more difficult to read and debug.

Let's consider an alternative approach…

Rule cascade

Instead of using a single complex regex to indentify token boundaries, it may be easier to apply a series of simpler prioritized rules (regexes). This type of rule application is known as a cascade¹.

❗ You may wish to repeat the application of your rules in a loop until each token can no longer be split.

What would a sequence of prioritized rules be? For example, you might first split on whitespace, then split any tokens containing a contraction, and finally split on certain cases of punctuation. In some cases, the order of applications of these rules isn't particularly important. It really depends on how contextualized the rules need to be and how prior rules may alter context through tokenization.

A rule cascade tokenizer takes a a) sequence of prioritized rules (ex. ordered by priority) and b) some text to tokenize.

Given those inputs, the algorithm for a rule cascade is …

1. Initialize a sequence of tokens using the untokenized text:

tokens = ["text to process"]
rules  = [rule1, rule2]

2. Apply each rule to each token.

from typing import Callable, List, Text
 
# type alias for a rule function
# input: seq of strings
# output: seq of strings
Rule = Callable[[List[Text]], List[Text]]
 
def rule_cascade_tokenizer(text: Text, rules: List[Rule]) -> List[Text]:
  # 1. Initialize a sequence of tokens using the untokenized text
  tokens = [text]
  # 2. Apply each rule to each token.
  for rule in rules:
    # generate a new set of tokens with each rule application
    tokens = rule(tokens)
    # continue to apply the remaining rules to these new tokens
  return tokens

3. Optionally repeat until the tokens can no longer be changed (split).

graph LR;
  tokens["tokens"]
  r1["Rule 1"]
  r2["..."]
  r3["Rule n"]

  tokens---->r1;
  r1---->r2;
  r2---->r3;
  r3-. repeat with new tokens .->tokens;
    r3-.->output;

click r1 mermaidcallback "split"

style tokens stroke:#333,stroke-width:4px
style r1 fill:#f9f,stroke:#333,stroke-width:2px
style r2 fill:#f9f,stroke:#333,stroke-width:2px
style r3 fill:#f9f,stroke:#333,stroke-width:2px

If you are new to programming, the implementation may not be immediately obvious. In such cases, there is a strategy to follow:

always start by breaking the problem into smaller, more manageable pieces (subproblems).

In this case, the key subproblem is defining a function to apply a single rule to a sequence of tokens. Once we have that, we simply call it in a loop for each rule and update our candidate tokens.

If we want to apply the rules until they can no longer match, we need to compare the tokens before a round of rule application with the tokens resulting after a round of rule application. If they're different, apply the rules again. If they're the same, we're finished².

Next steps

You've learned the basics of using regexes to detect token boundaries and examined how a tokenizer could apply one or more such regex. Let's practice …

Practice

• Write a regex to tokenize the following sentence in a way that preserves the ASCII emojis:

At first I felt a combination of :) and :O, then I got :| and started to feel :(.

• your regex should detect boundaries such that the following sequence is produced:

  [ "At", "first", "I", "felt", 
    "a", "combination", "of", ":)", "and", ":O", ",", 
    "then", "I", "got", ":|", "and", 
    "started", "to", "feel", ":(", "." ]

• You may wish to use a site like https://www.debuggex.com to test your regex.

• Consider how you might combine text normalization with tokenization. write a function called muppet_preprocessor(text) that takes the following string as input:

Fozzie and Kermit are movin' right along!

… and produces the following token sequence:

["MUPPET", "and", "MUPPET", "are", "movin'", "right", "along", "!"]