Building Search Applications: Lucene, LingPipe, and Gate

Applications, Gate, Building, Search, LingPipe

Post Last Edit by d2R at 5-1-2010 11:50

This book is a good resource to teach you to build a powerful search application.
Contents
Preface ix
1 Information Overload 1
1.1 Information Sources . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Information Management Tools . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 Search Engines . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.2 Entity Extraction . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.3 Organizing Information . . . . . . . . . . . . . . . . . . . . . 9
1.2.4 Tracking Information . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Visualization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.1 Social Network Visualization . . . . . . . . . . . . . . . . . . . 11
1.3.2 Stock Price and News Visualization . . . . . . . . . . . . . . . 11
1.3.3 Tag Clouds . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4.1 Spam Detection . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4.2 Email Usage and Management . . . . . . . . . . . . . . . . . . 15
1.4.3 Customer Service . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.4.4 Employee Surveys . . . . . . . . . . . . . . . . . . . . . . . . 17
1.4.5 Other Applications . . . . . . . . . . . . . . . . . . . . . . . . 18
2 Tokenizing Text 21
2.1 Character Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.1.1 Tokens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2 Lucene Analyzers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2.1 WhitespaceAnalyzer . . . . . . . . . . . . . . . . . . . . . . . 24
2.2.2 SimpleAnalyzer . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.2.3 Analyzer Design . . . . . . . . . . . . . . . . . . . . . . . . . . 27
i
2.2.4 StandardAnalyzer . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.2.5 PorterAnalyzer . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.2.6 StandardBgramAnalyzer . . . . . . . . . . . . . . . . . . . . . 32
2.2.7 Other Analyzers . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.3 LingPipe Tokenizers . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.3.1 IndoEuropeanTokenizer . . . . . . . . . . . . . . . . . . . . . 36
2.3.2 Filtered Tokenizers . . . . . . . . . . . . . . . . . . . . . . . . 37
2.3.3 Regular Expression Tokenizer . . . . . . . . . . . . . . . . . . 38
2.3.4 Character-based Ngram Tokenizer . . . . . . . . . . . . . . . . 38
2.3.5 A LingPipe Tokenizer in a Lucene Analyzer . . . . . . . . . . 39
2.3.6 A Lucene Analyzer in a LingPipe Tokenizer . . . . . . . . . . 41
2.4 Gate Tokenizer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.4.1 A Gate Tokenizer in a Lucene Analyzer . . . . . . . . . . . . . 47
2.5 Tokenizing Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.6 Text Extraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2.7 WordNet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
2.7.1 Word Stems and WordNet . . . . . . . . . . . . . . . . . . . . 67
2.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3 Indexing Text with Lucene 71
3.1 Databases and Search Engines . . . . . . . . . . . . . . . . . . . . . . 71
3.2 Early Search Engines . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
3.2.1 Web Search Engines and IR Systems . . . . . . . . . . . . . . 74
3.3 Generating an Index . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.3.1 Term Weighting . . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.3.2 Term Vector Model . . . . . . . . . . . . . . . . . . . . . . . . 82
3.3.3 Inverted Index . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
3.4 Creating an Index with Lucene . . . . . . . . . . . . . . . . . . . . . 84
3.4.1 Field Attributes . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.4.2 Boosting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.5 Modifying an Index with Lucene . . . . . . . . . . . . . . . . . . . . . 90
3.6 A Database Backed Index . . . . . . . . . . . . . . . . . . . . . . . . 93
3.6.1 Deleting a Document . . . . . . . . . . . . . . . . . . . . . . . 96
3.6.2 Updating a Document . . . . . . . . . . . . . . . . . . . . . . 98
3.7 Maintaining an Index . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
ii
3.7.1 Logs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
3.7.2 Transactions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
3.7.3 Database Index Synchronization . . . . . . . . . . . . . . . . . 102
3.7.4 Lucene Index Files . . . . . . . . . . . . . . . . . . . . . . . . 103
3.8 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
3.8.1 Index Tuning Parameters . . . . . . . . . . . . . . . . . . . . . 106
3.8.2 Evaluation of Parameters . . . . . . . . . . . . . . . . . . . . . 108
3.8.3 Memory-Based Index . . . . . . . . . . . . . . . . . . . . . . . 110
3.8.4 Index Performance with a Database . . . . . . . . . . . . . . . 113
3.8.5 Index Scalability . . . . . . . . . . . . . . . . . . . . . . . . . 114
3.8.6 Index Vocabulary . . . . . . . . . . . . . . . . . . . . . . . . . 115
3.9 Date Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
3.10 Metadata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
3.10.1 Document Metadata . . . . . . . . . . . . . . . . . . . . . . . 120
3.10.2 Multimedia Metadata . . . . . . . . . . . . . . . . . . . . . . . 121
3.10.3 Metadata Standards . . . . . . . . . . . . . . . . . . . . . . . 123
3.11 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
4 Searching Text with Lucene 125
4.1 Lucene Search Architecture . . . . . . . . . . . . . . . . . . . . . . . 125
4.2 Search Interface Design . . . . . . . . . . . . . . . . . . . . . . . . . . 128
4.3 Search Behavior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
4.3.1 Intranets and the Web . . . . . . . . . . . . . . . . . . . . . . 132
4.4 Searching the Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
4.4.1 Generating Queries with QueryParser . . . . . . . . . . . . . . 137
4.4.2 Expanded Queries . . . . . . . . . . . . . . . . . . . . . . . . 142
4.4.3 Span Queries . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
4.5 Query Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
4.6 Organizing Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
4.6.1 Sorting Results . . . . . . . . . . . . . . . . . . . . . . . . . . 151
4.6.2 Scoring Results . . . . . . . . . . . . . . . . . . . . . . . . . . 152
4.6.3 Customizing Query-Doc Similarity . . . . . . . . . . . . . . . 158
4.7 Filtering Queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
4.7.1 Range Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
4.7.2 Security Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
iii
4.7.3 Query Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
4.7.4 Caching Filters . . . . . . . . . . . . . . . . . . . . . . . . . . 164
4.7.5 Chained Filters . . . . . . . . . . . . . . . . . . . . . . . . . . 165
4.8 Modifying Queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
4.8.1 Spell Check . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
4.8.2 Finding Similar Documents . . . . . . . . . . . . . . . . . . . 177
4.9 Troubleshooting a Query . . . . . . . . . . . . . . . . . . . . . . . . . 179
4.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
5 Tagging Text 183
5.1 Sentences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
5.1.1 Sentence Extraction with LingPipe . . . . . . . . . . . . . . . 184
5.1.2 Sentence Extraction with Gate . . . . . . . . . . . . . . . . . 187
5.1.3 Text Extraction from Web Pages . . . . . . . . . . . . . . . . 191
5.2 Part of Speech Taggers . . . . . . . . . . . . . . . . . . . . . . . . . . 192
5.2.1 Tag Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
5.2.2 Markov Models . . . . . . . . . . . . . . . . . . . . . . . . . . 195
5.2.3 Evaluation of a Tagger . . . . . . . . . . . . . . . . . . . . . . 199
5.2.4 POS Tagging with LingPipe . . . . . . . . . . . . . . . . . . . 200
5.2.5 Rule-Based Tagging . . . . . . . . . . . . . . . . . . . . . . . . 206
5.2.6 POS Tagging with Gate . . . . . . . . . . . . . . . . . . . . . 208
5.2.7 Markov Model vs Rule-based Taggers . . . . . . . . . . . . . . 211
5.3 Phrase Extraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
5.3.1 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
5.3.2 Finding Phrases . . . . . . . . . . . . . . . . . . . . . . . . . . 213
5.3.3 Likelihood Ratio . . . . . . . . . . . . . . . . . . . . . . . . . 214
5.3.4 Phrase Extraction using LingPipe . . . . . . . . . . . . . . . . 218
5.3.5 Current Phrases . . . . . . . . . . . . . . . . . . . . . . . . . . 221
5.4 Entity Extraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
5.4.1 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
5.4.2 Entity Extraction with Gate . . . . . . . . . . . . . . . . . . . 225
5.4.3 Entity Extraction with LingPipe . . . . . . . . . . . . . . . . 232
5.4.4 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
5.4.5 Entity Extraction Errors . . . . . . . . . . . . . . . . . . . . . 239
5.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
iv
6 Organizing Text: Clustering 241
6.1 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
6.2 Creating Clusters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
6.2.1 Clustering Documents . . . . . . . . . . . . . . . . . . . . . . 245
6.2.2 Similarity Measures . . . . . . . . . . . . . . . . . . . . . . . . 246
6.2.3 Comparison of Similarity Measures . . . . . . . . . . . . . . . 251
6.2.4 Using the Similarity Matrix . . . . . . . . . . . . . . . . . . . 254
6.3 Cluster Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
6.3.1 Global Optimization Methods . . . . . . . . . . . . . . . . . . 257
6.3.2 Heuristic Methods . . . . . . . . . . . . . . . . . . . . . . . . 257
6.3.3 Agglomerative Methods . . . . . . . . . . . . . . . . . . . . . 259
6.4 Building Clusters with LingPipe . . . . . . . . . . . . . . . . . . . . 262
6.4.1 Debugging Clusters . . . . . . . . . . . . . . . . . . . . . . . . 265
6.4.2 Evaluating Clusters . . . . . . . . . . . . . . . . . . . . . . . . 266
6.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
7 Organizing Text: Categorization 273
7.1 Categorization Problem . . . . . . . . . . . . . . . . . . . . . . . . . 273
7.1.1 Applications for Document Categorization . . . . . . . . . . . 274
7.2 Categorizing Documents . . . . . . . . . . . . . . . . . . . . . . . . . 278
7.2.1 Training the Model . . . . . . . . . . . . . . . . . . . . . . . . 279
7.2.2 Using the Model . . . . . . . . . . . . . . . . . . . . . . . . . 280
7.3 Categorization Methods . . . . . . . . . . . . . . . . . . . . . . . . . 281
7.3.1 Character-based Ngram Models . . . . . . . . . . . . . . . . . 282
7.3.2 Binary and Multi Classifiers . . . . . . . . . . . . . . . . . . . 283
7.3.3 TF/IDF Classifier . . . . . . . . . . . . . . . . . . . . . . . . . 288
7.3.4 K-Nearest Neighbors Classifier . . . . . . . . . . . . . . . . . . 290
7.3.5 Naïve Bayes Classifier . . . . . . . . . . . . . . . . . . . . . . 292
7.3.6 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
7.3.7 Feature Extraction . . . . . . . . . . . . . . . . . . . . . . . . 294
7.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
8 Searching an Intranet and the Web 297
8.1 Early Web Search Engines . . . . . . . . . . . . . . . . . . . . . . . . 297
8.2 Web Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
v
8.2.1 A Bow-Tie Web Graph . . . . . . . . . . . . . . . . . . . . . . 299
8.2.2 Hubs & Authorities . . . . . . . . . . . . . . . . . . . . . . . . 304
8.2.3 PageRank Algorithm . . . . . . . . . . . . . . . . . . . . . . . 307
8.2.4 PageRank vs. Hubs & Authorities . . . . . . . . . . . . . . . . 310
8.3 Crawlers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
8.3.1 Building a Crawler . . . . . . . . . . . . . . . . . . . . . . . . 314
8.3.2 Search Engine Coverage . . . . . . . . . . . . . . . . . . . . . 319
8.4 Nutch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
8.4.1 Nutch Crawler . . . . . . . . . . . . . . . . . . . . . . . . . . 322
8.4.2 Crawl Configuration . . . . . . . . . . . . . . . . . . . . . . . 325
8.4.3 Running a Re-crawl . . . . . . . . . . . . . . . . . . . . . . . . 329
8.4.4 Search Interface . . . . . . . . . . . . . . . . . . . . . . . . . . 330
8.4.5 Troubleshooting . . . . . . . . . . . . . . . . . . . . . . . . . . 334
8.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336
9 Tracking Information 339
9.1 News Monitoring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
9.1.1 Web Feeds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
9.1.2 NewsRack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341
9.2 Sentiment Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344
9.2.1 Automatic Classification . . . . . . . . . . . . . . . . . . . . . 345
9.2.2 An Implementation with LingPipe . . . . . . . . . . . . . . . 351
9.3 Detecting Offensive Content . . . . . . . . . . . . . . . . . . . . . . . 358
9.3.1 Detection Methods . . . . . . . . . . . . . . . . . . . . . . . . 358
9.4 Plagiarism Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . 360
9.4.1 Forms of Plagiarism . . . . . . . . . . . . . . . . . . . . . . . 360
9.4.2 Methods to Detect Plagiarism . . . . . . . . . . . . . . . . . . 361
9.4.3 Copy Detection using SCAM . . . . . . . . . . . . . . . . . . 363
9.4.4 Other Applications . . . . . . . . . . . . . . . . . . . . . . . . 366
9.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367
10 Future Directions in Search 369
10.1 Improving Search Engines . . . . . . . . . . . . . . . . . . . . . . . . 370
10.1.1 Adding Human Intelligence . . . . . . . . . . . . . . . . . . . 370
10.1.2 Special Features . . . . . . . . . . . . . . . . . . . . . . . . . . 372
vi
10.1.3 OpenSearch . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374
10.1.4 Specialized Search Engines . . . . . . . . . . . . . . . . . . . . 379
10.2 Using Collective Intelligence to Improve Search . . . . . . . . . . . . 382
10.2.1 Tag-Based Search Engines . . . . . . . . . . . . . . . . . . . . 383
10.3 Question & Answer . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387
10.3.1 Q&A Engine Design . . . . . . . . . . . . . . . . . . . . . . . 388
10.3.2 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391
10.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392
Appendix A Software 393
Appendix B Bayes Classification 403
Appendix C The Berkeley DB 407
Index 417

Favor Share Rate

Reply Quote

Subscribe TOP