Tokenization

Dr. A. Kaliappan
ASP / SoC
SRMIST 1
 What is Tokenization?
Tokenization is the task of chopping text into pieces, called tokens
Token is an instance of a sequence of characters in some particular document (grouped as a useful semantic unit)

Type is the class of all tokens containing the same character sequence

Term is a (perhaps normalized) type that is included in the corpus dictionary

Example: to sleep more to learn

Token: to, sleep, more, to, learn

Type: to, sleep, more, learn

Term: sleep, more, learn (stop words removed)

2
 Tokenization Issues
● Maine's state capital
○ Maine, Maines, Maine’s?
● Dover-Foxcroft
○ Dover-Foxcroft or two tokens: Dover, Foxcroft
○ State-of-the-art: break up hyphenated sequence
● San Francisco: one token or two?
● Handling numbers
○ September 13, 2022
○ 13/9/2022 Dover-Foxcroft, Maine
○ (686)753-2910
○ Older IR systems may not index numbers
● Will often index “meta-data” separately

3
 Tokenization Issues (Other Languages)
● French
○ L'ensemble → one token or two?
○ L ? L’ ? Le ?
○ Want l’ensemble to match with un ensemble
● German
○ Noun compound are not segmented
○ Kraftfahrzeughaftpflichtversicherung
○ ‘motor vehicle indemnity insurance’
● Chinese & Japanese
○ No space between words
○ 自然语言处理课程 →‘Natural Language Processing course’
● Persian & Arabic
○ Right to left
○ Letters can be connected together
○ ‫ن =یعیبطن ابز شز ادرپ س ال ک‬
‫شزادرﺑﯾﻌ‬
‫ﯽ‬ ‫ط‬
‫ﮐﻼسﭘز ﺎﺑ‬
○ ‘Natural language processing class’

4
 Word-based Tokenization
Approach
● Splitting the text by spaces
● Other delimiters such as punctuation can be used
Advantages
● Easy to implement
Disadvantages
● High risk of missing words; e.g., Let and Let’s will have two different types
● Languages like Chinese do not have space
● Huge vocabulary size (token type)
○ Limit the number of words that can be added to the vocabulary
● Misspelled words will be considered as a token

5
 Character-based Tokenization
Approach
● Splitting the text into individual characters
Advantages
● There will be no or very few
unknown words (Out Of Vocabulary)
● Useful for languages that characters
carry information
● Fewer number of tokens
● Easy to implement
Disadvantages
● A character usually does not have a meaning
○ Cannot learn semantic for words
● Larger sequence to be processed by models
○ More input to process
6
 Subword Tokenization
Approach
● Frequently used words should not be split into smaller subwords
● Rare words should be decomposed into meaningful subwords
● Uses a special symbol to indicate which word is the start of the token and which word is the
completion of the start of the token
○ Tokenization → “Token”, “##ization”
● State-of-the-art approaches for NLP and IR rely on this type

7
 Subword Tokenization
Approach
● Frequently used words should not be split into smaller subwords
● Rare words should be decomposed into meaningful subwords
● Uses a special symbol to indicate which word is the start of the token and which word is the
completion of the start of the token
○ Tokenization → “Token”, “##ization”
● State-of-the-art approaches for NLP and IR rely on this type

Advantages
● Out-of-vocabulary word problem solved
● Manageable vocabulary sizes

Disadvantages
● New scheme and needs more exploration

Byte Per Encoding (BPE) and WordPiece are two examples of this scheme

8
 Byte-Pair Encoding (BPE) Tokenization
Uses Huffman encoding for tokenization (greedy algorithm)

Training Steps:
1. Starts with splitting the input words into single characters
(each of them corresponds to a symbol in the final vocabulary)
* In practice we commonly add special end of word symbol “ ” before space
2. Find the most frequent occurring pair of symbols from the current vocabulary
3. Add this to the vocabulary and size of vocabulary increases by one
4. Repeat steps (2) and (3) till the defined number of tokens are built
or no new combination of symbols exist with required frequency

Sennrich, R., Haddow, B., & Birch, A. (2016). Neural Machine Translation of Rare Words with Subword Units. In Proceedings of the
54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) (pp. 1715-1725) 15
 Byte-Pair Encoding (BPE) Tokenization
Training corpus: low low low low low lowest lowest newer newer newer newer
newer newer wider wider wider new new

Corpus Vocabulary
5 low , d, e, i, l, n, o, r, s, t, w
2 lowest
6 newer
3 wider
2 new

10
 Byte-Pair Encoding (BPE) Tokenization
Training corpus: low low low low low lowest lowest newer newer newer newer
newer newer wider wider wider new new

Corpus Vocabulary
5 low , d, e, i, l, n, o, r, s, t, w
2 lowest
9 times 6 newer
3 wider Vocabulary
2 new , d, e, i, l, n, o, r, s, t, w, er

11
 Byte-Pair Encoding (BPE) Tokenization
Training corpus: low low low low low lowest lowest newer newer newer newer
newer newer wider wider wider new new

Corpus Vocabulary
5 low , d, e, i, l, n, o, r, s, t, w, er
2 lowest
9 times 6 newer
3 wider Vocabulary
2 new , d, e, i, l, n, o, r, s, t, w, er, er

12
 Byte-Pair Encoding (BPE) Tokenization
Training corpus: low low low low low lowest lowest newer newer newer newer
newer newer wider wider wider new new

Corpus Vocabulary
5 low , d, e, i, l, n, o, r, s, t, w, er, er
2 lowest
8 times 6 newer
3 wider Vocabulary
2 new , d, e, i, l, n, o, r, s, t, w, er, er , ne

13
 Byte-Pair Encoding (BPE) Tokenization
Training corpus: low low low low low lowest lowest newer newer newer newer
newer newer wider wider wider new new

Corpus Vocabulary
5 low , d, e, i, l, n, o, r, s, t, w, er, er , ne
2 lowest
8 times 6 newer
3 wider Vocabulary
2 new , d, e, i, l, n, o, r, s, t, w, er, er , ne, new

14
 Byte-Pair Encoding (BPE) Tokenization
Corpus
5 low Final Vocabulary
2 lowest
6 newer , d, e, i, l, n, o, r, s, t, w, er, er , ne, new, lo, low, newer , low
3 wider
2 new

Using BPE for tokenization:

Input: newer → Tokens: newer Merge based on the order we learned:
er → er → ne → new → newer
Input: lower → Tokens: low, er er → er → lo → low

15
 WordPiece Tokenization

Assignment!
How WordPiece is different from BPE?
Use the example corpus from the previous slide to show how
WordPiece tokenization work

HuggingFace: [Link]
Paper: [Link]
Google Blog: [Link]

16
Stop Words
 Stopwords Removal
Stopping: Removing common words from the stream of tokens that become index terms
● Words that are function words helping form sentence structure: the, of, and, to, ….
● For an application, an additional domain specific stop words list may be constructed
● Why do we need to remove stop words?
○ Reduce indexing (or data) file size
○ Usually has no impact on the NLP task’s effectiveness, and may even improve it

18
 Stopwords Removal
Stopping: Removing common words from the stream of tokens that become index terms
● Words that are function words helping form sentence structure: the, of, and, to, ….
● For an application, an additional domain specific stop words list may be constructed
● Why do we need to remove stop words?
○ Reduce indexing (or data) file size
○ Usually has no impact on the NLP task’s effectiveness, and may even improve it
● Can sometimes cause issues for NLP tasks:
○ e.g., phrases: “to be or not to be”, “let it be”, “flights to Portland Maine”
○ Some tasks consider very small stopwords list
■ Sometimes perhaps only “the”
● List of stopwords: [Link]

19
Normalization
 Token Normalization
Token/Term Normalization: Reducing tokens to canonical token (creating equivalence classes)
● Deleting periods to form a term
○ U.S.A, USA
○ How about C.A.T (Caterpillar Inc) and CAT? (Test Google on this!)
● Deleting hyphens to form a term
○ anti-discriminatory, antidiscriminatory
● Keeping relationships between unnormalized tokens
○ car, automobile
● British vs. American spelling:
○ color vs. colour
● Other languages:
○ French: résumé vs. resume

27
Stemming
 Stemming
Stemming: To group words that are derived from a common stem
● e.g, “fish”, “fishes”, “fishing” could be mapped to “fish”
● Generally produces small improvements in tasks effectiveness
● Similar to stopping, stemming can be done aggressively, conservatively, or not at all
○ Aggressively: consider “fish” and “fishing” the same
○ Conservatively: just identifying plural forms using the letter “s”
■ issues: ‘Centuries’ → ‘Centurie”
○ Not at all: Consider all the word variants

23
 Stemming
Stemming: To group words that are derived from a common stem
● e.g, “fish”, “fishes”, “fishing” could be mapped to “fish”
● Generally produces small improvements in tasks effectiveness
● Similar to stopping, stemming can be done aggressively, conservatively, or not at all
○ Aggressively: consider “fish” and “fishing” the same
○ Conservatively: just identifying plural forms using the letter “s”
■ issues: ‘Centuries’ → ‘Centurie”
○ Not at all: Consider all the word variants
● In different languages, stemming can have different importance for effectiveness:
○ In Arabic, morphology is more complicated than English
○ In Chinese, stemming is not effective

24
 Evaluation of Stemmers
There are three criteria for evaluating stemmers:
1. Correctness
2. Efficiency of the task
3. Compression performance

There are two ways in which stemming can be incorrect:

● Over-stemming (too much of the term is removed)
○ Two or more words being reduced to the same wrong root
○ e.g., ‘centennial’, ‘century’, ‘center’: ‘cent’
● Under-stemming (too little of the term is removed)
○ Two or more words could be wrongly reduced to more than one root word
○ e.g., ‘acquire’, ‘acquiring’, ‘acquired’: acquir ‘acquisition’: ‘acquis’

25
 Porter Stemmer (1980)
The most common stemmer for English, introduced by Martin Porter
A rule-based stemmer with rules for mostly suffix-stripping such as:
● “ing” → “-” connecting → connect
● “sses” → “ss” caresses → caress
● (m>0) “EED” → “EE” feed → feed agreed → agree
○ m=measure of word or word part, when represented in form (VC+)
■ V= vowel and C=consonants

[Link]
26
 Porter Stemmer (1980)
The most common stemmer for English, introduced by Martin Porter
A rule-based stemmer with rules for mostly suffix-stripping such as:
● “ing” → “-” connecting → connect
● “sses” → “ss” caresses → caress
● (m>0) “EED” → “EE” feed → feed agreed → agree
○ m=measure of word or word part, when represented in form (VC)
■ V= vowel and C=consonants

Advantage: It produces the best output as compared to other stemmers, and it has less error rate
Disadvantage: Morphological variants produced are not always real words (produces stems)

[Link]
27
 Krovetz Stemmer (1993)
Hybrid algorithmic-dictionary-based method introduced by Robert Krovetz
Word checked in dictionary:
● If present, either left alone (or replaced with “exception”)
● If not present, word is checked for suffixes that could be removed
● After removal, dictionary is checked again

Advantage: Produces words not stems

Disadvantage: Lower false positive rate, somewhat higher false negative
FP: Policy → Police FN: noise/noisy

28
Example

29
Lemmatization
 Lemmatization
Reduce inflectional/variant forms to base form
● am, are, is → be
● car, cars, car's, cars' → car
● the boy's cars are different colors → the boy car be different color
Lemmatization implies doing “proper” reduction to dictionary headword form
● e.g., WordNet is a lexical database of semantic relations between words in more than 200
languages

Stemming is a process that extract stems by removing last few characters from a word, often
leading to incorrect meanings and spelling
Lemmatization considers the context and converts the word to its meaningful base form, which is
called Lemma
37
NLTK: Natural Language Toolkit
[Link]
Tokenization & Stopword Removal

33
Stemming & Lemmatization

34