UNIT-II

Cataloging and Indexing: Objectives, Indexing Process, Automatic Indexing, formation Extraction.
Data Structures: Introduction, Stemming Algorithms, Inverted file structures, N-gram data structure,
PAT data structure, Signature file structure, Hypertext data structure.

CATALOGING AND INDEXING

INDEXING:
The transformation from received item to searchable data structure is called indexing.

• Process can be manual or automatic.

• Creating a direct search in document data base or indirect search through index files.

• Concept based representation: instead of transforming the input into a searchable

format some systems transform the input into different representation that is concept
based .Search ? Search and return item as per the incoming items.

• History of indexing: shows the dependency of information processing capabilities on

manual and then automatic processing systems .

• Indexing originally called cataloguing : oldest technique to identity the contents of

items to assist in retrieval.

• Items overlap between full item indexing , public and private indexing of files

Objectives :

The public file indexer needs to consider the information needs of all users of library
system . Items overlap between full item indexing , public and private indexing of files.

•Users may use public index files as part of search criteria to increase recall.

•They can constrain there search by private index files

•The primary objective of representing the concepts within an item to facilitate users
finding relevant information .

•Users may use public index files as part of search criteria to increase recall.

•They can constrain there search by private index files

•The primary objective of representing the concepts within an item to facilitate users
finding relevant information

IRS notes Page 25

 Fig : Indexing process

1. Decide the scope of indexing and the level of detail to be provided. Based on usage
scenario of users.

2. Second decision is to link index terms together in a single index for a particular
concept.

TEXT PROCESSING

26
1. Document Parsing. Documents come in all sorts of languages,
character sets, and formats; often, the same document may contain
multiple languages or formats, e.g., a French email with Portuguese
PDF attachments. Document parsing deals with the recognition and
“breaking down” of the document structure into individual
components. In this pre processing phase, unit documents are
created; e.g., emails with attachments are split into one document
representing the email and as many documents as there are
attachments.
2. Lexical Analysis. After parsing, lexical analysis tokenizes a document,
seen as an input stream, into words. Issues related to lexical analysis
include the correct identification of accents, abbreviations, dates, and
cases. The difficulty of this operation depends much on the language
at hand: for example, the English language has neither diacritics nor
cases, French has diacritics but no cases, German has both diacritics
and cases. The recognition of abbreviations and, in particular, of time
expressions would deserve a separate chapter due to its complexity
and the extensive literature in the field For current approaches
3. Stop-Word Removal. A subsequent step optionally applied to the
results of lexical analysis is stop-word removal, i.e., the removal of
high-frequency words. For example, given the sentence “search
engines are the most visible information retrieval applications” and a
classic stop words set such as the one adopted by the Snowball
stemmer,1 the effect of stop-word removal would be: “search engine
most visible information retrieval applications”.
4. Phrase Detection. This step captures text meaning beyond what is
possible with pure bag- of-word approaches, thanks to the
identification of noun groups and other phrases. Phrase detection may
be approached in several ways, including rules (e.g., retaining terms
that are not separated by punctuation marks), morphological analysis
, syntactic analysis, and combinations thereof. For example, scanning
our example sentence “search engines are the most visible
information retrieval applications” for noun phrases would probably
result in identifying “search engines” and “information retrieval”.
5. Stemming and Lemmatization. Following phrase extraction, stemming
and lemmatization aim at stripping down word suffixes in order to
normalize the word. In particular, stemming is a heuristic process that
“chops off” the ends of words in the hope of achieving the goal
correctly most of the time; a classic rule based algorithm for this was
devised by Porter [280]. According to the Porter stemmer, our
example sentence “Search engines are the most visible information

27
 retrieval applications” would result in: “Search engin are the most
visibl inform retriev applic”.
1. Lemmatization is a process that typically uses dictionaries and
morphological analysis of words in order to return the base or
dictionary form of a word, thereby collapsing its inflectional forms
(see, e.g., [278]). For example, our sentence would result in “Search
engine are the most visible information retrieval application” when
lemmatized according to a WordNet-based lemmatizer
2. Weighting. The final phase of text pre processing deals with term
weighting. As previously mentioned, words in a text have different
descriptive power; hence, index terms can be weighted differently to
account for their significance within a document and/or a document
collection. Such a weighting can be binary, e.g., assigning 0 for term
absence and 1 for presence.
SCOPE OF NDEXING
• When perform the indexing manually, problems arise from two
sources the author and the indexer the author and the indexer .

• Vocabulary domain may be different the author and the indexer.

• This results in different quality levels of indexing.

• The indexer must determine when to stop the indexing process.

• Two factors to decide on level to index the concept in a item.

• The exhaustively and how specific indexing is desired.

• Exhaustively of index is the extent to which the different concepts in the item
are indexed.

• For example, if two sentences of a 10- item on

microprocessors discusses on-board caches, should this concept
be indexed

• Specific relates to preciseness of index terms used in indexing.

• For example, whether the term “processor” or the term

“microcomputer” or the term “Pentium” should be used in the
index of an item is based upon the specificity decision.

28
 • Indexing an item only on the most important concept in it and
using general index terms yields low exhaustively and specificity.

• Another decision on indexing is what portion of an item to be

indexed Simplest case is to limit the indexing to title and

abstract(conceptual ) zone .

• General indexing leads to loss of precision and recall.

PREORDINATION AND LINKAGES

• Another decision on linkages process whether linkages are
available between index terms for an item .

• Used to correlate attributes associated with concepts discussed in

an item .’this process is called preordination .

• When index terms are not coordinated at index time the

coordination occurs at search time. This is called post
coordination , implementing by “AND” ing index terms .

• Factors that must be determined in linkage process are the

number of terms that can be related.

• Ex., an item discusses ‘the drilling of oil wells in Mexico by CITGO

and the introduction of oil refineries in Peru by the U.S.’

DATA STRUCTURES
• Introduction to Data Structures
• Stemming Algorithms
• Inverted File Structure
• N-Gram Data Structure
• PAT Data Structure
• Signature File Structure
• Hypertext and XML Data Structures
MRCET-IT 29
Data structure :
The knowledge of data structure gives an insight into the capabilities
available to the system .
• Each data structure has a set of associated capabilities .
• Ability to represent the concept and their r/s.
• Supports location of those concepts Introduction
Two major data structures in any IRS:
1. One structure stores and manages received items in their
normalized form is called document manger

2. The other data structure contains processing tokens and

associated data to support search.

Item
normalization

Document
File creation

Document
Document
manager
Search manager

Original Major data Processing

document file
structure token

Result of a search are references to the items that satisfy the search
statement which are passed to the document manager for retrieval.
Focus : on data structure that support search function
Stemming : is the transformation often applied to data before placing it in
the searchable data structure
Stemming represents concept(word) to a canonical (authorized; recognized;
accepted)morphological (the patterns of word formation in a particular
30
language ) representation .Risk with stemming : concept discrimination
information may be lost in the
process. Causing decrease in performance.
Advantage : has a potential to increase recall.

STEMMING ALGORITHMS
• Stemming algorithm is used to improve the efficiency of IRS and improve
recall.
• Conflation(the process or result of fusing items into one entity;
fusion; amalgamation)is a term that is used to refer mapping
multiple morphological variants to single representation(stem).
• Stem carries the meaning of the concept associated with the word and the
affixes(ending) introduce subtle(slight) modification of the concept.
• Terms with a common stem will usually have similar meanings,
for example:
• Ex : Terms with a common stem will usually have similar
meanings, for example:
• CONNECT
• CONNECTED
• CONNECTING
• CONNECTION
• CONNECTIONS
• Frequently, the performance of an IR system will be improved if
term groups such as this are conflated into a single term. This may
be done by removal of the various suffixes -ED, -ING, -ION, IONS to
leave the single term CONNECT
• In addition, the suffix stripping process will reduce the total
number of terms in the IR system, and hence reduce the size and
complexity of the data in the system, which is always
advantageous.
 Major usage of stemming is to improve recall.

 Important for a system to categories a word prior to making the decision to

stem.
 Proper names and acronyms (A word formed from the initial letters of a name
say IARE …) should not have stemming applied.
 Stemming can also cause problems for natural language processing NPL
systems by causing loss of information .

31
PORTER STEMMING ALGORITHM

• Based on a set condition of the stem

• A consonant in a word is a letter other than A, E, I, O or U, some
important stem conditions are

1. The measure m of a stem is a function of sequence of vowels (V)

followed by a sequence of consonant ( C ) .
2. C (VC)mV. m is number VC repeats The case m = 0 covers the null
word.
3. *<X> - stem ends with a letter X 3.*v* - stem contains a
vowel
4. *d- stem ends in double consonant (e.g. -TT, -SS).

5. *o- stem ends in consonant vowel sequence where the

final consonant is not w,x,y(e.g. -WIL, -HOP).
Suffix cond.s takes the form current _suffix = = pattern Actions are
in the form old_suffix ->. New_suffix
Rules are divided into steps to define the order for applying the
rule.
Examples of the rules
Step Condition Suffix Replace Example
ment
1a Null Sses Ss Stresses -> stress
1b *v* Ing Null Making -> mak
1b1 Null At Ate Inflated-> inflate
1c *v* Y I Happy->happi

2 m>0 aliti al Formaliti->

formal
3 m>0 Icate Ic Duplicate->duplie

4 m>1 Able Null Adjustable ->

adjust
5a m>1 e Null Inflate-> inflat

5b m>1 and *d Null Single Control -> control

letter

32
2. Dictionary look up stemmers

 Use of dictionary look up.

 The original term or stemmed version of the term is looked up
in a dictionary and replaced by the stem that best represents it.
 This technique has been implemented in INQUERY and Retrieval ware
systems-

INQUERY system uses the technique called Kstem.

 Kstem is a morphological analyzer that conflates words variants to a root form.

 It requires a word to be in the dictionary

 Kstem uses 6 major data files to control and limit the stemming process.
1. Dictionary of words (lexicon)
2. Supplemental list of words for dictionary
3. Exceptional list of words that should retain a ‘e’ at the end (e.g., “suites” to
“suite” but “suited” to “suit”).

4. Direct _conflation - word pairs that override stemming algorithm.

5. County_nationality _conflation ( British maps to Britain )

6. Proper nouns -- that should not be stemmed

 New words that are not special forms (e.g., dates, phone
numbers) are located in the dictionary to determine simpler
forms by stripping off suffixes and respelling plurals as defined in
the dictionary.
3. Successor stemmers:
 Based on length of prefixes .

 The smallest unit of speech that distinguishes on word from another

 The process uses successor varieties for a word .

Uses information to divide a word into segments and selects on of the segments to stem.

33
Successor variety of words are used to segment a word by applying one of
the following four methods.
1. Cutoff method : a cut of value is selected to define the stem length.
2. Peak and plateau: a segment break is made after a character
whose successor variety exceeds that of the character.
3. Complete word method: break on boundaries of complete words.

4. Entropy method:uses the distribution method of successor variety letters.

1. Let |Dak| be the number of words beginning with k length sequence of letters a.

2. Let |Dakj| be the number of words in Dak with successor j.

3. The probability that a member of Dak has the successor j

is given as |Dakj| / |Dak| The entropy of |Dak| is

26
Hak = -(|Dakj| / |Dak|
)(log(|Dakj| /
|Dak| )) p=1

After a word has been segmented the segment to be used as stem

must be selected. Hafer and Weiss selected the following rule

If ( first segment occurs in <=12 words in database) First segment

is stem

Else (second segment is stem)

INVERTED FILE STRUCTURE
Inverted file structure

Most common data structure

Inverted file structures are composed of three files
The document file
1. The inversion list (Posting List)

2. Dictionary

3. The inverted file : based on the methodology of storing an inversion of

documents.

34
 4. For each word a listof documents in which the word is found is
stored(inversion of document
5. Each document is given a unique the numerical identifier that is stored in
inversion list . Dictionary is used to located the inversion list for a particular
word.
Which is a sorted list( processing tokens) in the system and a pointer to the
location of its inversion list.
Dictionary can also store other information used in query optimization
such as length of inversion lists to increase the precision.

 Use zoning to improve

 precision and Restrict entries.

 Inversion list consists of document identifier for each document

in which the word is found.
Ex: bit 1(10),1(12) 1(18) is in 10,12, 18 position of the word bit in the document #1.
 When a search is performed, the inversion lists for the terms in the query are
locate and appropriate logic is applied between inversion lists.
 Weights can also be stored in the inversion list.
 Inversion list are used to store concept and their relationship.
 Words with special characteristics can be stored in their own dictionary. Ex:
Date… which require date ranging and numbers.
 Systems that support ranking are re-organized in ranked order.
 B trees can also be used for inversion instead of dictionary.
 The inversion lists may be at the leaf level or referenced in higher level
pointers.
 A B-tree of order m is defined as:
 A root node with between 2 and 2m keys
 All other internal nodes have between m and 2m keys
 All keys are kept in order from smaller to larger.
 All leaves are at the same level or differ by at most one level.

35
N-GRAM DATA STRUCTURE
 N-Grams can be viewed as a special technique for conflation (stemming) and as
a unique data structure in information systems.
 N-Grams are a fixed length consecutive series of “n” characters.
 Unlike stemming that generally tries to determine the stem of a word that
represents the semantic meaning of the word, n-grams do not care about
semantics.
 The searchable data structure is transformed into overlapping n-grams, which
are then used to create the searchable database.
 Examples of bigrams, trigrams and pentagrams for the word phrase “sea
colony.” se ea co ol lo on ny Bigrams (no interword symbols)
sea col olo lon onyTrigrams (no interword symbols) #se sea ea# #co col olo lon ony ny# Trigrams
(with interword symbol #)

#sea# #colo colon olony lony#

Pentagrams (with interword
symbol #)
The symbol # is used to represent the interword symbol which is
anyone of a set of symbols (e.g., blank, period, semicolon, colon,
etc.).
 The symbol # is used to represent the interword symbol which is
anyone of a set of symbols (e.g., blank, period, semicolon, colon,
etc.).
 Each of the n-grams created becomes a separate processing tokens and are
searchable.
 It is possible that the same n-gram can be created multiple times from a single
word.
Uses :
 Widely used as cryptography in world war II Spelling errors detection and
correction
36
  Use bigrams for conflating terms.

 N-grams as a potential erroneous words.

 Damerau specified 4 categories of errors:

Error Category Example

single char insertion compuuter
single char deletion compter
single char substitution compiter
Transposition of 2 adjacent comptuer chars

 Zamora showed trigram analysis provided a viable data structure

for identifying misspellings and transposed characters.
 This impacts information systems as a possible basis for
identifying potential input errors for correction as a procedure
within the normalization process.
 Frequency of occurrence of n-gram patterns can also be used for
identifying the language of an item.
 Trigrams have been used for text compression and to manipulate the length of
index terms.
 To encode profiles for the Selective Dissemination of Information.

 To store the searchable document file for retrospective search databases.

Advantage:

They place a finite limit on the number of searchable token

MaxSeg n=( )n maximum number of unique n
grams that can be generated. “ n” is the length of
n-grams
number of process able symbols
Disadvantage: longer the n gram the size of inversion
list increase. Performance has 85 % precision .

37
PAT data structure (practical algorithm to retrieve information coded in alphanumeric)

 PAT structure or PAT tree or PAT array : continuous text input

data structures(string like N- Gram data structure).

 The input stream is transformed into a searchable data structure
consisting of substrings, all substrings are unique.
 Each position in a input string is a anchor point for a sub string.
 In creation of PAT trees each position in the input string is the
anchor point for a sub-string that starts at that point and includes
all new text up to the end of the input.
 Binary tree, most common class for prefix search,But Pat trees are
sorted logically which facilitate range search, and more accurate
then inversion file .
 PAT trees provide alternate structure if supporting strings search.

Text Economics for Warsaw is complex.

-----------------------------------------------------------
sistring 1 Economics for Warsaw is
complex. sistring 2 conomics for
Warsaw is complex. sistring 5 omics for
Warsaw is complex. sistring 10 for
Warsaw is complex.
sistring 20 w is
complex. sistring 30
ex.
Examples of sistrings

• The key values are stored at the leaf nodes (bottom nodes) in the PAT Tree.
• For a text input of size “n” there are “n” leaf nodes and “n-1” at most higher
level nodes.
• It is possible to place additional constraints on sistrings for the leaf nodes.
• If the binary representations of “h” is (100), “o” is (110), “m” is
(001) and “e” is (101) then the word “home” produces the input

38
 100110001101. .................................................................. Using the
sistrings.

INPUT 100110001101
sistring 1 1001....
sistring 2 001100...
sistring 3 01100....
sistring 4 11.......
sistring 5 1000...
sistring 6 000.....
sistring 7 001101
sistring 8 01101

The full PAT binary tree is

The value in the intermediate nodes (indicated by rectangles) is the

number of bits to skip until the next bit to compare that causes differences
between similar terms.

39
 Skipped final version of PAT tree
Signature file structure

 The coding is based upon words in the code.

 The words are mapped into word signatures .

 A word signature is fixed length code with a fixed number of bits set to 1.

 The bit positions that are set to one are determined via a hash function of the
word.
 The word signatures are Ored together to create signature of an item..

 Partitioning of words is done in block size ,Which is nothing but

set of words, Code length is 16 bits .
 Search is accomplished by template matching on the bit position .

 provide a practical solution applied in parallel processing , distributed

environment etc.

• To avoid signatures being too dense with “1”s, a maximum

number of words is specified and an item is partitioned into
blocks of that size.
• The block size is set at five words, the code length is 16 bits and
the number of bits that are allowed to be “1” for each word is five.
• TEXT: Computer Science graduate students study (assume block size is five
words)

40
 WORD Signature
-----------------------------------------------------------------
computer 0001 0110 0000 0110
Science 1001 0000 1110 0000
graduate 1000 0101 0100 0010
students 0000 0111 1000 0100
study 0000 0110 0110 0100
----------------------------------------------------------------
Block Signature 1001 0111 1110 0110
----------------------------------------------------------------
Superimposed Coding
Application(s)/Advantage(s)

• Signature files provide a practical solution for storing and locating

information in a number of different situations.
• Signature files have been applied as medium size databases,
databases with low frequency of terms, WORM devices, parallel
processing machines, and distributed environments
HYPERTEXT AND XML DATA STRUCTURES
 The advent of the Internet and its exponential growth and wide acceptance as a
new global information network has introduced new mechanisms for
representing information.
 This structure is called hypertext and differs from traditional information
storage data structures in format and use.
 The hypertext is Hypertext is stored in HTML format and XML .
 Bot of these languages provide detailed descriptions for subsets of text similar to the zoning.
 Hypertext allows one item to reference another item via a embedded pointer .
 HTML defines internal structure for information exchange over WWW on the internet.
 XML: defined by DTD, DOM, XSL, etc.
Document and term clustering
Two types of clustering:
1) clustering index terms to create a statistical thesaurus and
2) clustering items to create document clusters. In the first case clustering is used to increase recall
by expanding searches with related terms. In document clustering the search can retrieve items
similar to an item of interest, even if the query would not have retrieved the item. The clustering
process is not precise and care must be taken on use of clustering techniques to minimize the
negative impact misuse can have.

Page 41