现代信息检索导论英文课件：01-BooleanRetrieval

1、Search for Unstructured data in 1650Query: Which plays of Shakespeare contain the words Brutus AND Caesar but NOT Calpurnia?One could grep all of Shakespeares plays for Brutus and Caesar, then strip out lines containing Calpurnia?Slow (for large corpora)NOT Calpurnia is non-trivialOther operations (

2、e.g., find the word Romans near countrymen) not feasibleRanked retrieval (best documents to return)Later lectures1Term-document incidence matrix1 if play contains word, 0 otherwiseBrutus AND Caesar but NOT Calpurnia2Terms as incidence vectorsSo we have a 0/1 vector for each term.To answer query: tak

3、e the vectors for Brutus, Caesar and Calpurnia (complemented) bitwise AND.110100 AND 110111 AND 101111 = 100100. 3Answers to queryAntony and Cleopatra, Act III, Scene iiAgrippa Aside to DOMITIUS ENOBARBUS: Why, Enobarbus, When Antony found Julius Caesar dead, He cried almost to roaring; and he wept

4、When at Philippi he found Brutus slain.Hamlet, Act III, Scene iiLord Polonius: I did enact Julius Caesar I was killed i the Capitol; Brutus killed me.4Bigger corporaConsider N = 1M documents, each with about 1K terms.Avg 6 bytes/term incl spaces/punctuation 6GB of data in the documents.Say there are

5、 m = 500K distinct terms among these.5Cant build the matrix500K x 1M matrix has half-a-trillion 0s and 1s.But it has no more than one billion 1s.matrix is extremely sparse.Whats a better representation?We only record the 1 positions.Why?6Inverted indexFor each term T, we must store a list of all doc

6、uments that contain T.Do we use an array or a list for this?BrutusCalpurniaCaesar123581321342481632641281316What happens if the word Caesar is added to document 14? 7Inverted indexLinked lists generally preferred to arraysDynamic space allocationInsertion of terms into documents easySpace overhead o

7、f pointersBrutusCalpurniaCaesar248163264128235813213413161DictionaryPostings listsSorted by docID (more later on why).Posting8Inverted index constructionTokenizerToken stream.FriendsRomansCountrymenLinguistic modulesModified tokens.friendromancountrymanIndexerInverted index.friendromancountryman2421

8、3161More onthese later.Documents tobe indexed.Friends, Romans, countrymen.9Sequence of (Modified token, Document ID) pairs.I did enact JuliusCaesar I was killed i the Capitol; Brutus killed me.Doc 1So let it be withCaesar. The nobleBrutus hath told youCaesar was ambitiousDoc 2Indexer steps10Sort by

9、terms. Core indexing step.11Multiple term entries in a single document are merged.Frequency information is added. Why frequency?Will discuss later.12The result is split into a Dictionary file and a Postings file. 13Where do we pay in storage? PointersTermsWill quantify the storage, later.14The index

10、 we just builtHow do we process a query?Later - what kinds of queries can we process?Todays focus15Query processing: ANDConsider processing the query:Brutus AND CaesarLocate Brutus in the Dictionary;Retrieve its postings.Locate Caesar in the Dictionary;Retrieve its postings.“Merge” the two postings:

11、12834248163264123581321BrutusCaesar1634128248163264123581321The mergeWalk through the two postings simultaneously, in time linear in the total number of postings entries12834248163264123581321BrutusCaesar28If the list lengths are x and y, the merge takes O(x+y)operations.Crucial: postings sorted by

12、docID.17Boolean queries: Exact matchThe Boolean Retrieval model is being able to ask a query that is a Boolean expression:Boolean Queries are queries using AND, OR and NOT to join query termsViews each document as a set of wordsIs precise: document matches condition or not.Primary commercial retriev

13、al tool for 3 decades. Professional searchers (e.g., lawyers) still like Boolean queries:You know exactly what youre getting.18Example: WestLaw http:/Largest commercial (paying subscribers) legal search service (started 1975; ranking added 1992)Tens of terabytes of data; 700,000 usersMajority of use

14、rs still use boolean queriesExample query:What is the statute of limitations in cases involving the federal tort claims act?LIMIT! /3 STATUTE ACTION /S FEDERAL /2 TORT /3 CLAIM/3 = within 3 words, /S = in same sentence19Example: WestLaw http:/Another example query:Requirements for disabled people to

15、 be able to access a workplacedisabl! /p access! /s work-site work-place (employment /3 placeNote that SPACE is disjunction, not conjunction!Long, precise queries; proximity operators; incrementally developed; not like web searchProfessional searchers often like Boolean search:Precision, transparenc

16、y and controlBut that doesnt mean they actually work better.20Boolean queries: More general mergesExercise: Adapt the merge for the queries:Brutus AND NOT CaesarBrutus OR NOT CaesarCan we still run through the merge in time O(x+y) or what can we achieve?21MergingWhat about an arbitrary Boolean formu

17、la?(Brutus OR Caesar) AND NOT(Antony OR Cleopatra)Can we always merge in “linear” time?Linear in what?Can we do better?22Query optimizationWhat is the best order for query processing?Consider a query that is an AND of t terms.For each of the t terms, get its postings, then AND them together.BrutusCa

18、lpurniaCaesar123581621342481632641281316Query: Brutus AND Calpurnia AND Caesar23Query optimization exampleProcess in order of increasing freq:start with smallest set, then keep cutting further.BrutusCalpurniaCaesar123581321342481632641281316This is why we keptfreq in dictionaryExecute the query as (

19、Caesar AND Brutus) AND Calpurnia.24More general optimizatione.g., (madding OR crowd) AND (ignoble OR strife)Get freqs for all terms.Estimate the size of each OR by the sum of its freqs (conservative).Process in increasing order of OR sizes.25ExerciseRecommend a query processing order for(tangerine O

20、R trees) AND(marmalade OR skies) AND(kaleidoscope OR eyes)26Query processing exercisesIf the query is friends AND romans AND (NOT countrymen), how could we use the freq of countrymen?Exercise: Extend the merge to an arbitrary Boolean query. Can we always guarantee execution in time linear in the tot

21、al postings size?Hint: Begin with the case of a Boolean formula query: in this, each query term appears only once in the query.27ExerciseTry the search feature at Shakespeare Search“: http:/shakespeare/Write down five search features you think it could do better28Whats ahead in IR?Beyond term searchWhat about phrases?Stanford UniversityProximity: Find Gates NEAR Microsoft.Need index to capture position information in docs. More later.Zones