信息檢索與web搜索課件 03學(xué)習(xí)資料

信息檢索與Web搜索

第3講詞項(xiàng)詞典及倒排記錄表

Thetermvocabularyandpostingslists

授課人：高曙明

*改編自“現(xiàn)代信息檢索”網(wǎng)上公開(kāi)課件（/~wangbin）Tokenizer詞條流FriendsRomansCountrymen回顧：倒排索引構(gòu)建Linguisticmodules與詞項(xiàng)對(duì)應(yīng)的詞條friendromancountrymanIndexer倒排索引friendromancountryman24213161待索引文檔Friends,Romans,countrymen.詞條化工具語(yǔ)言分析工具文檔預(yù)處理任務(wù)目標(biāo)：將文檔轉(zhuǎn)化成詞項(xiàng)集合，支持倒排索引，支持基于詞項(xiàng)比對(duì)的文本檢索主要內(nèi)容文檔編碼轉(zhuǎn)換文檔單位選擇文本分析：詞條化、詞條歸一化、詞形歸并、詞干還原等主要方法：自然語(yǔ)言處理、語(yǔ)言學(xué)文檔編碼轉(zhuǎn)換任務(wù)：將字節(jié)序列轉(zhuǎn)換成線性的字符序列難點(diǎn)：多格式、多語(yǔ)言并存方法：采用啟發(fā)式方法進(jìn)行文檔語(yǔ)言識(shí)別、文檔編碼識(shí)別，再分類轉(zhuǎn)換文檔單位選擇任務(wù)：確定被索引文檔的合理粒度粒度過(guò)大：正確率低

粒度過(guò)?。赫倩芈实头椒ǎ禾峁┎煌臋n粒度，由用戶根據(jù)實(shí)際需要選擇合理的文檔粒度詞條化(Tokenization)任務(wù)：將字符序列分割成一系列有意義的子序列例子：輸入:“Friends,RomansandCountrymen”輸出:FriendsRomansCountrymen詞條：一個(gè)字符串實(shí)例，具有語(yǔ)義，適合作為索引單元作用：詞條化工作是構(gòu)建倒排索引的基礎(chǔ)，并影響檢索效果難點(diǎn)：如何有效地確定詞條詞條化面對(duì)的問(wèn)題“’”如何處理O’Neill、boys’、Chile’s、aren’tFinland’scapitalFinland?Finlands?Finland’s?“-”如何處理Hewlett-Packard看成Hewlett和Packard兩個(gè)詞條?空格如何處理SanFrancisco到底是一個(gè)還是兩個(gè)詞條？如何判斷是一個(gè)詞條？特殊詞條如何識(shí)別C++、C#、B-52、M*A*S*H、電話號(hào)碼、網(wǎng)址……中文分詞(ChineseWordSegmentation)難點(diǎn)：沒(méi)有空格符，字也可能有語(yǔ)義例子：“和尚”、“和”、“尚”方法：詞典、統(tǒng)計(jì)學(xué)習(xí)、啟發(fā)式規(guī)則、字詞混合方式/k-gram（K字符序列）例子：李明天天都準(zhǔn)時(shí)上班李明天天都準(zhǔn)時(shí)上班李明天天都準(zhǔn)時(shí)上班一般原則：沒(méi)把握的情況下細(xì)粒度優(yōu)先一個(gè)策略：查詢和文檔采用一致的分詞方法8停用詞去除停用詞：在進(jìn)行文檔和查詢匹配時(shí)作用不大的常見(jiàn)詞一般不包含語(yǔ)義信息的詞：the、a、and、to、be這些詞都是高頻詞:前30個(gè)詞就占了~30%的倒排記錄表空間停用詞去除的作用壓縮索引空間提高檢索響應(yīng)速度停用詞確定方法高文檔頻率且與文檔主題關(guān)系不大的詞應(yīng)用領(lǐng)域相關(guān)：“click”作為錨文本的停用詞在處理查詢時(shí)決定哪些詞不用停用詞去除現(xiàn)代信息檢索系統(tǒng)中傾向于不去掉停用詞在保留停用詞的情況下，采用良好的壓縮技術(shù)后，停用詞所占用的空間可以大大壓縮，最終它們?cè)谡麄€(gè)倒排記錄表中所占的空間比例很小采用良好的查詢優(yōu)化技術(shù)，基本不會(huì)增加查詢處理的開(kāi)銷所謂的停用詞并不一定沒(méi)用，比如：短語(yǔ)查詢:“KingofDenmark”、歌曲名或者臺(tái)詞等等:“Letitbe”,“Tobeornottobe”、“關(guān)系型”查詢

“flightstoLondon”詞條歸一化(Normalization)任務(wù)：將本質(zhì)上等價(jià)但形式上不完全一致的多個(gè)詞條歸納成一個(gè)等價(jià)類，即詞項(xiàng)作用：提高檢索效果，縮小索引空間兩類方法：規(guī)則法，關(guān)聯(lián)關(guān)系法規(guī)則法：采用隱式規(guī)則在處理文檔和查詢時(shí)將多個(gè)詞條映射成同一詞項(xiàng)，比如：剔除句點(diǎn)規(guī)則：U.S.A.,USAUSA剔除連接符規(guī)則：anti-discriminatory,antidiscriminatoryantidiscriminatory詞條歸一化(Normalization)關(guān)聯(lián)關(guān)系法：通過(guò)維護(hù)等價(jià)的非歸一化詞條之間的關(guān)聯(lián)關(guān)系，顯式地建立并應(yīng)用等價(jià)類，如建立并應(yīng)用同義詞詞典（Thesauri,WordNet）每一不重復(fù)的詞條都作為索引單元處理查詢時(shí)對(duì)每一詞項(xiàng)基于等價(jià)類進(jìn)行擴(kuò)展，并將擴(kuò)展后得到的多個(gè)詞所對(duì)應(yīng)的倒排表合到一起在索引構(gòu)建時(shí)就對(duì)詞進(jìn)行擴(kuò)展，如對(duì)于包含car的文檔也放入automobile的倒排表中方法比較：規(guī)則法效率高，關(guān)聯(lián)關(guān)系法更靈活歸一化相關(guān)問(wèn)題及其處理重音符問(wèn)題：如法語(yǔ)中résumévs.resume處理方法：常常歸一化成不帶重音符號(hào)的形式Tuebingen,Tübingen,Tubingen--

Tubingen大小寫問(wèn)題：Automobilevs.automobile處理方法：將句首詞轉(zhuǎn)換成小寫形式，將標(biāo)題中大寫或首字母大寫的全部單詞轉(zhuǎn)換成小寫形式時(shí)間格式問(wèn)題：3/12/91,Mar.12,1991（美式）,12/3/91（歐式）處理方法：?jiǎn)l(fā)式規(guī)則+語(yǔ)言識(shí)別詞形歸并(Lemmatization)任務(wù)：將單詞的不同語(yǔ)法形態(tài)還原為原形例子：am,are,is

be；car,cars,car's,cars'

cartheboy'scarsaredifferentcolors

theboycarbedifferentcolor作用：提高檢索效果，減少索引單元方法：詞典+相關(guān)詞列表問(wèn)題：如：found

find?found?上下文語(yǔ)義理解?詞干還原（Stemming）任務(wù)：將詞項(xiàng)歸約(reduce)成其詞干(stem)比如，將

automate(s),automatic,automation都還原成

automat作用：提高檢索效果，減少索引單元（5-10%forEnglish，50%inArabie，30%芬蘭語(yǔ)）方法：基于規(guī)則截除詞綴forexamplecompressedandcompressionarebothacceptedasequivalenttocompress.forexamplcompressandcompressarbothacceptasequivaltocompressPorter算法英語(yǔ)詞干還原中最常用的算法，開(kāi)始于70年代一些規(guī)則+5步驟的歸約過(guò)程Porter算法Porter算法問(wèn)題舉例[Note]falsepositive:pairsofdifferentwordshavethesamestem;falsenegative:pairsofwordshavedifferentstemwhentheyshouldhavethesame.其他詞干還原工具(stemmer)Lovins

p.lancs.ac.uk/computing/research/stemming/general/lovins.htm單遍掃描，最長(zhǎng)詞綴剔除(大概250條規(guī)則)Paice/Husk

http://www.cs.waikato.ac.nz/~eibe/stemmers基于詞形分析對(duì)于檢索只能提供一定的幫助未來(lái)：基于詞用分析？18回顧：基本合并算法兩個(gè)指針，同步掃描，線性時(shí)間128312484148641238111721BrutusCaesar28兩個(gè)表長(zhǎng)度為m和n的話，上述合并時(shí)間復(fù)雜度為O(m+n)

能否做得更好？帶跳表指針的倒排表跳表(skiplist)：作用：支持在遍歷倒排表時(shí)跳過(guò)那些不可能出現(xiàn)在檢索結(jié)果中的記錄項(xiàng)，以提高合并操作的效率需要解決的問(wèn)題：在什么地方加跳表指針？如何利用跳表指針支持倒排表的快速合并？12824841486441128基于跳表的倒排表快速合并128248414864311238111721311141128

假定匹配到上下的指針都指向8，接下來(lái)兩個(gè)指針都向下移動(dòng)一位

比較41和11，這里11小且有跳表指針（指向31），則直接比較41和31，由于31仍然比41小，于是下指針直接指向31，這樣就跳過(guò)了12、21兩項(xiàng)；跳表法基于跳表的倒排表快速合并跳表法跳表指針的位置選擇均衡性:指針數(shù)目過(guò)多過(guò)少都不合適指針越多

跳步越短

更容易跳轉(zhuǎn)，但是需要更多的與跳表指針指向記錄的比較指針越少

比較次數(shù)越少，但是跳步越長(zhǎng)

成功跳轉(zhuǎn)的次數(shù)少簡(jiǎn)單的啟發(fā)式策略：對(duì)于長(zhǎng)度為L(zhǎng)的倒排記錄表，每

L處放一個(gè)跳表指針，即均勻放置。均勻放置方法忽略了查詢?cè)~項(xiàng)的分布情況短語(yǔ)查詢短語(yǔ)查詢：以一個(gè)短語(yǔ)整體作為查詢的查詢方式，比如“stanforduniversity”“浙江大學(xué)”是一種符合人們需要的查詢方式基于關(guān)鍵詞的查詢難以達(dá)到短語(yǔ)查詢的效果原因何在？問(wèn)題：如何改造索引?

如何識(shí)別文檔中的短語(yǔ)？雙詞(Biword)索引目的：將文檔中每?jī)蓚€(gè)連續(xù)的詞組成詞對(duì)，作為索引單元例子：對(duì)文本片段

“Friends,Romans,Countrymen”

，產(chǎn)生兩個(gè)詞對(duì)friendsromansromanscountrymen方法：索引構(gòu)建時(shí)，將每個(gè)詞對(duì)看成一個(gè)詞項(xiàng)放到詞典中問(wèn)題：大大增加詞匯表的規(guī)模和索引的規(guī)模更長(zhǎng)的短語(yǔ)查詢處理方法：將其拆分成基于雙詞的布爾查詢式，拆分采用K-gram策略例子：

對(duì)于stanforduniversitypaloalto，將其拆分成

stanforduniversityANDuniversitypaloANDpaloalto進(jìn)行查詢處理滿足上述布爾表達(dá)式只是滿足短語(yǔ)查詢的必要條件很難避免偽正例的出現(xiàn)！雙詞擴(kuò)展（ExtendedBiword）目的：有效支持名詞短語(yǔ)查詢擴(kuò)展方法：對(duì)文檔進(jìn)行詞性標(biāo)注，將詞項(xiàng)進(jìn)行組塊，每個(gè)組塊包含名詞(N)和冠詞/介詞(X)稱具有NX*N形式的詞項(xiàng)序列為擴(kuò)展雙詞，放入詞典例子:catcherintheryeNXXN查詢處理：將查詢也分析成N和X序列將查詢切分成擴(kuò)展雙詞在索引中查找:catcherrye位置索引(Positionalindexes)是指帶詞項(xiàng)位置信息的倒排索引，即在倒排記錄表中，對(duì)每個(gè)詞項(xiàng)在每篇文檔中的每個(gè)位置(單詞序號(hào))進(jìn)行存儲(chǔ)目的：一般性地支持短語(yǔ)查詢和鄰近查詢<term,出現(xiàn)term的文檔篇數(shù)；doc1:位置1,位置2…;doc2:位置1,位置2…;等等><be:993427;1:7,18,33,72,86,231;2:3,149;4:17,191,291,430,434;5:363,367,…>基于位置索引的短語(yǔ)查詢處理短語(yǔ)查詢：“tobeornottobe”對(duì)每個(gè)詞項(xiàng)，抽出其對(duì)應(yīng)的倒排記錄表:to,be,or,not合并倒排記錄表，考慮位置匹配（保持位置關(guān)系一致）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;...K鄰近搜索中的搜索策略與此類似，不同的是此時(shí)考慮前后位置之間的距離不大于K基于位置索引的合并算法位置索引分析位置索引目前是實(shí)際檢索系統(tǒng)的標(biāo)配，這是因?yàn)閷?shí)際中需要處理短語(yǔ)和鄰近式查詢位置索引需要更大的存儲(chǔ)空間，因?yàn)樵黾恿宋恢眯畔?，但是可以采用索引壓縮技術(shù)進(jìn)行處理位置索引的大小大概是無(wú)位置信息索引的2-4倍位置索引大概是原始文本容量的35-50%提高了倒排記錄表合并操作的復(fù)雜性混合索引混合索引：將雙詞索引和位置索引合并形成的索引，其中雙詞為用戶查詢中的高頻雙詞目的：提高檢索效率對(duì)某些特定的短語(yǔ)

(如“MichaelJackson”,“BritneySpears”)，如果采用位置索引的方式