1 of 63

Text processing: tokenization

Text Processing: Basics

2 / 26

Week 1: Lecture 5

What is Tokenization?

Tokenization is the process of segmenting a string of characters into words.

Depending on the application in hand, you might have to perform sentence segmentation as well.

Courtsey (Most slides): Prof. Pawan Goyal

2 of 63

Sentence Segmentation

Text Processing: Basics

Week 1: Lecture 5

The problem of deciding where the sentences begin and end.

Challenges Involved

3 / 26

3 of 63

Sentence Segmentation

Text Processing: Basics

Week 1: Lecture 5

The problem of deciding where the sentences begin and end.

Challenges Involved

While ‘!’, ‘?’ are quite unambiguous

3 / 26

4 of 63

Sentence Segmentation

The problem of deciding where the sentences begin and end.

Challenges Involved

While ‘!’, ‘?’ are quite unambiguous

Period “.” is quite ambiguous and can be used additionally for

⁾Abbreviations (Dr., Mr., m.p.h.)

Text Processing: Basics

Week 1: Lecture 5

3 / 26

5 of 63

Sentence Segmentation

The problem of deciding where the sentences begin and end.

Challenges Involved

While ‘!’, ‘?’ are quite unambiguous

Period “.” is quite ambiguous and can be used additionally for

⁾Abbreviations (Dr., Mr., m.p.h.)

⁾Numbers (2.4%, 4.3)

Text Processing: Basics

Week 1: Lecture 5

3 / 26

6 of 63

Sentence Segmentation

Text Processing: Basics

Week 1: Lecture 5

The problem of deciding where the sentences begin and end.

Challenges Involved

While ‘!’, ‘?’ are quite unambiguous

Period “.” is quite ambiguous and can be used additionally for

⁾Abbreviations (Dr., Mr., m.p.h.)

⁾Numbers (2.4%, 4.3)

Approach: build a binary classifier

For each “.”

Decides EndOfSentence/NotEndOfSentence

3 / 26

7 of 63

Sentence Segmentation

Text Processing: Basics

Week 1: Lecture 5

The problem of deciding where the sentences begin and end.

Challenges Involved

While ‘!’, ‘?’ are quite unambiguous

Period “.” is quite ambiguous and can be used additionally for

⁾Abbreviations (Dr., Mr., m.p.h.)

⁾Numbers (2.4%, 4.3)

Approach: build a binary classifier

For each “.”

Decides EndOfSentence/NotEndOfSentence

Classifiers can be: hand-written rules, regular expressions, or machine learning

3 / 26

8 of 63

Sentence Segmentation: Decision Tree Example

Text Processing: Basics

Week 1: Lecture 5

Decision Tree: Is this word the end-of-sentence (E-O-S)?

4 / 26

9 of 63

Sentence Segmentation: Decision Tree Example

Text Processing: Basics

Week 1: Lecture 5

Decision Tree: Is this word the end-of-sentence (E-O-S)?

4 / 26

10 of 63

Text Processing: Basics

Week 1: Lecture 5

Other Important Features

Case of word with “.”: Upper, Lower, Cap, Number

5 / 26

11 of 63

Other Important Features

Text Processing: Basics

Week 1: Lecture 5

Case of word with “.”: Upper, Lower, Cap, Number Case of word after “.”: Upper, Lower, Cap, Number

5 / 26

12 of 63

Other Important Features

Text Processing: Basics

Week 1: Lecture 5

Case of word with “.”: Upper, Lower, Cap, Number Case of word after “.”: Upper, Lower, Cap, Number Numeric Features

5 / 26

13 of 63

Other Important Features

Text Processing: Basics

Week 1: Lecture 5

Case of word with “.”: Upper, Lower, Cap, Number Case of word after “.”: Upper, Lower, Cap, Number Numeric Features

⁾Length of word with “.”

⁾Probability (word with “.” occurs at end-of-sentence)

⁾Probability (word after “.” occurs at beginning-of-sentence)

5 / 26

14 of 63

Text Processing: Basics

Week 1: Lecture 5

Implementing Decision Trees

Just an if-then-else statement

Pawan Goyal (IIT Kharagpur)

6 / 26

15 of 63

Implementing Decision Trees

Text Processing: Basics

Week 1: Lecture 5

Just an if-then-else statement

Choosing the features is more important

Pawan Goyal (IIT Kharagpur)

6 / 26

16 of 63

Implementing Decision Trees

Text Processing: Basics

Week 1: Lecture 5

Just an if-then-else statement

Choosing the features is more important

For numeric features, thresholds are to be picked

Pawan Goyal (IIT Kharagpur)

6 / 26

17 of 63

Implementing Decision Trees

Just an if-then-else statement

Choosing the features is more important

For numeric features, thresholds are to be picked

With increasing features including numerical ones, difficult to set up the structure by hand

Text Processing: Basics

Week 1: Lecture 5

Pawan Goyal (IIT Kharagpur)

6 / 26

18 of 63

Implementing Decision Trees

Just an if-then-else statement

Choosing the features is more important

For numeric features, thresholds are to be picked

With increasing features including numerical ones, difficult to set up the structure by hand

Decision Tree structure can be learned using machine learning over a training corpus

Text Processing: Basics

Week 1: Lecture 5

6 / 26

19 of 63

Implementing Decision Trees

Text Processing: Basics

Week 1: Lecture 5

Just an if-then-else statement

Choosing the features is more important

For numeric features, thresholds are to be picked

With increasing features including numerical ones, difficult to set up the structure by hand

Decision Tree structure can be learned using machine learning over a training corpus

Basic Idea

Usually works top-down, by choosing a variable at each step that best splits the set of items. How: Using information Gain.

Popular algorithms: ID3, C4.5, CART

6 / 26

https://decisiontree-visualizer.streamlit.app/

20 of 63

Other Classifiers

Text Processing: Basics

Week 1: Lecture 5

The questions in the decision tree can be thought of as features, that could be exploited by any other classifier:

Support Vector Machines Logistic regression Neural Networks

Pawan Goyal (IIT Kharagpur)

7 / 26

21 of 63

Word Tokenization

Text Processing: Basics

Week 1: Lecture 5

What is Tokenization?

Tokenization is the process of segmenting a string of characters into words.

Pawan Goyal (IIT Kharagpur)

8 / 26

Or meaningful unit

of processing

Words

morphemes

Characters

(sub-words)??

22 of 63

Word Tokenization

Text Processing: Basics

Week 1: Lecture 5

What is Tokenization?

Tokenization is the process of segmenting a string of characters into words.

I have a can opener; but I can’t open these cans.

Word Token

An occurrence of a word

For the above sentence, 11 word tokens.

Word Type

A different realization of a word

For the above sentence, 10 word types.

Pawan Goyal (IIT Kharagpur)

8 / 26

23 of 63

NLTK Toolkit (Python) Stanford CoreNLP (Java) Unix Commands

Text Processing: Basics

9 / 26

Week 1: Lecture 5

Tokenization in practice

Pawan Goyal (IIT Kharagpur)

24 of 63

Word Tokenization

Text Processing: Basics

Week 1: Lecture 5

Issues in Tokenization

Finland’s → Finland Finlands Finland’s ?

What’re, I’m, shouldn’t → What are, I am, should not ? San Francisco → one token or two?

m.p.h. → ??

Pawan Goyal (IIT Kharagpur)

10 / 26

25 of 63

Word Tokenization

Text Processing: Basics

Week 1: Lecture 5

Issues in Tokenization

Finland’s → Finland Finlands Finland’s ?

What’re, I’m, shouldn’t → What are, I am, should not ? San Francisco → one token or two?

m.p.h. → ??

For information retrieval, use the same convention for documents and queries

Pawan Goyal (IIT Kharagpur)

10 / 26

26 of 63

Text Processing: Basics

Week 1: Lecture 5

Handling Hyphenation

Hyphens can be

Pawan Goyal (IIT Kharagpur)

11 / 26

27 of 63

Handling Hyphenation

Text Processing: Basics

Week 1: Lecture 5

Hyphens can be

End-of-Line Hyphen

Used for splitting whole words into part for text justification.

This paper describes MIMIC, an adaptive mixed initia-tive spoken dialogue system that provides movie show-time information.

Pawan Goyal (IIT Kharagpur)

11 / 26

28 of 63

Handling Hyphenation

Text Processing: Basics

Week 1: Lecture 5

Hyphens can be

End-of-Line Hyphen

Used for splitting whole words into part for text justification.

This paper describes MIMIC, an adaptive mixed initia-tive spoken dialogue system that provides movie show-time information.

Lexical Hyphen

Certain prefixes are offen written hyphenated, e.g. co-, pre-, meta-, multi-, etc.

Pawan Goyal (IIT Kharagpur)

11 / 26

29 of 63

Handling Hyphenation

Text Processing: Basics

Week 1: Lecture 5

Hyphens can be

End-of-Line Hyphen

Used for splitting whole words into part for text justification.

This paper describes MIMIC, an adaptive mixed initia-tive spoken dialogue system that provides movie show-time information.

Lexical Hyphen

Certain prefixes are offen written hyphenated, e.g. co-, pre-, meta-, multi-, etc.

Sententially Determined Hyphenation

Mainly to prevent incorrect parsing of the phrase. Some possible usages: Noun modified by an ‘ed’-verb: case-based, hand-delivered

Entire expression as a modifier in a noun group: three-to-five-year direct marketing plan

Pawan Goyal (IIT Kharagpur)

11 / 26

30 of 63

Text Processing: Basics

Week 1: Lecture 5

Language Specific Issues: French and German

French

l’ensemble: want to match with un ensemble

Pawan Goyal (IIT Kharagpur)

12 / 26

31 of 63

Language Specific Issues: French and German

Text Processing: Basics

Week 1: Lecture 5

French

l’ensemble: want to match with un ensemble

German

Noun coumpounds are not segmented

Lebensversicherungsgesellschaftsangestellter ‘life insurance company employee’

Compound splitter required for German information retrieval

Pawan Goyal (IIT Kharagpur)

12 / 26

What’s a simple algo you can think of?

32 of 63

Text Processing: Basics

Week 1: Lecture 5

Language Specific Issues: Chinese and Japanese

No space between words

Pawan Goyal (IIT Kharagpur)

13 / 26

33 of 63

Language Specific Issues: Chinese and Japanese

Text Processing: Basics

Week 1: Lecture 5

No space between words

Japanese: further complications with multiple alphabets intermingled.

Pawan Goyal (IIT Kharagpur)

13 / 26

morpheme

34 of 63

Language Specific Issues: Sanskrit

Text Processing: Basics

Week 1: Lecture 5

“One should tell the truth, one should say kind words; one should neither tell harsh truths, nor flattering lies; this is a rule for all times.”

Pawan Goyal (IIT Kharagpur)

14 / 26

35 of 63

Language Specific Issues: Sanskrit

Text Processing: Basics

Week 1: Lecture 5

“One should tell the truth, one should say kind words; one should neither tell harsh truths, nor flattering lies; this is a rule for all times.”

Segmented Text:

Pawan Goyal (IIT Kharagpur)

14 / 26

36 of 63

Text Processing: Basics

15 / 26

Week 1: Lecture 5

Longest Words

Pawan Goyal (IIT Kharagpur)

37 of 63

Longest Words

Text Processing: Basics

16 / 26

Week 1: Lecture 5

Compound word composed of 431 letters, from the Varadāmbikā Pariṅaya Campū by Tirumalāmba

Pawan Goyal (IIT Kharagpur)

Diacritics (phonetics):

acute accent ( ́ ): exposé,

grave accent ( ˋ ), crème

macron ( − ) , ā in fate

38 of 63

Text Processing: Basics

Week 1: Lecture 5

Word Tokenization in Chinese or Sanskrit

Also called ‘Word Segmentation’.

Pawan Goyal (IIT Kharagpur)

17 / 26

39 of 63

Word Tokenization in Chinese or Sanskrit

Text Processing: Basics

Week 1: Lecture 5

Also called ‘Word Segmentation’.

Greedy Algorithm for Chinese

Maximum Matching (Greedy Algorithm)

Start a pointer at the beginning of the string

Find the largest word in dictionary that matches the string starting at pointer

Move the pointer over the word in string

Think of the cases when word segmentation would be required for English Text.

Pawan Goyal (IIT Kharagpur)

17 / 26

40 of 63

Word Tokenization in Chinese or Sanskrit

Text Processing: Basics

Week 1: Lecture 5

Also called ‘Word Segmentation’.

Greedy Algorithm for Chinese

Maximum Matching (Greedy Algorithm)

Start a pointer at the beginning of the string

Find the largest word in dictionary that matches the string starting at pointer

Move the pointer over the word in string

Think of the cases when word segmentation would be required for English Text.

Finding constituent words in a compound hashtags: #ThankYouSachin, #musicmonday etc.

Pawan Goyal (IIT Kharagpur)

17 / 26

41 of 63

Text Segmentation for Sanskrit

Text Processing: Basics

Week 1: Lecture 5

General assumption behind the design

Sentences from Classical Sanskrit may be generated by a regular relation R of the Kleene closure W^∗of a regular set W of words over a finite alphabet Σ.

¹http://sanskrit.inria.fr

Pawan Goyal (IIT Kharagpur)

18 / 26

42 of 63

Text Segmentation for Sanskrit

Text Processing: Basics

Week 1: Lecture 5

General assumption behind the design

Sentences from Classical Sanskrit may be generated by a regular relation R of the Kleene closure W^∗of a regular set W of words over a finite alphabet Σ.

W: vocabulary of (inflected) words (padas) and

R: sandhi

¹http://sanskrit.inria.fr

Pawan Goyal (IIT Kharagpur)

18 / 26

43 of 63

Text Segmentation for Sanskrit

Text Processing: Basics

Week 1: Lecture 5

General assumption behind the design

Sentences from Classical Sanskrit may be generated by a regular relation R of the Kleene closure W^∗of a regular set W of words over a finite alphabet Σ.

W: vocabulary of (inflected) words (padas) and

R: sandhi

Analysis of a sentence

A candidate sentence w is analyzed by inverting relation R to produce a finite sequence w₁, w₂,...w_nof word forms, together with a proof that

w ∈ R(w₁· w₂... · w_n).

¹http://sanskrit.inria.fr

Pawan Goyal (IIT Kharagpur)

18 / 26

44 of 63

Text Processing: Basics

19 / 26

Week 1: Lecture 5

Word Segmentation in Sanskrit

Pawan Goyal (IIT Kharagpur)

45 of 63

July 28 Summary

Sentence Segmentation

Period (“.”) is ambiguous.
We need classifiers trained from data

Word Segmentation

Hyphenation
Clitics - a morpheme which is reduced in form ‘ve, ‘re, ‘m, ‘s
Other languages

German: no spaces
Chinese: no spaces
Japanese: multiple mixed scripts
Sanskrit: “Sandhi” of words

An application of tokenization is in Information retrieval

Document 1: Harry Potter is a character.
Document 2: Potter makes pots.
Document 3: Sachin played cricket.
Query: potter
Term Dictionary: sachin, harry, potter, character, make, pot, play

46 of 63

Normalization

Text Processing: Basics

Week 1: Lecture 5

Why to “normalize”?

Indexed text and query terms must have the same form.

U.S.A. and USA should be matched

Pawan Goyal (IIT Kharagpur)

20 / 26

47 of 63

Normalization

Why to “normalize”?

Indexed text and query terms must have the same form.

U.S.A. and USA should be matched

We implicitly define equivalence classes of terms

Text Processing: Basics

Week 1: Lecture 5

Pawan Goyal (IIT Kharagpur)

20 / 26

48 of 63

Case Folding

Text Processing: Basics

Week 1: Lecture 5

Reduce all letters to lower case Possible exceptions (Task dependent):

Upper case in mid sentence, may point to named entities (e.g. General Motors)

Pawan Goyal (IIT Kharagpur)

21 / 26

49 of 63

Case Folding

Text Processing: Basics

Week 1: Lecture 5

Reduce all letters to lower case Possible exceptions (Task dependent):

Upper case in mid sentence, may point to named entities (e.g. General Motors)
For MT and inforamtion extraction, some cases might be helpful (US vs. us)

Pawan Goyal (IIT Kharagpur)

21 / 26

50 of 63

Lemmatization

Reduce inflections or variant forms to base form:

am, are, is → be
car, cars, car’s, cars’ → car

Have to find the correct dictionary headword form

Text Processing: Basics

22 / 26

Week 1: Lecture 5

Pawan Goyal (IIT Kharagpur)

51 of 63

Morphology

Text Processing: Basics

Week 1: Lecture 5

Morphology studies the internal structure of words, how words are built up from smaller meaningful units called morphemes

Pawan Goyal (IIT Kharagpur)

23 / 26

52 of 63

Morphology

Morphology studies the internal structure of words, how words are built up from smaller meaningful units called morphemes

Morphemes are divided into two categories

Stems: The core meaning bearing units

Affixes: Bits and pieces adhering to stems to change their meanings and grammatical functions

Text Processing: Basics

Week 1: Lecture 5

Pawan Goyal (IIT Kharagpur)

23 / 26

53 of 63

Morphology

Morphology studies the internal structure of words, how words are built up from smaller meaningful units called morphemes

Morphemes are divided into two categories

Stems: The core meaning bearing units

Affixes: Bits and pieces adhering to stems to change their meanings and grammatical functions

⁾Prefix: un-, anti-, etc (a-, ati-, pra- etc.)

Text Processing: Basics

Week 1: Lecture 5

Pawan Goyal (IIT Kharagpur)

23 / 26

54 of 63

Morphology

Morphology studies the internal structure of words, how words are built up from smaller meaningful units called morphemes

Morphemes are divided into two categories

Stems: The core meaning bearing units

Affixes: Bits and pieces adhering to stems to change their meanings and grammatical functions

⁾Prefix: un-, anti-, etc (a-, ati-, pra- etc.)

⁾Suffix: -ity, -ation, etc (-taa, -ke, -ka etc.)

Text Processing: Basics

Week 1: Lecture 5

Pawan Goyal (IIT Kharagpur)

23 / 26

55 of 63

Morphology

Morphology studies the internal structure of words, how words are built up from smaller meaningful units called morphemes

Morphemes are divided into two categories

Stems: The core meaning bearing units

Affixes: Bits and pieces adhering to stems to change their meanings and grammatical functions

Prefix: un-, anti-, etc (a-, ati-, pra- etc.)
Suffix: -ity, -ation, etc (-taa, -ke, -ka etc.)
Infix: ‘n’ in ‘vindati’ (he knows), as contrasted with vid (to know).

Text Processing: Basics

Week 1: Lecture 5

Pawan Goyal (IIT Kharagpur)

23 / 26

56 of 63

(Extra) Morphemes and Typology

Translation quality often seems to depend on typological differences

How morphemes come together to form words

57 of 63

Stemming

Text Processing: Basics

Week 1: Lecture 5

Reducing terms to their stems, used in information retrieval Crude chopping of affixes

language dependent

Pawan Goyal (IIT Kharagpur)

24 / 26

58 of 63

Stemming

Text Processing: Basics

Week 1: Lecture 5

Reducing terms to their stems, used in information retrieval Crude chopping of affixes

language dependent
automate(s), automatic, automation all reduced to automat

Pawan Goyal (IIT Kharagpur)

24 / 26

59 of 63

Porter’s algorithm

Text Processing: Basics

Week 1: Lecture 5

Pawan Goyal (IIT Kharagpur)

25 / 26

60 of 63

Porter’s algorithm

Text Processing: Basics

Week 1: Lecture 5

Pawan Goyal (IIT Kharagpur)

25 / 26

61 of 63

Porter’s algorithm

Text Processing: Basics

Week 1: Lecture 5

Pawan Goyal (IIT Kharagpur)

25 / 26

62 of 63

Porter’s algorithm

Text Processing: Basics

Week 1: Lecture 5

Step 2

ational → ate (relational → relate) izer → ize (digitizer → digitize) ator → ate (operator → operate)

Pawan Goyal (IIT Kharagpur)

26 / 26

63 of 63

Porter’s algorithm

Text Processing: Basics

Week 1: Lecture 5

Pawan Goyal (IIT Kharagpur)

26 / 26

Great Book: Speech and Language Processing, Jurafsky Martin