Introduction to Information Storage and

Retrieval

Chapter 2: Text/Document Operations and

Automatic Indexing

AUWC School of Informatics and Technology Department of IS

 Introduction to Information Storage and Retrieval 10/16/2025

Assignment (5%)-Individual

 Explain in detail the contribution of Zipf's Law and Luhn’s Law for
information retrieval text operation?

AUWC School of Informatics and Technology Department of IS

Introduction to Information Storage and Retrieval 10/16/2025

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.
 Most words are very rare.
 Half the words in a corpus appear only once, called "read only once"
AUWC School of Informatics and Technology Department of IS
Introduction to Information Storage and Retrieval 10/16/2025

Text Operations
• 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, there is a need to preprocess the text of a document in a
collection to choose those 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
AUWC School of Informatics and Technology Department of IS
Introduction to Information Storage and Retrieval 10/16/2025

Text Operations
• Preprocessing is the process of controlling the size of the vocabulary or
the number of distinct words used as index terms
• It will lead to an improvement in the information retrieval performance
• However, some search engines on theWeb omit preprocessing
• i.e Every word in the document will be used an index term

AUWC School of Informatics and Technology Department of IS

 Introduction to Information Storage and Retrieval 10/16/2025

Text Operations
• Text operations is the process of text transformations in to logical
representations
• The main operations for selecting index terms, i.e. to choose
words/stems (or groups of words) to be used as indexing terms are:
– Lexical analysis/Tokenization of the text - digits, hyphens, punctuations marks,
and the case of letters
– Elimination of stop words - filter out words which are not useful in the retrieval
process
– Stemming words - remove affixes (prefixes and suffixes)
– Construction of term categorization structures such as thesaurus, to capture
relationship for allowing the expansion of the original query with related terms

AUWC School of Informatics and Technology Department of IS

Introduction to Information Storage and Retrieval 10/16/2025

Generating Document Representatives

• 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.
Documents Tokenization stop words stemming Thesaurus

Index
terms

AUWC School of Informatics and Technology Department of IS

Introduction to Information Storage and Retrieval 10/16/2025

Generating Document Representatives

• For instance, if a document contains significant words related to sports, it will
be indexed under the sports category.
• Similarly, if a document contains words related to politics, it will be indexed
under the politics category.
• For example, suppose you have a document that talks about various types of
flowers and their properties -if the document contains the word "rose," which
is a significant word related to the "flowers" category, the document will be
indexed under the "flowers" category.
• Similarly, if a document contains the word "election" or "voting," it will be
indexed under the "politics" category

AUWC School of Informatics and Technology Department of IS

Introduction to Information Storage and Retrieval 10/16/2025

Lexical Analysis/Tokenization of Text

 Change text of the documents into words to be adopted as index terms
 Objective - identify words in the text
 Digits, hyphens, punctuation marks, case of letters
 Numbers are not good index terms (like 1910, 1999); but 510 B.C. – unique
 Hyphen – break up the words (e.g. state-of-the-art = state of the art)- but
some words, e.g. gilt-edged, B-49 - unique words which require hyphens
 Punctuation marks – remove totally unless significant, e.g. program code:
[Link] and xexe
 Case of letters – not important and usually converted to all upper or lower
AUWC School of Informatics and Technology Department of IS
 Introduction to Information Storage and Retrieval 10/16/2025

Tokenization
• Analyze text into a sequence of discrete tokens (words).
• Input: “The world, can be a better place”
• Output: Tokens (an instance of a sequence of characters that are grouped together as a useful semantic unit
for processing)
• The
• World
• can
• Be
• A
• Better
• place
• Each such token is now a candidate for an index entry, after further processing
• AUWC
But School
whatofare valid tokens to use?
Informatics and Technology Department of IS
Introduction to Information Storage and Retrieval 10/16/2025

Issues in Tokenization
• One word or multiple: How do you decide it is one token or two or more?
 Addis Ababa  Addis and Ababa as two tokens?
 State-of-the-art: break up hyphenated sequence.
 San Francisco, Los Angeles
 lowercase, lower-case, lower case ?
 data base, database, data-base
• Numbers:
• dates (3/12/91 vs. Mar. 12, 1991);
• phone numbers,
• IP addresses ([Link])

AUWC School of Informatics and Technology Department of IS

 Introduction to Information Storage and Retrieval 10/16/2025

Issues in Tokenization
• How to handle special cases involving apostrophes, hyphens etc? C++, C#, URLs, emails, …
– Sometimes punctuation (e-mail), numbers (1999), and case can be a meaningful part of a token.
– However, frequently they are not.
• Simplest approach is to ignore all numbers and punctuation and use only case-insensitive
unbroken strings of alphabetic characters as tokens.
– Generally, systems do not index numbers as text, but often very useful for search.
– “meta-data” is often indexed, including creation date, format, etc. separately
• Issues of tokenization are language specific
– Requires the language to be known
– What works for one language doesn’t work for the other.
AUWC School of Informatics and Technology Department of IS
 Introduction to Information Storage and Retrieval 10/16/2025

Exercise in Tokenization
• Example Python code for tokenization:

AUWC School of Informatics and Technology Department of IS

Introduction to Information Storage and Retrieval 10/16/2025

Elimination of Stop words

• Stopwords are extremely common words across document collections that have no
discriminatory power
– They may occur in 80% of the documents in a collection.
– 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 stopwords are articles, prepositions, conjunctions, etc.:
– articles (a, an, the); pronouns: (I, he, she, it, their, his, her)
– 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 stopwords
• Stopwords are language dependent.
AUWC School of Informatics and Technology Department of IS
 Introduction to Information Storage and Retrieval 10/16/2025

Stop words
• Intuition:
– Stopwords have little semantic content; It is typical to remove such high-frequency
words
– Stopwords take up 50% of the text. Hence, document size reduces by 30-50%

• 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.

AUWC School of Informatics and Technology Department of IS

 Introduction to Information Storage and Retrieval 10/16/2025

How to determine a list of stop words?

• One method: Sort terms (in decreasing or increasing order) by
collection 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 the most common words from index terms.
• With the removal of stopwords, we can measure better approximation of
importance for classification, summarization, etc.
AUWC School of Informatics and Technology Department of IS
 Introduction to Information Storage and Retrieval 10/16/2025

Stop words
• Stop word elimination used to be standard in older IR systems.
• But the trend is getting 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 stopwords 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 stopwords might reduce recall (e.g. “To be or not to be” – all eliminated except
“be” – will produce no or irrelevant retrieval)

AUWC School of Informatics and Technology Department of IS

 Introduction to Information Storage and Retrieval 10/16/2025

Normalization
• It is Canonicalizing tokens (change to simplest form) 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
– A.A. AA Addis Ababa

AUWC School of Informatics and Technology Department of IS

Introduction to Information Storage and Retrieval 10/16/2025

Normalization Issues
• Case folding is good for
– Allowing instances of Automobile at the beginning of a sentence to match with
a query of automobile
– Helping 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, …
• In IR, lowercasing is most practical because of the way users issue
their queries
AUWC School of Informatics and Technology Department of IS
Introduction to Information Storage and Retrieval 10/16/2025

Stemming/Morphological analysis
• Stemming reduces tokens to their “root” form 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 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 and also, destruction → destroy

AUWC School of Informatics and Technology Department of IS

Introduction to Information Storage and Retrieval 10/16/2025

Stemming/Morphological analysis
• Stemming is language dependent
– Correct stemming is language specific and can be complex.

for example compressed and compress and

compression are both accepted. compress are both accept

AUWC School of Informatics and Technology Department of IS

 Introduction to Information Storage and Retrieval 10/16/2025

Stemming/Morphological analysis
 Removing inflectional and derivational morphology of a word" means reducing a word to its
simplest form by stripping away any suffixes, prefixes, or other affixes that modify the base form
of the word to create new forms or to change its grammatical function.
 Inflectional morphology example: The verb "run" can be inflected to reflect different tenses,
such as "ran" for past tense or "running" for present participle.
 Derivational morphology example: The verb "run" can be derived into the noun "runner" by
adding the suffix "-er", which indicates a person who performs the action of the verb.
 To remove inflectional and derivational morphology from the above examples:
 Inflectional morphology example: "Run" can be reduced to its base form "run" by
removing the inflectional suffixes "-an" and "-ing“
 Derivational morphology example: "Runner" can be reduced to its base form "run" by
removing the derivational suffix "-er".
 Removing inflectional and derivational morphology is a common step in processing tasks in
information retrieval systems.
AUWC School of Informatics and Technology Department of IS
Introduction to Information Storage and Retrieval 10/16/2025

Stemming
• The final output from a conflation(reducing to the same token) 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.
AUWC School of Informatics and Technology Department of IS
 Introduction to Information Storage and Retrieval 10/16/2025

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 (in so far 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.
 The third approach is to combines the two method.
AUWC School of Informatics and Technology Department of IS
Introduction to Information Storage and Retrieval 10/16/2025

Ways to implement Stemming

AUWC School of Informatics and Technology Department of IS

 Introduction to Information Storage and Retrieval 10/16/2025

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
[Link]

AUWC School of Informatics and Technology Department of IS

Introduction to Information Storage and Retrieval 10/16/2025

Porter Stemmer
• It is the 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
AUWC School of Informatics and Technology Department of IS
Introduction to Information Storage and Retrieval 10/16/2025

Porter Stemmer

• While the first column gets rid of plurals, second column removes
-ed or -ing.
• e.g.
;; agreed -> agree ;; disabled -> disable
;; matting -> mat ;; mating -> mate
;; meeting -> meet ;; milling -> mill
;; messing -> mess ;; meetings -> meet
;; feed -> feed
AUWC School of Informatics and Technology Department of IS
Introduction to Information Storage and Retrieval 10/16/2025

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.

AUWC School of Informatics and Technology Department of IS
 Introduction to Information Storage and Retrieval 10/16/2025

Thesauri/Thesaurus
• 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
(two words having similar meaning), homonyms (words pronounced or spelled the same way but
have different meanings), and related terms
– Example:
– Synonyms: Happy, Joyful, cheerful- These words have similar meanings
– Homonyms: These words are spelled and pronounced the same but have
different meanings.
– Two, too
– sea, see
– Right (correct) and Write (to form letters)
AUWC School of Informatics and Technology Department of IS
Introduction to Information Storage and Retrieval 10/16/2025

Thesauri/Thesaurus
– 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 (UF=used for), (BT=broader
term, and (RT=related term) to demonstrate inter-term relationships.
– e.g., car = automobile, truck, bus, taxi, motor vehicle
-color = colour, paint

AUWC School of Informatics and Technology Department of IS

Introduction to Information Storage and Retrieval 10/16/2025

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 standard vocabulary for indexing and searching
• Thesaurus rewrite words to form equivalence classes, and we index such equivalences
• 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

AUWC School of Informatics and Technology Department of IS

Introduction to Information Storage and Retrieval 10/16/2025

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
Where UF=used for, BT=broader term, and RT= related term

AUWC School of Informatics and Technology Department of IS

Introduction to Information Storage and Retrieval 10/16/2025

Thesaurus Construction in IR
 Example Use Case:
Suppose we have a collection of documents related to gardening, and we want to
construct a thesaurus to help users find information more easily. We can start by
manually identifying a set of keywords related to gardening, such as "plant", "flower",
"soil", "water", "fertilizer", "garden", "greenhouse", etc. For each keyword, we can then
identify its synonyms, antonyms, and related terms as shown in the table above.
Keyword Synonyms Antonyms Related Terms
seedling, sapling, shrub,
plant weed transplant, prune, graft, propagate
tree
blossom, bloom, petal,
flower weed arrangement, perfume, color, pollination
bud
soil earth, dirt, ground, loam rock fertility, texture, acidity, composition
AUWC School of Informatics and Technology Department of IS
water moisture, rain, irrigation drought drainage, absorption, evaporation, condensation
Introduction to Information Storage and Retrieval 10/16/2025

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

AUWC School of Informatics and Technology Department of IS

Introduction to Information Storage and Retrieval 10/16/2025

Language-specificity
• Many of the above features embody transformations that are
• Language-specific and
• Often, application-specific
• These are “plug-in” agenda to the indexing process
• Both open source and commercial plug-ins are available for handling
these issues

AUWC School of Informatics and Technology Department of IS

Introduction to Information Storage and Retrieval 10/16/2025

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 the 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

AUWC School of Informatics and Technology Department of IS

Introduction to Information Storage and Retrieval 10/16/2025

AUWC School of Informatics and Technology Department of IS

Introduction to Information Storage and Retrieval 10/16/2025

AUWC School of Informatics and Technology Department of IS