信息检索三Boolean queries.ppt

湖南大学计算机与通信学院 刘钰峰 Web Search System Problem Which plays of Shakespeare contain the words Brutus AND Caesar but NOT Calpurnia? One could grep all of Shakespeare’s plays for Brutus and Caesar, then strip out lines containing Calpurnia? Slow (for large corpora) Other operations (e.g., find the word Romans near countrymen) not feasible Ranked retrieval (best documents to return) Term-document incidence Incidence vectors So we have a 0/1 vector for each term. To answer query: take the vectors for Brutus, Caesar and Calpurnia (complemented) ? bitwise AND. Bigger corpora Consider N = 1M documents, each with about 1K terms. Say there are m = 500K distinct terms among these，The size of matrix is 500GB; Avg 6 bytes/term include spaces/punctuation 6GB of data in the documents. Can’t build the matrix 500K x 1M matrix has half-a-trillion 0’s and 1’s. But it has no more than one billion 1’s. matrix is extremely sparse. What’s a better representation? We only record the 1 positions. Inverted index For each term T, we must store a list of all documents that contain T. Do we use an array or a list for this? Inverted index Linked lists generally preferred to arrays Dynamic space allocation Insertion of terms into documents easy Space overhead of pointers Inverted index construction Indexer steps Sequence of (Modified token, Document ID) pairs. Sort by terms. Multiple term entries in a single document are merged. Frequency information is added. The result is split into a Dictionary file and a Postings file. Where do we pay in storage? The index we just built How do we process a query? Later - what kinds of queries can we process? Query processing: AND Consider processing the query: Brutus AND Caesar Locate Brutus in the Dictionary; Retrieve its postings. Locate Caesar in the Dictionary; Retrieve its postings. “Merge” the two postings: The merge Walk through the two postings simultaneously, in time linear in the total number of postings entries The merge Recall basic merge W