T w o

AUTOMATICTEXT ANALYSIS

Introduction

Before a computerised information retrieval system can actuallyoperate to retrieve some information, that information must havealready been stored inside the computer. Originally it will usually havebeen in the form of documents. The computer, however, is not likely tohave stored the complete text of each document in the natural language
in which it was written. It will have instead, a document representative
which may have been produced from the documents either manually or
automatically.
The starting point of the text analysis process may be the complete
document text, an abstract, the title only, or perhaps a list of words
only. From it the process must produce a document representative in aform which the computer can handle.
The developments and advances in the process of representation
have been reviewed every year by the appropriate chapters of Cuadra’s
Annual Review o f Information Science and Technology. The reader isreferred to them for extensive references. The emphasis in this Chapter
is on the statistical (a word used loosely here: it usually simply implies
counting) rather than linguistic approaches to automatic text analysis.
The reasons for this emphasis are varied. Firstly, there is the limit on
space. Were I to attempt a discussion of semantic and syntactic
methods applicable to automatic text analysis, it would probably fillanother book. Luckily such a book has recently been written by Sparck
Jones and Kay1. Also Montgomery2 has written a paper surveying
linguistics in information science. Secondly, linguistic analysis has
proved to be expensive to implement and it is not clear how to use it to
J2

AUTOMATIC TEXT ANALYSIS

enhance information retrieval. Part of the problem has been that very
little progress has been made in formal semantic theory. However, there
is some reason for optimism on this front, see for example Keenan3.
Undoubtedly a theory of languange will be of extreme importance tothe development of intelligent IR systems. But, to date no such theory
has been sufficiently developed for it to be applied successfully to IR.
In any case satisfactory, possibly even very good, document retrieval
systems can be built without such a theory. Thirdly, the statistical
approach has been examined and tried ever since the days of Luhn andhas been found to be moderately successful.
This chapter therefore starts with the original ideas of Luhn on
which much of automatic text analysis has been built, and then goes on
to describe a concrete way of generating document representatives.
Furthermore, ways of exploiting and improving document
representatives through weighting or classifying keywords are discussed.
In passing, some of the evidence for automatic indexing is presented.

Luhn’s ideas

In one of Luhn’s4 early papers he states: ‘It is here proposed that thefrequency of word occurrence in an article furnishes a usefulmeasurement of word significance. It is further proposed that therelative position within a sentence of words having given values ofsignificance furnish a useful measurement for determining thesignificance of sentences. The significance factor of a sentence will
therefore be based on a combination of these two measurements.’
I think this quote fairly summarises Luhn’s contribution toautomatic text analysis. His assumption is that frequency data can beused to extract words and sentences to represent a document.
Let / be the frequency of occurence of various word types <n agiven position of text and r their rank order, that is, the order of theirfrequency of occurrence, then a plot relating / and r yields a curve
similar to the hyperbolic curve in Figure 2.1. This is in fact a curve
demonstrating Zipfs Law5* which states that the product of thefrequency of use of words and the rank order is approximately
constant. Zipf verified his law on American Newspaper English. Luhn
used it as a null hypothesis to enable him to specify two cut-offs, anupper and a lower (see Figure 2.1), thus excluding non-significant
words. The words exceeding the upper cut-off were considered to be* Also see, Fairthorne, R. A., ‘Empirical hyperbolic distributions (Bradford-ZipfMandelbrot) for bibliometric description and prediction,’ Journal o f Documenta­
tion, 25, 319-343 (1969).

13

AUTOMATIC TEXT ANALYSIS

Figure 2.1. A plot o f the hyperbolic curve relating f, the frequency o f occurrence
and r, the rank order (Adapted from Schultz” , page 120)

common and those below the lower cut-off rare, and therefore notcontributing significantly to the content of the article. He thus deviseda counting technique for finding significant words. Consistent with thishe assumed that the resolving power of significant words, by which hemeant the ability of words to discriminate content, reached a peak at arank order position half way between the two cut-offs and from thepeak fell off in either direction reducing to almost zero at the cut-off
points. A certain arbitrariness is involved in determining the cut-offs.
Tbeng is no oracle which gives their values. They have to be establishedby trial and error.
It is interesting that these ideas are really basic to much of the later
work in IR. Luhn himself used them to devise a method of automatic
abstracting. He went on to develop a numerical measure of significancefor sentences based on the number of significant and non-significant
words in each portion of the sentence. Sentences were ranked according
to their numerical score and the highest ranking were included in the
abstract (extract really). Edmundson and Wyllys5 have gone on to
generalise some of Luhn’s work by normalising his measurements withrespect to the frequency of occurrence of words in general text.
There is no reason why such an analysis should be restricted to justwords. It could equally well be applied to stems of words (or phrases)
and in fact this has often been done.
14

AUTOMATIC TEXT ANALYSIS

Generating document representatives—conflation

Ultimately one would like to develop a text processing system which bymeans of computable methods with the minimum of humanintervention will generate from the input text (full text, abstract, or
title) a document representative adequate for use in an automatic
retrieval system. This is a tall order and can only be partially met. The
document representative I am aiming for is one consisting simply of alist of class names, each name representing a class of words occurring in
the total input text. A document will be indexed by a name if one of its
significant words occurs as a member of that class.
Such a system will usually consist of three parts: (1) removal of highfrequency words, (2) suffix stripping, (3) detecting equivalent stems.
The removal of high frequency words, ‘stop’ words or ‘fluff words is
one way of implementing Luhn’s upper cut-off. This is normally doneby comparing the input text with a ‘stop list’ of words which are to be
removed.
Table 2.1 gives a portion of such a list, and demonstrates the kind ofwords that are involved. The advantages of the process are not only that
non-significant words are removed and will therefore not interfere
during retrieval, but also that the size of the total document file can be
reduced by between 30 and 50 per cent.
The second stage, suffix stripping, is more complicated. A standard
approach is to have a complete list of suffixes and to remove thelongest possible one.
Table 2.2 lists some suffixes. Unfortunately, context free removal
leads to a significant error rate. For example, we may well want UAL
removed from FACTUAL but not from EQUAL. To avoid erroneously
removing suffixes context rules are devised so that a suffix will be
removed only if the context is right. ‘Right’ may mean a number ofthings:(1) the length of remaining stem exceeds a given number; thedefault is usually 2;(2) the stem-ending satisfies a certain condition, e.g. does not
end with Q.
Many words, which are equivalent in the above sense, map to one
morphological form by removing their suffixes. Others, unluckily,
though they are equivalent, do not. It is this latter category which
requires special treatment. Probably the simplest method of dealing
with it is to construct a list of equivalent stem-endings. For two stems
to be equivalent they must match except for their endings, whichthemselves must appear in the list as equivalent. For example stems
such as ABSORB- and ABSORPT- are conflated because there is an
15

AUTOMATIC TEXT ANALYSIS

a:

w
a^
H
a
U
Li. COa> a > <<
u a a a aajaHH!Z22aaa
j p i < < WWWWWW&
a Q COQX
H a: a a ,W < < adO O £ £ QH
o o
HH

CO

O

>
-J

CO

£
Ws wg
o z a§§

a

a
Q
<
a
W
PC O S- H H
CO Oh
a
2
2 a
a a a a > aa^ ^an Nl .r ^v^ jc > iu ja . HHa H nXi mM
a >*■
a pN
O U O U U U f t . a . a c O C O C O CCO
O CCOO COC OCOC OCOC COO C O C O C O C O M C O C O C O

n
a, O
CO

< U
co co xX2
a a a H W2 a: X
a: H so22

W WW WWW
2 2 2 222

xaooooooo

w
OS
p
w
X
> >•
a a:
£
o
WWH
wwH P
z
H *TX< H
S S 'G “ «< OS 0$ co i/i u co
H H < 1/3 D
z m h h h < < < b w h ? < ww^ o o p o p p ^£2EEEj j j j j j SSSSSSSSSSS5>-TABLE 2.1

UUUQQWWWWWWWWWWWWWWC l,

16

co
Q
a
<
CO ^
fc
r w « os os *.
p >*■ o u p t-i a
O O Bt H H <C<
amuLLOOX>O
Ha
Q C3 co COa
co W O <Xo >■ B 2Ho z z w o x <i g §QO>
2 0 0 h CO H ^ 2 2p p p Op p p 2 s 2 z 2 X 2< < < <1 < < < 5 c <HAUTOMATIC TEXT ANALYSIS

CO

x
OX
X>
>Z
X
7—x X X XX
-1
Hx
CQ X > Xwx>x x
CO c o 'c o
Xs XXXXZ
5 Q—i W . 1<y a: a; a:
X X coa: X cc: X H X X
x x XXXp p xi mx i dttfcoSgg 0 0 0
11 XXXm> >- >

H
X
co
X
x
x X 2
o
H X o
>
a >* U 2 O
n
X
o
O
i
XO X < X X X
u XXXXXXX
Xo P P
X. S CX J Xz H
S 2 2 XXXXXXC
O>- COI o o P
u < < X X X x X X X X X X X X X X 22 0 o X X X
XXI XXXX XX XXXXXXXX XX XX XH
XOH
C
HHHHHHHHHHHHHHH HHHHH
x
a:
x
X
£

co
co
x
X
x
c*
w
X X
>
2 x
x x H
Q
X
2
W
x
X x x h o w z_x s
H .> > xXx x x x _O
_ O O O O O O O fafa
222222222222200

x
cn
co ^

x

>
u x x
2222
o o o oXX
2BSH
0 X tow
X >■Jr X
XJ>X<X p X ►Ww
XCOCu X X X X O coQ co
£ £2 XXXXXXXXo o
XXXXXXXXXI I I I XXXXXX11 XI I I 11a; as as
www
I I I
HHH
o o o

Wh. Z

Q
z

<
o
[Jj
CO >7
I
Q
CO
w 5 WWE w w Q
XXXQ
z
os
as
S
3
S
S
S
2 o £0 Q s X zo X
I
o
o
<
<
o
o
o
z
wo
2
X COCO >- Hu u u u o u XXX X
as aS co !-< „ _____XX XXXwo p <3X X X u<<<<c a mmi n b a i M« B5 « i BX X X X X X 0

17

AUTOMATIC TEXT ANALYSISaP

P >fa J

M

<

<

^

o u o « QQtfcogggg< < ll» g g S
z z z <WWWWWE£ 3 KEm UUUUUUSS^CO CO CO
2
t
J
2
2
2
E
J
2
^
2
S
S
h
H
H
H
HHHHHHW CO CO C « a i C O ! Z I C O O O K i a i C / 3 C / 3 a i a ! ( Z l K l ! Z l ! / 3 l / l l / l C O ! 7 3 t / 2 [ / 5
<

m

cn
z z
o o
p p

m
a><
HHN
HM
N

cn

J
i'"
hp h) <zi_ _,u o o c i
QQf^wzzzz,

ss

as as

Oll/JC/3KlC0KI!/3!ZlKiaia!aiKIKl!«C0Kiail/3KlC0H

■<
i N

<
N

SSoi SSc i Sa i a i a i SSa s SSos Sa i Bi os oSB:

><
m
J

CO

a
a
>- W
cn
r
r
w
w
S3 >•
O
O
a Z
ss
CO
a a COb b z za a
CO CO CO
M CO
J
J
-1
J
JdwOOOOZ Z I
P P P
3 < S ££££>. o o o
UUUUUUUOWWWHHHHHHHHHHt - Hz z z z z z z z z z z z z z z z z z z z z z z.....................................................< ........................
CO
CO

CO CO
2 p

CO
U ^

CO CO
CO CO

>a
a -1

>• CO
< <! CO
z z z
jSS
S
3>
>
b . J CO< 2 2 52 CO
-1«
222
oooo
P
Q Q Oh coCOyh ic o S
H P.
. .P____________zzzz
w 5 S 2 5 s s h h h h h i h h P > , < < < < wwwww

C O C O C O CO C O C O C O C O C O C O C O C O C O C O H H N N N N N N N N N

CO
CO
a
CO CO
ISJ
CO CO
CO CO
a
> CO COW>• a a
CO CO
p >a
a z z
>« CO COCO CO
a J
CO CO CO CO
nJ a
a
o D
o
O O
P P D pQ - Q Z z PC CO z z z
CO 0 Oa a a a a W a> 0 0 O 0 a Q Q
a J hJ a a -1 nJ 2 a a a a a a a
CQ CQ CQ CQ CQ CQ CQ CQ CQ CQ CQ u u u u 3 3 3

TABLE 2.2

a

18

CO

a »

a a

:< < < <AUTOMATIC TEXT ANALYSIS

co

W

fa
>> O
O
w1s C
b H fa C
fa >>* C
CO
OC
CO
O
sO
fa
fa
fa
fa
fa
fa
fa
COC
>
>
COO
ca 3 ca m ca fa O Q fa
2 2 eS co U U <
as CO
o
V
U u2
< < < < < < < fa fa fa fa fa fa fa fa>
H
H
COCOCOH H H H H H H H H H H H H H H H P H H H H H<<<<<<<<<<<<<<<< <<<<<<<<<

CO

D >fa
><
fa -J
CO
fa >
o o
CQ fa
O
o
O
C
D
co
H H
"
Q Q B l M
2 h2, ,hz, h,z Q Q< Q Q os co §< < H | iI| i| UI iI hfa
fa fa fah
NNNN>
fa O 0 co S" WWW co co WWW
d ai os as ai as bS 3 2 os d as as as as d 53 co co 3 3 WWW< < C< < < << < < < < < < < C < <! <S <
Z Z

CO

fa

fa
D

co

>

2

b b2 cow
CO CO
O O O >HZfa fa
fa fa

CO

fa fa COco _ co^ J -a
3 ~5

222

-3 -

H H H HHHHHz z z 2 2 2 22
5 < c <1 <£ < •< <

fa

D

CO

M

co P

MW fa
fa

CO CO

3

S2S2coco5>-ww <COaSaSaSSoSaSaSOSaSaSaSaSaS fa<>

fa 25 w
25

>-

co

fa

O >- H
CO
S,
H
w
2’—*
h J Z
E_ M CO
<S2
S2
c
o
OOOu
2 co coQ Q OS co
Q O y y o y y Z Z Z g >« W
WW WWWWW
fa fa

fa fa
OOO
222

fa fa
fa fa

f a f a fa
< < <

<

<

j

S

Z

Z

c o O

O O U OJ J J J .J Z Z Z Z Z
<

< < <

<

j
D >d J><fa
fa fa< < CO

222

>«
OOO
fa
H H H H Q Q fiS
f a fa fa *5 ^
<
<
<
<
w
w
w
w
Q QOS co z 2 z< < < 22 E2 cococococococococo
f af af a f af a z ^^^S
faOOOOOOOO y y a a a a a j j j j j j - u j

.

2

<

<

<

<

<

<

<

<

<

>CO
f a CO ^5 «C<<<C<<<<<<C<U<<

19

AUTOMATIC TEXT ANALYSIS

entry in the list defining B and PT as equivalent stem-endings if thepreceding characters match.
The assumption (in the context of IR) is that if two words have thesame underlying stem then they refer to the same concept and should
be indexed as such. This is obviously an over-simplification since words
with the same stem, such as NEUTRON and NEUTRALISE, sometimes
need to be distinguished. Even words which are essentially equivalent
may mean different things in different contexts. Since there is no cheap
way of making these fine distinctions we put up with a certain
proportion of errors and assume (correctly) that they will not degrade
retrieval effectiveness too much.
It is inevitable that a processing system such as this will produce
errors. Fortunately experiments have shown that the error rate tends tobe of the order of 5 per cent (Andrews7). Lovins8’9 using a slightly
different approach to stemming also quotes errors of the same order ofmagnitude.
My description of the three stages has been deliberately undetailed,only the underlying mechanism has been explained. An excellent
description of a conflation algorithm, based on Lovins’ paper8 may befound in Andrews7, where considerable thought is given to
implementation efficiency.
Surprisingly, this kind of algorithm is not core limited but limited
instead by its processing time.
The final output from a conflation algorithm is a set of classes, one
for each stem detected. A class name is assigned to a document if andonly if one of its members occurs as a significant word in the text ofthe document. A document representative then becomes a list of classnames. These are often referred to as the documents index terms or
keywords.
Queries are of course treated in the same way. In an experimental
situation they can be processed at the same time as the documents. In
an operational situation, the text processing system needs to be applied
to the query at the time that it is submitted to the retrieval system.
Indexing

An index language is the language used to describe documents andrequests. The elements of the index language are index terms, which
may be derived from the text of the document to be described, or may
be arrived at independently. Index languages may be described as
pre-coordinate or post-coordinate, the first indicates that terms arecoordinated at the time of indexing and the latter at the time ofsearching. More specifically, in pre-coordinate indexing a logicalcombination of any index terms may be used as a label to identify a20

AUTOMATIC TEXT ANALYSIS

class of documents, whereas in post-coordinate indexing the same classwould be identified at search time by combining the classes of
documents labelled with the individual index terms.
One last distinction, the vocabulary of an index language may becontrolled or uncontrolled. The former refers to a list of approved
index terms that an indexer may use, such as for example used by
MEDLARS. The controls on the language may also include hierarchic
relationships between the index terms. Or, one may insist that certain
terms can only be used as adjectives (or qualifiers). There is really nolimit to the kind of syntactic controls one may put on a language.
The index language which comes out of the conflation algorithm inthe previous section may be described as uncontrolled, post-coordinate
and derived. The vocabulary of index terms at any stage in theevolution of the document collection is just the set of all conflation
class names.
There is much controversy about the kind of index language which isbest for document retrieval. The recommendations range from thecomplicated relational languages of Farradane et al. 10 and the Syntol
group (see Coates11 for a description) to the simple index terms
extracted by text processing systems just described. The main debate isreally about whether automatic indexing is as good as or better thanmanual indexing. Each can be done to various levels of complexity.
However, there seems to be mounting evidence that in both cases,
manual and automatic indexing, adding complexity in the form ofcontrols more elaborate than index term weighting do not pay
dividends. This has been demonstrated by the results obtained byCleverdon et al.12, Aitchison et al.12, Comparative Systems
Laboratory14 and more recently Keen and Diggerls. The message is that
uncontrolled vocabularies based on natural language achieve retrieval
effectiveness comparable to vocabularies with elaborate controls. This isextremely encouraging, since the simple index language is the easiest to
automate.
Probably the most substantial evidence for automatic indexing hascome out of the SMART Project (1966). Salton16 recently
summarised its conclusions: ‘. .. on the average the simplest indexing
procedures which identify a given document or query by a set of terms,
weighted or unweighted, obtained from document or query text arealso the most effective’. Its recommendations are clear, automatic text
analysis should use weighted terms derived from document excerpts
whose length is at least that of a document abstract.
The document representatives used by the SMART project are moresophisticated than just the lists of stems extracted^y conflation. Thereis no doubt that stems rather than ordinary word forms are more
effective (Carroll and Debruyn17). On top of this the SMART project21

AUTOMATIC TEXT ANALYSIS

adds index term weighting, where an index term may be a stem or someconcept class arrived at through the use of various dictionaries. For
details of the way in which SMART elaborates its document
representatives see Salton18.
In the next sections I shall give a simple discussion of the kind of
frequency information that may be used to weight document
descriptors and explain the use of automatically constructed termclasses to aid retrieval.

Index term weighting

Traditionally the two most important factors governing theeffectiveness of an index language have b&n thought to be theexhaustivity of indexing and the specificity of the index language.
There has been much debate about the exact meaning of these twoterms. Not wishing to enter into this controversy I shall follow Keenand Digger15 in giving a working definition of each.
For any document, indexing exhaustivity is defined as the numberof different topics indexed, and the index language specificity is theability of the index language to describe topics precisely. Keen andDigger further define indexing specificity as the level of precision withwhich a document is actually indexed. It is very difficult to quantify
these factors. Human indexers are able to rank their indexing
approximately in order of increasing exhaustivity or specificity.
However, the same is not easily done for automatic indexing.
It is of some importance to be able to quantify the notions ofindexing exhaustivity and specificity because of the predictable effectthey have on retrieval effectiveness. It has been recognised(Lancaster19) that a high level of exhaustivity of indexing leads to highrecall* and low precision*. Conversely a low level of exhaustivity leads
to low recall and high precision. The converse is true for levels ofindexing specificity, high specificity leads to high precision and low
recall, etc. It would seem, therefore, that there is an optimum level ofindexing exhaustivity and specificity for a given user population.
Quite a few people (Sparck Jones20’21, Salton and Yang22), haveattempted to relate these two factors to document collection statistics.
For example, exhaustivity can be assumed to be related to the numberof index terms assigned to a given document, and specificity related to
the number of documents to which a given term is assigned in a given
collection. The importance of this rather vague relationship is that thetwo factors are related to the distribution of index terms in the* These terms are defined in the introduction on page 9.

22

AUTOMATIC TEXT ANALYSIS

collection. The relationships postulated are consistent with theobserved trade-off between precision and recall just mentioned.
Changes in the number of index terms per document lead tocorresponding changes in the number of documents per term and viceversa.
I am arguing that in using distributional information about index
terms to provide, say, index term weighting we are really attacking theold problem of controlling exhaustivity and specificity.
If we go back to Luhn’s original ideas, we remember that hepostulated a varying discrimination power for index terms as a functionof the rank order of their frequency of occurrence, the highest
discrimination power being associated with the middle frequencies. His
model was proposed for the selection of significant terms from adocument. However, the same frequency counts can be used to provide
a weighting scheme for the individual terms in a document. In fact
there is a common weighting scheme in use which gives each index terma weight directly proportional to its frequency of occurrence in the
document. At first this scheme would appear to be inconsistent with
Luhn’s hypothesis that the discrimination power drops off at higher
frequencies. However, referring back to Figure 2.1, the scheme would
be consistent if the upper cut-off is moved to the point where the peakoccurs. It is likely that this is in fact what has happened in experiments
using this particular form of weighting.
Attempts have been made to apply weighting based on the way theindex terms are distributed in the entire collection. The index term
vocabulary of a document collection often has a Zipfian distribution,that is, if we count the number of documents in which each index term
occurs and plot them according to rank order then we obtain the usual
hyperbolic shape. Sparck Jones20 showed experimentally that if there
are N documents and an index term occurs in n of them then a weightof log(N/n) + 1 leads to more effective retrieval than if the term wereused unweighted. If indexing specificity is assumed to be inversely
proportional to the number of documents in which an index term
occurs then the weighting can be seen to be attaching more importanceto the more specific terms.
The difference between the last mode of weighting and the previous
one may be summarised by saying that document frequency weighting
places emphasis on content description whereas weighting by specificity
attempts to emphasise the ability of terms to discriminate one
document from another.
Salton and Yang22 have recently attempted to combine bothmethods of weighting by looking at both inter document frequencies
and intra document frequencies. Their conclusions are really an
extension of those reached by Luhn. By considering both the total
23

AUTOMATIC TEXT ANALYSIS

frequency of occurrence of a term and its distribution over the
documents, that is, how many times it occurs in each document, they
were able to draw several conclusions. A term with high total frequencyof occurrence is not very useful in retrieval irrespective of its
distribution. Middle frequency terms are most useful particularly if the
distribution is skewed. Rare terms with a skewed distribution are likely
to be useful but less so than the middle frequency ones. Very rare terms
are also quite useful but come bottom of the list except for the ones
with a high total frequency. The experimental evidence for these
conclusions is insufficient to make a more precise statement of their
merits.

Automatic keyword classification
Many automatic retrieval systems rely on thesauri to modify queries
and document representatives to improve the chance of retrieving
relevant documents. Salton23 has experimented with many different
kinds of thesauri and concluded that many of the simple ones justify
themselves in terms of improved retrieval effectiveness.
In practice many of the thesauri are constructed manually. They
have mainly been constructed in two ways:(1) words which are deemed to be about the same topic are linked;(2) words which are deemed to be about related things are linked.
The first kind of thesaurus connects words which are intersubstitutible,that is, it puts them into equivalence classes. Then one word could bechosen to represent each class and a list of these words could be used toform a controlled vocabulary. From this an indexer could be instructed
to select the words to index a document, or the user could be
instructed to select the words to express his query. The same thesaurus
could be used in an automatic way to identify the words of a query forthe purpose of retrieval.
The second kind of thesaurus uses semantic links between words to,for example, relate them hierarchically. The manually constructed
thesaurus used by the MEDLARS system is of this type.
However, methods have been proposed to construct thesauriautomatically. Whereas the manual thesauri are semantically based (e.g.
they recognise synonyms, more general, or more specific relationships)
the automatic thesauri tend to be syntactically and statistically based.
Again the use of syntax has proved to be of little value so I shallconcentrate on the statistical methods. These are based mainly on thepatterns of co-occurrence of words in documents. These ‘words’ are24

AUTOMATIC TEXT ANALYSIS

often the descriptive items which were introduced earlier as terms or
keywords.
The basic relationship underlying the automatic construction of
keyword classes is as follows. If keyword a and b are substitutible for
one another in the sense that we are prepared to accept a document
containing one in response to a request containing the other, this will
be because they have the same meaning or refer to a common subject or
topic. One way of finding out whether two keywords are related is bylooking at the documents in which they occur. If they tend to co-occur
in the same documents the chances are that they have to do with thesame subject and so can be substituted for one another.
It is not difficult to see that based on this principle a classification of
keywords can be automatically constructed, of which the classes areused analogously to those of the manual thesaurus mentioned before.
More specifically we can identify two main approaches to the use of
keyword classifications:(1) replace each keyword in a document (and query) representativeby the name of the class in which it occurs;(2) replace each keyword by all the keywords occurring in the class
to which it belongs.
If we think of a simple retrieval strategy as operating by matching on
the descriptors, whether they be keyword names or class names, then‘expanding’ representatives in either of these ways will have the effectof increasing the number of matches between document and query, andhence tends to improve recall*. The second way will improve precision
as well. Sparck Jones24 has reported a large number of experiments
using automatic keyword classifications and found that in general one
obtained a better retrieval performance with the aid of automatic
keyword classification than with the unclassified keywords alone.
Unfortunately even here the evidence has not been conclusive. The
work by Minker et al.25 has not confirmed the findings of Sparck Jones,
and in fact they have shown that in some cases keyword classification
can be detrimental to retrieval effectiveness. Salton26, in a review of thework of Minker et al., has questioned their experimental design whichleaves the question of the effectiveness of keyword classification still tobe resolved by further research.
The discussion of keyword classifications has by necessity beenrather sketchy. Readers wishing to pursue it in greater depth should
consult Sparck Jones’s book24 on the subject. We shall briefly return toit when we discuss automatic classification methods in Chapter 3.

* Recall is defined in the introduction.
IR -3

25

AUTOMATIC TEXT ANALYSIS

Normalisation

It is probably useful at this stage to recapitulate and show how anumber of levels of normalisation of text is involved in generating
document representatives. At the lowest level we have the document
which is merely described by a string of words. The first step innormalisation is to remove the ‘fluff words. We now have what
traditionally might have been called the ‘keywords’. The next stage
might be to conflate these words into classes and describe documentsby sets of class names which in modern terminology are the keywords
or index terms. The next level is the construction of keyword classes byautomatic classification. Strictly speaking this is where thenormalisation stops.
Index term weighting can also be thought of as a process ofnormalisation, if the weighting scheme takes into account the numberof different index terms per document. For example we may wish toensure that a match in one term among ten carries more weight than
one among twenty. Similarly, the process of weighting by frequency ofoccurrence in the total document collection is an attempt to normalise
document representatives with respect to expected frequency
distributions.
Bibliographic remarks

The early work of H. P. Luhn has been emphasised in this chapter.
Therefore, the reader may like to consult the book by Schultz27 whichcontains a selection of his papers. In particular, it contains his 1957 and1958 papers cited in the text. Some other early papers which have had
an impact on indexing are Maron and Kuhns28, and its sequel inMaron29. The first paper contains an attempt to construct a
probabilistic model for indexing. An interesting paper which seems tohave been largely ignored in the IR literature is Simon30. Simon
postulates a stochastic process which will generate a distribution for
word frequencies similar to the Zipfian distribution. Doyle31 examines
the role of statistics in text analysis. A recent paper by Sparck Jones32
compares many of the different approaches to index term weighting. A
couple of state-of-the-art reports on automatic indexing are Stevens33
and Sparck Jones34. Finally, Salton35 has compiled a report containing
a theory of indexing.
References
1. SPARCK JONES, K. and KAY, M., Linguistics and Information Science,
Academic Press. New York and London (1973 )26

AUTOMATIC TEXT ANALYSIS
2. MONTGOMERY, C. A., ‘Linguistics and information scienct ' , Journal o f theAmerican Society for Information Science, 23, 195-219 (1972)
3. KEENAN, E. L., ‘On semantically based grammar’, Linguistic Inquiry, 3,413-461 (1972)
4. LUHN, H. P., ‘The automatic creation of literature abstracts’, IBM Journal o f
Research and Development, 2, 159-165 (1958)
5. ZIPF, H. P., Human Behavior and the Principle o f Least Effort,
Addison-Wesley, Cambridge, Massachusetts (1949)
6. EDMONDSON, H. P. and WYLLYS, R. E., ‘Automatic abstracting andindexing survey and recommendations’, Communications o f the ACM, 4,
226-234 (1961)
7. ANDREWS, K., ‘The development of a fast conflation algorithm for English’.
Dissertation submitted for the Diploma in Computer Science, University ofCambridge (unpublished) (1971)
8. LOVINS, B.J., ‘Development of a stemming algorithm’. MechanicalTranslation and Computational Linguistics, 11,22-31 (1968)
9. LOVINS, B. J., ‘Error evaluation for stemming algorithms as clustering
algorithms’, Journal o f the American Society for Information Science, 22,
28-40 (1971)
10. FARRADANE, J., RUSSELL, J.M. and YATES-MERCER, A., ‘Problems in
information retrieval. Logical jumps in the expression of information’,Information Storage and Retrieval, 9 ,6 5 -7 7 (1973)
11. COATES, E. J., ‘Some properties o f relationships in the structure of indexing
languages’, Journal o f Documentation, 29, 390-404 (1973)
12. CLEVERDON, C. W., MILLS, J. and KEEN, M., Factors Determining the
Performance o f Indexing Systems, Vol. I, Design, Vol. II, Test Results,
ASLIB Cranfield Project, Cranfield (1966)
13. AITCHISON, T. M„ HALL, A. M„ LAVELLE, K. H. and TRACY, J. M„
Comparative Evaluation o f Index Languages, Part I, Design, Part II, Results,
Project INSPEC, Institute o f Electrical Engineers, London (1970)
14. Comparative Systems Laboratory, An Inquiry into Testing o f Information
Retrieval Systems, 3 Vols. Case-Western Reserve University (1968)
15. KEEN, E. M. and DIGGER, J. A., Report o f an Information Science Index
Languages Test, Aberystwyth College of Librarianship, Wales (1972)
16. SAL TON, G., ‘Automatic text analysis’, Science, 168, 335-343 (1970)
17. CARROLL, J. M. and DEBRUYN, J. G., ‘On the importance of root-stem
truncation in word-frequency analysis’, Journal o f the American Society for
Information Science, 21, 368-369 (1970)
18. SALTON, G., Automatic Information Organization and Retrieval,
McGraw-Hill, New York (1968)
19. LANCASTER, F. W., Information Retrieval Systems: Characteristics, Testingand Evaluation, Wiley, New York (1968)
20. SPARCK JONES, K., ‘A statistical interpretation of term specificity and its
application in retrieval’, Journal o f Documentation, 28, 11-21 (1972)
21. SPARCK JONES, K., ‘Does indexing exhaustivity matter?’, Journal o f theAmerican Society for Information Science, 24,313-316 (1973)
22. SALTON, G. and YANG, C. S., ‘On the specification of term values in
automatic indexing’, Journal o f Documentation, 29, 351-372 (1973)
23. SALTON, G., ‘Experiments in automatic thesaurus construction for
information retrieval’, Proceedings IFIP Congress 1971, TA-2, 43-49 (1971)
24. SPARCK JONES, K., Automatic Keyword Classification for Information
Retrieval, Butterworths, London (1971)
25. MINKER, J., WILSON, G. A. and ZIMMERMAN, B. H„ ‘An evaluation of27

AUTOMATIC TEXT ANALYSIS
query expansion by the addition of clustered terms for a document retrieval
system’, Information Storage and Retrieval, 8, 329-348 (1972)
26. SALTON, G., ‘Comment on “an evaluation of query expansion by theaddition of clustered terms for a document retrieval system” .’ Computing
Reviews, 14, 232 (1973)
27. SCHULTZ, C. K., H. P. Luhn: Pioneer o f Information Science-Selected
Works, Macmillan, London (1968)
28. MARON, M. E. and KUHNS, J. L., ‘On relevance, probabilistic indexing andinformation retrieval’, Journal o f the ACM, 7, 216-244 (1960)
29. MARON, M. E., ‘Automatic indexing: an experimental enquiry’, Journal o f
the ACM, 8, 404-417 (1961)
30. SIMON, H. A., ‘On a class of skew distributions’, Biometrika, 42, 425-440(1955)
31. DOYLE, L. B., ‘The microstatistics of text', Information Storage andRetrieval, 1, 189-214 (1963)
32. SPARCK JONES, K., ‘Index term weighting’, Information Storage andRetrieval, 9 ,6 19 -6 3 3 (1973)
33. STEVENS, M. E., Automatic Indexing: A State o f the A rt Report,
Monograph 91, National Bureau of Standards, Washington (1965)
34. SPARCK JONES, K., Automatic Indexing: A State o f the A rt Review, review
commissioned by the Office for Scientific and Technical Information,
London (1974)
35. SALTON, G., A Theory o f Indexing, Technical report No. TR74-203,
Department of Computer Science, Cornell University, Ithaca, New York(1974)

28