IMPROVING SUBJECT RETRIEVAIm IN ONLINE CATALOGUES&s. -A>2ekmmm
Stephen Walker andRichard M Jones

British Libra* y Research Paper 24

I m p r o s / ±n giLr-is u b j e c t

o r - i L ± n e

1. S t e m m i n g ,andStephenerat a L

automatico g u e sspelling

cross-reference

Walkerr e t r x e v a L

tablesand Richard

with contributions

correction

M Jonesby N i c k y Johns

The Polytechnic of Central London
1387

British Library Research Paper 2L^

1.15

f <v H
British Library Cataloguing in Publication Data

Walker, Stephen
Improving subject retrieval in online
catalogues.
(British Library research
paper, ISSN 0269-9257; 24).
1 :, Stemming, automatic spelling correction
and cross-reference tables
1. Catalogs, On-line
I. Title II. Jones, Richard M. III.Series
025.3'13
Z699
ISBN 0-7123-3129-85tephen Walker worked in management services in industry, and as amathematician, before moving into information science. He hastaught information science and computing in several institutions,and worked on the design of information systems. Since 1982 he has
worked exclusively in the field of online catalogues, both at the
Polytechnic of Central London and as Technical Consultant to
Swalcap Library 5ervices Ltd, Bristol.
Richard Jones is a librarian who worked for three years in the
Library of the University of London Institute of Education before
joining the Okapi projects. He surveyed the operation of the Geac
online catalogue at the Polytechnic of the South bank for his
Masters' dissertation.

©

The British Library Board 1387

The opionions expressed in this report are those of the authors
and not necessarily those of the British Library.
5I/G/720

BritishLibrary Research Papers are published by the British
Library and distributed by the British Library Publications 5ales
Unit, Boston Spa, Wetherby, West Yorkshire L523 7BQ, UK. In the
USA and Canada they are distributed by Longwood Publishing Group
Inc, 27 5outh Main Street, Wolfeboro, New Hampshire 03834-2069,
USA. In Japan they are distributed by Kinokuniya Co Ltd, P0 Box
55, Chitose, Tokyo 156.

Printed in Great Britain by the British Library.

-li-P r e f a c eThis report describes research ?.nto practical ways of
improving subject access in online catalogues. This ispart of a continuing programme which began in 1982 with theoriginal Okapi project [13. This is not a "final" report.
The next phase, on the use of relevance feedback, will be
published in 1988.
The work described here is concerned both with librarianship and with computing, particularly linguistic computing.
Some knowledge of online catalogues and of computing andlibrary jargon is assumed. We refer, for example, to"generations" of online catalogues, to "phrase" and"keyword-type" catalogues, subject searching and specific
Cor known-) item searching, to headings, entries, fields
and records. The most important source for backgroundmaterial to this report is [13. For online catalogues ingeneral, Hildreth's 1983 monograph C2J and his PRIST survey[33 ar& recommended.
The most useful work on subject
searching problems is Markey's book C 4 ] .
Rcknowledgment s
This work would not have been possible without the help andsupport of the British Library Research and Devlopment
Department. Particular thanks are due to Maureen Grieves
and to Derek Greenwood, who is now our project officer'.
We ar& also most grateful to Neil McLean (Project Head andHead of Library Services, Polytechnic of Central London},to Maura Coghlan Csite librarian of our test library} andto Dave Roberts and his staff at the Poytechnic's Computing
Services.
Others at PCL who have helped us include Winifred Hbbott
CTechnical Services Librarian), Jacky Conroy C5ystems
Librarian), Pat Manson (Information Officer, LibraryTechnology Centre) and Penny Pope CChief Cataloguer}. Manyother people have helped us with advice, criticism andencouragement.
They include Philip Bryant CDirector of theCentre for Catalogue Research), Charles Hildreth (RERD
L t d ) , Karen Markey (University of Michigan), Martin Porter(Scott Polar Research Institute) and Peter WiLLett(Sheffield University). Gilt Venner (Plymouth Polytechnic,
late of the Ukapi team) helped with the rewriting of someof the Okapi programs.

-121-

Hreface

Credits
It would not have been possible to design and program theexperimental catalogues used in this project without thefoundation provided by the original Okap:]. system.
This wasdesigned and written by Nathalie Mitev, Gill Venner andStephen Walker. The additional programs were written by
Nicky Johns and Stephen Walker. Nicky Johns did much of
the detailed design and wrote some complex programs withgreat speed and accuracy. Richard Jones made substantial
contributions to the design and did most of the evaluation
work - interviewing users and repeating searches. H e also
wrote a survey of methods of improving retrieval in subject
searching. Chapters 3, 4 and 5 of this report are condensed from this survey, which we hope will be publishedseparately Cit is too Long to be incorporated in fullhere}. Parts of Chapter B were written by Nicky Johns.
Most of the rest of the report was written by 5tephen
Walker, who is responsible for the inevitable inaccuracies.
It has not been easy to reconcile the demands of readability and conciseness with the need to include enoughdetail for other designers to be able to benefit from thiswork. It is hoped that complete Gkapi specifications will
be published Later this year, together with program sourcecode. Meanwhile, anyone wanting additional detailed information should contact Stephen Walker at PCL.

References
1 MITEV N N, VENNER G M and WRLKER 5. Designing
publicaccess catalogue: Okapi,a catalogue

an online
on a

local

area network
CLibrary and Information Research Report393. London : the British Library, 1385.
2 HILDRETH C R. Online

interface.

PublicAccess Catalogs: the user

OCLC Online Computer Library Center, 1S82.

3 WILLIPM5 M E CeditorD. Hnnual
Science and Technology.

Review of

Vol 20.

Information

Knowledge Industry

Publications, 1985.
A MRRKEY K. Subject searching in librarycatalogs: before
and after
the introductionof online catalogs. OCLC

Online Computer Library Center, 1S84.

-lv-

C o n t e n t s

List of figuresx

List of tablesxi

1

Introduction

1

1.1
1.2
1.3
1.4
1.5
1.6

The project proposal
Motivation
1.2.1 Feasibility study
5taffing
Environment
Historical summary of the project
The report

1
1
2
2
2
3
6

2

Subject searching problems

7

2.1
2.2
2.3

7
8
3

2.5

Introduction
What users bring to the catalogue
5ubject searching facilities in current online
catalogues
2.3.1 Phrase searching
2.3.2 Problems with subject headings
2.3.3 Keyword searching
2.3.4 Recess points
2.3.5 Recess method
How might subject access be improved?
2.4.1 Truncation and stemming
2.4.2 Cross-reference and other lookup facilities
2.4.3 5pelling correction
CITE

9
9
10
11
11
12
12
14
15
16

3

Stemming and truncation

21

3.1
3.2

Introduction
Methods and techniques in algorithm construction
3.2.1 Iterative or Idngest match?
3.2.2 Conditional rules
3.2.3 Stem modification
3.2.4 Compilation of the suffix list
3.2.5 Users1 needs

21
21
22
22
22
22
23

2.4

-v-

3.3

3.4
3.5

Conflation algorithms : a review
3.3.1 INTREX
3.3.2 RRDCOL
3.3.3 Generation of suffix lists
3.3.4 IN5PEC
3.3.5 5temning in 5MRRT and FIRST
3.3.6 MDRPH5
3.3.7 Cercone and linguistic analysis
3.3.6 MORS
3.3.9 Porter
3.3.10 Dawson
Evaluating conflation algorithms
Stemming in online catalogues
3.5.1 Choice of stemming procedure for online
catalogues

23
23
23
24
24
25
25
26
26
27
28
29
29
30

4 Tables and dictionaries

33

4.1
4.2

33
33
33
34

4.3

Introduction
Methods and techniques'}.2.1 Dictionaries in spelling correction
4.2.2 Proof-reading methods
4.2.3 Spelling correction using a dictionary
together with a word representation
technique4.2.4 Using tables to match related words
4.2.5 Linking natural language terms with
controlled language terms
4.2.6 Compound words and homographs
4.2.7 Stop lists
The use of tables in online catalogues

35
35
36
37
37
37

5 Fuzzy matching and spelling correction

41

5.1
5.2

41
41
41
42

5.3

5.4

Introduction
N-grams
5.2.1 Definition and applications
5.2.2 Use of n-gram techniques to improve recall
5.2.3 Use of n-gram techniques to detect spelling
errors
5.2.4 Different values of n
5.2.5 Effectiveness tests
Soundex, soundex-type and other abbreviation codes
5.3.1 Definition and applications
5.3.2 Use of soundex-type codes: a survey
Fuzzy matching in online catalogues
5.4.1 Spelling correction
5.4.2 Spelling correction using n-grams
5.4.3 Soundex-type codes in online catalogues

43
45
45
46
46
47
49
49
50
51

6 Design and implementation
6.1
6.2

6.3

6.4

6.5

6.6
6.7

6.8
6.5

Introduction
Stemming and spelling standardisation
6.2.1 Background6.2.2 Functional design considerations
6.2.3 Strong and weak stemming
6.2.4 Spelling standardisation
6.2.5 Two levels of stemming
6.2.6 Interaction design
6.2.7 Choice of stemming procedure
6.2.B Stage one - weak stemming and spellingstandardisation
6.2.9 Stage two - strong stemming
6.2.10 Discussions and examples
6.2.11 Some oddities
Phrases and the go/see list
6.3.1 Categories of equivalence class
6.3.2 Phrases
6.3.3 Problems in searching for phrases
6.3.4 Other go/see list categories
6.3.5 R note on stemming and indexing
Spelling correction
6.4.1 Dictionary
6.4.2 Selection of candidate replacements
6.4.3 Finding the nearest match
6.4.4 Discussion of the spelling correction
technique
Search processing and term combination
6.5.1 Preprocessing and index lookup
6.5.2 Rssignment of term weights
6.5.3 Calculation of 'good1 and •acceptable"
weights for record retrieval
6.5.4 Merging the posting lists
The bibliographic file
The subject index
6.7.1 Indexing and the go/see list
6.7.2 Source fields
6.7.3 Index contents and size
Storage requirements
The Okapi '86 programs

7 System description
7.1
7.2
7.3
7.4

7.5

Introduction
Keyboard and display
User input and preprocessing
The search
7.4.1 Control system
7.4.2 Experimental system
Term combination - the merge

7.6

7.7

Record display
7.6.1 Highlighting of search terms in records
7.6.2 Sequencing of displayed records
7.6.3 Options following record display
Second and subsequent input screens

102
103
104
104
105

8 Evaluation

107

8.1
8.2

Objects of the evaluation
Methodology
8.2.1 Evaluation considerations
8.2.2 Controlled or uncontrolled experiments?
8.3 Data collection and collation
8.3.1 Rcceptance tests
8.3.2 Observation and interviewing
8.3.3 The interview
8.3.4 Transaction log data
8.3.5 Searches and sessions
8.3.6 The 5RCHE5 file
8.3.7 Description of the 5RCHE5 file
8.4 Rnalysis of observation and interview data
8.4.1 5uccess rate reported by users
8.4.2 Brief analysis of the 17 'failure' sessions
8.4.3 Comments made by interviewed users
8.5 Statistical analysis of 5RCHE5 file
8.5.1 Distribution of number of records retrievedby system
8.6 Repetition of searches by experimenter
8.6.1 Notes on method
8.6.2 Measures of success
8.6.3 Experimenters' relevance judgments
8.6.4 5earches which retrieved no 'good' records:
EXP vs. CTL
8.6.5 Comparison of recall on first search of
session
8.7 Treatment of users' words which are not in theindex
8.7.1 Misspellings and miskeyings
8.7.2 Legitimate words which are not in the file
8.7.3 The effect of stemming on spelling correction
8.7.4 User response to 'CPN'T FIND' messages
8.7.5 Is spelling correction worth while?
8.8Conclusions
Use of theandgo/seelist
9
recommendations

107
108
108
109
109
110
111
111
112
113
113
115
116
116
117
119
121

9.1
9.2

137
138
138
139

Introduction
Stemming
9.2.1 Weak stemming
9.2.2 Spelling standardisation

121
124
124
124
125
125
126
129
129
131
132
132
133
134
137

9.2.3 5trong stemming
9.2.4 Answers to the questions on stemming
9.2.5 Recommendations on stemming
5pelling correction
9.3.1 Recommendations and discussion
Cross-reference tables - the go/see List
9.4.1 Rnswers to the questions on cross-referencetables
9.4.2 Recommendations on cross-reference tables
Users' perception of and behaviour with the system
Applicability of our findings
Concluding remarks

9.3
9.4

9.5
9.6
9.7

140
141
142
142
143
144
144
145
146
148
149

Appendixes
1
2
3
4
5

The soundex algorithm
The word-matching algorithm
Extracts from a log file
Notes on some failed searches
List of equivalence classes of terms used in theexperimental catalogue Cgo/see listD

151
152
153
160
167

References

172

Index

180

-lx-

C3-F

7.1 Introductory screen
90
7.2 Empty input screen
90
7.3 Input screen after user has started to type
91
7.4 5creen during Lookup (.EXP system)94
7.5 Display while looking up - word not found95
7.6 Retyping a misspelt word96
7.7 Display during and after merging
97
7.8 EXP system suggests a replacement99
7.9 User accepts suggested replacement99
7.10 R search for two common terms which do not co-occur 101
7.11 Two ,rarei terms which do not co-occur
101
7.12 Full record display
103
7.13 Subsequent input screen showing the results ofprevious searches
105
7.14 Improved subsequent input screen
105

LdLs-t

C3-F- b s t u L e s

2.1

R sample of subject searches

9

6.1

Types of word used in subject searches COkapi '84)

59

8.1
8.2
8.3
8.4

5uccess rate for observed searches by system
117
Proportion of "zero hits' searches by system
121
Distribution of number of terms in searches
122
Proportion of "good weight" searches by system by
number of terms in search
123
8.5 Searches which found no records of "good* weight on
CTL repeated on EXP
126
8.6 Repetition of initial searches
127
8.7 Initial searches which were the same in CTL as in
05TEM but retrieved more records in EXP
128
8.8 Treatment of misspellings and miskeyings
130
8.9 Legitimate words which were not in the file131
8.10 Response to 'CRN'T FIND" by system
134
8.11 List of go/see entries used in the searches
13b-xi-