單詞詞典
1、哈希加鏈表
2、樹形結(jié)構(gòu)：B樹或者B+樹
倒排列表：
單詞+文檔號，詞頻，出現(xiàn)的位置
文檔號一般采用差值存儲，以節(jié)省空間
建立索引
1、兩遍文檔遍歷法
第一遍，收集全局統(tǒng)計信息，文檔數(shù)N，每個文檔包含不同單詞數(shù)M，每個單詞在多少個文檔中出現(xiàn)過的信息DF，通過這些信息可以計算出最終索引的大小
第二遍，在建立好的內(nèi)存中建立索引，從磁盤讀取文檔并解析文檔是最消耗時間的步驟
2、排序法
始終在內(nèi)存中分配固定大小的空間，用來存放詞典信息和索引中間結(jié)果，當(dāng)分配空間消耗光的時候，把中間結(jié)果寫入磁盤，清空內(nèi)存數(shù)據(jù)進(jìn)行下一輪索引
中間結(jié)果排序，排序前，文檔ID，單詞ID，單詞頻率
排序后，單詞ID（主鍵），文檔ID（次鍵）
合并中間結(jié)果，把中間結(jié)果文件進(jìn)行合并，按單詞ID寫入最終結(jié)果文件
3、歸并法
在中間結(jié)果排序完成以后，把字典信息也寫入文檔中，這樣全額使用內(nèi)存
在建立中間索引中，實(shí)際單詞，文檔編號，詞頻
合并時，針對每個單詞的倒排列表進(jìn)行合并，形成最終的詞典信息
動態(tài)索引
倒排索引：詞典在內(nèi)存里，倒排列表存儲在磁盤文件中
臨時索引：詞典和倒排列表都在內(nèi)存中，當(dāng)有新文檔加入時，放到臨時索引中
刪除文檔列表：當(dāng)文檔內(nèi)容被更改時，系統(tǒng)認(rèn)為舊文檔被刪除，增加一篇新文檔
當(dāng)用戶輸入查詢時，先從找倒排索引+臨時索引，去掉刪除文檔列表中的文檔結(jié)果
索引更新策略
1、完全重建策略：當(dāng)新增文檔達(dá)到一定數(shù)量后，新老索引合并重建，適合小文檔集合，主流商業(yè)搜索引擎一般也采用此方式來維護(hù)
2、再合并策略：當(dāng)新增文檔達(dá)到一定數(shù)量后，新老索引合并重建，此時老索引還在被使用，由于老索引有序，所以合并策略執(zhí)行較快，但是讀老索引，建新索引，也需要較多IO時間，比較耗時
3、原地更新策略：在建立老索引時，在老索引倒排列表中留有一定的余地，新加入索引直接追加到預(yù)留空間，實(shí)驗(yàn)數(shù)據(jù)表明，更新效率比再合并策略低
4、混合策略：將單詞根據(jù)不同性質(zhì)進(jìn)行分類，對其索引采取不同的索引更新策略，長倒排列表單詞采取原地更新策略（讀寫開銷大），短倒排列表采取再合并策略（讀寫開銷不算太大）
查詢處理
1、一次一文檔，找到包含關(guān)鍵字的所有文檔集合，一次計算一個文檔的得分，依次計算所有文檔，計算后一般采用優(yōu)先隊(duì)列對分?jǐn)?shù)進(jìn)行排序
2、一次一單詞，一次計算一個單詞的得分，并把結(jié)果以文檔編寫為關(guān)鍵值，以hash表存儲得分，計算所有文檔得分后，對hash表進(jìn)行排序
跳躍指針
在存儲倒排索引文檔編號時，通常使用跳躍指針節(jié)省空間，跳躍指針分塊使用根號L為長度效果較好
多字段索引：對網(wǎng)頁的不同區(qū)域進(jìn)行字段劃分，進(jìn)行索引
1、多索引方式，對每個不同的字段分別建立索引
2、倒排列表方式，把字段信息存儲到倒排列表項(xiàng)中
3、擴(kuò)展列表方式，把每個字段出現(xiàn)的位置記錄到一張列表里，倒排索引找到單詞后，判斷單詞的位置是否在某字段范圍中
短語查詢：本質(zhì)上是如何在索引中維護(hù)單詞順序關(guān)系或位置信息
1、位置信息索引，通過位置信息判斷兩個詞是否為短語關(guān)系，適合常規(guī)短語
2、雙詞索引，首詞+下詞，只對計算代價高的短語建立雙詞索引，一般短語通過常規(guī)手段達(dá)到目的
3、短語索引，缺點(diǎn)無法將所有短語都建好索引，從用戶查詢?nèi)罩净蚓W(wǎng)頁本身挖掘短語，適合熱門短語
4、混合方法，用戶查詢->短語索引->雙詞索引->常規(guī)索引
分布式索引：多臺機(jī)器協(xié)作完成索引
1、按文檔劃分，每臺機(jī)器負(fù)責(zé)對某個文檔子集建立索引
2、按單詞劃分，將單詞分別傳送給服務(wù)器1，計算結(jié)果后，再傳送給服務(wù)器2，一次一單詞的查詢處理方式
posted on 2013-09-16 14:01
胡滿超 閱讀(548)
評論(0) 編輯 收藏 引用 所屬分類:
搜索引擎