Chapter 3

Text Analysis andAutomatic Indexing

0

PREVIEWIn the first two chapters of this book the design and operations of existing infor­
mation retrieval systems have been presented. Of all the operations required in
information retrieval, the most crucial and probably the most difficult one con­sists in assigning appropriate terms and identifiers capable of representing thecontent of the collection items. This task, known as indexing, is normally per­formed manually by trained experts. In modern environments the indexing task
can be performed automatically. This chapter is concerned with the techniques
used for automatic indexing, and with the effect and performance of these tech­niques.
The basic indexing task is first described, followed by a comparison ofmanual and automatic indexing. Basic techniques are then examined for choos­
ing good content terms and for assigning weights to the terms according to theirpresumed value for content identification. A simple automatic indexing proce­dure is then suggested, as well as refinements consisting of the use of termphrases and thesaurus classes. The use of linguistic and probabilistic tech­niques in automatic indexing is also briefly introduced. Finally, evaluation out­
put is included to demonstrate the effectiveness of the proposed indexing tech­niques applied to small sample collections.
52

TEXT ANALYSIS AND AUTOMATIC INDEXING

53

This chapter includes some technical material. The reader is urged to fol­
low the difficulty indications in mastering the theories underlying the automatic
indexing process.

1

INDEXING ENVIRONMENTOf all the procedures normally used in a document processing environment, themost important and also the most difficult to carry out are the analysis opera­
tions consisting of the assignment to the bibliographic items of terms or identi­
fiers capable of representing document content. In principle, a document anal­
ysis process is redundant if the document collection is small enough to permit
the scanning of the full text of all items whenever a request for information isreceived. In practice, such a solution is too time-consuming and too expensive.
Hence it is customary to characterize each item by assigning a short descrip­
tion, or profile, to the item which can be used to obtain access whenever theitem is wanted. In standard library environments, the analysis operations are
known variously as cataloging, classification, indexing, and abstracting.
The document profile fulfills the dual role of representing a given document
by providing a short-form description,1and also of describing the document
content; the profile is therefore often divided into two parts consisting first of
objective information relating to the data external to the document text itself,such as author name, publisher, and date and place of publication; and secondof identifiers specifically describing the information contained in the document.
In conventional libraries the choice of objective document identifiers is known
as author/title or descriptive cataloging, whereas the assignment of the content
information is termed subject cataloging. As explained in Chapter 1, the con­tent description of an item consists of a call number chosen from a hierarchi­
cally organized systematic list, and of additional subject headings that may be
represented by relatively free language words and phrases. Each subject head­ing assigned to a given item may be entered onto a separate catalog card, andthe resulting collection constitutes the library catalog. In a modern document
processing environment the conventional library catalog does not exist as aphysical entity. Rather the profiles are collected into a data base. In this case,the content analysis operations are then collectively known as indexing. Whenthe assignment of the content identifiers is carried out with the aid of modern
computing equipment, the operation becomes automatic indexing.
It would be nice to think that the choice of the objective document identi­
fiers presents no difficulties. In fact, elaborate cataloging standards have had to
be defined specifying what author names are acceptable and how the au­thor/title information is to be entered into the catalog. The study of existing au­
thor cataloging rules presents many challenges which deserve to be criticallyexamined [1,2]. In the present context, however, the most interesting problems
arise in connection with the generation and standardization of the content, as
opposed to the objective, identifiers. Therefore, this present chapter is con-

54

CHAPTER 3

cerned with the analysis of document content and in particular with automatic
indexing procedures.
The assignment of content identifiers to the information items is designed
to fulfill three related purposes [1]:
1 To allow the location of items dealing with topics of interest to the user
2 To relate items to each other, and thus relate the topic areas, by identi­
fying distinct items dealing with similar, or related, topic areas
3 To predict the relevance of individual information items to specific in­formation requirements through the use of index terms with well-defined scopeand meaning
The methods used to accomplish these aims depend on the particular indexing
environment in which the operations take place.
The first distinction to be made is that between manual and automatic in­dexing. Historically, the analysis operations have been carried out manually—
maybe one should say intellectually— by “ subject experts.” To this day, man­ual indexing is the rule rather than the exception in most operational environ­ments. A variety of aids are made available to the indexer to control the index­
ing process including terminology lists, instruction manuals, and speciallystructured worksheets to record the indexing products. “ Scope notes” mayalso be used to define the meaning and interpretation of each of the allowableindex terms. Obviously, lists of definitions and scope notes in natural language
text form are not easily incorporated into an automatic indexing system.
The second distinction to be made is that between controlled and uncon­
trolled indexing term s. Many experts feel that an uncontrolled indexing vocab­
ulary which in principle can include the whole variety of the natural language
introduces too many opportunities for ambiguity and error. Hence, a limited
indexing language is often advocated in which the terms available for content
identification are rigidly controlled. This permits the control of spelling and theelimination of synonyms by referring to unique accepted terms for each syn­onym class, and by identifying semantically related terms. The use of con­trolled terms guarantees retrieval of appropriately marked items when the cor­
rect search terms are known, but it also normally implies that trainedintermediaries are needed to formulate the query statements.
A third problem relates to the type of vocabulary used for indexing pur­poses. A distinction is made between the use of single terms to characterize
document content, as opposed to the use of terms in context where relationshipindicators may be available to connect several identifiers, and the basic units
may consist of compound entries and phrases. In'the single term mode, the con­tent identifiers, known as index terms, keywords, or descriptors, are repre­
sented by individual words used to express the concepts included in each docu­
ment. Then each document is characterized by a collection of individual terms.
The terms are eventually combined, or “ coordinated,” to form topic descrip­
tions when the search requests are formulated. This process is known as “post­
coordination.” On the other hand, when compound terms are utilized for in­dexing purposes, consisting of phrases possibly including nouns, adjectives,

TEXT ANALYSIS AND AUTOMATIC INDEXING

55

prepositions, and a variety of relationship indicators, the process is called“precoordination.” For example, indexing this book under “automatic infor­
mation retrieval” is a use of precoordination; indexing it separately under eachterm and finding it in response to a query such as INFORMATION AND RE­
TRIEVAL represents postcoordination.
In many manual indexing situations where trained experts are involved,
the use of controlled indexing languages using precoordinated compound terms
is preferred. Automatic indexing systems, on the other hand, often use single
terms because the automatic assignment of effective single terms is well under­stood; the terms are then combined by postcoordination at search time only.
No matter what indexing environment is preferred, it is always necessary totake into account two characteristics of the indexing products known as “ exhaustivity” and “ specificity.” Exhaustivity refers to the degree to which all theconcepts and notions included in a document are recognized in the index de­
scriptions. The more exhaustive the indexing the higher may be the proportionof the relevant items that can be retrieved, because all the various aspects ofthe subject matter are then properly recognized. Specificity, on the other hand,refers to the generic level of the index terms used to characterize the document
content. If the indexing vocabulary is very specific, and if narrowly definedterms are assigned to the bibliographic items, a large proportion of the nonrelevant items may be properly rejected when the documents to be retrieved aredetermined.
In many retrieval environments it is customary to measure the effective­
ness of retrieval by using two parameters for each search known respectively
as “recall” and “precision.” Recall measures the proportion of relevant infor­
mation actually retrieved in response to a search (that is, the number of rele­vant items actually obtained divided by the total number of relevant items con­tained in the collection), whereas precision measures the proportion of
retrieved items actually relevant (that is, the number of relevant items actuallyobtained divided by the total number of retrieved items). These evaluation
measures are examined in more detail in Chapter 5. The use of exhaustive in­dexing and a specific indexing language is believed to lead to high recall as wellas high precision.
The dual characteristics of exhaustivity and specificity are sometimes sub­sumed under the notions of deep and shallow indexing. Deep indexing implies
both high exhaustivity and specificity and hence a good retrieval performance.
Shallow indexing, on the other hand, is produced by using a few broad terms tocharacterize each document. In these circumstances, the retrieval performance
may be expected to suffer somewhat, but the indexing task may be performed
more rapidly and more economically.
2

MANUAL AND AUTOMATIC INDEXING

Before turning to a description of automatic indexing methods, it may be useful
to summarize briefly some of the conventional manual indexing practices. In
most situations a controlled indexing language is used in which a single stan-

56

CHAPTER 3

dard term or phrase represents a wide variety of related terms and descriptions.
Thus, if the standard entry “oscillation” is specified in the accepted indexing
terminology, alternative related expressions such as “vibration,” “undula­tion,” “pulsation,” “ swing,” and “rolling” are replaced by “ oscillation”
when the documents are indexed and the search requests are formulated. To
facilitate the interpretation of the indexing vocabulary and the retrieval of rele­vant information, the elements of the controlled vocabulary may be used incontext, through precoordination of terms. Thus, instead of assigning single
terms such as “dyes,” “ solvents,” or “ spectra,” many systems specify com­plex indexing entries such as “ dyes, spectra, effect of Solvents” or “ solvents,
effect on spectra of dyes” [2],When precoordinated, controlled indexing languages are manually as­
signed, it is necessary to abide by the rules relating to the degree of desirable
context. That is, the number of related terms that should preferably be used;
the order in which the associated terms should be listed; and also the type of
relationship indication to be used between the components of an indexing entry
are all specified. Thus, the indexing products may be restricted to short phrases
or may be of sentence length equivalent to a complete document title. The list­
ing order may prescribe that a thing or object be entered before any action per­formed on the object, which in turn should be listed before any instrument usedin the action. Thus, an entry might have to be specified as “coal, production”
and not “production, coal.”Among the relation indicators accepted in various systems are the stan­
dard natural language prepositions and conjunctions, as well as links to indicate
connections between two or more terms in a description, and roles to specify
the function of particular terms in an indexing description. Thus if one wereinterested in the hardness of copper and the conductivity of titanium, a link be­
tween the first two terms and another one between the last two would relate
each substance to the relevant property. Typical “roles” performed by index
entry components are “ action,” “instrument,” “object,” “ subject,” etc.
Prepositions and conjunctions that are sometimes ambiguous could be usedwith some types of free-language indexing; links and roles on the other hand arenormally defined precisely and used with controlled vocabulary indexing.
To solve the intellectual problems of index language design, and aid theindexer in the term assignment and the searcher in the formulation of searchrequests, a variety of vocabulary lists and terminology descriptions may be
used, including in particular thesauruses that contain lists of equivalent and re­lated terms for each standard thesaurus entry. Hierarchical dictionaries may beavailable containing general term arrangements capable of identifying broader
and narrower terms for the various dictionary entries. The following types ofcross references are often included in the existing terminology descriptions:
1 “ See” references which identify the standard entry for terms not ac­
cepted by the indexing language (“aircraft, see airplanes”)
2 “ See also” references, sometimes also designated RT (related terms),

TEXT ANALYSIS AND AUTOMATIC INDEXING

57

which provide references between groups of related terms (“accidents, see also
collisions, hazards, safety, survival”)
3 References to generically broader terms, sometimes designated BT(“conversion coating, BT coating”)
4 References to generically narrower terms, sometimes designated NT(“cooling, NT conduction cooling, convection cooling, evaporation cooling”)
The terminology lists may take a variety of forms, including in particularalphabetical term, arrangements in which the entries and subentries within en­tries are alphabetically arranged (Table 3-la). Alternatively systematic, hierar­
chical term arrangements in tree form can be used where indentation on thepage denotes the generic level (in the excerpt of Table 3-lb, “traffic potential”
is generically inferior to “traffic,” which in turn is inferior to “airlines”). In
addition to formal vocabulary arrangements, it is often convenient to maintainlists of index entries derived from the formal thesaurus together with references
to the documents indexed by the corresponding entries. To facilitate the con­sultation of these indexes, it is customary in many cases to repeat each entry

Airlines.

Airplanes_____ Certification____ _ Cargo____ i. Depreciation____ _ Convertible_____ Economics------- Light_____ Employees___ Fares(a)

Airlines
T raff ic
T ra ffic potential
Finance
Accounting
Operation
Equipment(b)Peas, deficiency o f copper and zinc in
Copper, deficiency in peas
Zinc, deficiency in peas
Deficiencies o f copper and zinc in peas(c)Table 3-1 Conventional dictionary for­mats. (a) Excerpt from alphabetical termi­
nology. (b) Excerpt from systematic te r­
minology. (c) Multiple entry articulated
term arrangement.

58

CHAPTER 3

several times by changing the “lead term,” that is, the term used to gain entry
into the index. Various strategies are used to construct the set of multiple en­tries, known as rotation, cycling, chaining, permutation, and so on. In eachcase, the aim is to furnish a separate entry into the index for each standard aswell as each related term in a given compound expression. An example is in­cluded in Table 3-lc where the various entries (under “peas,” “copper,”“ zinc,” and “deficiencies”) are all assumed to refer to the same document or
documents. A similar strategy is used in the so-called permuted title indexes
which are a part of many modern automatic indexing environments.
An evaluation of the performance of standard subject indexes shows thatthe use of full index term context leads to a much better precision performance
than the lack of context exemplified by the use of single term entries. Increased
term specificity and a better understanding of the meaning of the index entries
may suppress many nonrelevant items that would normally be retrieved if en­tries devoid of context were used. On the other hand, when the various formsof context are compared with each other, such as the use of rotated entries andof function words to designate term relationships, few differences in retrieval
effectiveness are detected [3].
The foregoing considerations make it plain that much can, in principle, be
gained by using a sophisticated indexing product in finding useful documents,
rejecting extraneous items, and determining the potential importance of thestored information items. These gains are dependent on the quality, accuracy,
and consistency of the indexing performance. Not only must indexers be inti­
mately aware of the available indexing vocabularies and practices, but theyshould also have knowledge of the collection characteristics and of the type ofuser queries the system may be expected to process in the future. Furthermore,
the performance of the various indexers and searchers that must participate inmost operational environments ought to be sufficiently consistent to guaranteethat similar documents are identified by comparable indexing entries.
In practice one finds that accuracy and consistency are difficult to main­
tain. The situation demands a good deal of sophistication, training, and experi­ence on the part of the indexing personnel. But more often than not, the result­ing index entries are insufficiently exhaustive, omitting relevant entries, or
lacking in specificity. The former produces recall losses, while the latter may
lead to recall as well as precision deficiencies [4], A lack of indexing consist­ency also produces difficulties in detecting similarities among queries and docu­
ments [5,6], Therefore, the potential advantages of strictly controlled, man­ually applied indexing languages may be largely illusory.
An uncontrolled, natural language indexing system that is applied automat­
ically exhibits substantial advantages. A natural language system, when prop­
erly used, can be specific in the sense that the language may provide just theright kind of expression to denote each particular concept. Furthermore, thenatural language is the language of discourse. The authors of documents as wellas users of information systems are accustomed to the language, and even thehuman indexers and other subject specialists are likely to feel comfortable deal-TEXT ANALYSIS AND AUTOMATIC INDEXING

59

ing with a natural language system. For this reason natural language indexing
may be carried out more rapidly, and hence more cheaply than indexing basedon a controlled vocabulary and precoordinated terms.
On the other hand, in a natural language indexing system where a con­trolled thesaurus is not immediately available to make the distinction between
acceptable and forbidden index terms, some way must be found to supply thesynonymous and related terms that are available in a controlled indexing en­
vironment. Various approaches have been used for this purpose. Thus, exhaus­
tive indexing products may be obtained by choosing a wide variety of different
index terms for assignment to queries and documents. Term relationships canbe added, for example, by constructing term phrases instead of individual
terms; and the precoordinated indexing entries available with controlled term
systems can be replaced by juxtaposing individual terms when the search re­quests are formulated. Nevertheless, the generation of effective indexing prod­
ucts remains a major problem in a natural language indexing system.
It has been claimed that automatic, free language indexing products arenecessarily inferior to manual systems because automatic systems are deriva­
tive in the sense that the original document and query texts must serve as prin­cipal inputs for the indexing operation. It becomes necessary in these circum­
stances to wrestle with the peculiarities of the languages used by individual
authors, and to worry about unusual terminologies and expressions. Any asser­
tions concerning the inadequacy of automatic indexing can also be bolstered by,demonstrations designed to show that the results of particular automatic index­
ing procedures will fail to pass any rational test carried out by independent
human observers [7]. In so doing, one forgets that the results of manual index­
ing are also influenced by the terminology contained in individual documents,
no matter how much control may be provided by the auxiliary indexing aids.
In any case, the justification of any indexing technique ultimately lies in
the retrieval results obtained. Substantial evidence now indicates that simple
automatic indexing methods are fast and inexpensive, and produce a recall andprecision performance at least equivalent to that obtainable in manual, con­trolled term environments. A wide variety of automatic indexing methods are
examined in the remainder of this chapter, and performance evaluation data are
given for some of the proposed methods.

3

AUTOMATIC TERM EXTRACTION AND WEIGHTINGAGeneral Considerations

The indexing task consists first of assigning to each stored item terms, or con­cepts, capable of representing document content, and second of assigning toeach term a weight, or value, reflecting its presumed importance for purposes ofcontent identification. The first and most obvious place where appropriate con­tent identifiers might be found is the text of the documents themselves, or the
text of document titles and abstracts. This section is thus concerned with

60

CHAPTER 3

methods for the extraction of content terms from documents and document ex­
cerpts and with the assignment of term weights in order of term importance.
Most automatic indexing efforts start with the observation that the fre­quency of occurrence of individual word types (that is, of distinct words) innatural language texts has something to do with the importance of these words
for purposes of content representation. Specifically, if all words were to occur
randomly across the documents of a collection with equal frequencies, it would
be impossible to distinguish between them using quantitative criteria. In fact, it
has been observed that the words occur in natural language text unevenly. As aresult of this, classes of words are distinguishable by their occurrence frequen­cies. To quote from H.P. Luhn, one of the pioneers in automatic indexing [8]:T he justification o f m easuring word significance by use-frequency is based on thefact that a writer norm ally repeats certain w ords as he advances or varies his argu­
m ents and as he elaborates on an aspect o f a subject. This m eans o f em phasis istaken as an indicator o f significance. . . .

In fact, it is known that when the distinct words in a body of text are ar­ranged in decreasing order of their frequency of occurrence (most frequentwords first), the occurrence characteristics of the vocabulary can be character­ized by the constant rank-frequency law of Zipf:
Frequency • rank — constant(1)

That is, the frequency of a given word multiplied by the rank order of that word
will be approximately equal to the frequency of another word multiplied by its
rank [9]. The law has been explained by citing a general “principle of least ef­fort” which makes it easier for a speaker or writer of a language to repeat cer­tain words instead of coining new and different words. The least-effort princi­
ple also accounts for the fact that the most frequent words (those with thelowest ranks) tend to be short function words (and, of, but, the, etc.) which areeasy to coin and whose cost of usage is small.
The law has been verified many times using text materials in different
areas. A short illustration is contained in Table 3-2 [10]. A typical graph show­
ing the cumulative fraction of word usage in natural language texts is shown in
Fig. 3-1. It may be seen from the figure that the most frequent 20 percent of thetext words account for some 70 percent of term usage.
Using the Z ipf law of expression (1) as a starting point, it is now possible toderive word significance factors based on the frequency characteristics of indi­vidual words in document texts. An early proposal was based on the following
general consideration [8]:1Given a collection of n documents, calculate for each document the fre­quency of each unique term in that document. This is the frequency of term k indocument i, or FREQlk.

61

TEXT ANALYSIS AND AUTOMATIC INDEXING

Table 3-2

Illustration of Rank-Frequency Law(N u m b e r o f W o rd O c c u rre n c e s N = 1,000,000)

Rank (R)

Term

Frequency (F)R - (F/1,000,000)

1
2
3
4
5
6
7
8
9
10

the
of
and
to
a
in
that
is
was
he

69,971
36,411
28,852
26,14923,237
21,341
10,595
10,099
9,816
9,543

0.070
0.073
0.086
0.104
0.116
0.128
0.074
0.081
0.088
0.095

Adapted from reference 10.

2Determine the total collection frequency TOTFREQk for each word bysumming the frequencies of each unique term across all n documents, that is,
TOTFREQk = £ FREQik.
i= l

3 Arrange the words in decreasing order according to their collection fre­quency. Decide on some suitable high threshold value and remove all words
with a collection frequency above this threshold. This eliminates high-fre­quency function words such as those shown in Table 3-2.
4 In the same way, eliminate from consideration low-frequency words.
That is, choose some low threshold and remove all words with a collection fre­quency below this threshold. This deletes terms occurring so infrequently inthe collection that their presence does not affect the retrieval performance in asignificant way.
5 The remaining medium-frequency words are now used for assignment
to the documents as index terms.

Fraction o f words(in decreasing frequency order)

Figure 3-1

Word usage statistics.

62

CHAPTER 3

Since neither the high- nor the low-frequency terms are good content iden­tifiers, Luhn conjectured that the “resolving power” of the index words ex­
tracted from document texts would peak in the middle-frequency range asshown in Fig. 3-2. By “resolving power” is meant the ability of the index terms
to identify relevant items and to distinguish them from the nonrelevant ma­
terial. Among the recommendations made by Luhn for an actual automatic in­dexing policy, the following may be considered typical [11]:A notion occurring at least tw ice in the sam e paragraph w ould be considered amajor notion; a notion w hich occurs also in the im m ediately preceding or su cceed ­ing paragraphs w ould be considered a major n otion ev en though it appears only
on ce in the paragraph under consideration; notations for major notions w ould thenbe listed in som e standard order. . . .

There is some evidence that these original ideas are too crude to serve in apractical operational retrieval environment. Thus the elimination of all high-fre­quency words might produce losses in recall, because the use of broad, highfrequency words for content identification is effective in retrieving large num­bers of relevant items. Contrariwise, the elimination of low-frequency terms
may produce losses in precision. Another problem is the necessity to choose
appropriate thresholds in order to distinguish the useful medium-frequency
terms from the remainder. Finally, a question of principle arises concerning theuse of absolute frequency measures (such as FREQlk or TOTFREQk) for theidentification of content indicators. The reason is that a useful index term must
fulfill a dual function: on the one hand, it must be related to the information
content of the document so as to render the item retrievable when it is wanted(the recall function); on the other hand, a good index term also distinguishes the
documents to which it is assigned from the remainder to prevent the indiscrimi­nate retrieval of all items, whether wanted or not (the precision function). Thusa term such as “ computer” may never constitute a reasonable term for assign­
ment to a document collection in computing, no matter what its frequency ofWords in decreasing
frequency orderFigure 3-2
ence 8.)Resolving power of significant (medium-frequency) words. (Adapted from refer­

TEXT ANALYSIS AND AUTOMATIC INDEXING

63

occurrence in the documents of the collection, because “computer” is likely tooccur in every collection item and cannot therefore be used to distinguish theitems from each other. This suggests the use of relative frequency measures to
identify terms occurring with substantial frequencies in some individual docu­
ments of a collection, but with a relatively low overall collection frequency.
Such terms may then help in retrieving the items to which they are assigned,
while also distinguishing them from the remainder of the collection [12,13].
Several term weighting functions have been derived from these basic con­siderations, including an inverse document frequency function, the signal-noise
ratio, and the term discrimination value. These weighting functions are briefly
introduced in the remainder of this section.
*B

The Inverse Document Frequency Weight

The first possibility consists in assuming that term importance is proportional
to the standard occurrence frequency of each term k in each document i (thatis, FREQik) and inversely proportional to the total number of documents towhich each term is assigned. Specifically, one counts the number of documents
in which a term k occurs. This produces the document frequency DOCFREQkof term k, representing the number of documents to which term k is assigned. A
possible measure of the inverse document frequency can now be written as [14]log2 DOCFREQk + 1 = log2(n) “ log2(DOCFREQk) + 1
where n is the number of documents in the collection. For example, in a collec­
tion of 1,000 documents, consider the term ALPHA occurring in 100 docu­
ments, term BETA occurring in 500 documents, and GAMMA occurring in 900
documents. The inverse document frequency factor will then be 4.322 for
ALPHA, 2.000 for BETA, and 1.132 for GAMMA. The emphasis is seen to beplaced on the terms exhibiting the lowest document frequencies.
A composite expression measuring the importance, or weight, of term k ina given document i would increase as the frequency of the term in the docu­
ment, FREQik, increases but decrease as the document frequency DOCFREQk
increases. A possible weighting function is
WEIGHTlk = FREQlk ' [log* (n) - log2 (DOCFREQk) + 1]

(2)

This function assigns a high degree of importance to terms occurring in only a
few documents of a collection [14].
**C

The Signal-Noise Ratio

A related viewpoint suggests using information theory considerations to con­struct a measure of term importance. In particular, it is known that the informa­tion content of a message, or term, can be measured as an inverse function of
the probability of occurrence of the words in a given text. Specifically, the64

CHAPTER 3

higher the probability of occurrence of a word, the less information it contains.
The information content of a word is measured as INFORMATION = - log2 p,
where p is the probability of occurrence of the word. For example, if the word
ALPHA occurs once in every 10,000 words, its probability of occurrence is
0.0001, and its information is
INFORMATION = - lo g 2 (0.0001)= - ( - 13.278)= 13.278
On the other hand, if the word THE occurs once in every 10 words, its proba­
bility is 0.1 and its information measure is
INFORMATION = - log* (0.1)= - ( - 3 .2 2 3 )= 3.223
The term information value can be regarded as a measure of reduced un­
certainty, in the sense that when terms are assigned as content identifiers to the
documents of a collection, knowing a particular term reduces the uncertainty
about the document content. Furthermore, the smaller the probability of occur­
rence of the terms (that is, the greater the term specificity) the larger is the re­duction in uncertainty.
By extension, when a document is characterized by t possible identifiers,or terms, each occurring with a specified probability pk, the average, or ex­
pected information (that is, the average reduction in uncertainty about the doc­
ument) gained by using one of the terms is given by Shannon’s formula [15]AVERAGE INFORMATION = -pk log pk

(3)

k=l

For example, if the terms ALPHA, BETA, GAMMA, and DELTA are ex­pected to occur with the probabilities 0.5, 0.2, 0.2, and 0.1, respectively, thethe average information is
AVERAGE INFORMATION = - [(0.5 log2 0.5) + (0.2 log2 0.2)
+ (0.2 log2 0.2) + (0.1 log2 0.1)]= - [ ( - 0 .0 5 ) + (-0 .4 6 ) + (-0 .4 6 ) + (-0.33)]= 1-3
It is known that the average information is maximized when the occurrence
probabilities of the terms are all equal to 1/t for t distinct terms. For example, if
ALPHA, BETA, GAMMA, and DELTA are all expected to occur one-fourthof the time, the average information value will be 2 instead of 1.3 as in the ear­lier example.

TEXT ANALYSIS AND AUTOMATIC INDEXING

65

By analogy to Shannon’s information measure, it is now possible to define
the noise NOISEk of an index term k for a collection of n documents

NOISEk^FREQikTOTFREQk£ TOTFREQk g2 FREQik(4)

This measure of noise varies inversely with the “concentration” of a term in
the document collection. That is, for perfectly even distributions, when a term
occurs an identical number of times in every document of the collection, thenoise is maximized. For example, if term k occurs exactly once in each docu­
ment (all FREQik = 1 )NOISE, = i ^ log2j
i=l 1= log2 n!

On the other hand, for perfectly concentrated distributions, when a term ap­
pears in only one document with frequency TOTFREQ,, the noise is zero be­cause in that case

NOTSF _ TOTFREQ,k TOTFREQ,= 1 log2 1= °to tfr eq ,82 TOTFREQk

A relation clearly exists between noise and term specificity, because
broad, nonspecific terms tend to have more even distributions across the docu­
ments of a collection, and hence high noise. An inverse function of the noise
might then be used as a possible function of term value [16,17]. One such func­tion, known as the signal of term k, is defined as follows
SIGNAL, = log2 (TOTFREQk) - NOISE,(5)

For the maximum noise case previously discussed (where each FREQik) isequal to 1 the SIGNAL is equal to 0, since TOTFREQ, in that case equals n.
On the other hand, when a term occurs in only one document, a maximum sig­
nal of log2 TOTFREQ, is obtained.
In principle* it is possible to rank the index words extracted from the docu­
ments of a collection in decreasing order of the signal value. Such an orderingfavors terms that distinguish one or two specific documents (the ones in which
the high-signal term exclusively occurs) from the remainder of the collection.
Alternatively, the importance, or weight, of term k in document i can be com­puted as a composite function taking into account FREQik as well as SIG-

66

CHAPTER 3

NALk. A possible measure of this type analogous to the term weighting func­tion of expression (2) is
WEIGHT* = FREQ* • SlGNALk(6)

It will be seen later that the signal value does not give optimal performance in a
retrieval environment.
*D The Term Discrimination Value

Luhn’s early proposals were designed to measure the “resolving power” of aterm with respect to a document by using the frequency of occurrence of theterm in the document. Another approach is to compute the discrimination
value of a term. This measures the degree to which the use of the term will help
to distinguish the documents from each Other [18,19]. Consider, in particular, acollection of documents, and let D, and Dj represent two documents each iden­tified by a set of index terms. A similarity measure SIM IL A R ^ ,1^) can beused to represent the similarity between the documents. Typical similarity
measures generate values of 0 for documents exhibiting no agreement among
the assigned index terms, and 1 when perfect agreement is detected. Interme­
diate values are obtained for cases of partial agreement.
If the similarity measure is computed for all pairs of documents (D, ,Dj) ex­
cept when i = j, an average value AVERAGE-SIMILARITY is obtainable.
This represents the average document-pair similarity for the collection. Specifi­
cally,AVERAGE-SIMILARITY = CONSTANT ££ SIMILARCDj.Dj)
i=1 i^ji=1(7a)

for some constant [for example, l/n(n — 1)]. The foregoing expression reflects
the density of the document space, that is, the degree to which the documents
are bunched up in the “ space” of documents. When all n documents are identi­
cal, SIMILARCD^Dj) = 1 for all document pairs, and AVERAGE-SIMI­LARITY reaches a maximum:
AVERAGE-SIMILARITY = CONSTANT
i=1 i # i=1= CONSTANT • n(n - 1)
The space density can be computed more efficiently by constructing an ar­tificial, “average” document D as the centroid, in which the terms are as­
sumed to exhibit average frequency characteristics, that is, the average fre­quency of term k is defined as(AVERAGE FREQ)k = - ^ FREQj,TEXT ANALYSIS AND AUTOMATIC INDEXING67

The density is then computed as the sum of the similarities of each documentwith the centroid

AVGSIM = CONSTANT £ SIM ILAR(DA)

(7b)

i= l

Consider now the original document collection with term k removed fromall the documents and let (AVGSIM)k represent the space density in that case.
If term k had been a broad, high-frequency term with a fairly even frequency
distribution, it is likely that it would have appeared in most document descrip­
tions; therefore, its removal will reduce the average document-pair similarity.
This case is clearly unfavorable, because when such a high-frequency term is
assigned to the documents, the average similarity will increase and the docu­
ment space is compressed. On the other hand, if term k had been assigned ahigh weight in some documents, but not in others, its removal would be likely
to increase the average similarity between documents.
The discrimination value DISCVALUEk can now be computed for eachterm k as
DISCVALUEk = (AVGSIM)k - AVGSIM(8)

Following the computation of DISCVALUEkfor all terms k, the terms canbe ranked in decreasing order of the discrimination value DISCVALUEk. A
typical ranking of this type for document collections in three different subject
areas appears in Table 3-3. In each case the 10 best discriminators are shown—
those whose removal will compress the document space the most— as well as
the 10 worst discriminators (other than the previously eliminated common
function words whose discrimination values would no doubt be even poorer). It
may be seen that the terms at the top of the table are highly specific, whereas
the terms at the bottom are much more general. A term such as “flow” occurs
in most documents in the Cranfield collection on aerodynamics, accounting for
its poor performance as a document discriminator.
For experimental purposes the index terms may be placed into three roughcategories according to their discrimination values:
1 The good discriminators with a positive DISCVALUEk whose intro­
duction for indexing purposes decreases the space density
2 The indifferent discriminators with a DISCVALUEk close to zero
whose removal or addition leaves the similarity among documents unchanged
3 The poor discriminators whose utilization renders the documents moresimilar, producing a negative DISCVALUEk
Frequency distributions for three typical terms, one from each category are
shown in Table 3-4. It may be seen that the negative discriminator in the right­
most column of the table exhibits a total collection frequency TOTFREQk of
527 and a document frequency DOCFREQk of 337 for a collection of 450 docu-

68

CHAPTER 3

Table 3-3 Best and Worst Discriminators for Three
Collections(C ra n fie ld : 424 D o c u m e n ts in A e ro d y n a m ic s ; M E D : 450
D o c u m e n ts in M e d ic in e ; Time: 425 D o c u m e n ts in W o rld
A ffa irs )Cranfield 424

MED 450a

1. Panel
2. Flutter
3. Jet
4. Cone5. Separate
6. Shell
7. Yaw
8. Nozzle
9. Transit
10. Degree

2642. Equate.2643. Theo
2644. Bound
2645. Effect2646. Solution
2647. Method
2468. Press
2649. Result
2650. Number
2651. FlowBest discriminators
1. Marrow
2. Amyloidosis
3. Lymphostasis
4. Hepatitis
5. Hela6. Antigen
7. Chromosome
8. Irradiate
9. Tumor
10. VirusbTime 425

1. Buddhist
2. Diem
3. Lao4. Arab
5. Viet6. Kurd
7. Wilson
8. Baath
9. Park
10. Nenni

Worst discriminators
4717. Clinic
4718. Children
4719. Act4720. High4721. Develop
4722. Treat
4723. Increase
4724. Result4725. Cell
4726. Patient

7560. Work7561. Lead
7562. Red
7563. Minister7564. Nation
7565. Party
7566. Commune
7567. U.S.
7568. Govern
7569. New

Adapted from reference 19.

ments; the term occurs once in 221 documents, twice in 75 additional docu­
ments, three times in 19 documents, four times in 15 documents, and five andsix times in 3 and 4 items, respectively. It is not surprising that such a ubiqui­
tous term operates poorly as a discriminator.
The second and third columns of Table 3-4 contain examples of an indiffer­
ent discriminator and a good discriminator, respectively. It may be seen thatthe indifferent discriminator term has a very low document frequency of 16
items out of 450. Its assignment leaves the document space more or less un­changed. The good discriminator in the third column has a document frequencyof 61 out of 450 and a total collection frequency of 188.
The document frequency DOCFREQk, total collection frequency TOTFREQk, and average frequency of each term are shown in Table 3-5 for the 10
best discriminators and 10 worst discriminators in a collection of 852 docu­
ments in ophthalmology. In each case the rank of each term in decreasing orderof the discimination value is also shown in the table.
The data of Tables 3-4 and 3-5 and related comparisons of the frequency

69

TEXT ANALYSIS AND AUTOMATIC INDEXING

Table 3-4 Distribution Characteristics of a Typical Term in Each of Three
Discrimination Categories(C o lle c tio n S ize 450)

Number of documents with corresponding frequency
Number of occurrencesof term k in documents

Low-frequency
term zeroDISCVALUEk

Medium-frequency
term positive
DISCVALUEk

High-frequency
term negative
DISCVALUEk

1
2
3

10
3
3

26
13
8

4

—

4

5
6
7
8
9
10
11-15
16-20
21-25
26-30
30+

—

2
2

221
75
19
15
3

Total term frequency
TOTFREQk
Total document frequency
DOCFREQk

—
—

—

2 •

—
—

—

—

—

—
—

—
—
—

2
2

—

4
—

—

—
—
—

—

—

—

—

—

—

25

188

527

16

61

337

characteristics of terms with their discrimination value confirm Lutin's original
notions that medium-frequency words are to be preferred for assignment as
index terms. The discrimination value computation [expression (8)] provides anobjective method for determining the frequency thresholds: high-frequency
terms with a negative DISCVALUEk are poor and should not be used directly
for indexing purposes; low-frequency terms with a zero DISCVALUEk may or
may not be used— their assignment will not hurt the performance of the re­trieval system but may be questioned on efficiency grounds because the storageand manipulation of large numbers of low-frequency terms tends to be expen­
sive; the good discriminators— those with resolving power to use Luhn’s ter­minology— have a positive DISCVALUEk, and they happen to be medium-fre­quency terms in the collection in which they occur [21,22].
A display of the frequency distribution of good, indifferent, and poor terms
in signal-value order [expression (5)] shows that the terms with the best SIGNALk values have very low document and collection frequencies. Typical
DOCFREQk and TOTFREQk values for those terms with good signal values
are 3, 20; 6, 33; and 2, 9, respectively, showing that the terms with the best
“information value” are not those best able to distinguish a substantial numberof documents in a collection [18].

1a> >7<o oc o
00 O
0> N 00 T05“ CCOO Is- CCOO CO oo oo
CM m
CM CM CO CM
a>> 3O'CO CO CM CM CM CM
< 0)

70

C M N C O C O ^ C O i-C O C M
it- CM CO

0 7

O 0>
O£

c

si
0) =

aO
>
■O
. o
(0)
i S'
=O >*
w .C
O £ > h ?a= >a> S
0 Qa.
®

.o
a
3 CO
cc O

-I

O O O

llO

£

d

>W

C M C O ^ l/ ) ( O N » D O

0)

o

2S

Nondiscriminators< S>(852 A b s tra c ts in O p h th a lm o lo g y )Table 3-5

Highest-Ranking Discriminator and Nondiscriminator Terms

Discriminators

O CM CD O CM CO in CM IT)
CM tn
CO
CO CM
a CCM
O **

CO i— 00 CM in o> in CO T~
CM in
o in CO CO o l“j CO Is- co CO CM in
1— 1“ c\i
TCM
T“ y—

05
CM h- Is- in o>
00 CM
3O a3> o00 O)
in h*.
CO in CO CM Is- 05
CM CM CM CM CM CM CM CM CM TH 07)

7C >
*
M
S
c>
E a
3 3 CoM d>iO 7

o > n o o N in sN ^

o a>

Q3

c
(1)
•p

ffl

0. <

CO c
TJ t
o
C o D
0) i lCl> >CO CD CO "! a o
C0 CO 0CO
0 o 0 uX X a . a . X LU DC X CL u

CM Y*“ o 05 CO
ro CM xCD in
Is- Is- Is - CD CD CO CD CO CO CO CD CO
CD CD CD CD CD CD CD CD CD CO CO CO
CO CO CO 00 00 00 00 00 00 00 CO 00

TEXT ANALYSIS AND AUTOMATIC INDEXING71

The term discrimination value of expression (8) can be used to compute animportance factor, or weight, for each term in each document of a collection by
combining the term frequency factor with the discrimination value. This pro­duces a weighting expression for term k in document i analogous to expressions(2) and (6) for the inverse document frequencies and the signal values asfollows:
WEIGHT* = FREQ* • DISCVALUEk(9)

The insights concerning the term occurrence frequencies are incorporated
into a simple automatic indexing process described in the following section.
4 A SIMPLE AUTOMATIC INDEXING PROCESSIt may be of interest briefly to describe a simple process for the automatic as­
signment of index terms to the documents of a collection. Such a process must
start with the identification of all the individual words that constitute the docu­
ments. A problem arising in this connection is the definition of the document to
be used. There are many so-called full-text retrieval systems where the full textof the documents is used for indexing purposes. This is true in specialized areasof discourse, for example, law or medicine, where the vocabulary may be spe­cialized and the presence of a particular term, say “tort” in a legal document,
has specific connotations [23]. However, the computer storage of the full textof documents is expensive and is rarely possible except as a by-product of auto­
matic typesetting operations. For many practical purposes, it is sufficient to use
document excerpts for analysis, such as the titles and abstracts. The available
experimental evidence indicates that the use of abstracts in addition to titles
brings substantial advantages in retrieval effectiveness. However, the addi­
tional utilization of the full texts of the documents appears to produce very little
improvement over titles and abstracts alone in most subject areas [24].
Following the identification of the words occurring in the document texts,
or abstracts, the high-frequency function words need to be eliminated. Thesecomprise 40 to 50 percent of the text words, and as suggested earlier, thesewords are poor discriminators and cannot possibly be used by themselves to
identify document content. In English, about 250 common words are involved,
and it is easy to include them in a dictionary, sometimes called a negative dic­tionary, or stop list. An excerpt from a typical stop list is shown in Table 3-6.
The next step, following removal of stop words, is the identification of“good” index terms and their assignment to the documents of a collection. It isuseful first to remove word suffixes (and possibly also prefixes), thereby reduc­ing the original words to word stem form. This reduces a variety of different
forms such as analysis, analyzing, analyzer, analyzed, and analysing to a com­
mon word stem “ analy.” The word stem “ analy” will have a higher frequencyof occurrence in the document texts than any of the variant forms. The genera­tion of word stems, and subsequent identification of common stems, is rela-

72

CHAPTER 3

Table 3-6

Excerpt from Typical Stop ListA
ABOUT
ACROSSAFTERAFTERWARDS
AGAIN
AGAINSTALL
ALMOST
ALONE
ALONG
ALREADY
ALSO
ALTHOUGHALWAYSAMONG

AMONGST
AN
AND
ANOTHERANY .
ANYHOW
ANYONEANYTHING
ANYWHERE
ARE
AROUNDAS
AT
BEBECAME
BECAUSEBECOMEBECOMESBECOMING
BEEN
BEFOREBEFOREHAND
BEHINDBEING
BELOW
BESIDEBESIDESBETWEEN
BEYOND
BOTH
BUT
BY
CAN

Excerpted from reference .25.

tively easy to do for many languages (including English) and serves as a recall­enhancing device. When the stems are used as index terms, a greater number ofpotentially relevant items can be identified than when one of the original fulltext words is in use. <.
Several well-known algorithms exist for the removal of word endings, gen­erally based on the use of a list of suffixes followed by the removal of the long­est suffix matching any entry on the suffix list [26,27]. An excerpt from a typi­
cal suffix list is shown in Table 3-7. In using, a suffix removal algorithm it isimportant to handle various classes of exceptional cases. The following list
identifies problems in English:
1 It is desirable to remove the suffix “ability” from computability, or thesuffix “ing” from singing; however, the same suffixes should not be removed
from the words ability and sing, respectively; problems such as these are nor­mally solved by specifying a minimum stem length that must remain following
the suffix removal.
2 Several suffixes may be attached to a single stem; thus effectivenessmay be shortened to effective by the removal of “ness,” which can in turn beshortened to effect by removal of ‘‘ive’’; multiple suffixes can be handled either
by applying the suffix removal process recursively several times or else by in­cluding in the suffix dictionary all multiple suffix entries, and removing longer
suffixes in preference to the shorter ones.
3 Various examples of morphological transformations exist in English
which may alter the stem of many suffixed words; for example, the word ab­sorb is transformed into absorption when the suffix “tion” is added; similarly
hop becomes hopping, relief becomes relieving, and so on. Transformationalrules can be set up in order to recode various automatically generated stems fol-

TEXT ANALYSIS AND AUTOMATIC INDEXING

Table 3-7

73

Exerpt from Typical Suffix List

ABILITIESABILITY
ABLE
ABLED
ABLEDLY
ABLENESS
ABLER
ABLES
ABLINGABLINGFULABLINGLYABLY
ACEOUSACEOUSLYACEOUSNESSACEOUSNESSESACIDOUSACIDOUSLYACIESACIOUSNESSACIOUSNESSESACITIES
ACITY
ACY
AE
AGE
AGED
AGER
AGES
AGING
AGINGFUL
AGINGLYAIC
AICAL
AICALLYAICALSAICISMAICISMS
AICS
AL
ALISATIONALISATIONALALISATIONALLY
ALlSE
ALISED
ALISEDLY
ALISER

Excerpted from reference 25.

lowing suffix removal. A typical rule might state “remove one of double occur­
rences of b, d, g, 1, m, n, p, r, s, t from the end of a generated stem.”
4
Finally, a number of additional exceptions which depend on the partic­
ular word context must be taken care of, using various context-sensitive rules.
For example, a rule for the suffix “allic” specifies a minimum stem length of
three and prevents suffix removal after “met” or “ryst” ; another rule applica­
ble to the suffix “yl” permits removal only after “ n” or “r” [27].
In summary, it is not difficult to implement a suffix removal algorithm pro­ducing usable word stems for the vast majority of existing English word forms.
A stored suffix list must be used together with a few contextual rules applicableto certain suffixes. A list of transformations to recode some of the generated
stems is also necessary, or a stored full word dictionary could be used for that
purpose.
After the word stems are generated, it becomes necessary to recognize
equivalent stems occurring in the texts and to choose those stems to be used asindex terms. The frequency-based techniques can be used to determine the po­tential usefulness of the remaining word stems.' A high standard of performanceat modest cost is obtainable by using the inverse document frequency function
l/DOCFREQk to obtain a term importance factor. Another possibility consists
in using the discrimination DISCVALUEk or the SlGNALk. The latter, how­ever, emphasizes term concentration in only a few documents of a collection
and should be used only in order to emphasize precision at the expense of re­call.
The terms (word stems) with sufficiently high term value factors can be
assigned to the documents of the collection either with or without a term
weight. When the indexing mode is binary, a term that occurs in a document is
assigned an implicit weight of 1, no matter what its actual frequency of occur-

74

CHAPTER 3

13,471 terms

13,301 terms left .

7,236 terms left

6,056 terms left

6,026 terms left

5,771 terms left

Final indexing vocabulary

Figure 3-3 Typical term deletion algorithm (data for 1,033 documents in medicine).

rence. In a weighted indexing system, a term weight may be used to reflect term
importance by using the weighting functions [expressions (2), (6), or (9)] pre­viously described. This produces for each document D, a document vector

Di = <du , d12, . . . , dit)(10)

where each djj is the weight assigned to the jth identifier for document Dt. For
example, if there are three terms ALPHA, BETA, and GAMMA, respectively,then
D i = (2, 4, 0)means that document number 1 is identified by the term ALPHA with a weightof 2, BETA with a weight of 4, and GAMMA with a weight of 0. The vector
length t corresponds to the number of distinct terms assigned to the whole col-

TEXT ANALYSIS AND AUTOMATIC INDEXING

75

lection, and weights of 0 are assumed for terms not assigned to a given docu­
ment vector.
It remains to determine what to do with terms whose importance factors
are not high enough to make it reasonable to assign them to the documents. In
principle such terms can simply be deleted from the identifying vocabulary. A
prototype indexing system based on various term deletion methods is repro­
duced in simplified form in the flowchart of Fig. 3-3. The index term data of Fig.
3-3 are based on the processing of 1,033 document abstracts in medicine. A
simplified stemming method was used in which the only recognized suffix is aterminal “ s .” The indexing vocabulary eventually is reduced to 5,771 stems
from the original 13,471 words.
Term deletion methods must be used with caution because the removal ofsome broad high-frequency terms may produce unwanted recall losses,
whereas deletion of certain low-frequency terms reduces indexing exhaustivity
and may result in reduced retrieval recall and precision. Instead of deleting thepoor discriminators, it may be preferable to improve such terms by turningthem into terms with better discrimination properties. This can be done in vari­
ous ways by using context and term associations, as explained in the next sec­tion.

5 AUTOMATIC TERM ASSOCIATION AND USE OF CONTEXTA Thesaurus Rules

It was seen earlier that some words or word stems extracted from document
texts may not function effectively as index terms. This is the case notable forvery high-frequency terms that occur in a large proportion of the documents ofa collection, and for very low-frequency words which occur very rarely. The
question is whether such terms can be transformed into different types of enti­
ties that prove more discriminating and better able to reflect document content.
The natural language provides a variety of devices for changing the specificity
and scope of individual terms: for example, the phrase “term specificity” has anarrower, more specific interpretation than either “term” or “ specificity”
alone; similarly, the term “ computer” has a broader meaning than “ minicom­
puter.”In the preceding discussion, several tools have been described that may be
useful for controlling or changing the scope of individual words or terms. Thus,a variety of dictionaries may be available in conventional indexing situations
which allow the manual indexer to choose broader or narrower or related terms
in addition to or instead of an initially available dictionary entry. A term broad­ening step was also included in the basic term extraction methods examined in
the preceding section in the form of a word stemming process. The stemming
process replaces a full text word by a word stem with a broader interpretation,
The basic idea in improving the usefulness of index terms with question­
able discrimination properties then consists in using associations between

76

CHAPTER 3

terms in the hope of refining or broadening the interpretation of these terms.
Many kinds of term associations can profitably be incorporated into an auto­
matic indexing system. The first and most obvious one consists in imitating themanual indexing process by using a term thesaurus.
A thesaurus provides a grouping, or classification, of the terms used in agiven topic area into categories known as thesaurus classes. As in the manualindexing case, thesauruses can be used for language normalization purposes inorder to replace an uncontrolled vocabulary by the controlled thesaurus cate­gory identifiers. A thesaurus may broaden the vocabulary terms by addition of
thesaurus class identifiers to the normal term lists, thereby enhancing the recall
performance in retrieval. Alternatively the thesaurus class identifiers can re­place the original term entries in the hope of improving recall and providing
vocabulary normalization. When hierarchical relationships are supplied for theentries in a thesaurus in the form of “broader” or “narrower” terms, the in­dexing vocabulary can be “ expanded” in various directions by adding thesebroader or narrower terms, or certain related terms, as the case may be.
An excerpt of a thesaurus used in an automatic indexing environment for
documents in engineering is shown in Table 3-8. The thesaurus class identifiers
are represented by identifying “ concept numbers” designating the various
term classes. Thus, when a document contains the term “ superconductivity”or (stem “ superconduct” ), that term may be replaced by class identifier 415.
The same operation could be used for another document, or for a user query,containing the term “ cryogenic.” Should the document contain “ superconduc­tivity” while the query term is “ cryogenic,” a term match would result throughthe thesaurus transformation, but not using the original word stems.
Thesauruses may be constructed manually, semiautomatically, and fully
automatically. No matter what process is used, two separate problems arise atonce:
1 A decision must be made about what terms should be included in thethesaurus.
2 The terms specified for inclusion must be suitably grouped.
To decide what to include, the various term value models described earlier
can be used. The discrimination value model specifies, for example, that themost important terms are those with medium document frequency, followed bythose with low document frequencies and near zero discrimination values.
Since the main purpose of a term classification is the improvement of the recall
performance, one concludes that a thesaurus should certainly include a group­
ing of the low-frequency terms into classes of higher frequency. In addition, agrouping of the medium-frequency good discriminators might also be useful forsome purposes, particularly when a high recall performance is wanted. On theother hand, the high-frequency low discriminators might be eliminated alto­
gether.
The following thesaurus construction principles derived in part from theTEXT ANALYSIS AND AUTOMATIC INDEXING

77

Table 3-8 Typical Thesaurus Excerpt
408

DISLOCATION
JUNCTIONMINORITY-CARRIER
N-P-N
P-N-P
POINT-CONTACTRECOMBINE
TRANSITIONUNIJUNCTION

409

BLAST-COOLEDHEAT-FLOW
HEAT-TRANSFER

410

ANNEALSTRAIN

411

412

COERCIVE
DEMAGNETIZEFLUX-LEAKAGE
HYSTERESISINDUCT
INSENSITIVEMAGNETORESISTANCESQUARE-LOOP
THRESHOLD

413

CAPACITANCEIMPEDANCE-MATCHING
IMPEDANCEINDUCTANCE
MUTUAL-IMPEDANCEMUTUAL-INDUCTANCE
MUTUALNEGATIVE-RESISTANCEPOSITIVE-GAP
REACTANCERESISTSELF-IMPEDANCESELF-INDUCTANCE
SELF

414

ANTENNAKLYSTRON
PULSES-PER-BEAM
RECEIVER
SIGNAL-TO-RECEIVER
TRANSMITTERWAVEGUIDE

415

CRYOGENIC
CRYOTRONPERSISTENT-CURRENT
SUPERCONDUCTSUPER-CONDUCT

416

RELAY

LONGITUDINAL
TRANSVERSE

earlier indexing models and in part from previously obtained experimental evi­
dence can be enunciated [28]:1 The thesaurus should include only those terms likely to be of interestfor content identification in a subject area (for example, a term such as “ hand”
might be used in a thesaurus dealing with biology, but it should not be included
if its frequency of occurrence is due largely to expressions such as “on theother hand” ).
2 Ambiguous terms should be coded only for those senses likely to beimportant in the document collection (at least two thesaurus categories should
thus be used for a term such as “field,” corresponding on the one hand to thenotion of subject area and on the other hand to its technical sense in algebra; noprovision need be made to cover the notions bf “ a patch of land” if the thesau­
rus deals with the mathematical sciences or related technical fields).
3 In order to obtain good matching characteristics between query anddocument terms, each thesaurus class should include terms of roughly equal
frequency; furthermore, the total frequency of occurrence should be as close toequal for each class as possible, thus ensuring that the probability of producing

78

CHAPTER 3

a match between queries and documents is approximately equal for all thesau­
rus classes. (If these frequency characteristics are grossly violated— for exam­
ple, :if a high-frequency term such as “computer” is entered into the same classas a more specific term such as “minicomputer” — queries about specific topics
will produce general responses, thereby depressing the precision of the search.)
4
Whenever possible, terms with negative discrimination values shouldbe eliminated; even if the size restrictions that control the thesaurus construc­tion do not immediately lead to the elimination of all high-frequency nondis­
criminators, the latter are best relegated to thesaurus classes of their own (theirclassification together with lower-frequency terms would produce low-pre­cision output).
Concerning now the actual thesaurus construction method, a manual the­saurus generation process is an art rather than a science. In recent years, anumber of automatic aids have considerably simplified the thesaurus construc­tion task. Thus, given a collection of documents, it is now easy to automatically
produce concordances exhibiting the occurrences of all terms in the context inwhich they occur, arranged in alphabetical order for convenient access. Thus
all occurrences of the term “information” would be collected under the letter I,
together with contextual information for each occurrence of the term. This
makes it-possible to determine the placement of each term within a thesaurus
class arrangement by collecting in a common class various terms occurring in agiven document set in the same context.
An automatically constructed alphabetical arrangement of terms derived
from a given document set can in fact function as a kind of thesaurus, and has
been widely used in practice to obtain access to document collections. Nor­
mally, the terms included in such a listing are the words occurring in the titlesof documents. The resulting products are known as keyword-in-context(KWIC) indexes. Alternatively, related term arrangements known as KWAC
and KWOC (keyword and context, keyword out of context) are also obtain­
able. An example of KWIC and KWAC arrangements is shown in Table 3-9.
The entries shown in the table are produced by a document (number 3,313) en­
titled “User Preference in Published Indexes.” This title generates four en­tries: one under I for the term “indexes,” two under P for “preference” and“published,” and finally one under U for “user.”
When aids such as KWIC indexes are used judiciously, and the previously
mentioned thesaurus construction principles are applied, the task of building
the term classification is simplified. The main intellectual decisions for the ac­tual term grouping process are, however, reached manually.
*B

Automatic Thesaurus Construction

A variety of fully automatic thesaurus construction methods are available,
based on the use of a set of document vectors of the type shown in expression(10). A document collection is then representable by a matrix such as that inTable 3-10. It was seen earlier that a similarity function SIM IL A R ^ ,Dj) re-79

TEXT ANALYSIS AND AUTOMATIC INDEXING

Table 3-9 KWIC and KWAC Entries Produced byDocument on “User Preference in Published Indexes”
KWIC
RENCE IN PUBLISHEDINDEXES/ USER PREFE
PREFERENCE IN PUBLISHED INDEXES/ USER
PUBLISHED INDEXES/
USER PREFERENCE IN
USER PREFERENCE IN P
UBLISHED INDEXES/KWAC
INDEXESUSER PREFERENCE IN PUBLISHED INDEXESPREFERENCE
USER PREFERENCE IN PUBLISHED INDEXES
PUBLISHEDUSER PREFERENCE IN PUBLISHED INDEXES
USER
USER PREFERENCE IN PUBLISHED INDEXES

3.313
3.313
3.313
3.313

3.313
3.313
3.313
3.313

Adapted from reference 3.

fleeting index term similarities can be computed for each document pair (Dj ,Dj)
by comparing pairs of rows of the document matrix. While the rows of the ma­trix represent the individual document vectors, the columns identify the term
assignments to the documents. That is, a column, j, of the document vector
matrix reflects the assignment of TERMj to the documents of the collection.
The vector comparison process previously used to compute the density of the
document space [see expression (7)] can also be used to obtain a similarity mea­
sure between pairs of columns SIMILAR(TERMk,TERMh), reflecting the simi­
larities between TERMk and TERMh. Given term vectors of the form
TERMk = (tlk, t2k, . . . , tnk), where tik indicates the weight or value of
TERMk in document i and assuming n documents in the collection, a typicalsimilarity measure may then be defined as
SIMILAR(TERMk,TERMh) = ^ tlk tlh
i= l

Table 3-10 Matrix ofDocument Vectors

JT,__ T^D,D2

dn d12
d2i

d22

D,

,dn1

d n2

T,

•*•

d n,

(i i )

80

CHAPTER 3 .

or, using a normalization factor to limit the computed results to yalues between
0 and 1,
2b k tih

SIMILAR(TERMk,TERMh) = —------------ --------------- ---------2
^
i= l

+

2
( t ih )2 i= l

(12)

2
tik tih
i= lWhen all pairs of distinct columns of the matrix of Table 3-10 are comparedwith each other, a term-term association matrix T is constructed in which theelement located in row k and column h equals SIMILAR(TERMk,TERMh). A
sample term-term association matrix is shown in Table 3-11.
A variety of automatic classification or clustering methods can now be
used to construct classes of similar terms (equivalent to thesaurus classes) bycollecting in a common class all terms whose similarity coefficients SIMILAR
are sufficiently large [29,30]. Automatic clustering methods are covered in de­tail in Chapter 6. Many different methodologies are available. For example, thesingle-link process collects in a single class all items TERMk such that the simi­
larity between TERMk and at least one other member of the same class exceeds
some threshold. In the clique process the similarity between TERMk and allother members of the same class must exceed the stipulated threshold.
In the single-link or clique methods, the term classes are constructed fromthe beginning starting from the term assignments to the documents of a collec­
tion. A number of classification methods assume the prior existence of termclasses, and proceed by refining the initial state of the classification. Various
possibilities exist for defining such an initial term grouping:1 A given term class may be defined as the set of terms assigned to a par­ticular document, or document set; this generates a number of initial termclasses equal to the number of documents used as starting sets.
2 A term class might also be defined as the terms contained in the set of
relevant documents retrieved in response to certain user queries; here the num­
ber of initial term classes is equal to the number of starting user queries forwhich relevance information is available.
For each existing class, a centroid TERM-CENTROID = (ti> t2, . . . ,tm) can then be defined as the average vector for the term vectors of that class.
Table 3-11
Matrix________ Ti

Term-Term Similarity
Tz

T, / s(T, ,Ti) s(T „T 2)
T2 / s(T2,T,) s(T2,T2)

T,\sfT.,T,)s(T„T2)•••T,s(T, ,Tt)'• • • s(T2,Tt)s(T«,T.)

81

TEXT ANALYSIS AND AUTOMATIC INDEXING

That is, term tk of the centroid is defined as the average value of all the values of
1 m
TERMk in the individual documents of the class, or tk = — ^ hk f°r a class
1 i= lwhich has m term vectors. The term class refinement now consists in comput­
ing the similarity between each term vector TERMk and each class centroid
TERM-CENTROID for all existing classes. Assuming t term vectors and pclasses, the process requires the generation of t x p similarity coefficients
SIMILAR(TERMk,TERM-CENTROIDh) for k ranging from 1 to t, and h rang­
ing from 1 to p. Each term vector is now entered into the class for which thesimilarity to the TERM-CENTROID is largest. If this involves a switch of agiven term vector from one class to another, the centroids of those classes must
be recomputed. This process can be pursued until no further class changes
occur for the vectors, or until the number of class changes which occur after
processing all the term vectors is sufficiently small [31].
Methods also exist for constructing a hierarchical arrangement of termclasses, for example, by first building small classes consisting of a few terms
exhibiting substantial pairwise similarities, and then expanding these initialclasses into large groups. The new term groups subsume the initial classes byadding new terms whose similarity with the other terms already included in theclass is successively weaker. Alternatively, large heterogeneous classes can be
broken down into small more homogeneous entities by removing terms thathave relatively weak similarities with the remainder.
Since the number of terms in a system is normally much larger than thenumber of thesaurus classes, thesaurus construction methods such as the sin­
gle-link and clique methods which depend on the availability of all pairwise
term similarities may be expensive to implement. Methods based on initialcluster assignments of the terms require less computer time. The available
evidence indicates that thesauruses and automatically constructed term asso­
ciations are quite effective in improving the recall performance provided theitems entered into common classes exhibit high similarities. That is,
SIMILAR(TERMk,TERMh) should be large if TERMk and TERMh are enteredinto a common class. The high-frequency terms must be excluded from thethesaurus.

C Thesaurus Use

A thesaurus can be used to broaden the existing indexing vocabulary by replac­
ing the initial terms with the corresponding thesaurus class identifiers, or byadding the thesaurus class identifiers to the original terms. A simple term ex­
pansion process which requires only the availability of term associations, but
not of formal thesaurus classes, is illustrated in the example of Fig. 3-4. Assum­
ing one already has term similarity information such as that provided by a termterm similarity matrix (see Table 3-11), a threshold K is chosen. This is used totransform the original term-term matrix into a binary form by replacing eachCHAPTER 3

A

(f
I

8
C
D 'l
E \

A

B

c

D

E

1
^

1
1
0
1
0

0
0
1
0
1

0
1
0
1
1

0
0
1
1
1

0
0
0

(a)

Original
term

Associated
terms

A

B

B

A, D

C

E

D

B, E

E

C, D

(b)

/ A = 5>

CM
II
CD

q '=

C= 1

s

add B = 'A , E = %add nothing

o
II

o

ii

/

hi

D=1

II
CO

add E = 'A

C=1

\

ro

II

<

add B = 2
add A = 1, D = 1

E= 1 /(0
Figure 3-4 Sample process for utilization of term associations, (a) Sample binary term-term
similarity matrix for five terms (A through E). (b) Corresponding term associations, (c) Alter­
native associative indexing strategy. (Add associated terms with weight equal to one-half theoriginal.)

matrix element by 1 whenever the value in the term similarity matrix is greateror equal to K and by 0 when the value is less than K.
A sample binary term-term similarity matrix for five terms, labeled A
through E, is shown in Fig. 3-4a. The corresponding term association informa­tion is detailed in Fig. 3-4b. Given a particular term vector, such as that labeled
q in Fig. 3-4c, it is now possible to add the information about the associatedterms with a weighting factor (arbitrarily selected here as one-half of the origi­
nal weight in the illustration of Fig. 3-4c). It may be noted that in the example
one new term has been added to the original vector (E) since its weight is now
greater than 0. The weight of several other already existing terms (A, B, and D)
has also been altered [32-34].
Term associations and thesaurus classes can be displayed in a variety offormats to help the information system users in formulating the search requests
and familiarizing themselves with the vocabulary. One attractive format is

TEXT ANALYSIS AND AUTOMATIC INDEXING

83

based on a graphlike structure where the nodes represent the individual terms
and different kinds of lines denote different strengths of association [different
magnitudes of the similarity coefficient SIMILAR(TERMk,TERMh)] between
the terms. An excerpt from such a term association map is shown in Fig. 3-5[35].
One major disadvantage inherent in the use of any thesaurus is the neces­sity to maintain it. Two different maintenance problems arise. First, the thesau­
rus may require rebuilding as a result of user interaction with the system. For
instance, new queries may be submitted for which the current thesaurus is in­adequate, or new user populations and interests may appear which in turn re­quire new vocabulary terms. Second, a thesaurus maintenance system may beneeded to accommodate collection growth. When new documents are added toa collection, several updating strategies are possible:
1 The original thesaurus might be left unchanged and used for the ex­panded collection.
2 New terms derived from the added items might be placed into existing
thesaurus categories only.
3 New terms might be placed into separate new classes.
4 The thesaurus might be completely restructured by generating a termclassification from the updated vocabulary.
The fourth alternative may be very expensive. Hence it is necessary toconsider one of the other possibilities. The available evidence indicates thatsome performance loss is produced when a thesaurus constructed for an origi­
nal document environment is later used for an updated collection [36]. Unfortu-

Flgure 3-5 Term association map. (Different types of connecting lines denote different
strengths of associations between terms). (Adapted from reference 35.)

84

CHAPTER 3

nately, no experimental data are available leading to a clear-cut choice between
the second and third alternatives.
Before leaving the subject of automatically generated term associations, it
should be mentioned that recall-enhancing expansions of the vocabulary can begenerated by using identifiers that are not standard index terms. Specifically,
documents exhibiting similarities in bibliographic citation patterns— either ref­erences included in the reference lists attached to the documents or citations to
the various documents made by other documents— may also reveal similarities
in subject content [37,38]. This finding suggests that improved retrieval may beobtained by adding this citation information to documents and query vectors in
addition to the normal subject identifiers. Alternatively, the standard subject
terms could be replaced by the citation patterns.
One possibility is to lengthen the document vectors by including biblio­
graphic reference indicators to documents outside the collection. Search re­quests (query vectors) can then be similarly lengthened by adding identifiers of
relevant documents designated by the users. One system of that kind is
sketched out in Fig. 3-6. The available experimental evidence indicates that
substantially better retrieval results are obtainable with the augmented vectors
including citations than with standard vectors consisting of subject indicators
only. To utilize such a system, it is however necessary to store substantial cita­tion information for the collection, and to obtain information regarding the rele­vance of documents from the users of the system. The use of bibliographic cita­
tions is examined in more detail in Chapter 6.
D Construction of Term Phrases

The recall of a search may be improved by broadening the terms used in queryand document specifications and by adding new associated terms. On the otherx x x x x x x x x x x x x x xYNormal document terms

y y y y y y yBibliographic
citations(a)x x x x x x x xy y y y y v

Normal query
terms

Citations toitems known
as relevant(b)Figure 3-6 Expanded document and query vectors, (a) Expanded document vector. (Each x
represents a standard index term, each y a bibliographic reference.) (b) Expanded query
vector.

85

TEXT ANALYSIS AND AUTOMATIC INDEXING

hand, the precision may be improved by using specific terms or by using terms
in combination with each other. Terms of high specificity can be identified sim­ply by their concentration in a few documents of a collection, as described ear­lier. To generate combinations of terms (phrases) one uses two or more terms,
say TERMk and TERMh, with particular occurrence properties, and replaces
them by a phrase (PHRASEkh). For example, “computer” and “program” maybe replaced by “computer program” or “computer programming.” One ex­pects the frequency of occurrence of PHRASEkh in the document collection tobe smaller than that of TERMk or TERMh; furthermore, the phrase term will
have a more specific interpretation than the individual phrase components.
Various phrase-generation methods are possible, including the use of syn­tactic language analysis. These methods are used to identify phrases whose
components exhibit acceptable syntactic relationships. However, consider firsta phrase-generation process based on frequency considerations like those usedearlier to generate individual terms. The best phrases (word pairs, triples, etc.)
may include terms whose joint frequency of occurrence in the collection islarger than expected, given the frequencies of the individual terms. If PAIRFREQkh is the total pair frequency in the collection of TERMk and TERMh,
and TOTFREQk and TOTFREQh represent the collection frequencies of the in­dividual terms, then the cohesion of the term pair may be defined as
COHESIONkh = SIZE-FACTOR ■T 0 TFREQk • TOTFREQh^

SIZE-FACTOR represents a factor related to the size of the indexing vocabu­
lary. Phrases can now be chosen as term pairs with a sufficiently high cohesion
factor, subject to certain restrictions.
To utilize the preceding formula, it is necessary to choose an appropriate
context for determining when two or more terms co-occur. In principle, it ispossible to choose a wide context by declaring that two terms co-occur when­ever they are included in a common document. Better (higher-precision) results
may be obtainable by restricting the context to terms occurring in the same sen­tences of particular documents, or in the same sentences but with at most kwords occurring between components, or in the same sentences in adjacent
word positions, or finally in the same sentences in adjacent word positions andin the correct word order. When the context used to define a phrase is re­stricted, the phrase detection process becomes more costly because tests must
be made to ensure that the various restrictions are obeyed, and this in turn im­
plies that word location information must be stored specifying the positions of
the individual words in the sentences. Furthermore, when restrictions are im­
posed on the phrase formation process, the number of phrases generated for agiven item will of course decrease.
In addition to using context for phrase definition purposes, it may also be
important to invoke frequency restrictions on one or more of the componentsof each phrase. As has been stated earlier, the phrase formation process is de-

86

CHAPTER 3

signed to create specific content identifiers to enhance precision. When rareterms that are already specific in the documents are combined into phrases, theresulting phrase terms may turn out to be overspecific and the retrieval results
may deteriorate. Therefore, the phrase formation process should be restricted
to include only relatively broad, high-frequency components.
In summary, a reasonable phrase formation method based on statisticalword occurrence properties would define a phrase from word pairs with suffi­
ciently high cohesion factors. The phrase components must occur in the samesentences of the document, and at least one component in each phrase shouldhave a document frequency exceeding a stated threshold.
Statistical procedures for the generation of phrase identifiers are often as­
sumed to be unreliable because they lead to the identification of statisticallymeaningful but syntactically incorrect phrases. Examples show that the statisti­
cal methodology leads to unfortunate results, such as, for example, the confu­
sion of “ blind Venetian” and “Venetian blind.” This particular objection may
however not be serious, since among other things these phrases are unlikely tooccur in the same documents. Nevertheless, it is important to determine
whether more sophisticated linguistic tools might be used to control the auto­
matic indexing process.
The approaches using syntactic and/or semantic analysis features have not
met with much success. This is largely because of the technical inadequacy andthe excessive cost of the linguistic procedures. However, some advances havetaken place in these areas which are mentioned briefly in the next section of thischapter and are covered in more detail in Chapter 7.
It is possible now to propose an automatic indexing process based on sim­ple, well-understood procedures, capable of producing high-performance re­trieval results. The word stems occurring in document titles and abstracts are
isolated and term weights are computed using either inverse document frequen­cies [expression (2)] or term discrimination values [expression (9)]. Threeclasses of terms are then identified. Those in the middle-frequency ranges withpositive discrimination values, or frequency characteristics, are used as index
terms directly without further transformation. The broad high-frequency termswith negative discrimination values and excessive document frequencies are ei­ther discarded or incorporated into phrases with lower-frequency characteris­tics. Finally the narrow low-frequency terms with discrimination values close
to zero are broadened by inclusion into thesaurus categories. The thesaurus
class identifiers are then used as index terms for content representation [22,32].
The process is represented schematically in Fig. 3-7 where a document fre­quency axis is used to arrange the terms into three classes. The terms in thecenter are used unchanged; the broad terms are subjected to the phrase-forma­tion process, represented by a right-to-left transformation in Fig. 3-7; the nar­row, specific terms are incorporated into term thesaurus classes and are repre­
sented by the corresponding left-to-right transformation of Fig. 3-7.
The automatic process will produce a large number of content identifiersfor each item— typically a hundred terms or more may be automatically as-

87

TEXT ANALYSIS AND AUTOMATIC INDEXING

Thesaurus transformation

Phrase transformation
Worst terms

Poor terms

Good terms'/ / / / X

XXXXX/

Low-frequency
narrow te rm s discrimlnation
DISCVALUEk ~ 0Medium-fre­quency goodterm s-discrimination value
positivei5

Figure 3-7// / / X r

1 ^n

Document
frequency

High-frequency
broad te rm s discrimination
value negative

Term characterization in frequency spectrum.

signed compared with the half dozen terms used in a manual system. This fact
explains in part the high order of performance of automatic indexing systems.
Some laboratory evaluation data for automatic indexing strategies are pre­sented in the last section of this chapter.
E Automatic Sentence Extraction

Text processing methods based on a determination of term or sentence impor­tance have been used not only for indexing but also for automatic abstracting
purposes. Ideally, given a document represented as natural language text, one
would like to construct a coherent, well-written abstract that informs the read­ers of the contents of the original, or at least indicates whether the full version
may be of interest to the reader. In fact, most procedures carry out an extrac­
tion process in which the abstract is defined simply as a small set of sentences
pulled from the original, which are deemed to be important for purposes of con­tent representation.
The extracting methods used over the years all start with a calculation ofword and sentence significance, similar in spirit to the computation of the term
weights in automatic indexing [12,39,40]. Criteria for the selection of important
terms may be positional, involving, the place in the document where a particu­
lar term is located (for example, in the summary, title, etc.); they may be se­mantic, involving for example the relationship of this word or sentence to cer­tain other words; or they may be pragmatic, such as a system which would
consider proper names as highly significant. Furthermore, statistical weights
based on term frequency or term distribution characteristics may be used inaddition to the above criteria.
Given an indication of term significance, it is possible to define the impor­tance of a phrase as a function of the weight of the individual terms and of the
distance between the significant phrase components (the number of words be­
tween them). Thus if two terms have weights WEIGHT, and WEIGHTj, re­spectively, a phrase developed by combining the two terms might be assigned aweight equal to
PHRASE-WEIGHT

1
2DISTANCE(WEIGHTj • WEIGHTj)

(14)

88

CHAPTER 3

where DISTANCE equals the number of intervening words. By extension, asignificant sentence may be one which contains a large number of significant
word groups. A flowchart for a typical sentence extracting process is shown in
Fig. 3-8.
Because pure frequency characteristics are not likely to be reliable for ei­
ther indexing or extracting, a variety of additional criteria have been used ex­
perimentally in an effort to obtain more satisfactory extracts. In particular, theword and sentence contexts can be taken into account in determining the con­textual inference and syntactic coherence criteria [41], Contextual inferencemeans that the context within which a given word or phrase is placed in a docu­
ment is used in addition to other criteria in an effort to decide on sentence se-Document

Abstract

Figure 3-8 Typical sentence extracting system. (Adapted from reference 39.)TEXT ANALYSIS AND AUTOMATIC INDEXING

89

lection or rejection. Contextual inferences may be based on sentence or word
location or on the presence of so-called cue words. Thus, sentences occurring
under certain headings may be particularly important; the same may be true ofsentences occurring very early or very late in the paragraph structure. Similarly
sentences ending with a question mark are normally rejected, as are certain
sentence portions occurring between pairs of commas.
The cue method is based on the presence of positive or negative indicatorsof sentence value. Thus, the presence of phrases such as “our work,” “thispaper,” and “the present research” is assumed to introduce a statement thatshould be included in an abstract. Contrariwise, opinions and references to fig­
ures or tables that might be identified by “obvious,” “believe,” “fig. 1,” etc.,
lead to sentence rejection. To operate effectively, the cue method depends on
the availability of a dictionary containing the cue words together with indica­
tions of their semantic and/or syntactic value. Such a cue word dictionary may
be particularly valuable for sentence rejection, as opposed to selection, be­cause rejection can often be based on the presence of a small number of fre­quently occurring words, whereas selection may depend on longer lists of de­sirable words.
No matter how sophisticated the extraction process, a set of extracted sen­tences is not likely to constitute a coherent whole. Even if the extract in fact
consists of appropriate topic sentences, the flow of ideas from one sentence tothe next is likely to be interrupted because the discourse and reasoning leading
to, or following from, the selected sentences is probably absent.
Coherence criteria based on syntactic or semantic considerations can beused to mitigate to some extent the shortcomings inherent in an automatic ex­
tracting process. Thus words or phrases indicating intersentence reference canbe included in the cue dictionary (“these,” “they,” “it,” “ above,” “pre­sented earlier,” “ stated above,” etc.), and their presence in a given extract canbe used as a clue for inclusion in the abstract of the earlier sentences being re­ferred to. Similarly, if the same important terms occur in adjacent sentences, apresumption exists that the sentences are related, and both should probably be
included or excluded [41].
No matter what is done, a stylistically beautiful abstract is not likely to becreated automatically because the linguistic difficulties are simply too severe
for an effective automatic treatment. For example, the clarification of ambigu­
ous antecedents such as those of certain pronouns is notoriously difficult. Someof the linguistic problems are further discussed in the next section together withother theoretical questions.
The overall conclusion is that automatic abstracting is less developed thanautomatic indexing and less likely to be used on a production basis in the near
future. Abstracts must be placed in a readable natural language context andmust obey the normal stylistic constraints. Sets of index terms, on the other
hand, are not burdened by stylistic rules. Readable extracts are obtainable
without excessive difficulties, but perfection cannot be expected within theforeseeable future.

90

CHAPTER 3

6 SOME THEORETICAL APPROACHES*AThe Use of Linguistic Methods

It has been mentioned that the absence of syntactic recognition features may
cause problems in the construction of indexing phrases capable of reflecting
correctly document or query content. Two phrase construction problems, inparticular, may be solved by using linguistic tools: first, the coordination ofterms in accordance with the available context, and second, the assignment ofroles to the phrase components. Given an indexing description such as “hard­
ness, density, titanium, water,” it is not clear a priori which qualification (hard­
ness or density) applies to which material (titanium or water); and in “blind,
Venetian,” blind could presumably function as a qualifying adjective, or alter­
natively as the governing noun.
The approaches using linguistic methods in information retrieval are reallyof two kinds: on the one hand, it is possible to use simple methodologies withlimited aims such as removing the ambiguity from some noun phrase identi­
fiers; on the other hand, more complex linguistic analysis systems can be uti­
lized but the context in which these systems operate must be limited. In thepresent discussion, it is possible only to give a very brief introduction; moredetails are included in Chapter 7 of this volume. A variety of other sources exist
describing the use of linguistic methods in retrieval [42-44].
Consider the use of simple syntactic aids for the construction of indexingphrases. Normally, a context-free phrase structure grammar is used to obtainfor each document, or query sentence, a parse tree which shows the syntactic
structure of the sentence. A context-free grammar decomposes a sentence into
nested and juxtaposed sentence portions, as in the example of Fig. 3-9, where“the man” and “the ball” are identified as noun phrases and “hit the ball” as averb phrase. Simple phrase structure grammars can be used to recognize many
types of noun phrases and prepositional phrases that might constitute useful
document identifiers.
s

NP

VP

Det

N

V

the

man

hit

NP

Det

N

the

ball

Figure 3-9 Sample context-free phrase
structure analysis (S = sentence; NP =noun phrase; VP = verb phrase; Det = ;determiner; N = noun; V = verb).

TEXT ANALYSIS AND AUTOMATIC INDEXING

91

Unfortunately, a simplified language analysis system based on context-freegrammars exhibits a number of disadvantages. First of all, some sentences
whose structure is not of the basic phrase structure type cannot be analyzed by
the phrase structure model. Second, a unique analysis pattern is not obtainable
for many sentences, but multiple parse trees can be generated— all ostensibly
correct according to the grammar in use— without any information that would
identify which of those analyses may be semantically acceptable. The notori­
ous sentence “time flies like an arrow” may serve to illustrate a case where atleast four reasonable analyses are generated by a typical context-free analysis
system [45]:
1 Time passes as quickly as an arrow flies.
2 You should time the flies as quickly as an arrow times the flies.
3 You should time the flies which are similar to an arrow.
4 There exists a species of flies, called “time flies,” which are fond of anarrow.
Most important of all, the phrase structure model is not sufficiently rich to
make it possible to recognize semantic relationships between sentence compo­
nents that may not be reflected by some sort of physical juxtaposition of thecomponents in the sentence. Thus a requirement that the phrase components
be grammatically related according to the phrase structure model— for exam­
ple, that the components appear in the same “ subtree” within the parse tree—
may actually amount to an overspecification, producing an underassignment ofphrases for the respective documents. Consider as an example the sentence“people in need of information require effective retrieval systems.” In thissample sentence the terms “information” and “retrieval” are not related in theusual noun phrase sense, where “information” is grammatically dependent andmodifies the governing element “retrieval.” Hence if the indexing rule con­sisted in requiring a noun phrase or prepositional phrase relationship between
phrase components, the phrase “information retrieval” would not be assigned
to a document containing this sentence. On the other hand, a frequency-based
phrase assignment method of the type covered earlier would correctly generate
the phrase “information retrieval.”
Various attempts have been made to use simple syntactic analysis systems
in actual information retrieval situations. While linguistic methods may even­tually prove essential in automatic indexing, the available evidence indicatesthat the simplified syntactic analysis systems do not yet provide the answer.
The frequency-based phrase-generation methods are simpler to implement andare currently more effective [46-50].
At least two possibilities are apparent for helping with the syntactic anal­
ysis problems. On the one hand, certain computer-aided indexing systems havebeen proposed where the indexers obtain access to a computer console during
the indexing process. In such circumstances, the human operators can intersvene at appropriate times during the indexing process. This can be done, for

92

CHAPTER 3

example, by choosing the correct analysis output from among a number ofparse trees or by identifying “good” phrases from among a large selection ofpotential phrases produced by statistical or syntactic procedures [51].
Alternatively, sophisticated linguistic methods are available for carryingout the text analysis. Specifically, syntactic models can be used in which con­textual constraints exercised at each level of the analysis are used to restrict the
number of syntactic parses [52,53], These constraints, or restrictions, may besubject matter-specific, or they may depend on the inclusion of semantic datasuch as “case frames” which identify the (semantic) role of the sentence com­ponents.
A conventional parse tree represents the “ surface” structure of a sen­tence, and the results of an initial parsing operation must be subjected to cer­tain transformations before the underlying “deep” (that is, semantic) structure
is obtained. The conventional (surface) parse for “John is easy to please” rec­ognizes “John” as the subject of the sentence and “easy to please” as the com­plement. The deep structure, on the other hand, reflects the meaning of “It iseasy for someone (unmentioned) to please John.” In that case “John” appears
properly as the complement.
Unfortunately the construction of transformational grammars capable ofperforming the required transformation operations has proved to be too diffi­
cult for practical purposes. Indeed, in conventional situations, dozens of possi­
ble transformations could in principle be applied at each point to a given sur­face structure, and no guidance is available for choosing the correct pattern oftransformations. Here again substantial progress is evident in recent years,
based on the use of restricted areas of discourse and of sufficient context toproduce for each sentence only a small number of surface structures, eachbeing subject to only a small number of possible transformations.
It now appears that when the input material is restricted to certain special­ized topic areas, limited vocabularies, and limited syntactic patterns, canonicalrepresentations are obtainable from natural language input. The canonical rep­resentations consist of standard forms in which each phrase in the text is as­
signed a well-defined role, reflecting the full complexity of the syntactic andsemantic structures of the text. The canonical forms for the documents can becompared with standard query forms to derive answers to incoming user
queries. For the most part, linguistic procedures are incorporated into special­ized question-answering systems where direct responses are given in answer tosearch requests, as opposed to answers consisting of document references thatmust be consulted before direct answers can be obtained [54-58],
In at least two cases, the natural language text of full-length medical rec­ords, such as radiology reports and pathology diagnostic reports, has beentransformed automatically into standard tabular formats where each text com­ponent is identified as to function and meaning. Such tabular formats can thenbe directly transformed into structured data bases used to generate answers tosearch requests [59-60]. Such methods may eventually be used in unrestrictedautomatic indexing environments; however, the linguistic procedures must

TEXT ANALYSIS AND AUTOMATIC INDEXING

93

then possess substantial sophistication, and their application will probably bevery costly. It remains to be seen whether this route will actually be pursued in
the future.

*B

Fragment Encoding

Indexing methods, based on probabilistic considerations, like the previously
discussed linguistic methods, offer great promise, although really practicalmethods applicable on a wide scale have not so far been generated. One line ofeffort, somewhat tangential to the main developments, is based on the pre­viously mentioned information theoretic considerations relating to the unevennature of the occurrence frequencies of the standard indexing products. Not
only is the number of index terms needed to represent the content of most doc­
ument collections extremely large— even small collections of a few hundred
documents may require several thousand different terms— but many of theseterms occur very rarely. Hence their utilization, storage, and maintenance isquite inefficient.
In these circumstances, it is not surprising that the suggestion has been
made to replace the normal index words or terms by a small number of artificial
entities exhibiting approximately equal occurrence frequencies in the docu­
ments of a collection. Specifically, variable length character strings known as“fragments” can be used for indexing instead of full-length words. Normallyfragments represent substrings of complete words, or terms. A redundant en­
coding is often used so that certain characters in the original terms are repeatedin several different fragments. For search purposes, a number of different frag­ments must then be used in a given document or query to replace each originalterm [61-66].
A variety of encoding procedures can be used to construct a fragment set
consisting of more or less equally occurring elements. Consider the following
procedure [66]:

1 A string of n characters is created starting from each character of theoriginal text sample; n must be chosen at least as large as the longest fragment
expected to occur in the final fragment set.
2 The character strings are sorted and the frequency of each string is de­termined.
3 The frequency of each distinct character string is then compared with agiven threshold frequency (the size of the final fragment set is inversely related
to the magnitude of the threshold).
4 Any string whose occurrence frequency exceeds the threshold is se­lected for inclusion in the final fragment set, and eliminated from the set of
strings still under consideration.
5 Strings whose frequency does not exceed the threshold frequency areshortened by truncation of the rightmost character, the equivalent shortened
strings being merged; new frequencies are computed for the shortened strings.

94

CHAPTER 3

6 Any shortened character string whose frequency now exceeds thethreshold is selected for inclusion in the final fragment set, and the procedure isrepeated until single character strings are reached.
7 The final fragment set also includes all single character strings.
The original set of index terms must now be mapped into a final fragmentset. Various methods suggest themselves such as, for example, the “longest
match” algorithm which chooses the longest fragment that matches the begin­ning (left-hand end) of each term. The longest fragments matching the left endof the remainder of the various words are then successively chosen until thewhole text is covered [67]. For efficiency in the final encoding, it is convenient
to operate with a total number of fragments equal approximately to a power of
2. Thus, each of 256 fragments can conveniently be represented by an 8-bit
code. The fragment encoding for some typical terms is illustrated in Table 3-12.
A thesaurus, or inverted index, giving access to a fragment encoded docu­
ment set is managed more easily than a standard index, because a dictionary ofa few hundred fragments can replace the normal list of many thousands of con­ventional index terms. However, a “false drop” problem must be contended
with in retrieval because certain sets of fragments included in a search request
may correspond to several different full index terms. Thus the two fragments
RAC and ER can correspond to RAC/ER and also to T/ER/RAC/E, causing
documents on terraces to be retrieved when racers are wanted. The seriousnessof this problem depends on the actual keyword set used for a particular collec­tion.
A great many automatic text compression methods other than fragment en­
coding are in use, designed to take advantage of the unequal occurrence proba­
bilities of individual characters and words, and of the redundancies built into
the natural language [68]. A description of these methods is beyond the scopeof the present discussion.
**C

Probabilistic Information Retrieval

Probability theory has also been used as a principal means for modeling the re­trieval process in mathematical terms. In conventional retrieval situations, aTable 3-12

Sample Fragment Encoding

Original term

Fragments

AMINO ACIDBETA HYDROXYLASEBETA-HYDROXY LASEDICHLOR ACETATHALOGENCHLOROFORMSULFONAMIDIONISATIONAMINO, ACIDHYDRO, BETA, OXY, YLA, ASE
BETA-, -HYDR, LASE, ROX, XY
CHLOR, ACETA, DIC, TAT
HALO, OGEN
CHLOR, FORM, RO, OF
AMID, SUL, FON, LF, NA
ATION, IONI, ISA

Adapted from reference 61.

TEXT ANALYSIS AND AUTOMATIC INDEXING

95

document is retrieved in response to a query whenever the keyword set at­
tached to the document appears similar in some sense to the query keywords.
In this case the document is assumed to be relevant to the corresponding query.
More explicitly, since relevance of a document with respect to a query is a mat­ter of degree, one postulates that when the document and query vectors are
sufficiently similar, the corresponding probability of relevance is large enoughto make it reasonable to retrieve the document in answer to the query.
More formally, the retrieval problem can be expressed as a decisiontheoretic process using three basic parameters as follows: P(Rel), the probabil­
ity of relevance of a record; LOSSj, a loss parameter associated with the re­trieval of a nonrelevant or extraneous record; and LOSS,, a loss associatedwith the nonretrieval of a relevant record. A loss minimizing rule can be de­vised by noting that the retrieval of an extraneous item causes a loss of [1 P(Rel)] • LOSSi, whereas the rejection of a relevant item produces a loss ofP(Rel) • LO SS,. In these circumstances the total loss is minimized by opting
for retrieval of an item wheneverP(Rel) • LOSS, > [1 - P(Rel)] • LOSSx(15)

Equivalently a discriminant function DISC may be defined, and an item may be
retrieved whenever DISC > 0 [69-71], where

DISC =

P(Rel)
1 - P(Rel)

LOSS!
LOSS,

(16)

A retrieval rule of the kind produced by equation (16) is not useful in prac­
tice because the relevance properties of the individual records cannot be di­vorced from other system parameters. Thus, it becomes necessary to relate thediscriminant function to other design parameters, and most notably to the in­dexing process. This can be done by defining two conditional probability pa­
rameters:
P(TERMi | Rel) = the probability of TERMj occurring in a document giventhat the document is relevant to a given queryandP(TERMi | Notrel) = the probability of TERMj occurring given that the
document is not relevant to the query [71,72].
Using a formula developed by Bayes, a retrieval function P(Rel|Doc) can be

96

CHAPTER 3

obtained, representing the probability of relevance given a document Doc =(TERMj, TERM2, . . . , TERMt). In particular,
P(Rel|Doc) =P(Doc|Rel) P(Rel)
P(Doc)and(17)
P(Notrel|Doc) =where P(Rel) and P(Notrel) are the a priori probabilities of relevance andnonrelevance of an item, andP(Doc) = P(Doc | Rel) • P(Rel) + P(Doc | Notrel) • P(Notrel)(18)

If one assumes that the two loss parameters are equal to 1 (LOSSi =LOSS2 = 1), then the obvious retrieval rule calls for retrieval wheneverP(Rel | Doc) s P(Notrel | Doc)(19)or whenever the discriminant function DISC > 1 whereP(Rel|Doc)
P(Doc|Rel) • P(Rel)
DISC - p(Notrel|Doc) - p(Doc|Notrel) • P(Notrel)(20)

The foregoing rule relates the retrieval of the records to the occurrence
characteristics of the terms in both the relevant and the nonrelevant items. For
practical application, it is necessary to specify how the probabilities
P(Doc | Rel) and P(Doc | Notrel) are to be determined. The problem is twofold inthat one must first determine the occurrence characteristics for each term sepa­
rately, and next the interactions between terms. In most abstract retrieval
models the second problem is settled either by considering single-term queries
only, where term interactions are of no consequence [71,73], or more drasti­cally by disregarding term interactions altogether, and assuming that terms
occur independently of each other in the records of the collection.1 The firstquestion relating to the individual term occurrences can be handled either byusing a probability distribution, such as the Poisson distribution, to character­ize the occurrence characteristics of the terms, or by studying the actual occur­
rences of the terms in a typical sample record collection and applying the find­ings to other collections at large. (The Poisson distribution is an approximation
to the binomial distribution which measures the probability of success in a se­quence of success-failure experiments when the number of experiments is large
and the probability of success of a given event is small. In the case at hand, thei97TEXT ANALYSIS AND AUTOMATIC INDEXING

texts under consideration are assumed to be long, the word occurrences are
randomly placed in the text, and the probability of occurrence of a particularword is assumed to be small.)Consider the Case where term independence is assumed and where the oc­
currence characteristics are obtained from a sample collection. In such circum­
stances one can write
P(Doc|Rel) = PCTERMjlRel) • P(TERM2|Rel). . . P(TERMt | Rel)

(21)

It remains to determine the probabilities of each term in both the relevant
and the nonrelevant items in a collection. Consider a sample collection of N
records and assume that R records out of N are relevant to a given query Q and
N - R items are nonrelevant. The term occurrence characteristics for a spe­cific TERMj are listed in Table 3-13.
If one assumes,that the term occurrences in the sample record collection of
Table 3-13 are typical of the term occurrences at large, one can postulate that
P(TERMi|Rel) and P(TERMi | Notrel) representing the probabilities that agiven TERMi occurs in a document, given that the document is respectively
relevant and nonrelevant, is equal toP(TERMj|Rel) = ^
(22)

and
P(TERMi|Notrel) = ^where rt represents the number of relevant documents in which TERM, occurs,and (nj - rj) is the number of nonrelevant documents with TERMj.
By inserting the expressions (21) and (22) into expression (20) for the disTable 3-13

Occurrence Table for One Term(r R e le v a n t D o c u m e n ts C o n ta in T e rm ; n -r Non­

re le v a n t D o c u m e n ts C o n ta in T e rm ; R R e le va n t
D o c u m e n ts E x is t in A ll w ith R e sp e ct to S o m e
Q u e ry Q in a C o lle c tio n o f N D o c u m e n ts )TermpresentTerm
absentRelevant

Nonrelevant

r

n - r

n

R- r

N - n - (R - r)

N- n

R

N- R

N

98

CHAPTER 3

criminant function, it is not hard to show that for each query term that matches
a given document term, an appropriate term weight is given by

TERMREL =r/(R - r)(n - r)/[N - n - (R - r)](23)

where r and n - r represent the number of relevant and nonrelevant documents
in which the given term occurs. The expression TERMREL, known as the term
relevance, represents the ratio of the proportion of relevant to the proportionof nonrelevant items in which the term occurs. TERMREL is a term weighting
function for the term akin to other term weighting functions (inverse document
frequency, term signal, and term discrimination value) previously introduced.
It differs from these earlier weighting systems in that the relevant documents toa given query are used to compute TERMREL. Relevance information of par­ticular documents with respect to particular queries may be obtainable in modern
on-line information retrieval systems where users have direct access to thesystem during the course of the retrieval operations [74-76]. The term relevanceweights may be most profitably incorporated into these on-line retrieval environ­ments [77-79].
It can be shown that if the terms occur independently of each other, andbinary (as opposed to weighted) terms are used to represent the documents,
then the optimum query will have terms weighted according to the term rele­vance factor TERMREL. Furthermore, given a document D = (xx, x2, . . . ,xt) and a query Q = (ql5 q2, . . . , qt) the best matching function SIMIt
LAR(D,Q) between them is the inner productxk qk previously introduced
k=l

in expression (11).
Some of the restrictions of the decision-theory model can be removed, forexample, by introducing term dependencies [72]. Of more immediate interest
may be the utilization of the probabilistic model for automatic indexing pur­poses. For expository purposes, the indexing problem may be considered to bea classification problem where m subject classes are given, each described by aclass term vector. The indexing (classification) task then consists in assigningeach document to the class whose subject area most nearly reflects the docu­
ment description. In indexing terms, the assignment of a document to a subject
class may simply imply the use of the corresponding class identifiers to repre­
sent individual document content.
In the earlier development, the documents were characterized by the term
occurrence probabilities in two classes, the class of relevant and nonrelevant
documents, respectively, with respect to a given query. An alternative (classifi­
cation) context represents a generalization of that used earlier, in that m classes
Cj, C2, . . . , Cm may be assumed to exist instead of only two. The decision
rule now specifies that a document D = (xx, x2, . . . , xt) is assigned to theclass for which its probability of occurrence is the largest.

TEXT ANALYSIS AND AUTOMATIC INDEXING99

A discriminant function can be constructed as before in terms of the proba­
bilities of occurrence of the individual terms in the various classes. Eventually,each document is assigned to that class which exhibits the largest sum of all the
probability values of the various document terms [80-82].
In the previous probabilistic models it was assumed that occurrence fre­quencies were available to characterize the term occurrences in the various
document classes. Unfortunately, in practice, these frequencies are often diffi­
cult to generate. An alternative approach may then serve in which a document
collection is broken down into homogeneous document classes such that theoccurrence properties of the index terms may be characterized by an overall
probability distribution with known parameters in each individual documentclass. In particular, if the terms are assumed to be randomly scattered acrossthe documents within each of the homogeneous classes, the previously men­tioned Poisson distribution accurately reflects the term occurrence characteris­
tics.
This fact has been used in many of the early automatic indexing models by
noting that the common function words which do not indicate document con­tent exhibit the same occurrence properties in all the documents of a collection,and thus are characterized by a single Poisson distribution. The specialty
words, on the other hand, that are reflective of document content tend to beclustered in a few documents and a single Poisson formula cannot be used torepresent their properties across the documents of a collection. Instead the col­lection is broken down into subcollections, and the assumption is made that adifferent Poisson distribution applies to a given term in each subclass with dif­ferent parameters. Several attempts have been made to predict the usefulness
of index terms based on an analysis of the term occurrence characteristics inthe documents of a collection, followed by a comparison with the Poisson model[71,73,83-86],
7 AUTOMATIC INDEXING EXPERIMENTS

Many observers consider the use of automatic indexing and text processing
methods to be acceptable only if substantial advantages can be demonstrated
for the automatic system compared with the conventional manual situation, in
the form of lower costs, greater speed of operations, or more extensive collec­
tion coverage. Unfortunately, it is a fact that comparative tests of indexing ef­
fectiveness (and efficiency) must normally be carried out under controlled con­ditions, using test collections of relatively small size with small sets of test
queries. Under these conditions it is not difficult to show that the retrieval ef­
fectiveness of many systems operating with automatically assigned content in­
dicators is at least equivalent to that obtaining for manually operated systems.
However, it is hazardous to extrapolate test results obtained in a laboratoryenvironment to operational situations possibly involving hundreds of thou­sands of items. This is particularly true with respect to an evaluation of operat­
ing efficiency, as opposed to effectiveness, because the cost or speed of opera-

100

CHAPTER 3

tions in the laboratory reveals little about costs or speeds in practicalenvironments.
A detailed recital of evaluation results in automatic indexing is unlikely toprove conclusive; however, a brief summary of some of the early evaluation
studies may provide a useful demonstration of the relative effectiveness of vari­
ous automatic procedures, and an indication of possible future trends. Several
different evaluation approaches are possible [87]:
1 Title word studies where an attempt is made to compare index entries
derived from document titles with automatically generated terms
2 Studies involving the comparison of automatically generated and man­ually assigned term or class indicators
3 Retrieval experiments in which the manual or automatic methodologies
are actually used in a retrieval environment and an attempt is made to assess
the effectiveness in terms of recall and precision
The title word studies conducted for a variety of subject areas such as
medicine [88], chemistry [89], or law [90] indicate that for a large proportion of
the documents, varying from 60 to 80 percent, some portions of the title areusable directly for indexing purposes. Furthermore, the number of titles which
are totally useless in automatic indexing appears to be small in most subject
areas— of the order of 10 percent.
These results are reinforced by studies based on a direct comparison be­
tween automatically generated sets of terms and their manual equivalents. The
coefficient of similarity between manual and automatic index sets may then be
taken simply as the proportion of common term assignments (that is, terms
present in both the manual and automatic sets) to distinct term assignments thatisQ

A + M - C

where Q is the similarity coefficient between indexing sets, A is the number ofdistinct terms derived automatically, M is the number of distinct manually as­
signed terms, and C is the number of common assignments. Various tests ofthis general type have been performed, and the consensus is that about 60 per­cent agreement between manually and automatically produced term sets is ob­
tainable [91,92],
While retrieval results based on a direct comparison of content identifiers
may be interesting, they prove relatively little in the end, since the terms them­selves are not the issue, but rather the retrieval performance obtainable withthem. For this reason, the evaluation of retrieval results produced by a variety
of different indexing methodologies has received considerable attention overthe last few years. The first comparison of a conventional, manual indexing sys­
tem with an automatic text processing system appears to be the one performed

TEXT ANALYSIS AND AUTOMATIC INDEXING

101

by Swanson in the late 1950s [93]. In that instance the manual utilization of aconventional subject-heading index was compared with a system based onwords and phrases automatically extracted from the document texts; in addi­tion, a thesaurus was also used to modify the words extracted from the docu­
ments. The test results indicate that the average retrieval performance over 50
queries and 100 documents was superior for the system based on automatic text
analysis. It may be worthwhile to quote from the conclusions of this early test[93]:
T he apparent superiority o f machine-retrieval techniques over conventional re­trieval . . . w ill becom e greater with subsequent experim entation as retrieval aids
for tex t searching are im proved . . . (because) no clear procedure is in evidence
w hich will guarantee im provem ent o f the conventional (manual) system . . . . Thus
even though m achines m ay never enjoy more than a partial su ccess in library index­
ing . . . people appear ev en le ss promising.

These original test results were later confirmed by additional experiments
in which, for the first time, natural language queries were used instead of man­ually constructed query formulations [94], Furthermore, an evaluation method­
ology very similar to that used to the present day was utilized, in the sense that
documents were retrieved in decreasing order of similarity to the queries, thesimilarity score for an article being computed by summing the weights of thosewords in the article which coincided with the query words. With such a ranked
list of retrieved documents, it is possible to compute recall and precision values
following the retrieval of each document (or each nth document) producing asequence of recall-precision pairs which can be plotted as a curve giving recall
against precision, or listed in a table containing average precision values at cer­tain fixed recall points.
Many additional experiments have been performed over the years, de­signed to evaluate a variety of automatic indexing theories, and in some cases
attempts were made to measure large numbers of index language variations [24,95-97], The Cranfield and SMART studies are perhaps among the best known.
The Cranfield II experiments were designed to measure many linguistic “de­vices” that are potentially useful for the representation of document content,
including synonym dictionaries, hierarchical subject classifications, phrase as­signment methods, and others [96,97]. While all indexing tasks were performed
manually by trained indexers, the indexing rules were carefully specified andcarried out in such a way as to simulate a computer assignment. A collection of
1,400 documents in aerodynamics was used with 279 search requests preparedby aerodynamicists. Three main indexing languages were utilized:
1 The single terms were content words chosen from document texts.
Controlled terms were single terms modified by consulting a manuallyconstructed subject authority list (thesaurus).
3 Simple concepts were phrases obtained by concatenation of single
terms.
2

102

CHAPTER 3'

Each of these basic languages was used with a variety of recall-improving pro­cedures (synonym dictionaries, concept associations, term hierarchies, etc.)
and precision-improving methods (assignment of weights, specification of term
relations).
Somewhat unexpectedly, the retrieval results obtained were apparently
counterintuitive, in the sense that the simple uncontrolled indexing language
involving single terms produced the best retrieval performance, while the con­trolled vocabulary and the phrases (simple concepts) furnished increasingly
worse results. To quote from Cleverdon [96]:The seemingly inexplicable conclusion . . . is that the single term index languages
are superior to any other type . . . the single terms appear to have been near thecorrect level of specificity; only to the relatively small extent of grouping true syn­onyms (using a synonym dictionary) and word forms (using a suffixing process togenerate word stems) could any improvement in performance be obtained. . . .
Of the controlled term index languages that using only the basic terms gave thebest performance; as narrower, broader or related terms are brought in . . . theperformance decreases. . . .
The simple concept (phrase) index languages were overspecific. . . .
In other words, the conclusion is that, on the average, the simplest index­
ing procedures which identify a given document or query by a set of terms,
weighted or unweighted, obtained from document or query texts are also themost effective. Only the use of synonym dictionaries exhibiting groups of re­lated terms could produce improvements in retrieval performance.
Such a result, if verified in other test environments, is of interest for two
reasons: first, the single term indexing process is easier to implement automati­
cally than the more sophisticated, seemingly less effective alternatives; and,second, if the single terms could be shown to operate at the correct level of
specificity for the average user query, an automatic indexing process might be­come competitive in both cost and effectiveness with a manual indexing
method.
The verification of the Cranfield results was provided by the extensive
evaluation work carried out for some years with the SMART system [98,99].
The experimental, automatic SMART document retrieval system uses a variety
of automatic text analysis and indexing methods, including synonym diction­aries, hierarchical term arrangements, statistical and syntactic phrase-genera­tion methods, and the like, to generate sets of weighted content identifiers use­
ful for the retrieval process. Information is retrieved by using a composite vec­
tor matching method producing for each query-document pair a coefficient ofsimilarity. A ranking is obtained for the stored items in decreasing order of thequery-document similarity, and a variable number of documents can be re­trieved as required by the individual requestors. The output is evaluated interms of recall and precision by processing the same search requests against thesame document collections several times, while making selected changes in theindexing procedures between runs as previously explained.

TEXT ANALYSIS AND AUTOMATIC INDEXING103

In one extensive set of tests, document collections were used in the fields
of computer engineering, aerodynamics, and documentation. A few quotations
from the published results may suffice for present purposes [24,87]:
The order o f merit is generally the sam e for all three collection s. . . .
T he u se o f unw eighted term s (with w eights restricted to 1 for terms that arepresent, and 0 for th ose that are absent) is generally le ss effective than the u se o f
w eighted term s. . . .
The u se o f docum ent titles alone is alw ays less effective for con ten t analysis
purposes than the u se o f full docum ent abstracts. . . .
T he thesaurus p ro cess involving synonym recognition perform s more effec­
tively than the word stem extraction m ethod w here synonym s and other word rela­tions are not recognized. . . .
T he thesaurus and statistical phrase m ethods (where phrases are form ed by
Statistical association o f term s) are substantially equivalent in overall system per­form ance; other dictionaries, including term hierarchies and syntactic phrases, per­form less w ell.

Thus, the principal conclusions reached by the Cranfield project are borneout by the SMART studies: that computer language devices are not substan­tially superior to single terms used as indexing devices, and that sophisticatedanalysis tools are less effective than had been expected. These conclusions areperhaps not surprising, given the fact that a retrieval system is designed toserve a large, sometimes heterogeneous user population. Since users may havedifferent needs and aims, the search requests range from survey or tutorial typequestions to very detailed analytical queries. In these circumstances, an exces­
sively specific analysis may be too specialized for most users.
Furthermore, the evaluation process is based on a performance criterion
averaged over many search requests. This implies that analysis methods whose
overall performance is moderately successful are preferred over possibly moresophisticated procedures which may operate excellently for certain queries but
far less well for others. In practice, it may turn out that for each query type, aspecific sophisticated analysis will be optimal, whereas for the average query
the simpler type of indexing is best.
It remains to apply the evaluation methodology to a comparison of auto­
matic indexing with conventional, manual indexing methods currently used
under operational conditions, and to the more advanced, automatic indexing
theories based on the term discrimination values and frequency transforma­tions described earlier in this chapter. To answer the first question, certain au­
tomatic indexing methods incorporated into the SMART system were utilized
together with the exhaustive evaluation work of the operating MEDLARS re­trieval system performed at the National Library of Medicine. The MEDLARS
system is based on a manual analysis of documents and incoming search re­quests, and on an exhaustive search of a stored collection of several hundred
thousand documents. In the conventional MEDLARS environment, an average
recall of 0.577 and an average precision of 0.504 is reported for 300 test queries

104

CHAPTER 3

processed against the complete MEDLARS collection, implying that an aver­age search manages to retrieve almost 60 percent of what is wanted, while only
half the retrieved items are not relevant [100],
These results were compared with the automatic indexing methods by ap­
plying both types of procedures to a subcollection from the full MEDLARS en­
vironment and a subset of the original queries used in the original MEDLARS
evaluation. The subcollection was constructed by using for each query one ormore documents known to be relevant to the user’s needs as entry points to the
Science Citation Index (SCI). For each query, 15 new documents were thenobtained from the SCI such that each new item cited the original known rele­vant document. Obviously, such a process produces a set of potentially rele­vant documents, independent of either of the retrieval systems.
The main retrieval results are summarized in Table 3-14 [101,102], It canbe seen that a deficiency of about 15 percent for the automatic indexing method
using word stem extraction techniques (from document abstracts) is reduced toa deficiency of only about 5 percent using the previously mentioned discrimina­tion values to delete negative discriminators. When a thesaurus is used to rec­ognize synonymous and related terms, a small advantage is produced for the
automatic indexing process. Other procedures, related to search strategy rather
than to indexing, eventually generate an advantage for the automatic system ofabout 30 percent in recall and precision [102].
It should be noted that the original MEDLARS searches retrieved a total
Table 3-14. Comparison of MEDLARS Controlled Indexing with SMART
Automatic Indexing(Cutoff in SMART Query-Document Similarity Measure Set to Retrieve a Totalof 127 Documents)

Analysis method
MEDLARS(controlledindexing)
SMART(word stems withfrequency
weights)
SMART(word stems withdiscrim ination
value weighting)
SMART(thesaurus)

Cutoffdetermining
numberretrieved
Booleansearch(exactmatch)
Querydocum ent
sim ilarity
0.2201
Query- ,docum ent
sim ilarity
0.2109Querydocum ent
sim ilarity
0.3720RecallPercent
difference
from
MEDLARS

0.3117

Precision

Percent
difference
from
MEDLARS0.61100.2622-1 6

0.4901-1 9

0.2872-80.5879-40.3223+40.61060

105TEXT ANALYSIS AND AUTOMATIC INDEXINGof only 127 documents over the 29 test queries, whereas the total number of
items determined to be relevant to the query set was equal to 284 documents.
Since the threshold in the query-document similarity coefficient used for
SMART must be set to retrieve exactly as many documents as MEDLARS had
obtained earlier (namely 127), the maximum recall obtainable by either system
is 127/284 = 0.4471, obtained when all retrieved items are found to be relevant.
This recall ceiling, imposed by the test conditions, accounts for the low recall
values obtained by both systems. The precision ceiling (maximum precision ob­
tainable) is of course always equal to. 1. One may interpret the results of theforegoing tests as showing that both conventional and automatic indexing
methods produce equally good (or equally poor) retrieval results.
The question now. arises to what extent the more advanced automatic in­dexing theories can produce improvements in the performance over the simple
frequency-based indexing methods. Consider first the performance of the morerefined term weighting system [18-22]. Table 3-15 contains average precision
figures for 10 recall points, ranging from 0.1 to 1.0, averaged over 24 user
queries for a collection of 425 documents from the world affairs section of Timemagazine. As previously explained, a recall-precision table may be obtained bychoosing various retrieval thresholds, that is, by retrieving a variable number

RecallBinaryweights
BINik

Term frequency
weights
FREQikBinary with
IDF weights
BINik/DOCFREQk

Term frequency
with IDF
FREQik/DOCFREQk

0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0

0.82570.75550.67540.62240.57080.52990.46180.40870.29590.28540.74960.70710.67100.6452d.63510.5866
0.54130.50040.38650.37210.80850.7741
0.7114
0.63280.62180.56730.51240.43840.33740.31880.85360.79010.75680.75030.67830.62430.58230.56430.4426
0.4170(a)

A. Binary weights BINik

A. Binary with IDF

VS.

VS.

VS.

B. Term frequency weights
FREQikB. Term frequency with IDF

B. Term frequency with IDF
FREQik/DOCFREQk

t-testt-testt-test0.00000.0000Wilcoxon

0.0000B better than A

B better than A

B better than A
Wilcoxon

0.0000A. Term frequency FREQik

0.0000Wilcoxon

0.0000(b)

Table 3-15 Com parison of binary term w eighting with inverse docum ent frequency (IDF)
weights (time collection, 425 documents, 24 search requests), (a) Com parison of binary andterm frequency w eigh ting with and w ith ou t inverse docum ent frequency norm alization, (b)Statistical significance ou tput fo r the results of Table 3-15a.

106

CHAPTER 3

of documents in decreasing order of the query-document similarity, and com­puting a recall and a precision value for each retrieval threshold. The various
recall-precision values can then be plotted on a graph or tabulated as shown in
Table 3-15. Detailed methods for the construction of recall-precision tables andgraphs are covered in Chapter 5.
It may be seen first of all that an unequivocal result is not obtained for thecomparison between binary (BINik) and term frequency (FREQik) weights. In
the binary case, the terms are not weighted, whereas a weight proportional to
the term occurrence frequency in each document is assigned to each term in theother case. The preferred result is shown in each case by a vertical line in thesecond and third columns of Table 3-15a. For the collection under study, thebinary weights are superior at the low recall end and the term frequency
weights at the high recall end. When these basic term weights are combined withan inverse document frequency (IDF) factor proportional to l/DOCFREQk, thecombined weighting system equivalent to FREQlk/DOCFREQk [see expres­sion (2)] is clearly superior. Indeed, the results in the rightmost column of Table
3-15a show improvements ranging from 3 percent at very low recall to over 30
percent at high recall.
Table 3-15b contains t-test and Wilcoxon signed rank test values, giving ineach case the probability that the output results for the two runs being com­pared could have been generated from the same distribution of values. Small
probabilities— for example, those less than 0.05— indicate that the answer tothis question is negative and that the test results differ significantly (hence thatone system is clearly superior to the other). The significance figures in Table
3-15b show that for the Time collection the method labeled B is significantly
better than the A method in all cases. The significance tests used in judging
evaluation output are examined in more detail in Chapter 5.
In Table 3-16 the two basic term weighting systems are combined with aterm deletion process which eliminates from the document and query vectors
those terms deemed to be poor content identifiers. A variety of term deletion
procedures are usable in practice [103], For test purposes two term deletion
systems were used to obtain the results of Table 3-16. The first one consists indeleting terms in increasing IDF order, that is, terms exhibiting the highest doc­
ument frequencies (which may be expected to produce the poorest index terms)
are eliminated first. In the other case, terms were deleted in increasing term
discrimination order by removing first the terms with the lowest discrimination
values. The two runs are labeled IDF CUT and DISC CUT respectively in
Table 3-16. For the Time collection under study, documents with a document
frequency greater than 104 (out of 425 documents) were actually removed togenerate the IDF CUT performance. For the DISC CUT performance, the term
deletion was restricted to terms with negative discrimination values.
The placement of the vertical bars in Table 3-16 shows that the deletion in
inverse document frequency order performs best at low recall, whereas the dis­
crimination value cutoff is best at high recall. A comparison of the results ofTables 3-15 and 3-16 shows that the removal of poor terms produces better re-107

TEXT ANALYSIS AND AUTOMATIC INDEXING

Table 3-16 Recall-Precision Results for Term Deletion Methods(Time 425 C o lle c tio n , 24 Q u e rie s)

RecallStandard
BINlk
weights

Standard
FREQ|kweights

DF CUT

DISC CUT

0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0

0.82570.75550.67540.62240.57080.52990.46180.40870.29590.28540.74960.70710.67100.6452
0.63510.5866
0.54130.50040.38650.37210.86010.82680.75030.71440.68720.61680.56450.50170.40710.3906

0.79110.74850.73620.70000.67770.63500.59070.55100.41770.4019

FREQ|k weights

A. IDF CUTvs.
B. Standard
FREQikA. DISC CUTvs.
B. Standard
FREQikt-testA better than B
0.0000t-testA better than B
0.0085Wilcoxon
A better than B
0.0000Wilcoxon
A better than B
0.0127

IDF = inverse docu m en t frequency
DISC = discrim in a tio n value

suits than the composite inverse document frequency weights at low and me­
dium recall points. The statistical significance probabilities on the right-handside of Table 3-16 show that the improvements obtained with the term deletion
process are fully significant.
Table 3-17 includes a comparison of various composite term weighting
systems such as those based on inverse document frequency weighting(FREQik/DOCFREQk) [equivalent to expression (2)], on the signal value
FREQlk • SIGNALk [expression (6)] and on the discrimination value FREQlk •DISCVALUEk [expression (9)]. It may be seen that the composite weights ob­
tained with the inverse document frequency and the discrimination value
weights are approximately comparable in efficiency. The results produced by
the signal value are substantially less attractive because of the emphasis on lowfrequency terms inherent in that weighting system. The two right-hand columnsof Table 3-17a demonstrate that the composite weights combined with the elim­
ination of poor terms produces superior precision values at low and medium
recall levels. The significance test results of Table 3-17b indicate fully signifi­
cant performance improvements with an average performance difference rang­
ing from 8 to 15 percent.
A wide variety of phrase-generation methods are potentially useful, as ex­
plained earlier. To generate the output of Table 3-18 a simple phrase-generation
method was used consisting of phrases obtained from pairs (P) and triples (T) of
co-occurring nondiscriminators [104]. Specifically, given three nondiscrimina­
tors Ti; Tj, and Tk occurring in a given document abstract, one triple Tijk can
be formed as well as three pairs Tu , Tlk, and Tjk. For the Time collection understudy an average of 11 phrases were generated by this simple process for eachdocument. Single terms (S), pairs (P), and triples (T) can all be used together(denoted SPT); alternatively, pairs and triples alone can be added to the vec-

cor>r»cD£DCDLnin^^d o d o o d d o 'd odir<FREQjk weights
w ith D ISC VALU Ek
FREQik* DfSCVALUEk

FREQik weights
FREQjk/DOCFREQk
w ith S IG N A Lk
withFREQik*S IG N A L k
IDF CUTo

G3C6Sr>.r-.<oLotfW^d d d d d d d d o d

o
h*
D
O
O
to
o
£

lo
o
LL
D
.£

1

1

CMto*-o>wi-»cocNOco

t-ONNOOO<D»-fOO)
C N O 'd -C N ^ -LD fN C O O O L n
ps.p>cD<o<oinm^-coco
d d d d d d d d o d

a
ID
GC
11
Q
a

d"
ID
GC
LL
■Q

iD
D
-J
<
>
O
to
D

FREQjk weights
w ith IDF
FREQik/DOCFREQk
RecallStandard
term frequency
FREQjk weights

d"
UJ
GC
LL
■o

C
O

cJ
LU
GC
LL

C
C
O

CO

d"
LU
GC
LL

CO

<

cri

<

CD

3

■o
c
(0

O
o
G
Q
o
C
o
O
o ■C
£0g0

oooooooooo
ts
<
ir

108

€jg
00
2P>-Q
>

o

S’
<

d
to i- c o io o o o o c o c o to o

C O O C D O O O ^ J-C N T tC N r*.
ina>u>cor,'.CL
MO
Cir>'3-*fr
o<o<d-*cor-r-»r'.co<O

d d d d d d d d o d

<
>
oto

a *
-a
COt-OCMf-tOCO^lOtor^^-inincoi-ococNo o o o o o o o o ot -cNco*-incor-.coo>od d d d d d d d o d

~o
•&o
•?Q
5^
-d"
a lu
UJoc
G
CULL
<

d
"
ID
G
C
LL
*D
*(0
o
c
+
2
CO
CD

s_i *
dJ"
J4O
T) U
C
*5 Q
L
s L
o
.* ~C
O
d'
■
UJ C
c-oO
G
C
U_ to
< CD

Table 3-17 Composite weighting functions (425 documents, 24 queries), (a) Comparison ofcomposite weighting systems, (b) Statistical significance results fo r output of Table 3-17a(testing for A better than B).

FREQjk * DISCVALUEi
w ith
DISC CUToooooocooor^oroinotn

^ (
n

(
I
<

TEXT ANALYSIS AND AUTOMATIC INDEXING

109

RecallFREQikcontrolrunBest frequency
weighting
FREQik/DOCFREQk

Best phrase
process
PT+SPT

Thesaurus
classes

Thesaurus +PT+SPT

0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0

0.74960.70710.67100.6452
0.63510.5866
0.54130.50040.38650.37210.85360.79010.75680.73050.67830.62430.58230.65430.4426
0.4170I I 0.8860
I I 0.7984
0.77610.74610.7020I I 0.6563
I I 0.6010
0.54830.42310.41180.73920.71660169350.66270.65410.60700.55980.51110.40910.39500.87610.79720.77780.74650.70270.6524
I I 0.6010
0.55230.42600.4149(a)

A. Thesaurus + PT
+ SPT phrases

t-testWilcoxon

0.68740.68330.45240.96570.00000.0003

B. FREQik/DOCFREQk
weights
A. Thesaurus + PT
+ SPT phrases
B. PT + SPT phrases
A. Thesaurus
B. Standard term
frequency FREQik(b)

Table 3-18 Thesaurus and phrase evaluation, (a) Thesaurus and phrase performance, (b)Statistical significance results for output of Table 4-17a (testing for A better than B).

tors, the corresponding single terms being deleted (PT). When high-frequency
nondiscriminators are used for phrase generation, the PT method appears tooffer a reasonably high performance standard.
A manually constructed thesaurus designed to group low-frequency terms(terms with a document frequency smaller than 20 out of 425 documents) was
also available for experimental purposes with the Time collection; the relevant
thesaurus class identifiers can be added in each case to the standard document
and query vectors.
The performance data are included in Table 3-18 together with the corre­
sponding statistical significance output. It may be seen that for the Time collec­
tion, the grouping of low-frequency terms into thesaurus classes affords recall
improvements over the standard FREQlk weighting system for all but thelowest recall levels. Moreover, the thesaurus advantage proves statistically sig­
nificant. The phrase-generation process, however, proved more effective
especially at the high precision-low recall end of the performance spectrum. In

110

CHAPTER 3

the middle recall range, the best performance of any of the retrieval runs dis­played in Tables 3-15 to 3-18 is obtained by using a combination of the phrasegeneration process applied to high-frequency terms with the thesaurus classgrouping of low-frequency terms.
The evaluation results presented in Tables 3-15 to 3-18 are indicative of theperformance of various sophisticated statistically based automatic indexing
methods. Substantial additional work remains to be done in order to determine
the optimum indexing system applicable to a particular retrieval environment
under given conditions. When no special information is available about a par­ticular collection, the following process will, however, provide a high-quality
indexing product:
1 Starting with document abstracts or excerpts, remove common highfrequency words and generate word stems by removing suffixes from the re­maining words.
2 Compute the discrimination values of the terms, generate phrases forthe high-frequency nondiscriminators with negative discrimination values, andassemble low-frequency nondiscriminators with near-zero discrimination
values into thesaurus classes.
3 Compute a weighting factor for each remaining single term, phrase, andthesaurus class, using, for example, the inverse document frequency function[expression (2)].
4 Assign to each document the weighted term vector consisting of single
terms, phrases, and thesaurus classes.
In interactive retrieval systems where user information is available during
the search process, improved index term assignments may be obtainable as aresult of the user-system interaction. The possibility is explored'further in
Chapter 6.
REFERENCES[1] E.M. Keen, On the Generation and Searching of Entries in Printed Subject In­
dexes, Journal of Documentation, Vol. 33, No. 1, March 1977, pp. 15-45.
[2] B.C. Vickery, Techniques of Information Retrieval, Archon Books, Hamden,
Connecticut, 1970.
[3] E.M. Keen, On the Performance of Nine Printed Subject Index Entry Types, Re­
search Report, College of Librarianship, Aberystwyth, Wales, September 1978.
[4] F.W. Lancaster, Information Retrieval Systems, Characteristics, Testing and
Evaluation, 2nd Edition, Wiley-Interscience, New York, 1979.
[5] W.S. Cooper, Is Interindexer Consistency a Hobgoblin?, American Documenta­
tion, Vol. 20, No. 3, July 1969, pp. 268-278.
[6] P. Zunde and M.E. Dexter, Indexing Consistency and Quality, American Docu­mentation, Vol. 20, No. 3, July 1969, pp. 259-267.
[7] M.E. Stevens, Automatic Indexing—A State of the Art Report, National Bureauof Standards, NBS Monograph 91, National Bureau of Standards, Washington,
D.C., March 1965.

TEXT ANALYSIS AND AUTOMATIC INDEXING

111[8] H.P. Luhn, The Automatic Creation of Literature Abstracts, IBM Journal of Re­
search and Development, Vol. 2, No. 2, April 1958, pp. 159-165.
[9] G.K. Zipf, Human Behavior and the Principle of Least Effort, Addison Wesley
Publishing, Reading, Massachusetts, 1949.
[10] H. Kucera and W.N. Francis, Computational Analysis of Present-Day American
English, Brown University Press, Providence, Rhode Island, 1967.
[11] H.P. Luhn, A Statistical Approach to Mechanized Encoding and Searching of Lit­
erary Information, IBM Journal of Research and Development, Vol. 1, No. 4, Oc­
tober 1957, pp. 309-317.
[12] H.P. Edmundson and R.E. Wyllys, Automatic Abstracting and Indexing—Survey
and Recommendations, Communications of the ACM, Vol. 4, No. 5, May 1961,
pp. 226-234.
[13] F.J. Damerau, An Experiment in Automatic Indexing, American Documentation,
Vol. 16, No. 4, October 1965, pp. 283-289.
[14] K . Sparck Jones, A Statistical Interpretation o f Term Specificity and Its A pplica­tion in R etrieval, Journal o f D ocum entation, V ol. 28, N o . 1, March 1972, pp. 1 1 -20[15] C -E. Shannon, Prediction and E ntropy o f Printed E nglish, B ell System Technical
Journal, V ol. 30, N o . 1, January 1951, pp. 5 0 -6 5 .

[11] S.F. Dennis, Law, Language, Words, Entropy, and Automatic Indexing, unpub­
lished manuscript.
[11] S.F. Dennis, The Design and Testing of a Fully Automatic Indexing-Searching
System for Documents Consisting of Expository Text, in Information Retrieval: A
Critical Review, G. Schecter, editor, Thompson Book Co., Washington, D.C.,
1967, pp. 67-94.
[18] G. Salton, A Theory of Indexing, Regional Conference Series in Applied Mathe­
matics No. 18, Society for Industrial and Applied Mathematics, Philadelphia,
Pennsylvania, 1975.
[19] G. Salton and C.S. Yang, On the Specification of Term Values in Automatic In­
dexing, Journal of Documentation, Vol. 29, No. 4, December 1973, pp. 351-372.
[20] G. Salton and M.E. Lesk, Recent Studies in Automatic Text Analysis and Infor­
mation Retrieval, Journal of the ACM, Vol. 20, No. 2, April 1973, pp. 258-278.
[21] G. Salton, C.S. Yang, and C.T. Yu, A Theory of Term Importance in Automatic
Text Analysis, Journal of the American Society for Information Science, Vol. 26,
No. 1, January-February 1975, pp. 33-44.
[22] G. Salton, C.S. Yang, and C.T. Yu, Contributions to the Theory of Indexing, In­formation Processing 74, North Holland Publishing Company, Amsterdam, 1974,
pp. 584-590.
[23] R.A. May, editor, Automated Law Research, American Bar Association, Chi­cago, Illinois, 1973.
[24] G. Salton and M.E. Lesk, Computer Evaluation of Indexing and Text Processing,
Journal of the ACM, Vol. 25, No. 1, January 1968, pp. 8-36.
[25] C.J. van Rijsbergen, Information Retrieval, 2nd Edition, Butterworths, London,
1979.
[26] G. Salton, Automatic Information Organization and Retrieval, McGraw-Hill Book
Company, New York, 1968.
[27] J.B. Lovins, Development of a Stemming Algorithm, Mechanical Translation andComputational Linguistics, Vol. 11, No. 1-2, March and June 1968, pp. 11-31.
[28] G. Salton and M.E. Lesk, Information Analysis and Dictionary Construction, in

112

CHAPTER 3

the SM A RT Retrieval S y ste m — Experim ents in A utom atic D ocum ent P rocessing,
G. Salton, editor, Chapter 6, Prentice-H all, In c ., E nglew ood C liffs, N e w Jersey,
1971.
[29] K . Sparck Jones, A utom atic K eyw ord C lassification for Information R etrieval,
B utterw orths,. L o n d o n , 1971.
[30] G. Salton, G eneration and Search o f Clustered F iles, ACM Transactions on Data
B ase S ystem s, V ol. 3, N o . 4, D ecem ber 1978, pp. 32 1 -3 4 6 .
[31] R .T . D attola, E xperim ents w ith Fast Algorithm s for A utom atic C lassification, in
the Smart Retrieval S y ste m — Experim ents in A utom atic D ocum ent P rocessing,
G. Salton, editor, Chapter 12, Prentice-H all, In c ., E n glew ood C liffs, N e w Jersey,
1971.
[32] G. Salton, D ynam ic Inform ation and Library P rocessin g, Prentice-H all, In c., E n­
glew ood Cliffs, N e w Jersey, 1975.
[33] V .E . Giuliano and P .E . Jo n es, Linear A sso cia tiv e Information R etrieval, in V istas
in Information H andling, P. H ow erton, editor, Spartan B o o k s, In c ., W ashington,
D .C ., 1963.
[34] M .E . L esk, Word-W ord A ssociation s in D ocum en t Retrieval S y stem s, Am erican
D ocum entation, V ol. 20, N o . 1, January 1969, pp. 2 7 -3 8 .
[35] L .B . D o y le, Information R etrieval and P rocessing, M elville Publishing Com pany,
L os A n geles, California, 1975.
[36] G. Jones and P. W ise, U pdating Thesaurus C lassifications in R esp o n se to Data
B ase C hanges, Scientific R eport N o . ISR-21, S ection X III, D epartm ent o f Com ­puter S cien ce, Cornell U n iversity, Ithaca, N e w Y ork, D ecem ber 1972.
[37] M .M . K essler, Com parison o f the R esults o f Bibliographic Coupling and A nalytic
Subject Indexing, A m erican D ocum entation, V ol. 16, N o . 3, 1965, pp. 2 2 3 -2 3 3 .
[38] G. Salton, A utom atic Indexing U sing Bibliographic C itations, Journal o f D o cu ­m entation, V ol. 27, N o . 2, June 1971, pp. 9 8 -1 1 0 .
[39] H .P . Edm undson, Problem s in A utom atic A bstracting, C om m unications o f the
A C M , V ol. 7, N o . 4, April 1964, pp. 2 5 9 -2 6 3.
[40] H .P . E dm undson, N e w M ethods in A utom atic E xtracting, Journal o f the A CM ,V ol. 26, N o . 2, April 1969, pp. 26 4 -2 8 5 .
[41] J.E . R ush, R. Salvador, and A . Zamora, A utom atic Abstracting and Indexing II,
Production o f Indicative A bstracts by A pplication o f C ontextual Inference andSyntactic C oherence Criteria, Journal o f the A S IS , V ol. 22, N o . 4 , J u ly -A u g u st
1971, pp. 2 6 0 -2 7 4 .
[42] C .A . M ontgom ery, L inguistics and Information S cien ce, Journal o f the American
Society for Information S cien ce, V ol. 23, N o . 3, M a y -J u n e 1972, pp. 195-219.
[43] K . Sparck Jones and M . K ay, L inguistics and Information S cien ce, A cadem ic
P ress, N e w Y ork, 1973.
[44] F. D am erau, A utom ated Language P rocessing, in Annual R eview o f Information
S cien ce and T ech n ology, M .E . W illiam s, editor, A m erican S ociety for Informa­tion S cien ce, W ashington, D .C ., V ol. 11, 1976, pp. 107-161.
[45] S. K uno and A . G. Oettinger, M ultiple-Path Syntactic A nalyzer, in Information
P rocessing 62, N orth H olland Publishing C om pany, A m sterdam , 1963, pp. 128—133.
[46] P. B axendale, A n Empirical M odel for M achine Indexing, in M achine Indexing—
Progress and Problem s, Third Institute on Information Storage and R etrieval,A m erican U n iversity, February 1961, pp. 2 0 7 -2 1 8 .
[47] W .D . C lim enson, N .H . H ardw ick, and S .N . Jacob son , A utom atic Syntax Anal-TEXT ANALYSIS AND AUTOMATIC INDEXING

113

y sis in M achine Indexing and A bstracting, A m erican D ocum entation, V ol. 12, N o .
3, M y 1961, pp. 178-183.
[48] F .J. D am erau, A utom atic Parsing for C ontent A n alysis, C om m unications o f the
A C M , V ol. 13, N o . 6, June 1970, pp. 3 5 6 -3 6 0 .
[49] D .J. Hillman and A .J. Kasarda, The L E A D E R Retrieval System , A FIPS P roceed­
ings, A FIPS P ress, M ontvale, N e w Jersey, V ol. 34, 1969, pp. 4 4 7 -4 5 5 .
[50] G. Salton, A utom atic Phrase M atching, in Readings in A utom atic Language Pro­
cessin g , D . H ays, editor, A m erican E lsevier Publishing C om pany, N e w York,
1966, pp. 169-188.
[51] J. Friedm an, A C om puter System for Transform ational Grammar, Com m unica­
tions o f the A C M , V ol. 12, N o . 6, June 1969, pp. 34 1 -3 4 8 .
[52] N . Sager and R. Grishman, T he R estriction Language for Computer Grammars o f
Natural Language, C om m unications o f the A C M , V ol. 18, N o . 7, July 1975, pp.
3 9 0 -4 0 0 .
[53] W .A . W oods, Transition N etw ork Grammars for Natural Language A nalysis,
C om m unications o f the A C M , V ol. 13, N o . 10, O ctober 1970, pp. 5 9 1 -6 0 6 .
[54] G .G . H endrix, Hum an Engineering for A pplied Natural Language P rocessing,
Fifth International Joint C onference on Artificial Intelligence, M .I.T ., Cambridge,
M assachusetts, 1977, pp. 183-191.
[55] L .R . Harris, U ser-O riented D ata B ase Query with the ROBOT Natural Language
Query System , International Journal o f M an-M achine Studies, V ol. 9, 1977, pp.
6 9 7 -7 1 3 .
[56] J. M ylopoulos, A . Borgida, P. C ohen, N . R ou sso p o u lo s, J. T so tso s and H . W ong,
T oru s— A Natural L anguage U nderstanding System for D ata M anagem ent,
Fourth International Joint C onference on Artificial Intelligence, T bilisi, U S S R ,Septem ber 1975, pp. 4 1 4 -4 2 1 .
[57] W .J. Plath, R E Q U E ST : A Natural Language Q uestion-A nsw ering S y stem , IBM
Journal o f R esearch and D evelop m en t, V ol. 20, N o . 4, July 1976, pp. 32 6 -3 3 5 .
[58] D .L . W altz, An E nglish Language Q uestion A nsw ering S ystem for a Large R ela­tional D atabase, C om m unications o f the A CM , V ol. 21, N o . 7, July 1978, pp. 5 2 6 539.
[59] G .S . Dunham , M .G . Pacak, and A .W . Pratt, A utom atic Indexing o f Pathology
D ata, Journal o f the A m erican Society for Inform ation S cien ce, V o l. 29, N o . 2,
M arch 1978, pp. 8 1 -9 0 .
[60] R. Grishman and L. H irschm an, Q uestion A nsw ering from Natural Language
M edical D ata B a ses, Artificial Intelligence, V ol. 11, N o . 1/2, 1978, pp. 2 5 -4 3 .
[61] H .J. Schek, The R eference String Indexing M ethod, R esearch R eport, IBM S cien­tific C enter, H eidelberg, Germ any, 1978.
[62] E .J. Schuegraf and H .S . H eap s, Query P rocessing in a R etrospective D ocum ent
R etrieval System That U s e s Word Fragments as Language E lem en ts, Information
P rocessing and M anagem ent, V ol. 12, N o . 4, 1976, pp. 28 3 -2 9 2 .
[63] E .J. Schuegraf and H .S . H eap s, Selection o f Equifrequent Word Fragm ents for
Inform ation R etrieval, Information Storage and R etrieval, V ol. 9, N o . 12, D ecem ­ber 1973, pp. 697 -7 1 1 .
[64] M .F . L ynch, Variety G eneration— A Reinterpretation o f Shannon’s M athem atical
T heory o f C om m unication and Its Im plications in Information S cien ce, Journal o f
the A m erican S ociety for Information S cien ce, V ol. 28, N o . 1, January 1977, pp.
1 9 -2 5 .
[65] T. Radhakrishnan, S election o f Prefix and Postfix W ord Fragments for D ata Com-

114

CHAPTER 3

p ression, Information P rocessing and M anagem ent, V ol. 14, N o . 2, 1978, pp. 9 7 106.
[66] I.J. Barton, S .E . C reasey, M .F . L ynch, and M .J. Snell, A n Inform ation-Theoretic
A pproach to T ext Searching in D irect A c c e ss S y stem s, C om m unications o f the
A C M , V ol. 17, N o . 6, June 1974, pp. 3 4 5 -3 5 0 .
[67] H .S . H eaps, Information R etrieval— Com putational and Theoretical A sp ects, A c ­adem ic P ress, N e w Y ork, 1978.
[68] D . G ottlieb, S .A . H agerth, P .G .H . L eh ot, and H .S . R abinow itz, A Classificationo f C om pression M ethods and Their U sefu ln ess for a Large D ata P rocessing C en­ter, A F IP S C onference P roceedings, V ol. 44, 1975, pp. 4 5 3 -4 5 8 .
[69] M . K och en , Principles o f Information R etrieval, M elville Publishing C om pany,
L os A n geles, California, 1974.
[70] W . Goffm an, A Searching Procedure for Inform ation R etrieval, Inform ation Stor­
age and R etrieval, V ol. 2, N o . 2, July 1964, pp. 7 3 -7 8 .
[71] A . B ookstein and D .R . S w an son , A D ecision T heoretic Foundation for Indexing,
Journal o f the A S IS , V ol. 26, N o . 1, January-F ebruary 1975, pp. 4 5 -5 0 .
[72] C.J. van R ijsbergen, A . Theoretical B asis for the U se o f C o-occurrence D ata inInformation R etrieval, Journal o f the D ocum entation, V ol. 33, N o . 2, June 1977,
pp. 106-119.
[73] A . B ookstein and D .R . Sw an son , Probabilistic M odels for A utom atic Indexing,
Journal o f the A S IS , V ol. 25, N o . 5, S ep tem b er-O cto b er 1974, pp. 3 1 2 -3 1 8 .
[74] F .W . L ancaster and E .G . F a y en , Information R etrieval O n-Line, John W iley andS o n s, N e w Y ork, 1973.
[75] M .E . L esk and G. Salton, Interactive Search and Retrieval M ethods U sin g A u to­m atic Information D isp la y s, in the SM ART R etrieval S ystem , E xperim ents in A u­
tom atic D ocum ent P rocessin g, G. Salton, editor, Prentice-H all, In c ., E nglew ood
C liffs, N e w Jersey, 1971, Chapter 25.
[76] G. Salton, R elevan ce F eedback and the O ptim ization o f R etrieval E ffectiv en ess in
the SM A RT R etrieval S y stem , Experim ents in A utom atic D ocum ent P rocessing,
G. Salton, editor, Prentice-H all, In c., E n glew ood C liffs, N e w Jersey, 1971, Chap­
ter 15.
[77] S .E . R obertson and K . Sparck Jones, R elevan ce W eighting o f Search Term s,
Journal o f the A S IS , V o l. 27, N o . 3, M a y -J u n e 1976, pp. 129-146.
[78] C .T . Y u and G. Salton, P recision W eighting— A n E ffective A utom atic Indexing
M ethod, Journal o f the A C M , V ol. 23, N o . 1, January 1976, pp. 7 6 -8 8 .
[79] G. Salton and R .K . W aldstein, Term R elevance W eights in O n-Line Information
R etrieval, Information P rocessing and M anagem ent, V ol. 14, N o . 1, 1978, pp. 2 9 35.
[80] M .E . M aron, A utom atic Indexing— An E xperim ental Inquiry, Journal o f the
A C M , V ol. 8, N o . 3, July 1961, pp. 4 0 4 -4 1 7 .
[81] M .E . Maron and J.L . K uhns, On R elevan ce, Probabilistic Indexing and Informa­tion R etrieval, Journal o f the A C M , V ol. 7, N o . 3, July 1960, pp. 2 1 6 -2 4 4 .
[82] W .B . Croft, A Study o f the E ffectiven ess and Im plem entation o f a M odel o f Clus­
ter Searching, R esearch R eport, U niversity o f Cambridge, Computer Laboratory,
1978.
[83] C .D . Stone and M . R ubinoff, Statistical G eneration o f a T echnical V ocabulary,A m erican D ocum entation, V ol. 19, N o . 4 , O ctober 1968, pp. 4 1 1 -4 1 2 .
[84] F. M osteller and E .L . W allace, Inference in an Authorship Problem , Journal o f theA m erican Statistical A sso cia tio n , V ol. 58, N o . 302, June 1963, pp. 2 7 5 -3 0 9 .

TEXT ANALYSIS AND AUTOMATIC INDEXING

115[85] S .P . Harter, A Probabilistic A pproach to K eyw ord Indexing, Part 1. On the Distri­bution o f Specialty W ords in a Technical Literature, Journal o f the A S IS , V ol. 26,
N o . 4, J u ly-A u gu st 1975, pp. 197-206.
[86] A . B ookstein and D . Kraft, Operations R esearch A pplied to D ocum ent Indexing
and Retrieval D ecisio n s, Journal o f the A C M , V ol. 24, N o . 3, July 1977, pp. 418—
427.
[87] G. Salton, A utom atic T ex t A n alysis, S cien ce, V ol. 168, N o . 3929, April 1970, pp.
3 3 5 -3 4 3 .
[88] C. M ontgom ery and D .R . Sw an son , M achine-like Indexing by P eo p le, American
D ocum entation, V ol. 13, N o . 4, O ctober 1962, pp. 35 9 -3 6 6 .
[89] M .J. Ruhl, Chem ical D ocum ents and Their Titles: Hum an C oncept Indexing vs.
KW IC M achine Indexing, A m erican D ocum entation, V ol. 15, N o . 2, April 1964,
pp. 136-141.
[90] D .H . Kraft, A Com parison o f K eyw ord in C ontext (KW IC) Indexing o f T itles witha Subject H eading C lassification System , A m erican D ocum entation, V ol. 15, N o .
1, January 1964, pp. 4 8 -5 2 .
[91] M .E . S teven s and G .H . U rban, Training a C om puter to A ssign D escriptors to
D ocum ents: E xperim ents in A utom atic Indexing, Proceedings o f the Spring Joint
C om puter C onference, Spartan B o o k s, 1964, pp. 56 3 -5 7 5 .
[92] T .N . Shaw and H . R othm an, A n Experim ent in Indexing by Word C hoosing, Jour­nal o f D ocum entation, V ol. 24, N o . 3, Septem ber 1968, pp. 159-172.
[93] D .R . Sw anson, Searching Natural Language T ex t by Com puter, S cien ce, V ol.
132, N o . 3434, O ctober 21, 1960, pp. 1099-1104.
[94] D .R . Sw anson, Interrogating a Computer in Natural Language, in Information
P rocessing 62 (Proceedings o f IFIP C ongress 62), C. P opplew ell, editor, North
H olland Publishing C o ., A m sterdam , 1963, pp. 2 8 8 -2 9 3 .
[95] T. Saracevic, A n Inquiry into Testing o f Information Retrieval S y stem s, Compara­tive S ystem s Laboratory T echnical Reports N o . CSL: T R -F IN A L 1 to 3, Center
for D ocum entation and Com m unication R esearch, C ase W estern R eserve U niver­sity, C leveland, O hio, 1968.
[96] C .W . C leverdon and E .M . K een , Factors Determ ining the Perform ance o f Index­
ing S ystem s, V ol. 1: D esign , V ol. 2: T est R esu lts, A slib Cranfield R esearch
Project, Cranfield, England, 1966.
[97] C .W . C leverdon, The Cranfield T ests on Index Language D ev ic e s, A slib P roceed­
ings, V ol. 19, N o . 6, June 1967, pp. 173-194.
[98] G. Salton, editor, the SM A R T Retrieval S y stem — Experim ents in A utom atic D o c ­um ent P rocessing, Prentice-H all, In c., E n glew ood C liffs, N e w Jersey, 1971.
[99] G. Salton, editor, Scientific Reports N o . ISR-11 to ISR-22, D epartm ent o f Com ­puter Scien ce, Cornell U n iversity, Ithaca, N e w Y ork, 1966-1974.
[100] F .W . L ancaster, E valuation o f the M E D L A R S D em and Search S erv ice, N ational
Library o f M edicine, B eth esd a, Maryland, January 1968.
[101] G. Salton, A Com parison b etw een Manual and A utom atic Indexing M ethods,
A m erican D ocum entation, V ol. 20, N o . 1, January 1969, pp. 6 1 -7 1 .
[102] G. Salton, A N e w Com parison betw een C onventional Indexing (M E D L A R S) andA utom atic T ext P rocessing (SM A RT), Journal o f the A m erican S o ciety for Infor­
m ation S cien ce, V ol. 23, N o . 2, M arch-A pril 1972, pp. 7 5 -8 4 .
[103] R .W . Crawford, N eg a tiv e D ictionary C onstruction, Scientific Report N o . ISR-22,
D epartm ent o f C om puter S cien ce, Cornell U n iversity, Ithaca, N e w Y ork, N o ­vem ber 1974.

116

CHAPTER 3[104] G. Salton and A . W ong, On the R ole o f W ords and Phrases in A utom atic T ext
A n alysis, Com puters and the H um anities, V ol. 10, N o . 2, M arch -A p ril 1976, pp.
6 9 -8 7 .

BIBLIOGRAPHIC REMARKS

For a review of conventional tools for document indexing see:
B .C . V ickery, Techniques o f Information R etrieval, A rchon B o o k s, H am den, C onnecti­
cut, 1970.
D . S oergel, Indexing Languages and Thesauri: C onstruction and M aintenance, M elville
Publishing C om pany, L o s A n g eles, California, 1974.

Additional basic information on automatic indexing methods may be obtained
from the following references:
M .E . S tev en s, A utom atic Indexing: A State o f the Art R eport, M onograph 91, N ational
Bureau o f Standards, W ashington, D .C ., M arch 1965.
G. Salton, A Theory o f Indexing, R egional C onference Series in A pplied M athem atics
N o . 18, S ociety for Industrial and Applied M athem atics, Philadelphia, P ennsylva­
nia, 1975.
L .B . D o y le , Information R etrieval and P rocessing, M elville Publishing C om pany, L os
A n geles, California, 1975.

EXERCISES
3-1

3-2

3-3

3-4

E xplain the significance o f each o f the follow ing indexing procedures, and deter­mine the effect o f each m ethod as a m eans o f enhancing recall and/or precision,respectively:
a Word stemming p rocessb U se o f synonym dictionaryc U se o f word location informationd U se o f term w eights
W hat is the significance o f term frequency in the theory o f indexing? W hat is thesignificance o f Z ip f s law as a basis for deriving an autom atic indexing m ethod? Is
the discrim ination value o f a term related to the occurrence frequency o f a term in adocum ent collection? If so , w hat is the relationship?
The term relevance factor T ER M R EL differs from all other term weighting system sin the sen se that relevance information m ust be available for som e docum ents withresp ect to a given query. E xplain the role o f relevance information for the com puta­tion o f the TER M R EL w eight and give tw o m ethods for estim ating the required
relevance information.
C onsider the follow ing sam ple docum ent collection:

D j = (1,0,1,0,0,0)
D 2 = (3,1,2,1,0,1)
D 3 = (1,2,3,0,1,0)
D 4 = (0,1,0,2,1,2)
D 5 = (1,0,1,4,2,1)
D 6 = (1,1,0,2,3,2)

TEXT ANALYSIS AND AUTOMATIC INDEXING

3-5

117

G enerate a term-term similarity matrix similar to that show n in Table 4-10 using one
o f the term similarity coefficien ts given in exp ression s (11) or (12). C h oose a thresh­
old value for the term similarity and “ exp an d ” the sam ple docum ents by adding
associated term s to the original term vectors. In w hat respects do the new e x ­panded vectors differ from the originals?
C onsider the docum ent collection o f E xercise 3-4 together w ith the follow ing querypair

Qi = (2,0,2,0,0,0)Q2 = (0,0,0,2,0,2)

a

b
c
d

e
f
g

Exhibit the normal query-docum ent similarity coefficients for all query-docu­
m ent pairs using a vecto r similarity function such as expressions (11) and (12) inthe form SIM ILA R (Dj ,Qj). D isplay the docum ents in decreasing order o f query
similarity.
C om pute the discrim ination value for each term , and construct updated docu­
m ent vectors using discrim ination value w eighting,R epeat part a using the discrimination value weighting,A ssum ing that D , , D 2, D 3 are relevant toand D 4 , D 3, D 6 are relevant to Q2,
com pute the term relevance value (TERM REL) for each term and construct up­
dated vectors using term relevance value weighting,R epeat part a using the relevance weighting.
R epeat part a for the “ expanded” collection derived in E xercise 3-4.
Compare the results o f parts a, c , e, and f.