Chapter Two

Text Operations
 Introduction
 Before a computerised information retrieval system can
actually operate to retrieve some information, that
information must have already been stored inside the
computer.
 Originally it will usually have been in the form of
documents.
 The computer, however, is not likely to have
stored the complete text of each document in the natural
language in which it was written.
 It will have, instead, a document representative which
may have been produced from the documents either
manually or automatically.
2
 The starting point of the text analysis process may be the
complete document text, an abstract, the title only, or
perhaps a list of words only.
 From it the process must produce a document
representative in a form which the computer can handle.
 Text operation is the task of preprocessing text documents
to control the size of the vocabulary or the number of
distinct words used as index terms.
 Preprocessing will lead to an improvement in the
information retrieval performance.
 However, some search engines on the Web omit
preprocessing
– Every word in the document is an index term

3
 Text Pre-processing Operations
 5 main operations for selecting index terms, i.e. to choose
words/stems to be used as indexing terms:
1. Lexical analysis/Tokenization of the text: generate a set or
words from text collection.
2. Elimination of stop words: filter out words which are not
useful in the retrieval process.
3. Normalization: Normalization is transforming text into a
single canonical form.
4. Stemming words: remove affixes (prefixes and suffixes)
and group together word variants with similar meaning.
5. Construction of term categorization structures such as
thesaurus, to capture relationship among words for
allowing the expansion of the original query with related
terms.
4
• Text Processing System
– Input text – full text, abstract or title
– Output – a document representative adequate for use in an
automatic retrieval system
• The document representative consists of a list of class names,
each name representing a class of words occurring in the total
input text. A document will be indexed by a name if one of its
significant words occurs as a member of that class.

5
 Lexical Analysis/Tokenization of Text
• Tokenization is one of the step used to convert text of the
documents into a sequence of words, w1, w2, … wn to be
adopted as index terms.
– It is the process of demarcating and possibly classifying
sections of a string of input characters into words.
– For example,
• The quick brown fox jumps over the lazy dog
• Objective of tokenization is identifying words in the text
– What is a word means?
• Is that a sequence of characters, numbers and alpha-
numeric once?
– How we identify a set of words that exist in a text
documents?
• Tokenization Issues
– numbers, hyphens, punctuations marks, apostrophes … 6
 Issues in Tokenization
• Two words may be connected by hyphens.
–Can two words connected by hyphens and punctuation marks
taken as one word or two words? Break up hyphenated sequence
as two tokens?
• In most cases hyphen – break up the words (e.g. state-of-the-art  state of
the art), but some words, e.g. MS-DOS, B-49 - unique words which
require hyphens.
• Two words may be connected by punctuation marks.
– remove totally punctuation marks unless significant, e.g. program code: x.exe
and xexe.
• Two words may be separated by space.
– E.g. Addis Ababa, San Francisco, Los Angeles
• Two words may be written in different ways
– lowercase, lower-case, lower case ?
– data base, database, data-base?
7
 Issues in Tokenization
• Numbers: Are numbers/digits words & used as index terms?
– dates (3/12/91 vs. Mar. 12, 1991);
– phone numbers (+251923415005)
– IP addresses (100.2.86.144)
– Generally, don’t index numbers as text most numbers are not
good index terms (like 1910, 1999)
• What about case of letters (e.g. Data or data or DATA):
– cases are not important and there is a need to convert all to
upper or lower. Which one is mostly followed by human
beings?
• Simplest approach is to ignore all numbers & punctuations and
use only case-insensitive unbroken strings of alphabetic
characters as tokens.
• Issues of tokenization are language specific
– Requires the language to be known
8
 Tokenization
• Analyze text into a sequence of discrete tokens (words).
• Input: “Friends, Romans and Countrymen”
• Output: Tokens (an instance of a sequence of characters that are
grouped together as a useful semantic unit for processing).
– Friends
– Romans
– and
– Countrymen
• Each such token is now a candidate for an index entry, after
further processing.
• But what are valid tokens to emit as index terms?

9
 Exercise: Tokenization
• The cat slept peacefully in the living room. It’s a very
old cat.

• The instructor (Dr. O’Neill) thinks that the boys’

stories about Chile’s capital aren’t amusing.

10
 Elimination of Stop words
• Stop words are extremely common words across document
collections that have no discriminatory power.
– They may occur in 80% of the documents in a collection.
• Stop words have little semantic content; It is typical to remove
such high-frequency words.
– They would appear to be of little value in helping select
documents matching a user need and needs to be filtered out
as potential index terms.
• Examples of stop words are articles, prepositions etc.:
– articles (a, an, the); pronouns: (I, he, she, it, their, his)
– Some prepositions (on, of, in, about, besides, against),
conjunctions/ connectors (and, but, for, nor, or, so, yet), verbs
(is, are, was, were), adverbs (here, there, out, because, soon,
after) and adjectives (all, any, each, every, few, many, some)
can also be treated as stop words.
11
 Stop words
• Intuition:
– Stopwords take up 50% of the text. Hence, document size
reduces drastically enabling to organizes smaller indices
for information retrieval
– Good compression techniques for indices: The 30
most common words account for 30% of the tokens
in written text
• Better approximation of importance for classification,
summarization, etc.
• Stop words are language dependent.

12
 How to detect a stop word?
• One method: Sort terms (in decreasing order) by document
frequency and take the most frequent ones
– In a collection about insurance practices, “insurance”
would be a stop word
• Another method: Build a stop word list that contains a set
of articles, pronouns, etc.
– Why do we need stop lists: With a stop list, we can
compare and exclude from index terms entirely the
commonest words.
• With the removal of stop words, we can measure better
approximation of importance for classification,
summarization, etc.

13
• Stop word elimination used to be standard in older IR systems.
• But the trend is away from doing this. Most web search engines
index stop words:
–Good query optimization techniques mean you pay little at
query time for including stop words.
–You need stop words for:
• Phrase queries: “King of Denmark”
• Various song titles, etc.: “Let it be”, “To be or not to be”
• “Relational” queries: “flights to London”
– Elimination of stop words might reduce recall (e.g. “To be or
not to be” – all eliminated except “be” – no or irrelevant
retrieval)

14
 Normalization
• It is canonicalizing tokens so that matches occur despite
superficial differences in the character sequences of the tokens
– Need to “normalize” terms in indexed text as well as query
terms into the same form
– Example: We want to match U.S.A. and USA, by deleting
periods in a term
• Case Folding: Often best to lower case everything, since users
will use lowercase regardless of ‘correct’ capitalization…
– Republican vs. republican
– haramaya vs. Haramaya vs. HARAMAYA
– Anti-discriminatory vs. antidiscriminatory
– Car vs. automobile?

15
 Normalization issues
• Good for
– Allow instances of Automobile at the beginning of
a sentence to match with a query of automobile
– Helps a search engine when most users type ferrari
when they are interested in a Ferrari car
• Bad for
– Proper names vs. common nouns
• E.g. General Motors, Associated Press, …
• Solution:
– lowercase only words at the beginning of the sentence
• In IR, lowercasing is most practical because of the way
users issue their queries
16
 Stemming/Morphological analysis
• Stemming reduces tokens to their “root” form of words to
recognize morphological variation.
–The process involves removal of affixes (i.e. prefixes and
suffixes) with the aim of reducing variants to the same stem.
• Often stemming removes inflectional and derivational
morphology of a word.
–Inflectional morphology: vary the form of words in order to
express grammatical features, such as singular/plural or
past/present tense. E.g. Boy → boys, cut → cutting.
–Derivational morphology: makes new words from old ones. E.g.
creation is formed from create , but they are two separate words.
And also, destruction → destroy.
• Stemming is language dependent
– Correct stemming is language specific and can be complex.
17
 Stemming
• The final output from a conflation algorithm is a set of classes, one
for each stem detected.
–A Stem: the portion of a word which is left after the removal of
its affixes (i.e., prefixes and/or suffixes).
–Example: ‘connect’ is the stem for {connected, connecting
connection, connections}
–Thus, [automate, automatic, automation] all reduce to 
automat
• A class name is assigned to a document if and only if one of its
members occurs as a significant word in the text of the document.
–A document representative then becomes a list of class names,
which are often referred as the documents index terms/keywords.
• Queries : Queries are handled in the same way.

18
 Ways to implement stemming
There are basically two ways to implement stemming.
 The first approach is to create a big dictionary that maps
words to their stems.
• The advantage of this approach is that it works perfectly (insofar
as the stem of a word can be defined perfectly); the disadvantages
are the space required by the dictionary and the investment
required to maintain the dictionary as new words appear.
 The second approach is to use a set of rules that extract stems
from words.
• The advantages of this approach are that the code is typically
small, and it can gracefully handle new words; the disadvantage
is that it occasionally makes mistakes.
• But, since stemming is imperfectly defined, anyway, occasional
mistakes are tolerable, and the rule-based approach is the one that
is generally chosen.
19
 Porter Stemmer
• Stemming is the operation of stripping the suffices from a word,
leaving its stem.
– Google, for instance, uses stemming to search for web pages
containing the words connected, connecting, connection and
connections when users ask for a web page that contains the word
connect.
• In 1979, Martin Porter developed a stemming algorithm that uses a
set of rules to extract stems from words, and though it makes some
mistakes, most common words seem to work out right.
– Porter describes his algorithm and provides a reference
implementation in C at

– http://tartarus.org/~martin/PorterStemmer/index.html

20
 Porter stemmer
• Most common algorithm for stemming English words to their
common grammatical root
• It is simple procedure for removing known affixes in English
without using a dictionary. To gets rid of plurals the following
rules are used:
– SSES  SS caresses  caress
–IES  i ponies  poni
–SS  SS caress → caress
–S   cats  cat
–EMENT   (Delete final ement if what remains is longer than
1 character )
replacement  replac
cement  cement

21
 Porter stemmer
• While step 1a gets rid of plurals, step 1b removes -ed or -
ing.
– e.g.
;; agreed -> agree ;; disabled -> disable
;; matting -> mat ;; mating -> mate
;; meeting -> meet ;; milling -> mill
;; messing -> mess ;; meetings -> mee
;; feed -> feedt

22
 Stemming: challenges
• May produce unusual stems that are not English
words:
– Removing ‘UAL’ from FACTUAL and EQUAL

• May conflate (reduce to the same token) words

that are actually distinct.
• “computer”, “computational”, “computation” all
reduced to same token “comput”

• Not recognize all morphological derivations.

23
 Thesauri
• Mostly full-text searching cannot be accurate, since different authors
may select different words to represent the same concept
– Problem: The same meaning can be expressed using different
terms that are synonyms, homonyms and related terms
– How can it be achieved such that for the same meaning the
identical terms are used in the index and the query?
• Thesaurus: The vocabulary of a controlled indexing language,
formally organized so that a priori relationships between concepts
(for example as "broader" and “related") are made explicit.
• A thesaurus contains terms and relationships between terms
– IR thesauri rely typically upon the use of symbols such as
USE/UF (UF=used for), BT, and RT to demonstrate inter-term
relationships.
–e.g., car = automobile, truck, bus, taxi, motor vehicle
-color = colour, paint 24
 Aim of Thesaurus
• Thesaurus tries to control the use of the vocabulary by showing
a set of related words to handle synonyms and homonyms.
• The aim of thesaurus is therefore:
– To provide a to form equivalence classes, and we index such
equivalent standard vocabulary for indexing and searching.
• When the document contains automobile, index it under
car as well (usually, also vice-versa).
– To assist users with locating terms for proper query
formulation: When the query contains automobile, look
under car as well for expanding query.
– To provide classified hierarchies that allow the broadening
and narrowing of the current request according to user
needs.

25
 Thesaurus Construction
Example: thesaurus built to assist IR for
searching cars and vehicles :
Term: Motor vehicles
UF : Automobiles
Cars
Trucks
BT: Vehicles
RT: Road Engineering
Road Transport

26
 More Example
Example: thesaurus built to assist IR in the fields of
computer science:
TERM: natural languages
– UF natural language processing (UF=used for NLP)
– BT languages (BT=broader term is languages)
– TT languages (TT = top term is languages)
– RT artificial intelligence (RT=related term/s)
computational linguistic
formal languages
query languages
speech recognition

27
 Language-specificity
• Many of the above features embody transformations
that are
– Language-specific and
– Often, application-specific

• These are “plug-in” addenda to the indexing process

• Both open source and commercial plug-ins are
available for handling these

28
 Index Term Selection
• Index language is the language used to describe documents
and requests.
• Elements of the index language are index terms which may
be derived from the text of the document to be described,
or may be arrived at independently.
– If a full text representation of the text is adopted, then
all words in the text are used as index terms = full text
indexing.
– Otherwise, need to select content-bearing words to be
used as index terms for reducing the size of the index
file which is basic to design an efficient searching IR
system.

29
Term weighting
 Terms
 Terms are usually stems. Terms can be also phrases, such as
“Computer Science”, “World Wide Web”, etc.
Documents and queries are represented as vectors or “bags of
words” (BOW).
 Each vector holds a place or every term in the collection.
 Position 1 corresponds to term 1, position 2 to term 2,
position n to term n.
W=0 if a term is absent

Documents are represented by binary weights or Non-binary

weighted vectors of terms.
31
 Document Collection
A collection of n documents can be represented in the vector
space model by a term-document matrix.
An entry in the matrix corresponds to the “weight” of a term
in the document; zero means the term has no significance in
the document or it simply doesn’t exist in the document.

32
 Binary Weights
• Only the presence (1) or absence (0) of
docs t1 t2 t3
a term is included in the vector D1 1 0 1
D2 1 0 0
• Binary formula gives every word that D3 0 1 1
appears in a document equal D4 1 0 0
relevance. D5 1 1 1
D6 1 1 0
D7 0 1 0
• It can be useful when frequency is not D8 0 1 0
important. D9 0 0 1
D10 0 1 1
D11 1 0 1
• Binary Weights Formula:
1 if freqij  0

freqij  
0 if freqij  0
 33
 Why we use term weighting?
 Binary weights are too limiting.
 Terms are either present or absent.
 Not allow to order documents according to their level of
relevance for a given query.

 Non-binary weights allow to model partial matching .

 Partial matching allows retrieval of docs that approximate
the query.
 Term-weighting improves quality of answer set.
 Term weighting enables ranking of retrieved documents;
such that best matching documents are ordered at the top as
they are more relevant than others.

34
 Term Weighting: Term Frequency (TF)
 TF (term frequency) - Count the number
of times term occurs in document.
docs t1 t2 t3
fij = frequency of term i in document j
D1 2 0 3
 The more times a term t occurs in D2 1 0 0
document d the more likely it is that t is
D3 0 4 7
relevant to the document, i.e. more
indicative of the topic.. D4 3 0 0
 If used alone, it favors common words and D5 1 6 3
long documents. D6 3 5 0
 It gives too much credit to words that D7 0 8 0
appears more frequently. D8 0 10 0
 May want to normalize term frequency (tf) D9 0 0 1
across the entire corpus: D10 0 3 5
tfij = fij / max{flj} D11 4 0 1

35
 Document Normalization
• Long documents have an unfair advantage:
– They use a lot of terms
• So they get more matches than short documents
– And they use the same words repeatedly
• So they have much higher term frequencies

• Normalization seeks to remove these effects:

– Related somehow to maximum term frequency.
– But also sensitive to the number of terms.
• If we don’t normalize short documents may not be
recognized as relevant.

36
 Problems with term frequency
 Need a mechanism for attenuating the effect of terms that
occur too often in the collection to be meaningful for
relevance/meaning determination
 Scale down the term weight of terms with high collection
frequency
– Reduce the tf weight of a term by a factor that grows with
the collection frequency
 More common for this purpose is document frequency
– how many documents in the collection contain the term

• The example shows that collection

frequency and document frequency
behaves differently
37
 Document Frequency
It is defined to be the number of documents in the
collection that contain a term
DF = document frequency
Count the frequency considering the whole
collection of documents.
Less frequently a term appears in the whole
collection, the more discriminating it is.

df i = document frequency of term i

= number of documents containing term i

38
 Inverse Document Frequency (IDF)
 IDF measures rarity of the term in collection. The IDF is a
measure of the general importance of the term.
 Inverts the document frequency.
 It diminishes the weight of terms that occur very frequently
in the collection and increases the weight of terms that occur
rarely.
 Gives full weight to terms that occur in one document
only.
 Gives lowest weight to terms that occur in all documents.
 Terms that appear in many different documents are less
indicative of overall topic.
idfi = inverse document frequency of term i,
= log2 (N/ df i) (N: total number of documents)

39
 Inverse Document Frequency
• E.g.: given a collection of 1000 documents and document
frequency, compute IDF for each word?

• IDF provides high values for rare words and low values for
common words.
• IDF is an indication of a term’s discrimination power.
• Log used to dampen the effect relative to tf.
40
 TF*IDF Weighting
 The most used term-weighting is tf*idf weighting scheme:

wij = tfij idfi = tfij * log2 (N/ dfi)

 A term occurring frequently in the document but rarely in

the rest of the collection is given high weight.
 The tf*idf value for a term will always be greater than or
equal to zero.
 Experimentally, tf*idf has been found to work well.
 It is often used in the vector space model together with
cosine similarity to determine the similarity between two
documents.

41
 TF*IDF weighting
When does TF*IDF registers a high weight? when a
term t occurs many times within a small number of
documents.
 Highest tf*idf for a term shows a term has a high term frequency
(in the given document) and a low document frequency (in the
whole collection of documents);
 the weights hence tend to filter out common terms.
 Thus lending high discriminating power to those documents.
Lower TF*IDF is registered when the term occurs fewer
times in a document, or occurs in many documents.
 Thus offering a less pronounced relevance signal
Lowest TF*IDF is registered when the term occurs in
virtually all documents.
42
 Computing TF-IDF: An Example
 Assume collection contains 10,000 documents and statistical
analysis shows that document frequencies (DF) of three terms are:
A(50), B(1300), C(250). And also term frequencies (TF) of these
terms are: A(3), B(2), C(1) with a maximum term frequency of 3.
Compute TF*IDF for each term?

A: tf = 3/3=1.0 idf = log2(10000/50) = 7.644 tf*idf =

7.644
B: tf = 2/3=0.667 idf = log2(10000/1300) = 2.943;
tf*idf = 1.962
C: tf = 1/3=0.33 idf = log2(10000/250) = 5.322;
tf*idf = 1.774

43
 More Example
• Consider a document containing 100 words wherein
the word cow appears 3 times. Now, assume we have
10 million documents and cow appears in one
thousand of these.
– The term frequency (TF) for cow :
3/100 = 0.03
– The inverse document frequency is
log2(10,000,000 / 1,000) = 13.228
– The TF*IDF score is the product of these frequencies: 0.03
* 13.228 = 0.39684

44
 Exercise 1
• Let C = number of
times a given word
appears in a document;
• TW = total number of
words in a document;
• TD = total number of
documents in a corpus,
and
• DF = total number of
documents containing
a given word;
• Compute TF, IDF and
TF*IDF score for
each term

45
 Exercise 2
• A database collection consists of 1 million documents,
of which 200,000 contain the term holiday while
250,000 contain the term season. A document repeats
holiday 7 times and season 5 times. It is known that
holiday is repeated more than any other term in the
document. Calculate the weight of both terms in this
document using
(i) normalized and un-normalized TF;
(ii) TF*IDF based on normalized and un-normalized
TF

46
 Statistical Properties of Text
 Most large collections of text documents have similar
statistical characteristics. Such properties of text collection
greatly affect the performance of IR system & can be used to
select suitable term weights & other aspects of the system.
 Retrieval models and ranking algorithms depend heavily on
statistical properties of words.
 Statistical Properties of text
 How is the frequency of different words distributed?
 How fast does vocabulary size grow with the size of a corpus?
 There are three well-known researcher who define statistical
properties of words in a text:
 Zipf’s Law: models word distribution in text corpus
 Luhn’s idea: measures word significance
 Heap’s Law: shows how vocabulary size grows with the growth
corpus size.
47
 Word Distribution
• A few words are very
common.
2 most frequent
words (e.g. “the”,
“of”) can account for
about 10% of word
occurrences.
• Most words are very
rare.
Half the words in a
corpus appear only
once, called “read
only once”
48
 Word distribution: Zipf's Law
• Zipf's Law- named after the Harvard linguistic professor George
Kingsley Zipf (1902-1950),
 Attempts to capture the distribution of the frequencies (i.e. ,
number of occurances ) of the words within a text.
• For all the words in a collection of documents, for each word w
 f : is the frequency that w appears
 r : is rank of w in order of frequency. (The most commonly
occurring word has rank 1, etc.)

49
 Word distribution: Zipf's Law
• Zipf's Law states that when the distinct words in a text are
arranged in decreasing order of their frequency of occuerence
(most frequent words first), the occurence characterstics of the
vocabulary can be characterized by the constant rank-frequency
law of Zipf.
• If the words, w, in a
collection are ranked, r,
by their frequency, f,
they roughly fit the
relation:
r*f=c
– Different collections
have different constants
c.

• The table shows the most frequently occurring words from 336,310 document corpus
containing 125, 720, 891 total words; out of which 508, 209 are unique words 50
 More Example: Zipf’s Law
• Illustration of Rank-Frequency Law. Let the total number
of word occurrences in the sample N = 1, 000, 000

51
 Zipf’s law: modeling word distribution
• Given that occurrence of the most frequent word is f1
times, the collection frequency of the ith most
1
common term is proportional to 1/i fi 
– If the most frequent term occurs f1 times, then the i
second most frequent term has half as many
occurrences, the third most frequent term has a
third as many, etc
• Zipf's Law states that the frequency of the ith most
frequent word is 1/iӨ times that of the most frequent
word
– occurrence of some event (P), as a function of the
rank (i) when the rank is determined by the
frequency of occurrence, is a power-law function
Pi ~ 1/i Ө with the exponent Ө close to unity.
52
 Methods that Build on Zipf's Law
• Stop lists:
• Ignore the most frequent words (upper cut-off).
Used by almost all systems.
• Significant words:
• Take words in between the most frequent (upper
cut-off) and least frequent words (lower cut-off).
• Term weighting:
• Give differing weights to terms based on their
frequency, with most frequent words weighed less.
Used by almost all ranking methods.

53
 Word significance: Luhn’s Ideas
 Luhn Idea (1958): the frequency of word occurrence in a text
furnishes a useful measurement of word significance.
 Luhn suggested that both extremely common and extremely
uncommon words were not very useful for indexing.
 For this, Luhn specifies two cutoff points: an upper and a
lower cutoffs based on which non-significant words are
excluded.
 The words exceeding the upper cutoff were considered to be
common.
 The words below the lower cutoff were considered to be rare
 Hence they are not contributing significantly to the content of
the text.
 The ability of words to discriminate content, reached a peak at a
rank order position half way between the two-cutoffs.
 Let f be the frequency of occurrence of words in a text, and r
their rank in decreasing order of word frequency, then a plot
relating f & r yields the following curve.
54
 Luhn’s Ideas

Luhn (1958) suggested that both extremely common and

extremely uncommon words were not very useful for
document representation & indexing.
55
 Vocabulary Growth: Heaps’ Law
 How does the size of the overall vocabulary (number of
unique words) grow with the size of the corpus?
 This determines how the size of the inverted index will scale
with the size of the corpus.
 Heap’s law: estimates the number of vocabularies in a given
corpus
 The vocabulary size grows by O(nβ), where β is a constant
between 0 – 1.
 If V is the size of the vocabulary and n is the length of the
corpus in words, Heap’s provides the following equation:
Where constants:
 K  10100 
   0.40.6 (approx. square-root) V  Kn
56
 Heap’s distributions
Distribution of size of the vocabulary vs. total number
of terms extracted from text corpus

Example: from 1,000,000,000 documents, there may be

1,000,000 distinct words. Can you agree?
57
 Example: Heaps Law
 We want to estimate the size of the vocabulary for a corpus
of 1,000,000 words.
 Assume that based on statistical analysis on smaller corpora
sizes:
 A corpus with 100,000 words contain 50,000 unique words;
and
 A corpus with 500,000 words contain 150,000 unique words
 Estimate the vocabulary size for the 1,000,000 words
corpus?
 What about for a corpus of 1,000,000,000 words?

58