Basic Text Processing

IP notices: slides from D. Jurafsy, C. Manning and S. Batzoglou

Outline

• Regular Expressions
• Tokenization
• Word Tokenization
• Normalization
• Lemmatization and stemming
• Sentence Tokenization
• Clitics

Regular expressions

• A formal language for specifying text strings
• How can we search for any of these?
• woodchuck
• woodchucks
• Woodchuck
• Woodchucks

​

​

Regular Expressions: Disjunctions

• Letters inside square brackets []

​

​

​

​

• Ranges [A-Z]

​

​

Regular Expressions: Negation in Disjunction

• Negations: [^Ss]
• Carat means negation only when first in []

​

Regular Expressions: More Disjunction

• Woodchucks is another name for groundhog!
• The pipe | for disjunction

​

Regular Expressions: ? * + .

Stephen C Kleene

Kleene *, Kleene +

Regular Expressions: anchors ^ $

Example

Find me all instances of the word “the” in a text.

the

Misses capitalized examples

[tT]he

Incorrectly returns other or theology

[^a-zA-Z][tT]he[^a-zA-Z]

​

Errors

• The process we just went through was based on fixing two kinds of errors
• Matching strings that we should not have matched (there, then, other)
• False positives (Type I)
• Not matching things that we should have matched (The)
• False negatives (Type II)

Errors (cont.)

• In NLP we are always dealing with these kinds of errors.
• Reducing the error rate for an application often involves two antagonistic efforts:
• Increasing accuracy or precision (minimizing false positives)
• Increasing coverage or recall (minimizing false negatives).

Exercise

• Write a RE that matches a simple (not nested) HTML element
• Write a RE that matches email addresses
• Write a RE that matches URLs

(Experiment on Jupyter notebook: HLT/RegExpr.ipynb)

​

​

Summary

• Regular expressions play a surprisingly large role
• Sophisticated sequences of regular expressions are often the first model for any text processing text
• For many hard tasks, we use machine learning classifiers
• But regular expressions are used as features in the classifiers
• Can be very useful in capturing generalizations

​

13

Tokenization

Text Normalization

• Text normalization before text analysis:
1. Segmenting/tokenizing words in running text
2. Normalizing word formats
3. Segmenting sentences in running text

​

Tokenization

• For
• Information retrieval
• Information extraction (detecting named entities, etc.)
• Spell-checking
• 3 tasks
• Segmenting/tokenizing words in running text
• Normalizing word formats
• Segmenting sentences in running text
• Why not just periods and white-space?
• Mr. Sherwood said reaction to Sea Containers’ proposal has been "very positive." In New York Stock Exchange composite trading yesterday, Sea Containers closed at $62.625, up 62.5 cents.
• “I said, ‘what’re you? Crazy?’ “ said Sadowsky. “I can’t afford to do that.’’

​

​

​

What’s a word?

• I do uh main- mainly business data processing
• Fragments
• Filled pauses
• Are cat and cats the same word?
• Some terminology
• Lemma: a set of lexical forms having the same stem, major part of speech, and rough word sense
• Cat and cats = same lemma
• Wordform: the full inflected surface form.
• Cat and cats = different wordforms
• Token/Type

How many words?

they lay back on the San Francisco grass and looked at the stars and their

​

• Type/Form: an element of the vocabulary.
• Token: an instance of that type in running text.
• How many?
• 15 tokens (or 14)
• 13 types (or 12?)

How many words?

N = number of tokens

V = vocabulary = set of types

|V| is the size of the vocabulary

​

​

​

​

​

​

Church and Gale (1990): |V| > O(N^½)

​

Simple Tokenization in Unix

• Inspired by Ken Church’s “UNIX for Poets”
• Given a text file, output the word tokens and their frequencies

tr -sc 'A-Za-z' '\n' < shakes.txt

| sort

| uniq –c

​

1945 A

72 AARON

19 ABBESS

5 ABBOT

... ...

Change non-alpha to newlines

Sort in alphabetical order

Merge and count each type

The first step: tokenizing

tr -sc 'A-Za-z' '\n' < shakes.txt | head

​

THE

SONNETS

by

William

Shakespeare

From

fairest

creatures

We

...

The second step: sorting

tr -sc 'A-Za-z' '\n' < shakes.txt | sort | head

​

A

A

A

A

A

A

A

A

A

...

More counting

• Merging upper and lower case

tr 'A-Z' 'a-z' < shakes.txt | tr –sc 'A-Za-z' '\n' | sort | uniq –c

• Sorting the counts

tr 'A-Z' 'a-z' < shakes.txt | tr –sc 'A-Za-z' '\n' | sort | uniq –c | sort –n –r

23243 the

22225 i

18618 and

16339 to

15687 of

12780 a

12163 you

10839 my

10005 in

8954 d

What happened here?

Issues in Tokenization

• Finland’s capital?

Finland? Finlands? Finland’s

• what’re, I’m, isn’t?
• What are, I am, is not
• Hewlett-Packard?
• Hewlett and Packard as two tokens?
• state-of-the-art:
• Break up?
• lowercase, lower-case, lower case?
• San Francisco, New York: one token or two?
• Words with punctuation
• m.p.h., PhD.

Slide from Chris Manning

Tokenization: language issues

• Italian
• L’insieme? one token or two?
• L ? L’ ? Lo ?
• Want l’insieme to match with un insieme

​

• German noun compounds are not segmented

Lebensversicherungsgesellschaftsangestellter Leben’s+versicherung’s+gesellschaft’s+angestellter

‘life insurance company employee’

German text processing benefits greatly from a compound splitter module

Slide from Chris Manning

Tokenization: language issues

• Chinese and Japanese no spaces between words:
• 莎拉波娃现在居住在美国东南部的佛罗里达。
• 莎拉波娃 现在 居住 在 美国 东南部 的 佛罗里达
• Sharapova now lives in US southeastern Florida
• Further complicated in Japanese, with multiple alphabets intermingled
• Dates/amounts in multiple formats

フォーチュン500社は情報不足のため時間あた$500K(約6,000万円)

End-user can express query entirely in hiragana!

Slide from Chris Manning

Word Tokenization in Chinese

• Words composed of characters
• Characters are generally 1 syllable and 1 morpheme.
• Average word is 2.4 characters long.
• Standard segmentation algorithm:
• Maximum Matching
• (also called Greedy)

Maximum Matching Word Segmentation Algorithm

Given a wordlist of Chinese, and a string.

1. Start a pointer at the beginning of the string
2. Find the longest word in dictionary that matches the string starting at pointer
3. Move the pointer over the word in string
4. Go to 2

English failure example (Palmer 2000)

• the table down there
• thetabledownthere
• Theta bled own there

​

• But works astonishingly well in Chinese
• 莎拉波娃现在居住在美国东南部的佛罗里达。
• 莎拉波娃 现在 居住 在 美国 东南部 的 佛罗里达
• Modern algorithms better still:
• probabilistic segmentation
• Using “sequence models” like HMMs

Word Normalization and Stemming

Normalization

• Need to “normalize” terms
• For IR, indexed text & query terms must have same form.
• We want to match U.S.A. and USA
• We most commonly implicitly define equivalence classes of terms
• e.g., by deleting periods in a term
• Alternative is to do asymmetric expansion:
• Enter: window Search: window, windows
• Enter: windows Search: Windows, windows, window
• Enter: Windows Search: Windows
• Potentially more powerful, but less efficient

​

Slide from Chris Manning

Case folding

• For Information Retrieval: reduce all letters to lower case
• exception: upper case in mid-sentence?
• e.g., General Motors
• Fed vs. fed
• SAIL vs. sail
• Often best to lower case everything, since users will use lowercase regardless of ‘correct’ capitalization…
• For sentiment analysis, MT, Info extraction
• Case is helpful (“US” versus “us” is important)

Slide from Chris Manning

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: find correct dictionary headword form
• Machine translation
• Spanish quiero (‘I want’), quieres (‘you want’) same lemma as querer ‘want’

​

Slide from Chris Manning

Morphology

• Morphemes:
• smaller meaningful units that make up words:
• Stems: The core meaning bearing units
• Affixes: Bits and pieces that adhere to stems to change their meanings and grammatical functions

Stemming

• Reduce terms to their “roots” before indexing
• “Stemming” is crude chopping of “affixes”
• language dependent
• e.g., automate(s), automatic, automation all reduced to automat.

for example compressed

and compression are both

accepted as equivalent to

compress.

for exampl compress and

compress ar both accept

as equival to compress

Slide from Chris Manning

Porter’s algorithm

• Commonest algorithm for stemming English
• A sequence of phases
• each phase consists of a set of rules
• sses → ss
• ies → i
• ational → ate
• tional → tion
• Some rules only apply to multi-syllable words
• (syl > 1) EMENT → ø
• replacement → replac
• cement → cement

​

​

​

Slide from Chris Manning

Porter’s algorithm

Step 1a

sses → ss caresses → caress

ies → I ponies → poni

ss → ss caress → caress

s → ø cats → cat

Step 1b

(*v*)ing → ø walking → walk

sing → sing

(*v*)ed → ø plastered → plaster

…

​

Step 2 (for long stems)

ational → ate relational → relate

izer → ize digitizer → digitize

ator → ate operator → operate

…

Step 3 (for longer stems)

al → ø revival → reviv

able → ø adjustable → adjust

ate → ø activate → activ

…

​

Viewing morphology in a corpus

(*v*)ing → ø walking → walk

sing → sing

​

Vowel present

Viewing morphology in a corpus

• Why only strip-ing if there is a vowel?

(*v*)ing → ø walking → walk

sing → sing

​

tr -sc 'A-Za-z' '\n' < shakes.txt | grep ’ing$' | sort | uniq -c | sort –nr

​

​

​

​

​

​

​

​

​

​

​

​

tr -sc 'A-Za-z' '\n' < shakes.txt | grep '[aeiou].*ing$' | sort | uniq -c | sort –nr

548 being

541 nothing

152 something

145 coming

130 morning

122 having

120 living

117 loving

116 Being

102 going

1312 King

548 being

541 nothing

388 king

375 bring

358 thing

307 ring

152 something

145 coming

130 morning

Vowel present

Dealing with complex morphology

• Some languages require segmenting morphemes

Turkish:

Uygarlastiramadiklarimizdanmissinizcasina

‘(behaving) as if you are among those whom we could not civilize’

Uygar `civilized’ + las `become’

+ tir `cause’ + ama `not able’

+ dik `past’ + lar ‘plural’

+ imiz ‘p1pl’ + dan ‘abl’

+ mis ‘past’ + siniz ‘2pl’ + casina ‘as if’

​

Sentence Segmentation

Sentence Segmentation

• !, ? relatively unambiguous
• Period “.” is quite ambiguous
• Sentence boundary
• Abbreviations like Inc. or Dr.
• General idea:
• Build a binary classifier:
• Looks at a “.”
• Decides EndOfSentence/NotEOS
• Classifiers: hand-written rules, regular expressions, or machine-learning

Decision Tree Classifier for EOS

More sophisticated decision tree features

• Prob(word with “.” occurs at end-of-s)
• Prob(word after “.” occurs at begin-of-s)
• Length of word with “.”
• Length of word after “.”
• Case of word with “.”: Upper, Lower, Cap, Number
• Case of word after “.”: Upper, Lower, Cap, Number
• Punctuation after “.” (if any)
• Abbreviation class of word with “.” (month name, unit-of-measure, title, address name, etc)

Slide from Richard Sproat

Learning Decision Trees

• DTs are rarely built by hand
• Hand-building only possible for very simple features, domains
• Several algorithms available for DT induction:
• S. Ruggieri. Efficient C4.5

Alternative: using a ML classifier

Train a binary classifier to determine whether a punctuation character is an end of sentence

• Training set:
• A list of sentences
• Features
• Example: Splitta (uses SVM classifier)

Punkt Sentence Splitter

• Sentence splitting

import nltk.data

splitter = nltk.data.load(

'tokenizers/punkt/english.pickle')

for line in file:

for sent in splitter.tokenize(line.strip()):

print sent

• Tokenizer

tokenizer = splitter._lang_vars.word_tokenize

print ' '.join(tokenizer(sent))

​

Even Better

• Train a ternary classifier to distinguish between:
• Normal character
• End of token
• End of sentence
• See Stanza tokenizer tokenizer
• https://stanfordnlp.github.io/stanza/tokenize.html

Dealing with clitics

• Some languages have composite words, called clitics, or enclitics
• For example, in Italian:

lasciami, lasciatemelo

lascia-mi, lasciate-me-lo

• Splitting the clitics is important for parsing, since clitics incorporate relevant syntactic components, e.g. a pronoun corresponding to an object of the verb, which the parser needs to identify
• Train 4-class tokenizer (https://stanfordnlp.github.io/stanza/mwt.html):
• Normal character
• End of token
• End of sentence
• Start of clitic

Summary

• Regular Expressions
• Tokenization
• Word Tokenization
• Normalization
• Lemmatization and stemming
• Sentence Tokenization
• Splitting clitics

​