Lab 02

Text Preprocessing

Index pipeline Tokenization Normalization Stemming
Work in progress These notes are still being written and reviewed: content may change, and some parts may still contain mistakes.

Overview of the lab

  1. Main steps for building an index
  2. Tokenization: sentences and words
  3. Normalization and stopwords
  4. Stemming and lemmatization
  5. Exercise: preprocessing the 20 Newsgroups posts
  6. Querying with the same preprocessing
Big picture

Main steps for building an index

The text of each document passes through a tokenizer and linguistic modules before the indexer of Lab 01 sorts the terms into a dictionary and postings.

See it with the notebook's example document

Tokenization

Tokenization

Split a document into sentences, then each sentence into tokens. Every decision here (keep km/h together? split can't?) changes which terms end up in the index.

Sentences: Punkt

PunktSentenceTokenizer splits the example document into its 4 sentences. Punkt is unsupervised: it learns abbreviations, collocations and typical sentence starters from a corpus of text.

  • PunktSentenceTokenizer(): the notebook's call, with no training text, so it knows no abbreviations.
  • sent_tokenize(text): loads the Punkt model pre-trained on English (punkt_tab). Lab 01's preprocess_document uses it.

Try it: split into sentences

The outputs were computed with NLTK 3.9. Compare the two models on Abbreviations.

Words: four NLTK tokenizers

  • WhitespaceTokenizer: splits only on spaces, tabs and newlines, so punctuation stays attached (Portugal,).
  • WordPunctTokenizer: the regex \w+|[^\w\s]+: runs of letters and digits, and runs of punctuation.
  • TreebankWordTokenizer: follows the Penn Treebank conventions. It splits contractions (ca n't), separates most punctuation, and keeps 50,000 and 366.88 whole. It expects one sentence at a time, so only a final period is split off.
  • TweetTokenizer: uses regexes for URLs, emoticons, @handles, #hashtags, e-mails and phone numbers, and then for words.

Try it: compare the tokenizers

The first row has the notebook's examples, with its comments, and the second row has more cases to try. You can also type your own text. Punctuation-only tokens are red.

Notebook
More

๐Ÿ’ก The widgets run JavaScript ports of the NLTK 3.9 tokenizers and stemmers. We checked them against NLTK on all 33,228 sentences of mini_newsgroups and all 56,530 distinct words in them, and the output was identical.

tokenizers.py Python
from nltk.tokenize import PunktSentenceTokenizer
from nltk.tokenize import TweetTokenizer, WhitespaceTokenizer, WordPunctTokenizer, TreebankWordTokenizer

example_document = """
Hurricane-force winds have struck central and northern Portugal, leaving 300,000 homes without power.

The remnants of Hurricane Leslie swept in overnight on Saturday, with winds gusting up to 176km/h (109mph).

Civil defence officials said 27 people suffered minor injuries, with localised flooding, hundreds of trees uprooted and a number of flights cancelled.

The storm, one of the most powerful to ever hit the country, is now passing over northern Spain.
"""
sent_tokenizer = PunktSentenceTokenizer()
sentences = sent_tokenizer.tokenize(example_document)   # 4 sentences

tweet_tok, whsp_tok, wordpunct_tok, treebank_tok = TweetTokenizer(), WhitespaceTokenizer(), WordPunctTokenizer(), TreebankWordTokenizer()

print(whsp_tok.tokenize(sentences[0]))
# ['Hurricane-force', 'winds', 'have', 'struck', 'central', 'and', 'northern', 'Portugal,', 'leaving', '300,000', 'homes', 'without', 'power.']
print(wordpunct_tok.tokenize('On a $50,000 mortgage of 30 years at 8 percent, the monthly payment would be $366.88.'))
# ['On', 'a', '$', '50', ',', '000', 'mortgage', ..., 'be', '$', '366', '.', '88', '.']
print(treebank_tok.tokenize('On a $50,000 mortgage of 30 years at 8 percent, the monthly payment would be $366.88.'))
# ['On', 'a', '$', '50,000', 'mortgage', ..., 'be', '$', '366.88', '.']
print(treebank_tok.tokenize('My email is admin@sth.com'))    # ['My', 'email', 'is', 'admin', '@', 'sth.com']
print(tweet_tok.tokenize('My email is admin@sth.com'))       # ['My', 'email', 'is', 'admin@sth.com']
print(tweet_tok.tokenize('Last sunny day before winter :) #sunisenergy'))
# ['Last', 'sunny', 'day', 'before', 'winter', ':)', '#sunisenergy']
print(tweet_tok.tokenize('Here is my ip address 192.33.24.45'))   # we might want to fix this
# ['Here', 'is', 'my', 'ip', 'address', '192.33', '.', '24.45']
print(tweet_tok.tokenize("I can't stop singing that song!"))     # we might want to split can't in can, 't instead
# ['I', "can't", 'stop', 'singing', 'that', 'song', '!']
1Exercise: play with the tokenizers and find more cases where they fail.

URLs, e-mails, file names: WordPunct and Treebank cut a URL into pieces that match unrelated words. Treebank also splits e-mails at @.

Hyphens and dates: state-of-the-art, York-based, 2024-09-27: one token or several? Tweet produces 2024-09- 27.

Names with symbols: C++, C#, Node.js, O'Neill, AT&T.

Abbreviations: U.S.A., e.g., p.m. are spelled out letter by letter, and they also confuse sentence splitting.

Numbers: IP addresses, phone numbers, times (10:30am), prices (โ‚ฌ25.50), units (176km/h).

Apostrophes: can't, won't, workstation's, and the typographic โ€™ in cโ€™รจ.

Other languages: German compounds and Chinese or Japanese text have no spaces between words and need a word segmenter.

There is no single right answer: choose what the queries of your users need, and apply the same tokenizer to documents and queries.

Normalization

Normalization

How we normalize the text depends on the domain and the task. Some normalization steps:

  • Irrelevant parts: whole chunks of the document might be irrelevant, e.g. HTML tags.
  • Numbers: remove them or replace them with a common token.
  • Other token types we don't care about, e.g. URLs, @ mentions, ๐Ÿ˜€: remove or replace them the same way.
  • Lower-case all words, or even use a tool to upper-case all named entities, like geographic names.
  • Equivalence classes for matching synonyms, abbreviations, etc.
  • Stopwords: remove them. The list is usually made by hand.
  • Google N-Grams: a huge collection of frequency counts of word n-grams in web pages, for many languages. Use it to see which words are used most often.
  • Stemming: crudely remove prefixes and suffixes, so that different forms of a word match, like car-sharing and car sharing.
  • Lemmatization: replace the word by its lemma (its dictionary form).

Try it: normalize a text

We split the text with TweetTokenizer, then apply the steps you switch on. Struck-out tokens are dropped, and changed tokens show their old form crossed out. The default is the notebook's sentence.

punctuation   number   stopword   changed

๐Ÿ’ก In When it hurts, lower-casing makes IT the stopword it, and The Who and To be or not to be disappear completely.

Stopwords

NLTK's English list, as printed in the notebook: 179 words (the current NLTK data has 198). It includes fragments such as don, ll, ve, t, which tokenizers produce when they split contractions.

Exercise: for each method above, find examples where we would not want to use it.

2Removing HTML tags and other chunks

Tags carry structure: words in <title> or <h1> matter more than words in the footer (zones, Lab 01). On a site about web development, <table> may be exactly what users search for. In the newsgroup posts, dropping the headers also drops the Subject, the best summary of the post.

3Removing or replacing numbers

Numbers are often the query: Windows 95, COVID-19, iPhone 15, 1984 (the novel), error 404, a year in news search, a product code. In sci.crypt, the query 1993 is left with no terms (see querying).

4Removing URLs, @ mentions and emoji

Users search for a domain (nltk.org) or a person (@nlp_lab). Emoji carry sentiment and meaning (๐Ÿ˜€ vs ๐Ÿ˜ก) that sentiment analysis needs. Splitting a URL into words (en, wikipedia, org) is often better than removing it.

5Lower-casing

Case separates meanings: US / us, WHO / who, IT / it, Apple / apple, Bush / bush, DES (the cipher) / des. After lower-casing, WHO and IT are even removed as stopwords.

6Equivalence classes (synonyms, abbreviations)

Synonyms depend on context: jaguar = car only for some queries. C.A.T. (a company) is not cat, and Windows is not windows. Expanding every query with its synonyms raises recall but lowers precision.

7Removing stopwords

Phrases made of stopwords: To be or not to be, the bands The Who and Take That. Meaning carried by stopwords: flights to London vs flights from London, negation not good. Sentiment analysis needs not. In sci.crypt, not secure becomes just secure.

8Stemming

Over-stemming merges unrelated words: university, universe โ†’ univers; organization, organ โ†’ organ; general, generator โ†’ gener (Porter); data, date โ†’ dat and news โ†’ new (Lancaster). Under-stemming misses irregular forms: children / child, mice / mouse, ran / run. Names get stemmed too: Portugal โ†’ portug.

9Lemmatization

It needs the part of speech: lemmatize('meeting') is meeting (a noun), lemmatize('meeting', 'v') is meet. With the default noun reading, lemmatize('was') gives wa and lemmatize('us') gives u. better โ†’ good works only with pos='a'. It is slower than stemming, and words that are not in the dictionary (typos, names) are left unchanged.

Stemming

Stemming and lemmatization

Resources: Introduction to stemming (GeeksforGeeks) and A Comparative Study of Stemming Algorithms (Jivani, 2011).

๐Ÿ“ Stemmer vs lemmatizer

A stemmer cuts suffixes with rules and no dictionary. The result does not have to be a word (automobil, eventu). A lemmatizer looks the word up (NLTK uses WordNet) and returns a dictionary form (pollutions โ†’ pollution). It needs the part of speech and leaves unknown words, such as the notebook's typo decreas, as they are.

Where stemming is used

  • Information retrieval systems like search engines.
  • Domain analysis: determining domain vocabularies.
  • Indexing: mapping documents that use different forms of a word to common subjects.
  • Sentiment analysis of reviews and comments (e.g. for online retail stores): stemming is a text-preparation step.
  • Document clustering (text clustering): subject extraction, automatic document structuring, fast information retrieval.

Popular stemmers

StemmerIdeaโœ… AdvantageโŒ Limitation
PorterRemoves the common morphological and inflectional endings of English words, in five steps of rules.Best output compared to other stemmers, lower error rate.The stems are not always real words.
LovinsRemoves the longest suffix, then recodes the stem to turn it into a valid word.Fast; handles irregular plurals like teeth and tooth.Slow, and often fails to turn the stems into words.
DawsonSuffixes stored in reversed order, indexed by their length and last letter.Fast; covers more suffixes.Very complex to implement.
KrovetzPlural โ†’ singular, past tense โ†’ present, removes -ing.Light; can be a pre-stemmer for other stemmers.Inefficient for large documents.
SnowballAlso called Porter2: improves on Porter and has versions for many languages.Can stem non-English words too.Still rule-based: over- and under-stemming.
N-gramCompares words by their shared character n-grams.Based on string comparisons; language independent.Needs space to create and index the n-grams, and is slow.

๐Ÿ’ก The notebook calls the N-gram stemmer "language dependent". The cited survey (Jivani, 2011, Table 2) lists it as language independent: it uses only string statistics, with no rules for a particular language. The Lancaster (Paice/Husk) stemmer used below is the most aggressive of NLTK's three.

Try it: compare the stemmers and the lemmatizer

The default is the notebook's list, and the first three columns match its table. Car sharing is the notebook's lemmatizer example. Type any words.

Words that end up as the same term

๐Ÿ’ก We precomputed the lemmas with NLTK's WordNetLemmatizer for every word of mini_newsgroups. Other words you type are shown unchanged. The lemmatizer is case-sensitive: Car stays Car, while the stemmers lower-case first.

stemming.py Python
import nltk
nltk.download('wordnet')
nltk.download('omw-1.4')
nltk.download('stopwords')
from nltk.stem.porter import PorterStemmer
from nltk.stem import WordNetLemmatizer, porter, lancaster, snowball
from nltk.corpus import stopwords
from nltk.tokenize import TweetTokenizer
from collections import defaultdict
import pandas as pd

tweet_tok = TweetTokenizer()

stemmer = PorterStemmer()
lemmatizer = WordNetLemmatizer()
tokens = tweet_tok.tokenize('Car sharing will bring a whole new era to the automobile industry. Eventually, it may even decreas air pollutions.')
for token in tokens:
    print(token, lemmatizer.lemmatize(token), stemmer.stem(token))
# Car Car car / sharing sharing share / automobile automobile automobil / industry industry industri
# Eventually Eventually eventu / decreas decreas decrea / pollutions pollution pollut ...

print(len(stopwords.words('english')))   # 179 in the notebook's NLTK data, 198 in current NLTK data

stem_list = [porter.PorterStemmer(), lancaster.LancasterStemmer(), snowball.SnowballStemmer('english')]
examples = ['agreed', 'children', 'flies', 'humbled', 'colonizer', 'owned', 'meeting', 'sitting', 'understood', 'whom']
result = defaultdict(list)
for word in examples:
    result['original'].append(word)
    for s in stem_list:   # the notebook reuses the name `stemmer` here
        result[s.__class__.__name__].append(s.stem(word))
print(pd.DataFrame(result).to_markdown())
# |  0 | agreed   | agre     | agree  | agre     |
# |  1 | children | children | childr | children |
# |  2 | flies    | fli      | fli    | fli      |  ...
Exercise

Exercise: preprocessing the 20 Newsgroups posts

Explore the 20 Newsgroups dataset and write another preprocessing method that cleans the text of the news articles:

  • Select one of the tokenizers, or try to write one of your own.
  • Clean the headings and any common parts.
  • Lower-case the text and decide whether to remove any token types, e.g. URLs. You can also split URLs into meaningful words and use those as tokens.
  • Look at the most frequent words in the corpus and add more stopwords. Depending on your tokenizer, you may need to change the stopwords too. Then remove them from the text.
  • Add a parameter that chooses between lemmatization and stemming.
  • Finally, compare how the steps reduced or changed the index.
tokenize_documents.py Python
from nltk.tokenize import sent_tokenize, TweetTokenizer
from string import punctuation
from os import scandir
from collections import Counter
from pandas import DataFrame
from nltk.corpus import stopwords
from nltk.stem.porter import PorterStemmer
tw_tokenizer = TweetTokenizer()

def tokenize_documents(path, tokenizer):
    """
    Returns a list of tokenized documents: lower-cased tokens without punctuation.
    """
    documents = []
    for entry in sorted(scandir(path), key=lambda e: e.name):
        with open(entry.path, errors='ignore') as f:
            content = f.read()
        tokens = []
        for sentence in sent_tokenize(content):
            tokens += [tok.lower() for tok in tokenizer.tokenize(sentence) if tok not in punctuation]
        documents.append(tokens)
    return documents

print(tokenize_documents('data/mini_newsgroups/sci.crypt/', tw_tokenizer)[1][:12])
# ['path', 'cantaloupe.srv.cs.cmu.edu', 'das-news.harvard.edu', 'ogicse', 'uwm.edu', 'zaphod.mps.ohio-state.edu',
#  'howland.reston.ans.net', 'sol.ctr.columbia.edu', 'news.cs.columbia.edu', 'ji', 'from', 'ji@cs.columbia.edu']

# how the most frequent tokens change
word_freqs = Counter(sum(tokenize_documents('data/mini_newsgroups/sci.crypt/', tw_tokenizer), []))
df = DataFrame(list(word_freqs.items()), columns=['text', 'freq'])
df.sort_values(['freq'], inplace=True, ascending=False)
print(df.head())                 # the 1718, to 831, of 711, a 563, and 506

en_stopwords = set(stopwords.words('english'))
df_no_stopwords = df[~df['text'].isin(en_stopwords)].copy()
print(df_no_stopwords.head())    # sci.crypt 158, cantaloupe.srv.cs.cmu.edu 150, encryption 148, key 133, clipper 115

df_no_stopwords['stemmed'] = df_no_stopwords['text'].apply(PorterStemmer().stem)
stemmed_freqs = df_no_stopwords.groupby(['stemmed'])['freq'].sum()
stemmed_freqs.sort_values(inplace=True, ascending=False)
print(stemmed_freqs.head())      # key 198, encrypt 187, use 185, sci.crypt 158, cantaloupe.srv.cs.cmu.edu 150

print(len(df), len(df_no_stopwords), len(stemmed_freqs))
# 5769 5624 4592 with the notebook's 179 stopwords; 5769 5612 4580 with the 198 of current NLTK data

๐Ÿ’ก scandir and os.listdir return files in an order that depends on the machine, so we sort by file name. The notebook's document [1] is then the file 15169.

Try it: the preprocessing pipeline on sci.crypt

These are the 100 real sci.crypt posts. The default settings are the notebook's (Tweet, lower-case, no punctuation, NLTK stopwords, Porter): 5,769 โ†’ 5,624 โ†’ 4,592 terms, top term key with 198 occurrences. Switch the steps on and off and watch the dictionary.

1Tokenizer
2Headers
3Clean-up
4Hosts, e-mails
5Stopwords
Your stopwords
6Normalization

๐Ÿ’ก Your stopwords starts with header field names, the newsgroup and host found in every post, and frequent words from the top of the notebook's table. Edit the list freely. Hosts, e-mails covers tokens with ., @, ! or / between letters or digits, such as cantaloupe.srv.cs.cmu.edu. Split into words turns them into cantaloupe srv cs cmu edu. With the Whitespace tokenizer, splitting adds terms.

Querying

Querying with the same preprocessing

Your query methods must apply the same steps to the query words. A query term matches only if it went through the same tokenizer, case folding, stopword list and stemmer as the documents.

  • Positive: stemming and lemmatization match other forms of a word (higher recall).
  • Negative: unrelated words merge, and removed words (stopwords, numbers) make parts of the query disappear (lower precision, or no answer).

Try it: query the Lab 01 index and your pipeline

An AND query against two indexes of sci.crypt: the Lab 01 index (Tweet, lower-case, no punctuation) and the one from the pipeline above. Each scenario sets the pipeline and a query, and then you can change either.

Your pipeline:

๐Ÿ’ก Green documents are found only by your pipeline, red ones only by the Lab 01 index. Whether a gain is good depends on the user: keys โ†’ key helps, data โ†’ every Date: header does not.

Summary: key takeaways

  1. Pipeline: documents โ†’ tokenizer โ†’ linguistic modules โ†’ indexer. Documents and queries must go through the same steps.
  2. Sentences: Punkt needs a trained model (sent_tokenize) to know abbreviations such as Mr. and U.S.
  3. Tokenizers: Whitespace, WordPunct, Treebank and Tweet disagree on URLs, e-mails, numbers, contractions and emoji. Pick one for your data and queries.
  4. Normalization: remove irrelevant parts, numbers and token types; lower-case; equivalence classes; stopwords. Each step also has cases where it hurts.
  5. Stemming: rule-based suffix removal (Porter, Snowball, Lancaster). It is cheap and raises recall, but over-stems (university = universe) and under-stems (children โ‰  child).
  6. Lemmatization: dictionary forms via WordNet; needs the part of speech.
  7. On sci.crypt: stopwords and Porter take the dictionary from 5,769 to 4,592 terms. Header noise (sci.crypt, host names) needs corpus-specific cleaning.