InformationRetrievalDataStructuresandAlgorithms(WilliamB.Frakes,RicardoBaeza-Yates)资源-CSDN文库

5星 · 超过95%的资源需积分: 9 194 浏览量 2009-06-26 17:56:02 上传评论 1 收藏 2.71MB PDF 举报

资源推荐

资源详情

资源评论

CHAPTER 1: INTRODUCTION TO INFORMATION STORAGE AND RETRIEVAL

SYSTEMS.............................................................................................................................. 9

1.1 INTRODUCTION............................................................................................................ 9

1.2 A DOMAIN ANALYSIS OF IR SYSTEMS.................................................................10

1.2.1 Conceptual Models of IR ......................................................................................... 11

1.2.2 File Structures.......................................................................................................... 12

1.2.3 Query Operations.....................................................................................................13

1.2.4 Term Operations...................................................................................................... 13

1.2.5 Document Operations .............................................................................................. 14

1.2.6 Hardware for IR.......................................................................................................14

1.2.7 Functional View of Paradigm IR System ................................................................ 15

1.3 IR AND OTHER TYPES OF INFORMATION SYSTEMS.........................................17

1.4 IR SYSTEM EVALUATION......................................................................................... 18

1.5 SUMMARY....................................................................................................................20

REFERENCES ..................................................................................................................... 21

CHAPTER 2: INTRODUCTION TO DATA STRUCTURES AND ALGORITHMS

RELATED TO INFORMATION RETRIEVAL.................................................................. 22

2.1 INTRODUCTION.......................................................................................................... 22

2.2 BASIC CONCEPTS.......................................................................................................22

2.2.1 Strings ......................................................................................................................23

2.2.2 Similarity between Strings....................................................................................... 23

2.2.3 Regular Expressions ................................................................................................ 23

2.2.4 Finite Automata.......................................................................................................25

2.3 DATA STRUCTURES ...................................................................................................27

2.3.1 Search Trees.............................................................................................................27

2.3.2 Hashing....................................................................................................................29

2.3.3 Digital Trees ............................................................................................................ 30

2.4 ALGORITHMS .............................................................................................................. 32

2.4.1 Retrieval Algorithms ...............................................................................................33

2.4.2 Filtering Algorithms ................................................................................................ 34

2.4.3 Indexing Algorithms................................................................................................ 34

REFERENCES ..................................................................................................................... 35

CHAPTER 3: INVERTED FILES ....................................................................................... 38

3.1 INTRODUCTION.......................................................................................................... 38

3.2 STRUCTURES USED IN INVERTED FILES .............................................................40

3.2.1 The Sorted Array .....................................................................................................40

3.2.2 B-trees......................................................................................................................40

3.2.3 Tries ......................................................................................................................... 41

3.3 BUILDING AN INVERTED FILE USING A SORTED ARRAY...............................41

3.4 MODIFICATIONS TO THE BASIC TECHNIQUE ..................................................... 44

3.4.1 Producing an Inverted File for Large Data Sets without Sorting ............................ 44

3.4.2 A Fast Inversion Algorithm..................................................................................... 47

3.5 SUMMARY....................................................................................................................52

REFERENCES ..................................................................................................................... 52

CHAPTER 4: SIGNATURE FILES..................................................................................... 54

4.1 INTRODUCTION.......................................................................................................... 54

4.2 BASIC CONCEPTS.......................................................................................................56

4.3 COMPRESSION ............................................................................................................ 59

4.3.1 Bit-block Compression (BC)................................................................................... 59

4.3.2 Variable Bit-block Compression (VBC).................................................................60

4.3.3 Performance.............................................................................................................62

4.4 VERTICAL PARTITIONING ....................................................................................... 62

4.4.1 Bit-Sliced Signature Files (BSSF)...........................................................................63

4.4.2 B'SSF, a Faster Version of BSSF............................................................................ 64

4.4.3 Frame-Sliced Signature File....................................................................................64

4.4.4 The Generalized Frame-Sliced Signature File (GFSSF).........................................65

4.4.5 Performance.............................................................................................................66

4.5 VERTICAL PARTITIONING AND COMPRESSION................................................. 67

4.5.1 Compressed Bit Slices (CBS)..................................................................................67

4.5.2 Doubly Compressed Bit Slices (DCBS).................................................................. 69

4.5.3 No False Drops Method (NFD)............................................................................... 70

4.5.4 Performance.............................................................................................................71

4.6 HORIZONTAL PARTITIONING ................................................................................. 72

4.6.1 Data Independent Case............................................................................................ 72

Gustafson's method.......................................................................................................72

Partitioned signature files .............................................................................................73

4.6.2 Data Dependent Case...............................................................................................73

Two-level signature files .............................................................................................. 73

S-tree.............................................................................................................................74

4.7 DISCUSSION................................................................................................................. 74

REFERENCES ..................................................................................................................... 75

CHAPTER 5: NEW INDICES FOR TEXT: PAT TREES AND PAT ARRAYS............... 79

5.1 INTRODUCTION.......................................................................................................... 79

5.2 THE PAT TREE STRUCTURE..................................................................................... 80

5.2.1 Semi-infinite Strings................................................................................................ 81

5.2.2 PAT Tree................................................................................................................. 81

5.2.3 Indexing Points ........................................................................................................ 83

5.3 ALGORITHMS ON THE PAT TREE...........................................................................83

5.3.1 Prefix Searching.......................................................................................................83

5.3.2 Proximity Searching ................................................................................................ 84

5.3.3 Range Searching...................................................................................................... 84

5.3.4 Longest Repetition Searching..................................................................................84

5.3.5 "Most Significant" or "Most Frequent" Searching ..................................................85

5.3.6 Regular Expression Searching................................................................................. 86

5.4 BUILDING PAT TREES AS PATRICIA TREES ........................................................87

5.5 PAT TREES REPRESENTED AS ARRAYS ...............................................................88

5.5.1 Searching PAT Trees as Arrays............................................................................... 89

5.5.2 Building PAT Trees as Arrays................................................................................. 89

Building PAT arrays in memory................................................................................... 90

Merging small against large PAT arrays ...................................................................... 90

5.5.3 Delayed Reading Paradigm ..................................................................................... 92

5.5.4 Merging Large Files ................................................................................................ 93

5.6 SUMMARY....................................................................................................................94

REFERENCES ..................................................................................................................... 95

CHAPTER 6: FILE ORGANIZATIONS FOR OPTICAL DISKS ...................................... 97

6.1 INTRODUCTION.......................................................................................................... 97

6.2 OVERVIEW OF OPTICAL DISK TECHNOLOGY ....................................................97

Features and benefits ........................................................................................................ 98

Technical description........................................................................................................ 99

Materials and registration techniques for WORM disks ................................................100

Materials and registration techniques for erasable disks................................................100

Optics.............................................................................................................................. 102

Lasers and light paths.....................................................................................................103

Recording formats .......................................................................................................... 103

6.3 FILE SYSTEMS ...........................................................................................................104

6.3.1 Technical Issues for File Systems.......................................................................... 104

6.3.2 Write-Once B -Tree ................................................................................................ 106

6.3.3 Time-Split B-Tree.................................................................................................. 108

6.3.4 Compact Disk File System ....................................................................................109

6.3.5 The Optical File Cabinet........................................................................................112

6.3.6 Buffered Hashing (Bhash)..................................................................................... 113

6.3.7 Balanced Implicit Multiway Trees (BIM Trees)................................................... 114

6.3.8 Hashing for CD-ROM and CLV Format Optical Disks........................................ 115

REFERENCES ................................................................................................................... 116

CHAPTER 7: LEXICAL ANALYSIS AND STOPLISTS................................................117

7.1 INTRODUCTION........................................................................................................ 117

7.2 LEXICAL ANALYSIS ................................................................................................ 117

7.2.1 Lexical Analysis for Automatic Indexing.............................................................. 117

7.2.2 Lexical Analysis for Query Processing .................................................................119

7.2.3 The Cost of Lexical Analysis ................................................................................119

7.2.4 Implementing a Lexical Analyzer .........................................................................119

7.3 STOPLISTS..................................................................................................................126

7.3.1 Implementing Stoplists .......................................................................................... 129

7.3.2 A Lexical Analyzer Generator............................................................................... 129

7.4 SUMMARY..................................................................................................................139

REFERENCES ................................................................................................................... 139

CHAPTER 8: STEMMING ALGORITHMS .................................................................... 141

8.1 INTRODUCTION........................................................................................................ 141

8.1.1 Example of Stemmer Use in Searching.................................................................142

8.2 TYPES OF STEMMING ALGORITHMS.................................................................. 143

8.2.1 Successor Variety .................................................................................................. 143

8.2.2 n-gram stemmers ...................................................................................................146

8.2.3 Affix Removal Stemmers......................................................................................148

8.3 EXPERIMENTAL EVALUATIONS OF STEMMING.............................................. 152

8.3.1 Stemming Studies: Conclusion.............................................................................. 157

8.4 STEMMING TO COMPRESS INVERTED FILES ....................................................159

8.5 SUMMARY..................................................................................................................159

REFERENCES ................................................................................................................... 160

APPENDIX......................................................................................................................... 161

CHAPTER 9: THESAURUS CONSTRUCTION.............................................................. 168

9.1 INTRODUCTION........................................................................................................ 168

9.2 FEATURES OF THESAURI....................................................................................... 170

9.2.1 Coordination Level ................................................................................................ 170

9.2.2 Term Relationships................................................................................................ 172

9.2.3 Number of Entries for Each Term .........................................................................172

9.2.4 Specificity of Vocabulary ......................................................................................173

9.2.5 Control on Term Frequency of Class Members ....................................................173

9.2.6 Normalization of Vocabulary ................................................................................173

9.3 THESAURUS CONSTRUCTION............................................................................... 174

9.3.1 Manual Thesaurus Construction............................................................................ 174

9.3.2 Automatic Thesaurus Construction .......................................................................175

9.3.3 From a Collection of Document Items.................................................................. 175

9.3.4 By Merging Existing Thesauri............................................................................... 176

9.3.5 User Generated Thesaurus..................................................................................... 176

9.4 THESAURUS CONSTRUCTION FROM TEXTS..................................................... 176

9.4.1 Construction of Vocabulary................................................................................... 177

Stem evaluatio n and selection ....................................................................................177

Phrase construction.....................................................................................................179

9.4.2 Similarity Computation ......................................................................................... 180

9.4.3 Vocabulary Organization....................................................................................... 181

9.5 MERGING EXISTING THESAURI...........................................................................182

9.6 BRIEF DESCRIPTION OF C PROGRAMS INCLUDED.......................................... 182

9.6.1 Program Select.c.................................................................................................... 182

9.6.2 Program Hierarchy.c.............................................................................................. 183

9.6.3 Program merge.c.................................................................................................... 183

9.7 CONCLUSION.............................................................................................................184

REFERENCES ................................................................................................................... 184

APPENDIX......................................................................................................................... 185

CHAPTER 10: STRING SEARCHING ALGORITHMS................................................. 224

10.1 INTRODUCTION...................................................................................................... 224

10.2 PRELIMINARIES...................................................................................................... 225

10.3 THE NAIVE ALGORITHM......................................................................................226

10.4 THE KNUTH-MORRIS -PRATT ALGORITHM......................................................227

10.5 THE BOYER-MOORE ALGORITHM.....................................................................229

10.5.1 The Simplified Boyer-Moore Algorithm.............................................................232

10.5.2 The Boyer-Moore-Horspool Algorithm .............................................................. 232

10.6 THE SHIFT-OR ALGORITHM................................................................................. 234

10.7 THE KARP-RABIN ALGORITHM.......................................................................... 238

10.8 CONCLUSIONS ........................................................................................................ 239

REFERENCES ................................................................................................................... 242

CHAPTER 11: RELEVANCE FEEDBACK AND OTHER QUERY MODIFICATION

TECHNIQUES ................................................................................................................... 247

11.1 INTRODUCTION...................................................................................................... 247

11.2 RESEARCH IN RELEVANCE FEEDBACK AND QUERY MODIFICATION.....248

11.2.1 Early Research.....................................................................................................248

11.2.2 Evaluation of Relevance Feedback...................................................................... 249

11.2.3 Research in Term Reweighting without Query Expansion .................................250

11.2.4 Query Expansion without Term Reweighting..................................................... 253

11.2.5 Query Expansion with Term Reweighting.......................................................... 254

11.2.6 Other Research in Relevance Feedback .............................................................. 256

11.3 USE OF RELEVANCE FEEDBACK IN ON-LINE RETRIEVAL SYSTEMS.......257

11.4 RECOMMENDATIONS FOR USE OF RELEVANCE FEEDBACK..................... 259

11.4.1 Relevance Feedback Methodologies ...................................................................259

Feedback in Boolean retrieval systems.......................................................................260

Feedback in retrieval systems based on the vector space model ................................ 260

Feedback in retrieval systems based on other types of statistical ranking ................. 261

11.5 SOME THOUGHTS ON THE EFFICIENT IMPLEMENTATION OF RELEVANCE

FEEDBACK OR QUERY MODIFICATION .................................................................... 263

11.5.1 Data and Structure Requirements for Relevance Feedback and Query

Modification ................................................................................................................... 264

11.5.2 A Proposal for an Efficient Implementation of Relevance Feedback ................. 265

11.6 SUMMARY................................................................................................................266

REFERENCES ................................................................................................................... 266

CHAPTER 12: BOOLEAN OPERATIONS ...................................................................... 271

12.1 INTRODUCTION...................................................................................................... 271

12.2 BOOLEAN EXPRESSIONS AND THEIR REPRESENTATION AS SETS...........272

12.3 OPERATIONS ON SETS .......................................................................................... 275

12.3.1 Set Interface .........................................................................................................276

12.3.2 Packaging.............................................................................................................279

12.3.3 Example............................................................................................................... 279

12.4 GENERAL CONSIDERATIONS FOR IMPLEMENTING SETS ...........................280

12.5 BIT VECTORS...........................................................................................................281

12.6 HASHING..................................................................................................................288

12.7 ANALYSIS ................................................................................................................. 294

REFERENCES ................................................................................................................... 297

CHAPTER 13: HASHING ALGORITHMS...................................................................... 298

13.1 INTRODUCTION...................................................................................................... 298

13.2 CONCEPTS OF HASHING....................................................................................... 299

13.3 HASHING FUNCTIONS ...........................................................................................301

13.4 IMPLEMENTING HASHING................................................................................... 302

13.4.1 Chained Hashing.................................................................................................. 303

13.4.2 Open Addressing .................................................................................................305

13.5 MINIMAL PERFECT HASH FUNCTIONS .............................................................309

13.5.1 Existence Proof.................................................................................................... 310

13.5.2 An Algorithm to Compute a MPHF: Concepts................................................... 310

13.5.3 Sager's Method and Improvement.......................................................................311

13.5.4 The Algorithm .....................................................................................................313

The main program .......................................................................................................313

The mapping step........................................................................................................ 314

The ord ering step ........................................................................................................ 316

The searching step ...................................................................................................... 319

Using the MPHF .........................................................................................................320

Discussion ................................................................................................................... 321

REFERENCES ................................................................................................................... 322

APPENDIX: MPHF IMPLEMENTATION .......................................................................323

CHAPTER 14: RANKING ALGORITHMS.....................................................................351

14.1 INTRODUCTION...................................................................................................... 351

14.2 HOW RANKING IS DONE....................................................................................... 352

14.3 RANKING MODELS AND EXPERIMENTS WITH THESE MODELS................353

14.3.1 The Vector Space Model ..................................................................................... 354

14.3.2 Probabilistic Models ............................................................................................ 355

14.3.3 Other Models for Ranking Individual Documents .............................................. 358

14.3.4 Set -Oriented Ranking Models .............................................................................358

14.4 OTHER EXPERIMENTS INVOLVING RANKING................................................359

14.4.1 Direct Comparison of Similarity Measures and Term-Weighting Schemes .......359

14.4.2 Ranking Based on Document Structure...............................................................360

14.4.3 Ranking Techniques Used in Operational Systems.............................................360

14.5 A GUIDE TO SELECTING RANKING TECHNIQUES .........................................361

14.6 DATA STRUCTURES AND ALGORITHMS FOR RANKING.............................. 364

14.6.1 The Creation of an Inverted File.......................................................................... 365

14.6.2 Searching the Inverted File..................................................................................368

14.7 MODIFICATIONS AND ENHANCEMENTS TO THE BASIC INDEXING AND

SEARCH PROCESSES ...................................................................................................... 370

14.7.1 Handling Both Stemmed and Unstemmed Query Terms.................................... 370

14.7.2 Searching in Very Large Data Sets...................................................................... 372

14.7.3 A Boolean System with Ranking.........................................................................372

14.7.4 Hashing into the Dictionary and Other Enhancements for Ease of Updating.....373

14.7.5 Pruning................................................................................................................. 374

14.8 TOPICS RELATED TO RANKING.......................................................................... 375

14.8.1 Ranking and Relevance Feedback.......................................................................375

14.8.2 Ranking and Clustering ....................................................................................... 375

14.8.3 Ranking and Boolean Systems ............................................................................ 376

14.8.4 Use of Ranking in Two-level Search Schemes....................................................376

14.8.5 Ranking and Signature Files................................................................................376

14.9 SUMMARY................................................................................................................377

REFERENCES ................................................................................................................... 377

CHAPTER 15: EXTENDED BOOLEAN MODELS ........................................................381

15.1 INTRODUCTION...................................................................................................... 381

15.2 EXTENDED BOOLEAN MODELS .........................................................................383

15.2.1 The MMM model ................................................................................................ 383

15.2.2 The Paice Model .................................................................................................. 384

15.2.3 The P-norm Model...............................................................................................385

15.3 IMPLEMENTATION.................................................................................................386

15.3.1 Data Structures.....................................................................................................386

Document structure.....................................................................................................386

Query Structure ...........................................................................................................386

15.3.2 Algorithms and Examples ....................................................................................390

15.4 CONCLUSION...........................................................................................................392

REFERENCES ................................................................................................................... 393

APPENDIX......................................................................................................................... 394

CHAPTER 16: CLUSTERING ALGORITHMS ...............................................................401

16.1 CLUSTER ANALYSIS .............................................................................................. 402

16.1.1 Introduction.......................................................................................................... 402

16.1.2 Applications in Information Retrieval .................................................................403

16.2 MEASURES OF ASSOCIATION.............................................................................404

16.2.1 Introduction.......................................................................................................... 404

16.2.2 Similarity Measures .............................................................................................404

16.2.3 The Similarity Matrix .......................................................................................... 405

16.3 CLUSTERING METHOS.......................................................................................... 407

16.3.1 Methods and Associated Algorithms...................................................................407

16.3.2 Computational and Storage Requirements .......................................................... 407

16.3.3 Survey of Clustering Methods.............................................................................407

Nonhierarchical methods ............................................................................................ 408

Hierarchical methods .................................................................................................. 408

16.4 ALGORITHMS FOR NONHIERARCHICAL METHODS ...................................... 410

16.4.1 Single Pass Methods ............................................................................................ 410

16.4.2 Reallocation Methods.......................................................................................... 410

16.5 ALGORITHMS FOR HIERARCHICAL METHODS .............................................. 411

16.5.1 General Algorithm for the HACM ...................................................................... 411

16.5.2 Single Link Method.............................................................................................413

Van Rijsbergen algorithm...........................................................................................413

SLINK algorithm ........................................................................................................ 413

Minimal spanning tree algorithms.............................................................................. 415

16.5.3 Complete Link Method........................................................................................416

Defays' CLINK algorithm...........................................................................................416

Voorhees algorithm .................................................................................................... 417

16.5.4 Group Average Link Method ............................................................................... 417

Voorhees algorithm .................................................................................................... 417

16.5.5 Ward's Method.....................................................................................................417

Reciprocal nearest neighbor algorithm.......................................................................418

16.6 EVALUATION AND VALIDATION .......................................................................419

16.6.1 Evaluation............................................................................................................ 419

16.6.2 Validation ............................................................................................................ 420

16.7 UPDATING THE CLUSTER STRUCTURE............................................................ 420

16.8 DOCUMENT RETRIEVAL FROM A CLUSTERED DATA SET.......................... 421

16.8.1 Approaches to Retrieval ......................................................................................421

16.8.2 Cluster Representatives ....................................................................................... 422

16.9 CONCLUSION...........................................................................................................422

REFERENCES ................................................................................................................... 422

CHAPTER 17: SPECIAL-PURPOSE HARDWARE FOR INFORMATION RETRIEVAL

............................................................................................................................................ 427

17.1 INTRODUCTION...................................................................................................... 427

17.1.1 Search Patterns.....................................................................................................428

17.1.2 Hardware Implementations..................................................................................429

17.2 TEXT SEARCHERS .................................................................................................. 429

17.2.1 Searcher Structure................................................................................................ 430

Associative Memories ................................................................................................ 431

Finite State Machines .................................................................................................432

Cellular Arrays............................................................................................................ 434

Standard Microprocessors .......................................................................................... 435

17.2.2 Search Performance.............................................................................................436

Seek and search mode.................................................................................................437

17.3 SURROGATE PROCESSORS..................................................................................437

17.3.1 List Merging ........................................................................................................ 438

17.3.2 Signature Processors............................................................................................ 438

17.4 OPTICAL PROC ESSORS......................................................................................... 439

17.4.1 Improved Optical Storage....................................................................................439

17.4.2 Optical Data Processing....................................................................................... 439

17.5 SUMMARY................................................................................................................440

REFERENCES ................................................................................................................... 441

CHAPTER 18: PARALLEL INFORMATION RETRIEVAL ALGORITHMS ............... 443

18.1 INTRODUCTION...................................................................................................... 443

18.2 DATA PARALLEL COMPUTING...........................................................................444

18.2.1 Shapes and Local Computation...........................................................................444

18.2.2 Nonlocal Operations ............................................................................................ 446

18.2.3 Performance Model.............................................................................................447

18.4 RANKING..................................................................................................................449

18.4.1 System-Supplied Rank Functions........................................................................ 450

18.4.2 Iterative Extraction .............................................................................................. 451

18.4.3 Hutchinson's Algorithm....................................................................................... 452

18.4.4 Summary.............................................................................................................. 455

18.5 PARALLEL SIGNATURE FILES.............................................................................456

18.5.1 Overlap Encoding ................................................................................................ 456

18.5.2 Probing a Signature.............................................................................................. 457

18.5.3 Scoring Algorithms.............................................................................................. 458

18.5.4 An Optimization .................................................................................................. 461

18.5.5 Combining Scoring and Ranking.........................................................................462

18.5.6 Extension to Secondary/Tertiary Storage............................................................ 463

18.5.7 Effects of Signature Parameters...........................................................................464

18.5.8 Discussion............................................................................................................ 465

18.6 PARALLEL INVERTED FILES ............................................................................... 466

18.6.1 Data Structure ...................................................................................................... 467

18.6.2 The Scoring Algorithm........................................................................................468

18.6.3 Document Term Weighting ................................................................................. 470

18.8 SECONDARY STORAGE........................................................................................471

18.8.1 Single-Transfer I/O on Disk Arrays.................................................................... 471

18.8.2 Independent Disk Access..................................................................................... 472

18.9 SUMMARY................................................................................................................472

REFERENCES ................................................................................................................... 472

CHAPTER 1: INTRODUCTION TO

INFORMATION STORAGE AND

RETRIEVAL SYSTEMS

W. B. Frakes

Software Engineering Guild, Sterling, VA 22170

Abstract

This chapter introduces and defines basic IR concepts, and presents a domain model of IR

systems that describes their similarities and differences. The domain model is used to

introduce and relate the chapters that follow. The relationship of IR systems to other

information systems is dicussed, as is the evaluation of IR systems.

1.1 INTRODUCTION

Automated information retrieval (IR) systems were originally developed to help manage

the huge scientific literature that has developed since the 1940s. Many university,

corporate, and public libraries now use IR systems to provide access to books, journals, and

other documents. Commercial IR systems offer databases containing millions of documents

in myriad subject areas. Dictionary and encyclopedia databases are now widely available

for PCs. IR has been found useful in such disparate areas as office automation and software

engineering. Indeed, any discipline that relies on documents to do its work could potentially

use and benefit from IR.

This book is about the data structures and algorithms needed to build IR systems. An IR

system matches user queries --formal statements of information needs--to documents stored

in a database. A document is a data object, usually textual, though it may also contain other

types of data such as photographs, graphs, and so on. Often, the documents themselves are

not stored directly in the IR system, but are represented in the system by document

surrogates. This chapter, for example, is a document and could be stored in its entirety in an

IR database. One might instead, however, choose to create a document surrogate for it

consisting of the title, author, and abstract. This is typically done for efficiency, that is, to

reduce the size of the database and searching time. Document surrogates are also called

documents, and in the rest of the book we will use document to denote both documents and

document surrogates.

An IR system must support certain basic operations. There must be a way to enter

documents into a database, change the documents, and delete them. There must also be

some way to search for documents, and present them to a user. As the following chapters

illustrate, IR systems vary greatly in the ways they accomplish these tasks. In the next

section, the similarities and differences among IR systems are discussed.

1.2 A DOMAIN ANALYSIS OF IR

SYSTEMS

This book contains many data structures, algorithms, and techniques. In order to find,

understand, and use them effectively, it is necessary to have a conceptual framework for

them. Domain analysis--systems analysis for multiple related systems--described in Prieto -

Diaz and Arrango (1991), is a method for developing such a framework. Via domain

analysis, one attempts to discover and record the similarities and differences among related

systems.

The first steps in domain analysis are to identify important concepts and vocabulary in the

domain, define them, and organize them with a faceted classification. Table 1.1 is a faceted

classification for IR systems, containing important IR concepts and vocabulary. The first

row of the table specifies the fa cets--that is, the attributes that IR systems share. Facets

represent the parts of IR systems that will tend to be constant from system to system. For

example, all IR systems must have a database structure-- they vary in the database structures

they have; some have inverted file structures, some have flat file structures, and so on.

A given IR system can be classified by the facets and facet values, called terms, that it has.

For example, the CATALOG system (Frakes 1984) discussed in Chapter 8 can be classified

as shown in Table 1.2.

Terms within a facet are not mutually exclusive, and more than one term from a facet can

be used for a given system. Some decisions constrain others. If one chooses a Boolean

conceptual model, for example, then one must choose a parse method for queries.

Table 1.1: Faceted Classification of IR Systems (numbers in parentheses indicate

chapters)

Conceptual File Query Term Document Hardware

Model Structure Operations Operations Operations

------------------------------------------------------------------------------

Boolean(1) Flat File(10) Feedback(11) Stem(8) Parse(3,7) vonNeumann(1)

Extended Inverted Parse(3,7) Weight(14) Display Parallel(18)

Boolean(15) File(3)

Probabil- Signature(4) Boolean(12) Thesaurus Cluster(16) IR

istic(14) (9) Specific(17)

String Pat Trees(5) Cluster(16) Stoplist(7) Rank(14) Optical

Search(10) Disk(6)

Vector Graphs(1) Truncation Sort(1) Mag. Disk(1)

Space(14) (10)

Hashing(13) Field Mask(1)

Assign IDs(3)

剩余236页未读，继续阅读

评论收藏

内容反馈

Copper_PKU

2013-05-06

字有点小，还算不错的资源
趴窗观天

2015-07-11

不错的书，感觉比较适合感兴趣的人
changwang23

2012-07-20

排版怪异，字小，不好读

Zylinkultamyyrä

粉丝: 10
资源: 103

Information Retrieval Data Structures and Algorithms (William B....

最新资源

Information Retrieval Data Structures and Algorithms (William B....

Information Retrieval Data Structures & Algorithms

Information Retrieval Data Structures Algorithms

Think Data Structures Algorithms and Information Retrieval in mobi

Think Data Structures Algorithms and Information Retrieval in epub

Think Data Structures: Algorithms and Information Retrieval in Java

Think Data Structures Algorithms and Information Retrieval in Java-OReilly(2017)

十部经典的算法书籍（上部分）

十部经典的算法书籍（下部分）

10部算法经典著作.chm(卷1)

Think Data Structures Algorithms and Information Retrieval in 无水印pdf

algorith_books_10_十本经典算法书

Essential Books on Algorithms and Data Structures(part1)(chm version)

Essential Books on Algorithms and Data Structures(part2)(chm version)

国外数据结构和算法合集书籍的种子

RemObjects DataAbstract Documents mht

Dr. Dobb's Essential Books on Algorithms and Data Structures(Part 1)

Information Retrieval: Architechture and Algorithms

Big.Data.Algorithms.Analytics.and.Applications.pdf

wget-1.11.4-1

Dr. Dobb's Essential Books on Algorithms and Data Structures(Part 2)

STM32循迹小车（灰度+OpenMV权重判断）

谭浩强C语言程序设计第五版详细答案

MQTT协议设备客户端与图传APP.zip

Keil.STM32H7xx-DFP.3.1.1.pack

基于stm32f407的示波器+FFT频谱分析

C语言求一个正整数的位数

zlib-1.2.13.tar.gz

STM32CubeIDE 1.14.0 自动补全代码

最新资源