第六章高性能檢索子系統(tǒng)張宇計算機科學與技術學院第六章高性能檢索子系統(tǒng)張宇1主要內容檢索系統(tǒng)基本技術倒排文件性能模型混合索引技術倒排文件緩存機制本章小結主要內容檢索系統(tǒng)基本技術主要內容檢索系統(tǒng)基本技術倒排文件性能模型混合索引技術倒排文件緩存機制本章小結主要內容檢索系統(tǒng)基本技術檢索系統(tǒng)基本技術系統(tǒng)設計與結構索引創(chuàng)建檢索過程檢索系統(tǒng)基本技術系統(tǒng)設計與結構檢索系統(tǒng)基本技術系統(tǒng)設計與結構索引創(chuàng)建檢索過程檢索系統(tǒng)基本技術系統(tǒng)設計與結構檢索系統(tǒng)基本技術

-系統(tǒng)設計與結構搜索引擎檢索系統(tǒng)設計遵循的指標檢索效率—用戶查詢的響應時間用戶的需求是“隨心所欲的”響應遲緩的系統(tǒng)只能意味著較少的用戶檢索效果—用戶的滿意度搜索引擎的檢索技術相對于最新的信息檢索研究成果是落后的提高檢索效果面臨的問題用戶普遍使用短查詢、不作優(yōu)化相關度計算檢索系統(tǒng)基本技術

-檢索系統(tǒng)基本技術

-系統(tǒng)設計與結構用戶查詢請求檢索代理布爾查詢元數(shù)據(jù)全局屬性語義約束SEServicePointIndexingServicePoint天網(wǎng)檢索系統(tǒng)集成框架結構檢索系統(tǒng)基本技術

-檢索系統(tǒng)基本技術

-系統(tǒng)設計與結構天網(wǎng)檢索系統(tǒng)的設計原則系統(tǒng)效率和可擴展性通過集成的框架結構，能夠有效地把各種有利于改善檢索效果的技術集成起來天網(wǎng)系統(tǒng)框架文檔表示用戶信息需求的類型識別不同檢索排序方式得到的結果的融合檢索系統(tǒng)基本技術

-檢索系統(tǒng)基本技術

-系統(tǒng)設計與結構天網(wǎng)系統(tǒng)的實現(xiàn)基于信息檢索技術排序算法和模型的選擇模型布爾模型向量空間模型檢索系統(tǒng)的相關性排序由多種因素綜合決定查詢詞的鄰接關系運算結果查詢詞出現(xiàn)的位置，包括Title、AnchorText相似度權值與其他的權值，如全局屬性的PageRank值檢索系統(tǒng)基本技術

-檢索系統(tǒng)基本技術

-系統(tǒng)設計與結構索引的實現(xiàn)技術采用倒排文件索引索引文件的組織結構鏈表有利于提高更新效率，但會降低檢索效率索引項數(shù)據(jù)連續(xù)存放有利于提高檢索效率，但不利于更新索引文件的壓縮檢索系統(tǒng)基本技術

-檢索系統(tǒng)基本技術

-系統(tǒng)設計與結構檢索系統(tǒng)采用分布式系統(tǒng)結構WWW1WWWnindex1index2indexNdoc1doc2docMWeb查詢服務節(jié)點索引服務節(jié)點文檔服務節(jié)點Internet檢索服務系統(tǒng)共使用20臺PC（PIII733/1GB）一臺為WWW查詢服務器，其余19臺為索引服務器，文檔服務節(jié)點和WWW查詢服務器使用同一機器檢索系統(tǒng)基本技術

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

-倒排文件的概念倒排文件（InvertedFile）是描述一個詞項集合（terms）元素和一個文檔集合（docs）元素對應關系的數(shù)據(jù)結構詞項：可以是英文的單詞，也可以是中文的字或者詞terms={t1,t2,t3,……tM}docs={d1,d2,d3,……dN}M：詞項集合的大小N：文檔集合的大小倒排文件性能模型

-倒倒排文件性能模型

-倒排文件的概念M詞項總數(shù)記錄表（PostingLists）不同詞項組成的索引Vocbulary每個詞項出現(xiàn)過的文檔集合倒排文件性能模型

-倒倒排文件性能模型

-倒排文件的概念幾個相關的變量sj=|PL(tj)|詞項tj所涉及的文檔的個數(shù)DF(tj)=sj/N詞項tj的文檔頻率IDF(tj)=-lgDF(tj)?倒置文檔頻率，值越小表示出現(xiàn)頻率越高倒排文件性能模型

-倒倒排文件性能模型

-倒排文件的概念fi,j第j個詞項tj在第i個文檔di中出現(xiàn)的次數(shù)

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

詞項tj在所有文檔中出現(xiàn)的頻度ITF(tj)=-lgTF(tj)?倒置詞頻，越小表示出現(xiàn)頻率越高倒排文件性能模型

-倒倒排文件性能模型

-倒排文件的概念M詞項總數(shù)N文檔總數(shù)sjp(i)：倒排表長度分布q1q2……qk同時到達的查詢r：響應時間B系統(tǒng)最大輸出帶寬S：實現(xiàn)吞吐率倒排文件性能模型

-倒倒排文件性能模型倒排文件的概念倒排文件的一種性能模型結合計算機性能指標的考慮倒排文件性能模型倒排文件的概念倒排文件性能模型

-倒排文件的一種性能模型性能模型就是要給出N、M、p(i)、d、B、r和k的一種關系N：文檔總數(shù)M：詞項集合的大小p(i)：倒排表長度分布d：文檔平均數(shù)據(jù)量B：系統(tǒng)最大輸出帶寬r：響應時間K：同時到達的查詢的數(shù)量倒排文件性能模型

-倒排文件的一種性能模型性能倒排文件性能模型

-倒排文件的一種性能模型對p(i)和B的說明p(i)是倒排表長度的統(tǒng)計分布函數(shù)M*p(i)的長度表示i的記錄表的個數(shù)，i∈[0,N]倒排表的平均長度為倒排文件性能模型

-倒排文件的一種性能模型對倒排文件性能模型

-倒排文件的一種性能模型B是系統(tǒng)最大輸出帶寬，是支持倒排文件運行的下層系統(tǒng)的瓶頸帶寬磁盤的I/O帶寬網(wǎng)絡帶寬根據(jù)同時到達的查詢量k，得到一個數(shù)據(jù)量D，看能否有：針對查詢q1,q2,q3,……qk的假設它們都屬于集合terms它們在terms上隨機、獨立分布對于磁盤I/O帶寬和網(wǎng)絡帶寬不作區(qū)別倒排文件性能模型

-倒排文件的一種性能模型B倒排文件性能模型

-倒排文件的一種性能模型倒排文件性能的基本模型考察k個查詢導致的輸出數(shù)據(jù)量D每個查詢可能落到M個詞項中的任何一個k個查詢可能涉及M的任何1,2,……k項，對應不同的數(shù)據(jù)量計算涉及i項的概率fm,k(i)，i=1,2,3,……k倒排文件性能模型

-倒排文件的一種性能模型倒排倒排文件性能模型

-倒排文件的一種性能模型D=一個倒排表的平均數(shù)據(jù)量*k個并發(fā)查詢平均涉及的倒排表個數(shù)倒排文件性能模型

-倒排文件的一種性能模型D倒排文件性能模型

-倒排文件的一種性能模型考慮全文索引與非全文索引非全文索引：只考慮哪些文檔含有特定的詞項全文索引：還要考慮該詞在相關文檔中出現(xiàn)的位置信息全文索引的情況下，每個倒排表的數(shù)據(jù)量正比于文檔號和頻率位置信息占用的長度倒排文件性能模型

-倒排文件的一種性能模型考慮倒排文件性能模型

-倒排文件的一種性能模型TN（所有文檔中詞的集合）遠遠大于N系統(tǒng)中每個詞項倒排表的長度主要由詞頻率TF和數(shù)據(jù)規(guī)模TN決定的平均情況下非全文索引全文索引C表示了為記錄一個詞項在文檔中一次出現(xiàn)位置信息所需的數(shù)據(jù)量倒排文件性能模型

-倒排文件的一種性能模型TN倒排文件性能模型

-倒排文件的一種性能模型倒排表的長度影響操作執(zhí)行的時間索引網(wǎng)頁量增加時，高頻詞項的倒排表將急劇膨脹，占用大量I/O帶寬、內存空間、CPU時間，降低系統(tǒng)效率理想情況：所有詞項頻率盡可能低，而且大小相近，使得所有倒排表同步增長。詞項的頻率分布和語言相關倒排文件性能模型

-倒排文件的一種性能模型倒排倒排文件性能模型

-倒排文件的一種性能模型頻率英語單詞（E）漢語字符（H）0.1%1032520.07%1483480.05%2204750.02%6328670.01%128512150.007%178014000.005%238116090.002%547422100.001%67132676英漢詞頻統(tǒng)計排序對照倒排文件性能模型

-倒排文件的一種性能模型頻率倒排文件性能模型

-倒排文件的一種性能模型英語單詞和漢語字符的ITF分布倒排文件性能模型

-倒排文件的一種性能模型英語倒排文件性能模型倒排文件的概念倒排文件的一種性能模型結合計算機性能指標的考慮倒排文件性能模型倒排文件的概念倒排文件性能模型

-結合計算機性能指標的考慮決定系統(tǒng)性能的關鍵I/O的性能磁盤I/O網(wǎng)絡I/ODiskModelSize(GB)?AverageaccessTime(msec)?RPMRandomIOPSInternalTransferRate(MB/s)?InterfaceIBMUltrastar36ZX365.41000011915~29Ultra160QuantumAtlasV36.76.310000107.517~29Ultra160SeagateCheetahX1518.43.915000169.538~47FC-ALSeagateCheetah7373.45.61000011626~40Ultra160倒排文件性能模型

-結合計算機性能指標的考慮決定系統(tǒng)倒排文件性能模型

-結合計算機性能指標的考慮提高磁盤I/O性能的方法Ultra160SCSI，最高帶寬可達150MBps當前單個磁盤的平均數(shù)據(jù)傳輸率在20~50MBps之間解決辦法RAID：冗余磁盤陣列技術倒排文件性能模型

-結合計算機性能指標的考慮提高磁盤倒排文件性能模型

-結合計算機性能指標的考慮系統(tǒng)吞吐量與倒排表索引的數(shù)據(jù)量假設將每個倒排表讀入內存只需一次I/O，所花費的時間為Tlatency：磁盤訪問平均延遲時間（s）IObandwith：I/O可用帶寬（Bps）TN：所有文檔包含的詞項總量TF：頻率倒排文件性能模型

-結合計算機性能指標的考慮系統(tǒng)吞吐倒排文件性能模型

-結合計算機性能指標的考慮每次讀取倒排表的時間乘Lq*m不大于1秒當I/O系統(tǒng)性能（Tlatency、IObandwith）和TF確定下來后，可以看到TN和m之間成反比關系假設IOPS=100，Lq=5，則系統(tǒng)平均每秒處理查詢的上限是m=IOPS/Lq=20如果磁盤的可用帶寬為20MBps，則每個查詢的I/O小于1MB倒排文件性能模型

-結合計算機性能指標的考慮每次讀取倒排文件性能模型

-結合計算機性能指標的考慮根據(jù)上式，可得出如下結論對漢字字符：TN=<400MB（TF=0.05%，Lq=5）對英文字符：TN=<4GB（TF=0.005%，Lq=5）倒排文件性能模型

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

-倒排文件緩存體系結構倒排文件倒排文件緩存查詢執(zhí)行器查詢結果緩存用戶查詢結果查詢服務器索引服務節(jié)點倒排文件緩存機制

倒排文件緩存機制

-倒排文件緩存用戶提交的查詢中包含查詢詞的個數(shù)通常很少，詞間的位置臨近關系對結果排序十分重要天網(wǎng)使用帶位置數(shù)據(jù)的全文倒排索引，對多個詞的用戶查詢計算臨近權值查詢執(zhí)行器訪問倒排文件的數(shù)據(jù)分為兩類查詢詞對應的倒排表中的文檔編號和文檔內權值數(shù)據(jù)文檔數(shù)據(jù)查詢詞對應的出現(xiàn)在每篇文檔中的位置數(shù)據(jù)位置數(shù)據(jù)倒排文件緩存機制

倒排文件緩存機制

-倒排文件緩存執(zhí)行過程各個查詢詞按倒置文檔頻率降序處理讀取文檔數(shù)據(jù)，執(zhí)行文檔集合的布爾運算，得到一個小的結果集合使用文檔內權值數(shù)據(jù)計算每個結果文檔對查詢的相關性讀取對應的位置數(shù)據(jù)，對結果集合進行鄰近權值排序倒排文件緩存機制

倒排文件緩存機制

-倒排文件緩存名稱數(shù)值名稱數(shù)值用戶查詢總數(shù)7,341,383I/O序列長度1,887,198結果緩存未命中個數(shù)3,522,968I/O序列唯一對象數(shù)112,145文檔總數(shù)2,603,035PAGE序列長度20,808,025文檔數(shù)據(jù)原始大小30.18GBPAGE序列唯一對象數(shù)965,929倒排文件大小5.77GB數(shù)據(jù)集基本統(tǒng)計統(tǒng)計信息倒排文件緩存機制

倒排文件緩存機制倒排文件緩存負載特性緩存策略的選擇倒排文件緩存機制倒排文件緩存倒排文件緩存機制-負載特性I/O序列對象大小位置數(shù)據(jù)訪問產生的部分是固定大小（32KB）文檔數(shù)據(jù)訪問產生的對象大小分布很不均勻有效的緩存替換算法需要考慮對象的大小大量的小數(shù)據(jù)對象優(yōu)先緩存，可以提高緩存的命中率大對象優(yōu)先緩存可以提高緩存的字節(jié)命中率倒排文件緩存機制-負載特性I/O序列對象大小倒排文件緩存機制-負載特性文檔數(shù)據(jù)訪問對象大小分布倒排文件緩存機制-負載特性文倒排文件緩存機制-負載特性序列中對象的頻度分布如果序列中對象訪問頻率分布不均勻緩存少數(shù)高頻對象可以提高性能不區(qū)分出大量低頻對象將降低性能對象訪問頻率和訪問的時間局部性是相關的頻率是倒排文件緩存替換算法應該考慮的一個因素I/O序列的頻率特性比PAGE序列更有利于緩存倒排文件緩存機制-負載特性序列中對象的頻度分布倒排文件緩存機制-負載特性I/O與PAGE序列序號--頻度分布倒排文件緩存機制-負載特性I/O倒排文件緩存機制-負載特性序列中對象的時間間隔分布序列的時間局部性可以從序列中對同一個對象的兩次連續(xù)訪問的時間間隔分布來考察I/O序列可以預期得到比PAGE序列更高的緩存命中率較強的時間局部性有利于緩存的設計倒排文件緩存機制-負載特性序列中對象的時間間隔分布倒排文件緩存機制-負載特性I/O與PAGE序列時間間隔分布倒排文件緩存機制-負載特性I/O倒排文件緩存機制-負載特性序列的重復模式序列的空間局部性是指序列中固定模式的重復，可以通過原始序列和隨機排列處理后的序列中的唯一的定長串個數(shù)來說明空間局部性也是緩存設計需要考慮的因素倒排文件緩存機制-負載特性序列的重復模式倒排文件緩存機制-負載特性I/O與PAGE序列中唯一模式串倒排文件緩存機制-負載特性I/O倒排文件緩存機制倒排文件緩存負載特性緩存策略的選擇倒排文件緩存機制倒排文件緩存倒排文件緩存機制

-緩存策略的選擇緩存變長的I/O序列對象，采用GD-SIZE1替換算法，可以明顯減少磁盤系統(tǒng)I/O訪問次數(shù)通過按頁面對齊方式組織倒排文件，選取大的頁面作為訪問倒排文件的單位，可以使磁盤系統(tǒng)寬帶利用率得到優(yōu)化倒排文件緩存機制

-倒排文件緩存機制

-緩存策略的選擇主要替換算法LRU：替換最近最少使用的對象LFU：替換緩存中最少被引用的對象LRU—k：替換緩存中最近第K次訪問時間最遠的對象。K=2時，性能提高比較明顯SIZE：替換最大的對象試圖保留更多的小對象來提高命中率倒排文件緩存機制

-倒排文件緩存機制

-緩存策略的選擇天網(wǎng)使用的替換算法：GD—SIZE算法替換效用最小的對象效用的計算如下：ci是對象i裝入緩存的代價si是對象i的大小L是緩存運行的年齡因子倒排文件緩存機制

-倒排文件緩存機制

-緩存策略的選擇ci取1時，為GD—SIZE1算法L相同時，先替換大對象，具有較好的命中率倒排文件緩存機制

-倒排文件緩存機制

-緩存策略的選擇I/O緩存替換算法比較倒排文件緩存機制

-主要內容檢索系統(tǒng)基本技術倒排文件性能模型混合索引技術倒排文件緩存機制本章小結主要內容檢索系統(tǒng)基本技術本章小結檢索系統(tǒng)的設計目標圍繞著檢索效果和檢索效率兩方面展開從I/O數(shù)據(jù)量的角度分析了影響倒排文件查詢效率的各種因素，以及提高系統(tǒng)效率的一些技術，試圖定量描述數(shù)據(jù)規(guī)模和查詢效率之間的關系提出了基于自動識別新詞技術的混合索引技術，有效地提高搜索引擎的檢索效率，同時不會導致檢索效果下降本章小結檢索系統(tǒng)的設計目標圍繞著檢索效果和檢索效率兩方面展開第六章高性能檢索子系統(tǒng)張宇計算機科學與技術學院第六章高性能檢索子系統(tǒng)張宇90主要內容檢索系統(tǒng)基本技術倒排文件性能模型混合索引技術倒排文件緩存機制本章小結主要內容檢索系統(tǒng)基本技術主要內容檢索系統(tǒng)基本技術倒排文件性能模型混合索引技術倒排文件緩存機制本章小結主要內容檢索系統(tǒng)基本技術檢索系統(tǒng)基本技術系統(tǒng)設計與結構索引創(chuàng)建檢索過程檢索系統(tǒng)基本技術系統(tǒng)設計與結構檢索系統(tǒng)基本技術系統(tǒng)設計與結構索引創(chuàng)建檢索過程檢索系統(tǒng)基本技術系統(tǒng)設計與結構檢索系統(tǒng)基本技術

-系統(tǒng)設計與結構搜索引擎檢索系統(tǒng)設計遵循的指標檢索效率—用戶查詢的響應時間用戶的需求是“隨心所欲的”響應遲緩的系統(tǒng)只能意味著較少的用戶檢索效果—用戶的滿意度搜索引擎的檢索技術相對于最新的信息檢索研究成果是落后的提高檢索效果面臨的問題用戶普遍使用短查詢、不作優(yōu)化相關度計算檢索系統(tǒng)基本技術

-檢索系統(tǒng)基本技術

-系統(tǒng)設計與結構用戶查詢請求檢索代理布爾查詢元數(shù)據(jù)全局屬性語義約束SEServicePointIndexingServicePoint天網(wǎng)檢索系統(tǒng)集成框架結構檢索系統(tǒng)基本技術

-檢索系統(tǒng)基本技術

-系統(tǒng)設計與結構天網(wǎng)檢索系統(tǒng)的設計原則系統(tǒng)效率和可擴展性通過集成的框架結構，能夠有效地把各種有利于改善檢索效果的技術集成起來天網(wǎng)系統(tǒng)框架文檔表示用戶信息需求的類型識別不同檢索排序方式得到的結果的融合檢索系統(tǒng)基本技術

-檢索系統(tǒng)基本技術

-系統(tǒng)設計與結構天網(wǎng)系統(tǒng)的實現(xiàn)基于信息檢索技術排序算法和模型的選擇模型布爾模型向量空間模型檢索系統(tǒng)的相關性排序由多種因素綜合決定查詢詞的鄰接關系運算結果查詢詞出現(xiàn)的位置，包括Title、AnchorText相似度權值與其他的權值，如全局屬性的PageRank值檢索系統(tǒng)基本技術

-檢索系統(tǒng)基本技術

-系統(tǒng)設計與結構索引的實現(xiàn)技術采用倒排文件索引索引文件的組織結構鏈表有利于提高更新效率，但會降低檢索效率索引項數(shù)據(jù)連續(xù)存放有利于提高檢索效率，但不利于更新索引文件的壓縮檢索系統(tǒng)基本技術

-檢索系統(tǒng)基本技術

-系統(tǒng)設計與結構檢索系統(tǒng)采用分布式系統(tǒng)結構WWW1WWWnindex1index2indexNdoc1doc2docMWeb查詢服務節(jié)點索引服務節(jié)點文檔服務節(jié)點Internet檢索服務系統(tǒng)共使用20臺PC（PIII733/1GB）一臺為WWW查詢服務器，其余19臺為索引服務器，文檔服務節(jié)點和WWW查詢服務器使用同一機器檢索系統(tǒng)基本技術

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

-倒排文件的概念倒排文件（InvertedFile）是描述一個詞項集合（terms）元素和一個文檔集合（docs）元素對應關系的數(shù)據(jù)結構詞項：可以是英文的單詞，也可以是中文的字或者詞terms={t1,t2,t3,……tM}docs={d1,d2,d3,……dN}M：詞項集合的大小N：文檔集合的大小倒排文件性能模型

-倒倒排文件性能模型

-倒排文件的概念M詞項總數(shù)記錄表（PostingLists）不同詞項組成的索引Vocbulary每個詞項出現(xiàn)過的文檔集合倒排文件性能模型

-倒倒排文件性能模型

-倒排文件的概念幾個相關的變量sj=|PL(tj)|詞項tj所涉及的文檔的個數(shù)DF(tj)=sj/N詞項tj的文檔頻率IDF(tj)=-lgDF(tj)?倒置文檔頻率，值越小表示出現(xiàn)頻率越高倒排文件性能模型

-倒倒排文件性能模型

-倒排文件的概念fi,j第j個詞項tj在第i個文檔di中出現(xiàn)的次數(shù)

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

詞項tj在所有文檔中出現(xiàn)的頻度ITF(tj)=-lgTF(tj)?倒置詞頻，越小表示出現(xiàn)頻率越高倒排文件性能模型

-倒倒排文件性能模型

-倒排文件的概念M詞項總數(shù)N文檔總數(shù)sjp(i)：倒排表長度分布q1q2……qk同時到達的查詢r：響應時間B系統(tǒng)最大輸出帶寬S：實現(xiàn)吞吐率倒排文件性能模型

-倒倒排文件性能模型倒排文件的概念倒排文件的一種性能模型結合計算機性能指標的考慮倒排文件性能模型倒排文件的概念倒排文件性能模型

-倒排文件的一種性能模型性能模型就是要給出N、M、p(i)、d、B、r和k的一種關系N：文檔總數(shù)M：詞項集合的大小p(i)：倒排表長度分布d：文檔平均數(shù)據(jù)量B：系統(tǒng)最大輸出帶寬r：響應時間K：同時到達的查詢的數(shù)量倒排文件性能模型

-倒排文件的一種性能模型性能倒排文件性能模型

-倒排文件的一種性能模型對p(i)和B的說明p(i)是倒排表長度的統(tǒng)計分布函數(shù)M*p(i)的長度表示i的記錄表的個數(shù)，i∈[0,N]倒排表的平均長度為倒排文件性能模型

-倒排文件的一種性能模型對倒排文件性能模型

-倒排文件的一種性能模型B是系統(tǒng)最大輸出帶寬，是支持倒排文件運行的下層系統(tǒng)的瓶頸帶寬磁盤的I/O帶寬網(wǎng)絡帶寬根據(jù)同時到達的查詢量k，得到一個數(shù)據(jù)量D，看能否有：針對查詢q1,q2,q3,……qk的假設它們都屬于集合terms它們在terms上隨機、獨立分布對于磁盤I/O帶寬和網(wǎng)絡帶寬不作區(qū)別倒排文件性能模型

-倒排文件的一種性能模型B倒排文件性能模型

-倒排文件的一種性能模型倒排文件性能的基本模型考察k個查詢導致的輸出數(shù)據(jù)量D每個查詢可能落到M個詞項中的任何一個k個查詢可能涉及M的任何1,2,……k項，對應不同的數(shù)據(jù)量計算涉及i項的概率fm,k(i)，i=1,2,3,……k倒排文件性能模型

-倒排文件的一種性能模型倒排倒排文件性能模型

-倒排文件的一種性能模型D=一個倒排表的平均數(shù)據(jù)量*k個并發(fā)查詢平均涉及的倒排表個數(shù)倒排文件性能模型

-倒排文件的一種性能模型D倒排文件性能模型

-倒排文件的一種性能模型考慮全文索引與非全文索引非全文索引：只考慮哪些文檔含有特定的詞項全文索引：還要考慮該詞在相關文檔中出現(xiàn)的位置信息全文索引的情況下，每個倒排表的數(shù)據(jù)量正比于文檔號和頻率位置信息占用的長度倒排文件性能模型

-倒排文件的一種性能模型考慮倒排文件性能模型

-倒排文件的一種性能模型TN（所有文檔中詞的集合）遠遠大于N系統(tǒng)中每個詞項倒排表的長度主要由詞頻率TF和數(shù)據(jù)規(guī)模TN決定的平均情況下非全文索引全文索引C表示了為記錄一個詞項在文檔中一次出現(xiàn)位置信息所需的數(shù)據(jù)量倒排文件性能模型

-倒排文件的一種性能模型TN倒排文件性能模型

-倒排文件的一種性能模型倒排表的長度影響操作執(zhí)行的時間索引網(wǎng)頁量增加時，高頻詞項的倒排表將急劇膨脹，占用大量I/O帶寬、內存空間、CPU時間，降低系統(tǒng)效率理想情況：所有詞項頻率盡可能低，而且大小相近，使得所有倒排表同步增長。詞項的頻率分布和語言相關倒排文件性能模型

-倒排文件的一種性能模型倒排倒排文件性能模型

-倒排文件的一種性能模型頻率英語單詞（E）漢語字符（H）0.1%1032520.07%1483480.05%2204750.02%6328670.01%128512150.007%178014000.005%238116090.002%547422100.001%67132676英漢詞頻統(tǒng)計排序對照倒排文件性能模型

-倒排文件的一種性能模型頻率倒排文件性能模型

-倒排文件的一種性能模型英語單詞和漢語字符的ITF分布倒排文件性能模型

-倒排文件的一種性能模型英語倒排文件性能模型倒排文件的概念倒排文件的一種性能模型結合計算機性能指標的考慮倒排文件性能模型倒排文件的概念倒排文件性能模型

-結合計算機性能指標的考慮決定系統(tǒng)性能的關鍵I/O的性能磁盤I/O網(wǎng)絡I/ODiskModelSize(GB)?AverageaccessTime(msec)?RPMRandomIOPSInternalTransferRate(MB/s)?InterfaceIBMUltrastar36ZX365.41000011915~29Ultra160QuantumAtlasV36.76.310000107.517~29Ultra160SeagateCheetahX1518.43.915000169.538~47FC-ALSeagateCheetah7373.45.61000011626~40Ultra160倒排文件性能模型

-結合計算機性能指標的考慮決定系統(tǒng)倒排文件性能模型

-結合計算機性能指標的考慮提高磁盤I/O性能的方法Ultra160SCSI，最高帶寬可達150MBps當前單個磁盤的平均數(shù)據(jù)傳輸率在20~50MBps之間解決辦法RAID：冗余磁盤陣列技術倒排文件性能模型

-結合計算機性能指標的考慮提高磁盤倒排文件性能模型

-結合計算機性能指標的考慮系統(tǒng)吞吐量與倒排表索引的數(shù)據(jù)量假設將每個倒排表讀入內存只需一次I/O，所花費的時間為Tlatency：磁盤訪問平均延遲時間（s）IObandwith：I/O可用帶寬（Bps）TN：所有文檔包含的詞項總量TF：頻率倒排文件性能模型

-結合計算機性能指標的考慮系統(tǒng)吞吐倒排文件性能模型

-結合計算機性能指標的考慮每次讀取倒排表的時間乘Lq*m不大于1秒當I/O系統(tǒng)性能（Tlatency、IObandwith）和TF確定下來后，可以看到TN和m之間成反比關系假設IOPS=100，Lq=5，則系統(tǒng)平均每秒處理查詢的上限是m=IOPS/Lq=20如果磁盤的可用帶寬為20MBps，則每個查詢的I/O小于1MB倒排文件性能模型

-結合計算機性能指標的考慮每次讀取倒排文件性能模型

-結合計算機性能指標的考慮根據(jù)上式，可得出如下結論對漢字字符：TN=<400MB（TF=0.05%，Lq=5）對英文字符：TN=<4GB（TF=0.005%，Lq=5）倒排文件性能模型

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

-倒排文件緩存體系結構倒排文件倒排文件緩存查詢執(zhí)行器查詢結果緩存用戶