高性能檢索子系統(tǒng)

高性能檢索子系統(tǒng)主要內(nèi)容檢索系統(tǒng)基本技術(shù)倒排文件性能模型混合索引技術(shù)倒排文件緩存機(jī)制本章小結(jié)第2頁(yè),共89頁(yè)，2024年2月25日，星期天主要內(nèi)容檢索系統(tǒng)基本技術(shù)倒排文件性能模型混合索引技術(shù)倒排文件緩存機(jī)制本章小結(jié)第3頁(yè),共89頁(yè)，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)系統(tǒng)設(shè)計(jì)與結(jié)構(gòu)索引創(chuàng)建檢索過(guò)程第4頁(yè),共89頁(yè)，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)系統(tǒng)設(shè)計(jì)與結(jié)構(gòu)索引創(chuàng)建檢索過(guò)程第5頁(yè),共89頁(yè)，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)

-系統(tǒng)設(shè)計(jì)與結(jié)構(gòu)搜索引擎檢索系統(tǒng)設(shè)計(jì)遵循的指標(biāo)檢索效率—用戶查詢的響應(yīng)時(shí)間用戶的需求是“隨心所欲的”響應(yīng)遲緩的系統(tǒng)只能意味著較少的用戶檢索效果—用戶的滿意度搜索引擎的檢索技術(shù)相對(duì)于最新的信息檢索研究成果是落后的提高檢索效果面臨的問(wèn)題用戶普遍使用短查詢、不作優(yōu)化相關(guān)度計(jì)算第6頁(yè),共89頁(yè)，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)

-系統(tǒng)設(shè)計(jì)與結(jié)構(gòu)用戶查詢請(qǐng)求檢索代理布爾查詢?cè)獢?shù)據(jù)全局屬性語(yǔ)義約束SEServicePointIndexingServicePoint天網(wǎng)檢索系統(tǒng)集成框架結(jié)構(gòu)第7頁(yè),共89頁(yè)，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)

-系統(tǒng)設(shè)計(jì)與結(jié)構(gòu)天網(wǎng)檢索系統(tǒng)的設(shè)計(jì)原則系統(tǒng)效率和可擴(kuò)展性通過(guò)集成的框架結(jié)構(gòu)，能夠有效地把各種有利于改善檢索效果的技術(shù)集成起來(lái)天網(wǎng)系統(tǒng)框架文檔表示用戶信息需求的類型識(shí)別不同檢索排序方式得到的結(jié)果的融合第8頁(yè),共89頁(yè)，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)

-系統(tǒng)設(shè)計(jì)與結(jié)構(gòu)天網(wǎng)系統(tǒng)的實(shí)現(xiàn)基于信息檢索技術(shù)排序算法和模型的選擇模型布爾模型向量空間模型檢索系統(tǒng)的相關(guān)性排序由多種因素綜合決定查詢?cè)~的鄰接關(guān)系運(yùn)算結(jié)果查詢?cè)~出現(xiàn)的位置，包括Title、AnchorText相似度權(quán)值與其他的權(quán)值，如全局屬性的PageRank值第9頁(yè),共89頁(yè)，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)

-系統(tǒng)設(shè)計(jì)與結(jié)構(gòu)索引的實(shí)現(xiàn)技術(shù)采用倒排文件索引索引文件的組織結(jié)構(gòu)鏈表有利于提高更新效率，但會(huì)降低檢索效率索引項(xiàng)數(shù)據(jù)連續(xù)存放有利于提高檢索效率，但不利于更新索引文件的壓縮第10頁(yè),共89頁(yè)，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)

-系統(tǒng)設(shè)計(jì)與結(jié)構(gòu)檢索系統(tǒng)采用分布式系統(tǒng)結(jié)構(gòu)WWW1WWWnindex1index2indexNdoc1doc2docMWeb查詢服務(wù)節(jié)點(diǎn)索引服務(wù)節(jié)點(diǎn)文檔服務(wù)節(jié)點(diǎn)Internet檢索服務(wù)系統(tǒng)共使用20臺(tái)PC（PIII733/1GB）一臺(tái)為WWW查詢服務(wù)器，其余19臺(tái)為索引服務(wù)器，文檔服務(wù)節(jié)點(diǎn)和WWW查詢服務(wù)器使用同一機(jī)器第11頁(yè),共89頁(yè)，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)系統(tǒng)設(shè)計(jì)與結(jié)構(gòu)索引創(chuàng)建檢索過(guò)程第12頁(yè),共89頁(yè)，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)-索引創(chuàng)建索引詞選擇索引詞的選擇是檢索系統(tǒng)實(shí)現(xiàn)的一個(gè)重要環(huán)節(jié)中文文本必須通過(guò)自動(dòng)分詞程序的處理基于詞典的分詞方法基于統(tǒng)計(jì)語(yǔ)言模型的分詞方法英文文本統(tǒng)一轉(zhuǎn)換為小寫，但不作詞根詞形變換第13頁(yè),共89頁(yè)，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)-索引創(chuàng)建網(wǎng)頁(yè)預(yù)處理編碼轉(zhuǎn)換GBK、GB2312、GB18030……簡(jiǎn)繁轉(zhuǎn)換簡(jiǎn)繁并不是一一對(duì)應(yīng)的發(fā)（發(fā)、髮），臺(tái)（臺(tái)、檯、颱）大量網(wǎng)頁(yè)不符合HTML規(guī)范、網(wǎng)頁(yè)中存在大量無(wú)用的信息（廣告、導(dǎo)航條）第14頁(yè),共89頁(yè)，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)-索引創(chuàng)建索引創(chuàng)建算法頁(yè)面分析按HTML語(yǔ)法規(guī)則分析網(wǎng)頁(yè)標(biāo)簽結(jié)構(gòu)提取索引詞記錄每個(gè)索引詞的TF（詞頻）DF（文檔頻率）值通過(guò)散列表轉(zhuǎn)換為索引詞編碼，保存得到的詞典文件保存頁(yè)面分析的結(jié)果到臨時(shí)文件第15頁(yè),共89頁(yè)，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)-索引創(chuàng)建生成臨時(shí)倒排文件根據(jù)計(jì)算的TF和DF值，可以估算出倒排文件中相應(yīng)數(shù)據(jù)項(xiàng)的長(zhǎng)度，預(yù)申請(qǐng)整個(gè)文檔集合倒排所需要的內(nèi)存空間重新讀取頁(yè)面分析保存結(jié)果的臨時(shí)文件，在內(nèi)存中執(zhí)行倒排，把結(jié)果保存到臨時(shí)倒排文件中對(duì)生成的多個(gè)臨時(shí)倒排文件，執(zhí)行多路歸并、壓縮編碼，輸出得到最終的倒排文件第16頁(yè),共89頁(yè)，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)系統(tǒng)設(shè)計(jì)與結(jié)構(gòu)索引創(chuàng)建檢索過(guò)程第17頁(yè),共89頁(yè)，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)-檢索過(guò)程索引壓縮優(yōu)點(diǎn)減小倒排項(xiàng)數(shù)據(jù)長(zhǎng)度減少內(nèi)存和I/O帶寬的使用缺點(diǎn)對(duì)壓縮數(shù)據(jù)解碼，增加了CPU時(shí)間消耗方法字節(jié)對(duì)齊索引壓縮變長(zhǎng)索引壓縮第18頁(yè),共89頁(yè)，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)-檢索過(guò)程字節(jié)對(duì)齊索引壓縮用少量最左邊的比特位（bit）表示整數(shù)實(shí)際占用的字節(jié)數(shù)優(yōu)點(diǎn)容易編碼和解碼位操作少，占用CPU時(shí)間少缺點(diǎn)壓縮效率低每個(gè)整數(shù)至少占用一個(gè)字節(jié)的空間第19頁(yè),共89頁(yè)，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)-檢索過(guò)程整數(shù)大小需要字節(jié)0=<x<64164=<x<16,384216,384=<x<4,194,30434,194,304=<x<1,073,741,8244可變長(zhǎng)字節(jié)表示的整數(shù)第20頁(yè),共89頁(yè)，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)-檢索過(guò)程變長(zhǎng)索引壓縮一元編碼整數(shù)x編碼成x-1個(gè)比特位，后跟一個(gè)0表示結(jié)束104111071111110210511110811111110311061111109111111110第21頁(yè),共89頁(yè)，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)-檢索過(guò)程γ編碼將整數(shù)x分成兩個(gè)部分1+[logx]和x-2[logx]1+[logx]用一元編碼實(shí)現(xiàn)x-2[logx]用[logx]比特位的二進(jìn)制編碼表示整數(shù)一元編碼γ編碼10021010031101014111011000511110110016111110110107111111011011811111110111000091111111101110001第22頁(yè),共89頁(yè)，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)-檢索過(guò)程δ編碼將整數(shù)x分成兩個(gè)部分1+[logx]和x-2[logx]1+[logx]用γ編碼實(shí)現(xiàn)x-2[logx]用[logx]比特位的二進(jìn)制編碼表示當(dāng)整數(shù)小于15時(shí)，δ編碼比γ編碼編碼長(zhǎng)，大于15時(shí)，δ編碼優(yōu)于γ編碼整數(shù)一元編碼γ編碼δ編碼10002101001000311010110014111011000101005111101100110101611111011010101107111111011011101118111111101110000110000009111111110111000111000001第23頁(yè),共89頁(yè)，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)-檢索過(guò)程隨機(jī)訪問(wèn)的索引組織對(duì)索引項(xiàng)建立二級(jí)索引，使得可以隨機(jī)訪問(wèn)倒排項(xiàng)數(shù)據(jù)塊數(shù)據(jù)塊的大小小數(shù)據(jù)塊訪問(wèn)頻繁系統(tǒng)調(diào)用尋道時(shí)間消耗較大大數(shù)據(jù)塊訪問(wèn)讀入冗余數(shù)據(jù)數(shù)據(jù)傳輸時(shí)間消耗較大天網(wǎng)使用32K為最小塊單位第24頁(yè),共89頁(yè)，2024年2月25日，星期天檢索系統(tǒng)基本技術(shù)-檢索過(guò)程重要索引詞單獨(dú)索引可以產(chǎn)生小的倒排索引文件，保存在內(nèi)存中查詢?cè)谛∷饕募蝎@得足夠的返回結(jié)果，則查詢結(jié)束當(dāng)查詢得到的結(jié)果不足時(shí)，去訪問(wèn)磁盤上的整個(gè)倒排文件重要索引詞包括AnchorText、Title，文摘中的詞第25頁(yè),共89頁(yè)，2024年2月25日，星期天主要內(nèi)容檢索系統(tǒng)基本技術(shù)倒排文件性能模型混合索引技術(shù)倒排文件緩存機(jī)制本章小結(jié)第26頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件性能模型大規(guī)模信息檢索系統(tǒng)的主要指標(biāo)效果：即質(zhì)量，指檢索返回結(jié)果集合的準(zhǔn)確性和完整性（準(zhǔn)確率、召回率，第十章中介紹）效率：即性能查詢響應(yīng)時(shí)間（responsetime）從用戶想系統(tǒng)提交查詢到他開(kāi)始看到結(jié)果的時(shí)間間隔查詢吞吐率（throughput）系統(tǒng)在單位時(shí)間（秒）里可以服務(wù)的最大用戶查詢數(shù)量第27頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件性能模型倒排文件的概念倒排文件的一種性能模型結(jié)合計(jì)算機(jī)性能指標(biāo)的考慮第28頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件性能模型倒排文件的概念倒排文件的一種性能模型結(jié)合計(jì)算機(jī)性能指標(biāo)的考慮第29頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件性能模型

-倒排文件的概念倒排文件（InvertedFile）是描述一個(gè)詞項(xiàng)集合（terms）元素和一個(gè)文檔集合（docs）元素對(duì)應(yīng)關(guān)系的數(shù)據(jù)結(jié)構(gòu)詞項(xiàng)：可以是英文的單詞，也可以是中文的字或者詞terms={t1,t2,t3,……tM}docs={d1,d2,d3,……dN}M：詞項(xiàng)集合的大小N：文檔集合的大小第30頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件性能模型

-倒排文件的概念M詞項(xiàng)總數(shù)記錄表（PostingLists）不同詞項(xiàng)組成的索引Vocbulary每個(gè)詞項(xiàng)出現(xiàn)過(guò)的文檔集合第31頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件性能模型

-倒排文件的概念幾個(gè)相關(guān)的變量sj=|PL(tj)|詞項(xiàng)tj

所涉及的文檔的個(gè)數(shù)DF(tj)=sj/N詞項(xiàng)tj

的文檔頻率IDF(tj)=-lgDF(tj)?倒置文檔頻率，值越小表示出現(xiàn)頻率越高第32頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件性能模型

-倒排文件的概念fi,j第j個(gè)詞項(xiàng)tj

在第i個(gè)文檔di

中出現(xiàn)的次數(shù)

系統(tǒng)所有文檔包含詞項(xiàng)的總量（包括重復(fù)）

詞項(xiàng)tj

在所有文檔中出現(xiàn)的頻度ITF(tj)=-lgTF(tj)?倒置詞頻，越小表示出現(xiàn)頻率越高第33頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件性能模型

-倒排文件的概念M詞項(xiàng)總數(shù)N文檔總數(shù)sjp(i)：倒排表長(zhǎng)度分布q1q2……qk同時(shí)到達(dá)的查詢r(jià)：響應(yīng)時(shí)間B系統(tǒng)最大輸出帶寬S：實(shí)現(xiàn)吞吐率第34頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件性能模型倒排文件的概念倒排文件的一種性能模型結(jié)合計(jì)算機(jī)性能指標(biāo)的考慮第35頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件性能模型

-倒排文件的一種性能模型性能模型就是要給出N、M、p(i)、d、B、r和k的一種關(guān)系N：文檔總數(shù)M：詞項(xiàng)集合的大小p(i)：倒排表長(zhǎng)度分布d：文檔平均數(shù)據(jù)量B：系統(tǒng)最大輸出帶寬r：響應(yīng)時(shí)間K：同時(shí)到達(dá)的查詢的數(shù)量第36頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件性能模型

-倒排文件的一種性能模型對(duì)p(i)和B的說(shuō)明p(i)是倒排表長(zhǎng)度的統(tǒng)計(jì)分布函數(shù)M*p(i)的長(zhǎng)度表示i的記錄表的個(gè)數(shù)，i∈[0,N]倒排表的平均長(zhǎng)度為第37頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件性能模型

-倒排文件的一種性能模型B是系統(tǒng)最大輸出帶寬，是支持倒排文件運(yùn)行的下層系統(tǒng)的瓶頸帶寬磁盤的I/O帶寬網(wǎng)絡(luò)帶寬根據(jù)同時(shí)到達(dá)的查詢量k，得到一個(gè)數(shù)據(jù)量D，看能否有：針對(duì)查詢q1,q2,q3,……qk的假設(shè)它們都屬于集合terms它們?cè)趖erms上隨機(jī)、獨(dú)立分布對(duì)于磁盤I/O帶寬和網(wǎng)絡(luò)帶寬不作區(qū)別第38頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件性能模型

-倒排文件的一種性能模型倒排文件性能的基本模型考察k個(gè)查詢導(dǎo)致的輸出數(shù)據(jù)量D每個(gè)查詢可能落到M個(gè)詞項(xiàng)中的任何一個(gè)k個(gè)查詢可能涉及M的任何1,2,……k項(xiàng)，對(duì)應(yīng)不同的數(shù)據(jù)量計(jì)算涉及i項(xiàng)的概率fm,k(i)，i=1,2,3,……k第39頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件性能模型

-倒排文件的一種性能模型D=一個(gè)倒排表的平均數(shù)據(jù)量*k個(gè)并發(fā)查詢平均涉及的倒排表個(gè)數(shù)第40頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件性能模型

-倒排文件的一種性能模型考慮全文索引與非全文索引非全文索引：只考慮哪些文檔含有特定的詞項(xiàng)全文索引：還要考慮該詞在相關(guān)文檔中出現(xiàn)的位置信息全文索引的情況下，每個(gè)倒排表的數(shù)據(jù)量正比于文檔號(hào)和頻率位置信息占用的長(zhǎng)度第41頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件性能模型

-倒排文件的一種性能模型TN（所有文檔中詞的集合）遠(yuǎn)遠(yuǎn)大于N系統(tǒng)中每個(gè)詞項(xiàng)倒排表的長(zhǎng)度主要由詞頻率TF和數(shù)據(jù)規(guī)模TN決定的平均情況下非全文索引全文索引C表示了為記錄一個(gè)詞項(xiàng)在文檔中一次出現(xiàn)位置信息所需的數(shù)據(jù)量第42頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件性能模型

-倒排文件的一種性能模型倒排表的長(zhǎng)度影響操作執(zhí)行的時(shí)間索引網(wǎng)頁(yè)量增加時(shí)，高頻詞項(xiàng)的倒排表將急劇膨脹，占用大量I/O帶寬、內(nèi)存空間、CPU時(shí)間，降低系統(tǒng)效率理想情況：所有詞項(xiàng)頻率盡可能低，而且大小相近，使得所有倒排表同步增長(zhǎng)。詞項(xiàng)的頻率分布和語(yǔ)言相關(guān)第43頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件性能模型

-倒排文件的一種性能模型頻率英語(yǔ)單詞（E）漢語(yǔ)字符（H）0.1%1032520.07%1483480.05%2204750.02%6328670.01%128512150.007%178014000.005%238116090.002%547422100.001%67132676英漢詞頻統(tǒng)計(jì)排序?qū)φ盏?4頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件性能模型

-倒排文件的一種性能模型英語(yǔ)單詞和漢語(yǔ)字符的ITF分布第45頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件性能模型倒排文件的概念倒排文件的一種性能模型結(jié)合計(jì)算機(jī)性能指標(biāo)的考慮第46頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件性能模型

-結(jié)合計(jì)算機(jī)性能指標(biāo)的考慮決定系統(tǒng)性能的關(guān)鍵I/O的性能磁盤I/O網(wǎng)絡(luò)I/ODiskModelSize(GB)?AverageaccessTime(msec)?RPMRandomIOPSInternalTransferRate(MB/s)?InterfaceIBMUltrastar36ZX365.41000011915~29Ultra160QuantumAtlasV36.76.310000107.517~29Ultra160SeagateCheetahX1518.43.915000169.538~47FC-ALSeagateCheetah7373.45.61000011626~40Ultra160第47頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件性能模型

-結(jié)合計(jì)算機(jī)性能指標(biāo)的考慮提高磁盤I/O性能的方法Ultra160SCSI，最高帶寬可達(dá)150MBps當(dāng)前單個(gè)磁盤的平均數(shù)據(jù)傳輸率在20~50MBps之間解決辦法RAID：冗余磁盤陣列技術(shù)第48頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件性能模型

-結(jié)合計(jì)算機(jī)性能指標(biāo)的考慮系統(tǒng)吞吐量與倒排表索引的數(shù)據(jù)量假設(shè)將每個(gè)倒排表讀入內(nèi)存只需一次I/O，所花費(fèi)的時(shí)間為Tlatency：磁盤訪問(wèn)平均延遲時(shí)間（s）IObandwith：I/O可用帶寬（Bps）TN：所有文檔包含的詞項(xiàng)總量TF：頻率第49頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件性能模型

-結(jié)合計(jì)算機(jī)性能指標(biāo)的考慮每次讀取倒排表的時(shí)間乘Lq*m不大于1秒當(dāng)I/O系統(tǒng)性能（Tlatency、IObandwith）和TF確定下來(lái)后，可以看到TN和m之間成反比關(guān)系假設(shè)IOPS=100，Lq=5，則系統(tǒng)平均每秒處理查詢的上限是m=IOPS/Lq=20如果磁盤的可用帶寬為20MBps，則每個(gè)查詢的I/O小于1MB第50頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件性能模型

-結(jié)合計(jì)算機(jī)性能指標(biāo)的考慮根據(jù)上式，可得出如下結(jié)論對(duì)漢字字符：TN=<400MB（TF=0.05%，Lq=5）對(duì)英文字符：TN=<4GB（TF=0.005%，Lq=5）第51頁(yè),共89頁(yè)，2024年2月25日，星期天主要內(nèi)容檢索系統(tǒng)基本技術(shù)倒排文件性能模型混合索引技術(shù)倒排文件緩存機(jī)制本章小結(jié)第52頁(yè),共89頁(yè)，2024年2月25日，星期天混合索引技術(shù)混合索引原理混合索引實(shí)現(xiàn)第53頁(yè),共89頁(yè)，2024年2月25日，星期天混合索引技術(shù)混合索引原理混合索引實(shí)現(xiàn)第54頁(yè),共89頁(yè)，2024年2月25日，星期天混合索引技術(shù)-混合索引原理索引技術(shù)面臨的問(wèn)題通過(guò)自動(dòng)分詞來(lái)選擇索引詞分詞單位是指具有確定語(yǔ)義或語(yǔ)法功能的基本單位目前，中文自動(dòng)分詞的成熟技術(shù)都是基于分詞詞典的機(jī)械型分詞方法網(wǎng)上大量的常用詞、新出現(xiàn)詞、專業(yè)詞匯，詞典中沒(méi)有收錄分詞詞典的分詞單位一般很短，導(dǎo)致常用的短語(yǔ)也會(huì)被分詞程序且分開(kāi)第55頁(yè),共89頁(yè)，2024年2月25日，星期天混合索引技術(shù)-混合索引原理混合索引技術(shù)用統(tǒng)計(jì)的方法對(duì)索引文檔中的未登錄詞進(jìn)行識(shí)別，把識(shí)別出的新詞（詞典中未收錄的字串）放入一個(gè)擴(kuò)展詞典有效擴(kuò)大詞典的規(guī)模統(tǒng)計(jì)的方法存在相當(dāng)?shù)腻e(cuò)誤率天網(wǎng)中，擴(kuò)展詞典的規(guī)?？刂圃?0萬(wàn)詞左右第56頁(yè),共89頁(yè)，2024年2月25日，星期天混合索引技術(shù)-混合索引原理索引創(chuàng)建過(guò)程中首先是基于基本分詞詞典的常規(guī)分詞對(duì)基本分詞結(jié)果使用基于擴(kuò)展詞典的分詞兩次的分詞結(jié)果都被選擇作為索引詞例如：基本詞典中有“國(guó)家”、“圖書館”兩個(gè)基本詞條，無(wú)“國(guó)家圖書館”系統(tǒng)通過(guò)未登錄詞識(shí)別，把“國(guó)家圖書館”加入擴(kuò)展詞典文檔中出現(xiàn)“……國(guó)家圖書館……”字串，第一遍分詞得到“國(guó)家”、“圖書館”兩個(gè)基本詞條，第二遍得到“國(guó)家圖書館”最終索引詞包括“國(guó)家”、“圖書館”、“/2國(guó)家圖書館”三個(gè)單位?！?”表示轉(zhuǎn)義符，后面數(shù)字表示擴(kuò)展詞包含的基本分詞詞條個(gè)數(shù)第57頁(yè),共89頁(yè)，2024年2月25日，星期天混合索引技術(shù)-混合索引原理對(duì)用戶輸入的查詢串的處理首先是基于基本分詞詞典的常規(guī)分詞對(duì)基本分詞結(jié)果使用基于擴(kuò)展詞典的分詞例如用戶輸入查詢“國(guó)家圖書館”經(jīng)過(guò)兩遍分詞，得到“國(guó)家”、“圖書館”、“/2國(guó)家圖書館”三個(gè)單位前兩個(gè)基本詞條被第三個(gè)擴(kuò)展詞條覆蓋，查詢執(zhí)行時(shí)只需直接讀取索引詞“/2國(guó)家圖書館”對(duì)應(yīng)的倒排項(xiàng)數(shù)據(jù)，即可完成查詢第58頁(yè),共89頁(yè)，2024年2月25日，星期天混合索引技術(shù)-混合索引原理混合索引vs.短語(yǔ)索引混合索引使用統(tǒng)一的倒排索引詞典，沒(méi)有額外的二級(jí)索引詞典訪問(wèn)開(kāi)銷混合索引不限制擴(kuò)展詞條為兩個(gè)基本詞條長(zhǎng)，可以索引更長(zhǎng)的短語(yǔ)，更加靈活混合索引vs.詞索引+Bi-gram混合索引使用了未登錄詞識(shí)別技術(shù)，可以有效控制倒排索引詞典規(guī)模，避免了Bi-gram詞典膨脹的問(wèn)題第59頁(yè),共89頁(yè)，2024年2月25日，星期天混合索引技術(shù)混合索引原理混合索引實(shí)現(xiàn)第60頁(yè),共89頁(yè)，2024年2月25日，星期天混合索引技術(shù)-混合索引實(shí)現(xiàn)未登錄詞的識(shí)別提取n元組使用基本詞典，將文本進(jìn)行部分分詞，從部分分詞結(jié)果中提取n元組單字，只有連續(xù)出現(xiàn)的單字才能生成n元組形成新詞的n元組必須包含一個(gè)單字噪聲剔除刪除那些包含低構(gòu)詞能力字的n元組第61頁(yè),共89頁(yè)，2024年2月25日，星期天混合索引技術(shù)-混合索引實(shí)現(xiàn)剔除n元重疊把那些在n取不同值情況下重復(fù)被提取的n元組剔除最后剩下的n元組按出現(xiàn)頻次降序排列，為識(shí)別結(jié)果第62頁(yè),共89頁(yè)，2024年2月25日，星期天混合索引技術(shù)-混合索引實(shí)現(xiàn)擴(kuò)展詞典組織與分詞輸入基本分次結(jié)果序列，找到序列中在擴(kuò)展詞典里的所有最長(zhǎng)匹配詞條基本詞典和擴(kuò)展詞典中的詞典均按照整數(shù)編碼進(jìn)行存放市……大學(xué)……NULL生NULL北京NULL第63頁(yè),共89頁(yè)，2024年2月25日，星期天混合索引技術(shù)-混合索引實(shí)現(xiàn)擴(kuò)展詞典匹配查找算法輸入：基本分次結(jié)果詞條序列（t1,t2,……ti）輸出：最長(zhǎng)匹配擴(kuò)展詞條init_scoreboard();初始化匹配任務(wù)表while（ti!=EOF）{code=get_code(ti);從編碼三列表中取得ti的編碼foreachtaskinscoreboard{ret=search_token(code);測(cè)匹配任務(wù)追加一個(gè)詞，是否結(jié)束？if(ret==NULL){clear_taskadd_hit;得到一個(gè)匹配}elseupdate_task;根據(jù)檢測(cè)結(jié)果更新匹配任務(wù)狀態(tài)}check_hit；檢測(cè)匹配結(jié)果，輸出}第64頁(yè),共89頁(yè)，2024年2月25日，星期天主要內(nèi)容檢索系統(tǒng)基本技術(shù)倒排文件性能模型混合索引技術(shù)倒排文件緩存機(jī)制本章小結(jié)第65頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件緩存機(jī)制搜索引擎檢索系統(tǒng)中通常被研究的緩存對(duì)象查詢結(jié)果用戶查詢具有很強(qiáng)的局部性，因此對(duì)查詢結(jié)果進(jìn)行緩存是可行的布爾操作的中間結(jié)果把布爾查詢的中間結(jié)果作為緩存對(duì)象，并利用查詢結(jié)果間的語(yǔ)義關(guān)系加速后續(xù)查詢的執(zhí)行倒排文件用戶查詢經(jīng)過(guò)查詢器執(zhí)行，轉(zhuǎn)換為對(duì)倒排文件數(shù)據(jù)的訪問(wèn)序列，這些數(shù)據(jù)也可以作為緩存的對(duì)象第66頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件緩存機(jī)制倒排文件緩存負(fù)載特性緩存策略的選擇第67頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件緩存機(jī)制倒排文件緩存負(fù)載特性緩存策略的選擇第68頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件緩存機(jī)制

-倒排文件緩存體系結(jié)構(gòu)倒排文件倒排文件緩存查詢執(zhí)行器查詢結(jié)果緩存用戶查詢結(jié)果查詢服務(wù)器索引服務(wù)節(jié)點(diǎn)第69頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件緩存機(jī)制

-倒排文件緩存用戶提交的查詢中包含查詢?cè)~的個(gè)數(shù)通常很少，詞間的位置臨近關(guān)系對(duì)結(jié)果排序十分重要天網(wǎng)使用帶位置數(shù)據(jù)的全文倒排索引，對(duì)多個(gè)詞的用戶查詢計(jì)算臨近權(quán)值查詢執(zhí)行器訪問(wèn)倒排文件的數(shù)據(jù)分為兩類查詢?cè)~對(duì)應(yīng)的倒排表中的文檔編號(hào)和文檔內(nèi)權(quán)值數(shù)據(jù)文檔數(shù)據(jù)查詢?cè)~對(duì)應(yīng)的出現(xiàn)在每篇文檔中的位置數(shù)據(jù)位置數(shù)據(jù)第70頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件緩存機(jī)制

-倒排文件緩存執(zhí)行過(guò)程各個(gè)查詢?cè)~按倒置文檔頻率降序處理讀取文檔數(shù)據(jù)，執(zhí)行文檔集合的布爾運(yùn)算，得到一個(gè)小的結(jié)果集合使用文檔內(nèi)權(quán)值數(shù)據(jù)計(jì)算每個(gè)結(jié)果文檔對(duì)查詢的相關(guān)性讀取對(duì)應(yīng)的位置數(shù)據(jù)，對(duì)結(jié)果集合進(jìn)行鄰近權(quán)值排序第71頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件緩存機(jī)制

-倒排文件緩存名稱數(shù)值名稱數(shù)值用戶查詢總數(shù)7,341,383I/O序列長(zhǎng)度1,887,198結(jié)果緩存未命中個(gè)數(shù)3,522,968I/O序列唯一對(duì)象數(shù)112,145文檔總數(shù)2,603,035PAGE序列長(zhǎng)度20,808,025文檔數(shù)據(jù)原始大小30.18GBPAGE序列唯一對(duì)象數(shù)965,929倒排文件大小5.77GB數(shù)據(jù)集基本統(tǒng)計(jì)統(tǒng)計(jì)信息第72頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件緩存機(jī)制倒排文件緩存負(fù)載特性緩存策略的選擇第73頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件緩存機(jī)制-負(fù)載特性I/O序列對(duì)象大小位置數(shù)據(jù)訪問(wèn)產(chǎn)生的部分是固定大?。?2KB）文檔數(shù)據(jù)訪問(wèn)產(chǎn)生的對(duì)象大小分布很不均勻有效的緩存替換算法需要考慮對(duì)象的大小大量的小數(shù)據(jù)對(duì)象優(yōu)先緩存，可以提高緩存的命中率大對(duì)象優(yōu)先緩存可以提高緩存的字節(jié)命中率第74頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件緩存機(jī)制-負(fù)載特性文檔數(shù)據(jù)訪問(wèn)對(duì)象大小分布第75頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件緩存機(jī)制-負(fù)載特性序列中對(duì)象的頻度分布如果序列中對(duì)象訪問(wèn)頻率分布不均勻緩存少數(shù)高頻對(duì)象可以提高性能不區(qū)分出大量低頻對(duì)象將降低性能對(duì)象訪問(wèn)頻率和訪問(wèn)的時(shí)間局部性是相關(guān)的頻率是倒排文件緩存替換算法應(yīng)該考慮的一個(gè)因素I/O序列的頻率特性比PAGE序列更有利于緩存第76頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件緩存機(jī)制-負(fù)載特性I/O與PAGE序列序號(hào)--頻度分布第77頁(yè),共89頁(yè)，2024年2月25日，星期天倒排文件緩存機(jī)制-負(fù)載特性序列中對(duì)象的時(shí)間間隔分布序列的時(shí)間局部性可以從序列中對(duì)同一個(gè)對(duì)象的兩次連續(xù)訪問(wèn)的時(shí)間間隔分布來(lái)考察I/O序列可以預(yù)期得到比PAGE序列更高的緩存命中率較強(qiáng)的時(shí)間局部性有利于緩存的設(shè)計(jì)第78頁(yè),共