Chapter 2 Text Operations
Index Term Selection and Text Operations
Index Term Selection – Noun words (or group of noun
words) are more representative of the semantics of a doc
content
Preprocess the text of docs in collection in order to select
the meaningful/representative index terms
• Control the size of the vocabulary
E.g., “the house of the lord”
10/03/2025
2
Statistical Properties of Text
How is the frequency of different words distributed?
How fast does vocabulary size grow with the size of a
corpus?
Such factors affect the performance of IR system & can be
used to select suitable term weights & other aspects of the
system.
A few words are very common.
2 most frequent words (e.g.“the”,“of”) can account for about
10% of word occurrences in a document.
Most words are very rare.
Half the words in a corpus appear only once, called“read only
once”
Called a“heavy tailed”distribution,since most of the probability
10/03/2025
Zipf’s distributions Rank Frequency Distribution
3
10/03/2025
Word distribution: Zipf's Law
4
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 occurrences ) of the words within a
text.
Zipf's Law states that when the distinct words in a text are
arranged in decreasing order of their frequency of occurrences
(most frequent words first),the occurrence characteristics of the
vocabulary can be characterized by the constant rank-frequency
law of Zipf: Frequency * Rank = constant
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.
10/03/2025
Example: Zipf's Law
5
The table shows the most frequently occurring words from 336,310
document collection containing 125,720,891 total words ; out of
which there are 508,209 unique words
10/03/2025
More Example: Zipf’s Law
6
Illustration of Rank-Frequency Law. Let the total number of word occurrences in
the sample N = 1,000,000
Rank(R) Term Frequency(F) R.(F/N)
1 the 69971 0.070
2 of 36411 0.073
3 and 28852 0.086
4 to 26149 0.104
5 a 23237 0.116
6 in 21341 0.128
7 that 10595 0.074
8 is 10099 0.081
9 was 9816 0.088
10 he 9543 0.095
10/03/2025
Methods that Build on Zipf's Law
7
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
weighted less. Used by almost all ranking methods.
10/03/2025
Explanations for Zipf’s Law
8
The law has been explained by “principle of least effort” which
makes it easier for a speaker or writer of a language to repeat certain
words instead of coining new and different words.
Zipf’s explanation was his “principle of least effort” which balance
between speaker’s desire for a small vocabulary and hearer’s desire
for a large one.
Zipf’s Law Impact on IR
Good News:Stopwords will account for a large fraction of text so
eliminating them greatly reduces inverted-index storage costs.
Bad News:For most words, gathering sufficient data for meaningful
statistical analysis (e.g. for correlation analysis for query expansion)
is difficult since they are extremely rare.
10/03/2025
Word significance: Luhn’s Ideas
9
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
10/03/2025
10
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
10/03/2025
Luhn’s Ideas
11
Luhn’s Ideas
uhn (1958) suggested that both extremely common and
xtremely uncommon words were not very useful for documen
representation & indexing.
10/03/2025
Vocabulary size : Heaps’ Law
12
How to estimates the number of vocabularies in a given corpus
Dictionaries
600,000 words and above
But they do not include names of people, locations, products etc
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
10/03/2025
13
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 10100
0.40.6 (approx. square-root)
10/03/2025
Heap’s distributions
14
Distribution of size of the vocabulary: there is a linear
relationship between vocabulary size and number of
tokens
• Example: from 1,000,000,000 words, there may be 100,000
distinct words. Can you agree?
10/03/2025
15
Example
We want to estimate the size of the vocabulary for a
corpus of 1,000,000 words. How ever, we only know
the statistics computed on smaller corpora sizes:
For 100,000 words, there are 50,000 unique words
For 500,000 words, there are 150,000 unique words
Estimate the vocabulary size for the 1,000,000 words
corpus?
How about for a corpus of 1,000,000,000 words?
10/03/2025
16
Relevance Measure
retrieved& notretrieved
irrelevant relevant
irrelevant &irrelevant
retrieved& notretrieved
relevant butrelevant
10/03/2025
Issues: recall and precision
17
breaking up hyphenated terms increase recall but
decrease precision
preserving case distinctions enhance precision but
decrease recall
commercial information systems usually take recall
enhancing approach (numbers and words containing
digits are index terms, and all are case insensitive)
10/03/2025
Text Operations
18
Are all words in a document important?
Not all words in a document are equally significant to represent the
contents/meanings of a document
Some word carry more meaning than others
Noun words are the most representative of a document content
Therefore, need to preprocess the text of a document in a
collection to be used as index terms
Using the set of all words in a collection to index documents
creates too much noise for the retrieval task
Reduce noise means reduce words which can be used to refer to
the document
Text operations is the process of transforming text documents in to
their logical representations that can be used as index terms
10/03/2025
Text Operations
19
Encryption
10/03/2025
Text Operations (cont…)
20
Preprocessing is the process of controlling 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
10/03/2025
Main Text Operations
21
5 main operations for selecting index terms, i.e. to choose
words/stems (or groups of words) to be used as indexing terms:
Tokenization of the text: generate a set of words from text
collection
Elimination of stop words - filter out words which are not
improrant in the retrieval process
Normalization – resolving artificial difference among words
Stemming words - remove affixes (prefixes and suffixes) and
group together word variants with similar meaning
Construction of term categorization structures such as
thesaurus, to capture relationship for allowing the expansion of
the original query with related terms
10/03/2025
Generating Document Representatives
22
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.
10/03/2025
23
The logical view of the document is provided by
representative keywords or index terms, which are
frequently used historically to represent documents in a
collection.
In modern computers, retrieval systems adopt a full-text
logical view of the document.
However, with very large collections, the set of
representative keywords may have to be reduced.
This process of reduction or compression of the set of
representative keywords is called text operations (or
transformation).
10/03/2025
24
Logic view of a doc in text preprocessing
10/03/2025
Goals of Text Operations
25
Improve the quality of answer set (recall-
precision figures)
Reduce the space and search time
Document Preprocessing
Lexical analysis of the text
Elimination of stop words
Stemming the remaining words
Selecting of indexing terms
Construction term categorization structures
– Thesauri
– Word/Doc Clustering
10/03/2025
1. Lexical Analysis/Tokenization of Text
26
Lexical analysis or Tokenization is a fundamental operation in both
query processing and automatic indexing.
It is the process of converting an input stream of characters into a
stream of words or tokens.
Tokens are groups of characters with collective significance.
In other words, it is one of the steps used to convert the text of the
documents into the 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.
10/03/2025
1. Lexical Analysis/Tokenization of Text(cont…)
27
Generally, Lexical analysis is the first stage of automatic indexing,
and of query processing.
Automatic indexing is the process of algorithmically examining
information items to generate lists of index terms.
The lexical analysis phase produces candidate index terms that
may be further processed and eventually added to indexes.
Query processing is the activity of analyzing a query and
comparing it to indexes to find relevant items.
Lexical analysis of a query produces tokens that are parsed and
turned into an internal representation suitable for comparison with
indexes.
10/03/2025
Issues in Tokenization
28
The main Objective of Tokenization is – the identification of words
in the text document.
Tokenization is greatly dependent on how the concept of the word
is defined.
The first decision that must be made in designing a lexical analyzer
for an automatic indexing system is: What counts as a word or token
in the indexing scheme?
Is that a sequence of characters, numbers, and alpha-numeric once?
A word is a sequence of letters terminated by a separator (period,
comma, space, etc).
The definition of letter and separator is flexible; e.g., a hyphen
could be defined as a letter or as a separator. Usually, common words
(such as “a”, “the”, “of”, …) are ignored.
10/03/2025
29
The standard tokenization approach is single-word
tokenization where input is split into words using white
space characters as delimiters and it ignores other
characters rather than words.
This approach introduces errors at an early stage
because it ignores multi-word units, numbers, hyphens,
punctuation marks, and apostrophes.
10/03/2025
Lexical Analysis of the Text
30
Numbers/Digits
Most numbers are usually not good index terms –
Without a surrounding context, they are inherently
vague
The preliminary approach is to remove all words
containing sequences of digits unless specified
otherwise
The advanced approach is to perform date and
number normalization to unify format
anti-virus, anti-war,…
Hyphens
Breaking up hyphenated words seems to be useful
But, some words include hyphens as an integrated
part 10/03/2025
Adopt a general rule to process hyphens and specify
Lexical Analysis of the Text
31
Punctuation marks
Removed entirely in the process of lexical analysis
But, some are an integrated part of the word
• 510B.C.
The case of letters
Not important for the identification of index terms
Converted all the text to either to either lower or
upper cases
But, parts of semantics will be lost due to case
conversion
10/03/2025
2. Normalization
32
• 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
Fasil vs. fasil vs. FASIL
Anti-discriminatory vs. antidiscriminatory
Car vs. Automobile?
10/03/2025
Normalization issues
33
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 while they are
interested in a Ferrari car
Not advisable for:
Proper names vs. common nouns
E.g. General Motors, Associated Press, Kebede…
Solution:
lowercase only words at the beginning of the sentence
In IR, lowercasing is most practical because of the way users issue
their queries
10/03/2025
3. Elimination of Stop words
34
Stop words
Word which are too frequent among the docs
in the collection are not good discriminators
A word occurring in 80% of the docs in the
collection is useless for purposes of retrieval
E.g, articles, prepositions, conjunctions, …
Filtering out stop words achieves a
compression of 40% size of the indexing
structure
The extreme approach: some verbs, adverbs,
and adjectives could be treated as stop words
The stop word list – Usually contains hundreds10/03/2025
of
4. Stemming/Morphological analysis
35
Stemming reduces tokens to their root form of words to recognize
morphological variation.
The process involves removal of affixes (i.e. prefixes & suffixes)
with the aim of reducing variants to the same stem
Often removes inflectional & 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.
10/03/2025
Stemming/Morphological analysis(cont…)
36
Compressed and compression are both accepted.
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 stem is used as index terms/keywords for document
representations
Queries : Queries are handled in the same way.
10/03/2025