IMPROVING SUBJECT RETRIEVAI m IN ONLINE CATALOGUES
&s
. -A>2ek

m m m
Stephen Walker and Richard M Jones

British Libra* y Research Paper 24

I m p r o s / ±n g iLr-i

s u b j e c t erat a L

r e t r x e v a L o g u e s correction

o r - i L ± n e

1. S t e m m i n g , and

automatic

spelling

cross-reference

tables

Stephen

Walker

and Richard

M Jones

with contributions

by N i c k y Johns

The Polytechnic of Central London 1387

British Library Research Paper 2L^

f <v H
British Library Cataloguing in Publication Data

1.15

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-8
5tephen Walker worked in management services in industry, and as a mathematician, before moving into information science. He has taught 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

British Library 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 e
This report describes research ?.nto practical ways of improving subject access in online catalogues. This is part of a continuing programme which began in 1982 with the original 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 and library 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 background material to this report is [13. For online catalogues in general, 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 and support 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 and Head of Library Services, Polytechnic of Central London}, to Maura Coghlan Csite librarian of our test library} and to 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, Library Technology Centre) and Penny Pope CChief Cataloguer}. Many other people have helped us with advice, criticism and encouragement. They include Philip Bryant CDirector of the Centre 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 some of the Okapi programs.

-121-

Hreface

Credits It would not have been possible to design and program the experimental catalogues used in this project without the foundation provided by the original Okap:]. system. This was designed and written by Nathalie Mitev, Gill Venner and Stephen 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 with great 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 published separately Cit is too Long to be incorporated in full here}. 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 enough detail for other designers to be able to benefit from this work. It is hoped that complete Gkapi specifications will be published Later this year, together with program source code. Meanwhile, anyone wanting additional detailed information should contact Stephen Walker at PCL.

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

an online
on a local

area network CLibrary and Information Research Report 393. London : the British Library, 1385.
2 HILDRETH C R. Online Public Access Catalogs : the user

interface.

OCLC Online Computer Library Center, 1S82. Review of Information

3 WILLIPM5 M E CeditorD. Hnnual
Science and Technology.

Vol 20.

Knowledge Industry

Publications, 1985.
A MRRKEY K. Subject searching in library catalogs : before and after the introduction of online catalogs. OCLC

Online Computer Library Center, 1S84.

-lv-

C o n t e n t s

List of figures List of tables

x xi

1 1.1 1.2 1.3 1.4 1.5 1.6 2 2.1 2.2 2.3

Introduction The project proposal Motivation 1.2.1 Feasibility study 5taffing Environment Historical summary of the project The report Subject searching problems 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 Stemming and truncation 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

1 1 1 2 2 2 3 6 7 7 8 3 9 9 10 11 11 12 12 14 15 16 21 21 21 22 22 22 22 23

2.4

2.5 3 3.1 3.2

-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 33 33 33 33 34

4 Tables and dictionaries 4.1 4.2 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 technique 4.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 41 41 41 41 42 43 45 45 46 46 47 49 49 50 51

4.3

5 Fuzzy matching and spelling correction 5.1 5.2 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

5.3

5.4

6 Design and implementation 6.1 6.2 Introduction Stemming and spelling standardisation 6.2.1 Background 6.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 spelling standardisation 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

6.3

6.4

6.5

6.6 6.7

6.8 6.5

7 System description 7.1 7.2 7.3 7.4 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.5

7.6

7.7

Record 7.6.1 7.6.2 7.6.3 Second

display Highlighting of search terms in records Sequencing of displayed records Options following record display and subsequent input screens

102 103 104 104 105 107 107 108 108 109 109 110 111 111 112 113 113 115 116 116 117 119 121 121 124 124 124 125 125 126 129 129 131 132 132 133 134 137 137 138 138 139

8 Evaluation 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 retrieved by 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 the index 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.8 Use of the go/see list 9 Conclusions and recommendations 9.1 9.2 Introduction Stemming 9.2.1 Weak stemming 9.2.2 Spelling standardisation

9.3 9.4

9.5 9.6 9.7

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-reference tables 9.4.2 Recommendations on cross-reference tables Users' perception of and behaviour with the system Applicability of our findings Concluding remarks

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 the experimental catalogue Cgo/see listD 151 152 153 160 167 172 180

References Index

-lx-

C3-F

7.1 7.2 7.3 7.4 7.5 7.6 7.7 7.8 7.9 7.10 7.11 7.12 7.13

Introductory screen Empty input screen Input screen after user has started to type 5creen during Lookup (.EXP system) Display while looking up - word not found Retyping a misspelt word Display during and after merging EXP system suggests a replacement User accepts suggested replacement R search for two common terms which do not co-occur Two ,rarei terms which do not co-occur Full record display Subsequent input screen showing the results of previous searches 7.14 Improved subsequent input screen

90 90 91 94 95 96 97 99 99 101 101 103 105 105

LdLs-t 2.1 6.1 8.1 8.2 8.3 8.4

C3-F

- b s t u L e s 9 59 117 121 122 123 126 127 128 130 131 134 13b

R sample of subject searches Types of word used in subject searches COkapi '84)

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

-xi-