信息检索导论-第一章-布尔检索(英文)

IntroducingInformationRetrievalandWebSearchInformationRetrievalInformationRetrieval(IR)isfindingmaterial(usuallydocuments)ofanunstructurednature(usuallytext)thatsatisfiesaninformationneedfromwithinlargecollections(usuallystoredoncomputers).Thesedayswefrequentlythinkfirstofwebsearch,buttherearemanyothercases:E-mailsearchSearchingyourlaptopCorporateknowledgebasesLegalinformationretrieval2Unstructured(text)vs.structured(database)datainthemid-nineties3Unstructured(text)vs.structured(database)datatoday4BasicassumptionsofInformationRetrievalCollection:AsetofdocumentsAssumeitisastaticcollectionforthemomentGoal:Retrievedocumentswithinformationthatisrelevanttotheuser’sinformationneed

andhelpstheusercompleteatask5Sec.1.1howtrapmicealiveTheclassicsearchmodelCollectionUsertaskInfoneed

Query

Results

Searchengine

Query

refinementGetridofmiceinapoliticallycorrectwayInfoaboutremovingmicewithoutkillingthemMisconception?Misformulation?SearchHowgoodaretheretrieveddocs?Precision:Fractionofretrieveddocsthatarerelevanttotheuser’sinformationneedRecall

:FractionofrelevantdocsincollectionthatareretrievedMoreprecisedefinitionsandmeasurementstofollowlater7Sec.1.1Term-documentincidencematricesUnstructureddatain1620WhichplaysofShakespearecontainthewordsBrutus

AND

CaesarbutNOT

Calpurnia?OnecouldgrepallofShakespeare’splaysforBrutusandCaesar,thenstripoutlinescontainingCalpurnia?Whyisthatnottheanswer?Slow(forlargecorpora)NOT

Calpurniaisnon-trivialOtheroperations(e.g.,findthewordRomansnear

countrymen)notfeasibleRankedretrieval(bestdocumentstoreturn)Laterlectures9Sec.1.1Term-documentincidencematrices1ifplaycontainsword,0otherwiseBrutus

AND

Caesar

BUT

NOT

CalpurniaSec.1.1IncidencevectorsSowehavea0/1vectorforeachterm.Toanswerquery:takethevectorsforBrutus,CaesarandCalpurnia(complemented)bitwiseAND.110100AND110111AND101111=10010011Sec.1.1AnswerstoqueryAntonyandCleopatra,

ActIII,SceneiiAgrippa[AsidetoDOMITIUSENOBARBUS]:Why,Enobarbus,WhenAntonyfoundJuliusCaesardead,Hecriedalmosttoroaring;andheweptWhenatPhilippihefoundBrutusslain.Hamlet,ActIII,SceneiiLordPolonius:IdidenactJuliusCaesarIwaskilledi’theCapitol;Brutuskilledme.12Sec.1.1BiggercollectionsConsiderN=1milliondocuments,eachwithabout1000words.Avg6bytes/wordincludingspaces/punctuation6GBofdatainthedocuments.SaythereareM=500Kdistincttermsamongthese.13Sec.1.1Can’tbuildthematrix500Kx1Mmatrixhashalf-a-trillion0’sand1’s.Butithasnomorethanonebillion1’s.matrixisextremelysparse.What’sabetterrepresentation?Weonlyrecordthe1positions.14Why?Sec.1.1TheInvertedIndexThekeydatastructureunderlyingmodernIRInvertedindexForeachtermt,wemuststorealistofalldocumentsthatcontaint.IdentifyeachdocbyadocID,adocumentserialnumberCanweusedfixed-sizearraysforthis?16WhathappensifthewordCaesarisaddedtodocument14?Sec.1.2BrutusCalpurniaCaesar12456165713212411314517323117454101InvertedindexWeneedvariable-sizepostingslistsOndisk,acontinuousrunofpostingsisnormalandbestInmemory,canuselinkedlistsorvariablelengtharraysSometradeoffsinsize/easeofinsertion17DictionaryPostingsSortedbydocID(morelateronwhy).PostingSec.1.2BrutusCalpurniaCaesar12456165713212411314517323117454101TokenizerTokenstreamFriendsRomansCountrymenInvertedindexconstructionLinguisticmodulesModifiedtokensfriendromancountrymanIndexerInvertedindexfriendromancountryman24213161DocumentstobeindexedFriends,Romans,countrymen.Sec.1.2InitialstagesoftextprocessingTokenizationCutcharactersequenceintowordtokensDealwith“John’s”,astate-of-the-artsolutionNormalizationMaptextandquerytermtosameformYouwantU.S.A.andUSAtomatchStemmingWemaywishdifferentformsofaroottomatchauthorize,authorizationStopwordsWemayomitverycommonwords(ornot)the,a,to,ofIndexersteps:TokensequenceSequenceof(Modifiedtoken,DocumentID)pairs.IdidenactJuliusCaesarIwaskilledi’theCapitol;Brutuskilledme.Doc1SoletitbewithCaesar.ThenobleBrutushathtoldyouCaesarwasambitiousDoc2Sec.1.2Indexersteps:SortSortbytermsAndthendocIDCoreindexingstepSec.1.2Indexersteps:Dictionary&PostingsMultipletermentriesinasingledocumentaremerged.SplitintoDictionaryandPostingsDoc.frequencyinformationisadded.Whyfrequency?Willdiscusslater.Sec.1.2Wheredowepayinstorage?23PointersTermsandcountsIRsystemimplementationHowdoweindexefficiently?Howmuchstoragedoweneed?Sec.1.2ListsofdocIDsQueryprocessingwithaninvertedindexTheindexwejustbuiltHowdoweprocessaquery?Later-whatkindsofqueriescanweprocess?25OurfocusSec.1.3Queryprocessing:ANDConsiderprocessingthequery:Brutus

AND

CaesarLocateBrutusintheDictionary;Retrieveitspostings.LocateCaesarintheDictionary;Retrieveitspostings.“Merge”thetwopostings(intersectthedocumentsets):2612834248163264123581321BrutusCaesarSec.1.3ThemergeWalkthroughthetwopostingssimultaneously,intimelinearinthetotalnumberofpostingsentries2734128248163264123581321BrutusCaesarIfthelistlengthsarexandy,themergetakesO(x+y)operations.Crucial:postingssortedbydocID.Sec.1.3Intersectingtwopostingslists

(a“merge”algorithm)28TheBooleanRetrievalModel&ExtendedBooleanModelsBooleanqueries:ExactmatchTheBooleanretrievalmodelisbeingabletoaskaquerythatisaBooleanexpression:BooleanQueriesarequeriesusingAND,ORandNOTtojoinquerytermsViewseachdocumentasasetofwordsIsprecise:documentmatchesconditionornot.PerhapsthesimplestmodeltobuildanIRsystemonPrimarycommercialretrievaltoolfor3decades.ManysearchsystemsyoustilluseareBoolean:Email,librarycatalog,MacOSXSpotlight30Sec.1.3Example:WestLaw://westlaw/Largestcommercial(payingsubscribers)legalsearchservice(started1975;rankingadded1992;newfederatedsearchadded2010)Tensofterabytesofdata;~700,000usersMajorityofusersstillusebooleanqueriesExamplequery:Whatisthestatuteoflimitationsincasesinvolvingthefederaltortclaimsact?LIMIT!/3STATUTEACTION/SFEDERAL/2TORT/3CLAIM/3=within3words,/S=insamesentence31Sec.1.4Example:WestLaw://westlaw/Anotherexamplequery:Requirementsfordisabledpeopletobeabletoaccessaworkplacedisabl!/paccess!/swork-sitework-place(employment/3placeNotethatSPACEisdisjunction,notconjunction!Long,precisequeries;proximityoperators;incrementallydeveloped;notlikewebsearchManyprofessionalsearchersstilllikeBooleansearchYouknowexactlywhatyouaregettingButthatdoesn’tmeanitactuallyworksbetter….Sec.1.4Booleanqueries:

MoregeneralmergesExercise:Adaptthemergeforthequeries:

Brutus

ANDNOT

Caesar Brutus

ORNOT

CaesarCanwestillrunthroughthemergeintimeO(x+y)?Whatcanweachieve?33Sec.1.3MergingWhataboutanarbitraryBooleanformula?(Brutus

ORCaesar)ANDNOT(AntonyORCleopatra)Canwealwaysmergein“linear”time?Linearinwhat?Canwedobetter?34Sec.1.3QueryoptimizationWhatisthebestorderforqueryprocessing?ConsideraquerythatisanANDofnterms.Foreachofthenterms,getitspostings,thenANDthemtogether.BrutusCaesarCalpurnia123581621342481632641281316Query:Brutus

AND

Calpurnia

AND

Caesar35Sec.1.3QueryoptimizationexampleProcessinorderofincreasingfreq:startwithsmallestset,thenkeep

cuttingfurther.36Thisiswhywekeptdocumentfreq.indictionaryExecutethequeryas(Calpurnia

AND

Brutus)

ANDCaesar.Sec.1.3BrutusCaesarCalpurnia123581621342481632641281316Moregeneraloptimizatione.g.,(maddingORcrowd)AND(ignobleORstrife)Getdoc.freq.’sforallterms.EstimatethesizeofeachORbythesumofitsdoc.freq.’s(conservative).ProcessinincreasingorderofORsizes.37Sec.1.3ExerciseRecommendaqueryprocessingorderforWhichtwotermsshouldweprocessfirst?38(tangerineORtrees)AND(marmaladeORskies)AND(kaleidoscopeOReyes)QueryprocessingexercisesExercise:Ifthequeryisfriends

ANDromansAND(NOTcountrymen),howcouldweusethefreqofcountrymen?Exercise:ExtendthemergetoanarbitraryBooleanquery.Canwealwaysguaranteeexecutionintimelinearinthetotalpostingssize?Hint:BeginwiththecaseofaBooleanformulaquery:inthis,eachquerytermappearsonlyonceinthequery.39ExerciseTrythesearchfeatureat://rhymezone/shakespeare/Writedownfivesearchfeaturesyouthinkitcoulddobetter40PhrasequeriesandpositionalindexesPhrasequeriesWewanttobeabletoanswerqueriessuchas“stanforduniversity”–asaphraseThusthesentence“IwenttouniversityatStanford”isnotamatch.Theconceptofphrasequerieshasproveneasilyunderstoodbyusers;oneofthefew“advancedsearch”ideasthatworksManymorequeriesareimplicitphrasequeriesForthis,itnolongersufficestostoreonly<term:docs>entriesSec.2.4Afirstattempt:BiwordindexesIndexeveryconsecutivepairoftermsinthetextasaphraseForexamplethetext“Friends,Romans,Countrymen”wouldgeneratethebiwordsfriendsromansromanscountrymenEachofthesebiwordsisnowadictionarytermTwo-wordphrasequery-processingisnowimmediate.Sec.2.4.1LongerphrasequeriesLongerphrasescanbeprocessedbybreakingthemdownstanforduniversitypaloaltocanbebrokenintotheBooleanqueryonbiwords:stanforduniversityANDuniversitypaloANDpaloaltoWithoutthedocs,wecannotverifythatthedocsmatchingtheaboveBooleanquerydocontainthephrase.Canhavefalsepositives!Sec.2.4.1IssuesforbiwordindexesFalsepositives,asnotedbeforeIndexblowupduetobiggerdictionaryInfeasibleformorethanbiwords,bigevenforthemBiwordindexesarenotthestandardsolution(forallbiwords)butcanbepartofacompoundstrategySec.2.4.1Solution2:PositionalindexesInthepostings,store,foreachtermtheposition(s)inwhichtokensofitappear:<term,numberofdocscontainingterm;doc1:position1,position2…;doc2:position1,position2…;etc.>Sec.2.4.2PositionalindexexampleForphrasequeries,weuseamergealgorithmrecursivelyatthedocumentlevelButwenowneedtodealwithmorethanjustequality<be:993427;1:7,18,33,72,86,231;2:3,149;4:17,191,291,430,434;5:363,367,…>Whichofdocs1,2,4,5couldcontain“tobeornottobe”?Sec.2.4.2ProcessingaphrasequeryExtractinvertedindexentriesforeachdistinctterm:to,be,or,not.Mergetheirdoc:positionliststoenumerateallpositionswith“tobeornottobe”.to:2:1,17,74,222,551;

4:8,16,190,429,433;

7:13,23,191;...be:1:17,19;4:17,191,291,430,434;

5:14,19,101;...SamegeneralmethodforproximitysearchesSec.2.4.2ProximityqueriesLIMIT!/3STATUTE/3FEDERAL/2TORTAgain,here,/kmeans“withinkwordsof”.Clearly,positionalindexescanbeusedforsuchqueries;biwordindexescannot.Exercise:Adaptthelinearmergeofpostingstohandleproximityqueries.Canyoumakeitworkforanyvalueofk?ThisisalittletrickytodocorrectlyandefficientlySeeFigure2.12ofIIRSec.2.4.2PositionalindexsizeApositionalindexexpandspostingsstoragesubstantiallyEventhoughindicescanbecompressedNevertheless,apositionalindexisnowstandardlyusedbecauseofthepowerandusefulnessofphraseandproximityqueries…whetherusedexplicitlyorimplicitlyinarankingretrievalsystem.Sec.2.4.2PositionalindexsizeNeedanentryforeachoccurrence,notjustonceperdocumentIndexsizedependsonaveragedocumentsizeAveragewebpagehas<1000termsSECfilings,books,evensomeepicpoems…easily100,000termsConsideratermwithfrequency0.1%Why?1001100,000111000PositionalpostingsPostingsDocumentsizeSec.2.4.2RulesofthumbApositionalindexis2–4aslargeasanon-positionalindexPositionalindexsize35–50%ofvolumeoforiginaltextCaveat:allofthisholdsfor“English-like”languagesSec