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