範圍搜尋

定義

搜尋問題就是找出與給定關鍵字值相對應的記錄，或者說是確定在數據結構中不存在這樣的記錄。如果數據是自然的線性順序(例如，字典中字的順序)，這就使研究相關的問題非常有意義，我們稱之為範圍搜尋(range searching)。

這個問題是定位的問題，並不是搜尋規定關鍵字值的單一記錄，而是搜尋位於兩個具體關鍵字限值之間的所有記錄。

為了抽象地描述這個問題，我們假構想要表示的有序對

由key值和info值組成，我們希望在info值上實現任意操作Op：

RangeSearch(L,U,S,Op)：在每個info I 上執行Op操作，當

。

在普通的二分搜尋樹中很容易實現範圍搜尋。其基本的思想就是，從樹中的一個節點開始，對存儲在節點上的信息執行相應的操作，如果節點的關鍵字K在這個範圍內；如果

就在左子樹中遞歸搜尋(因為在左子樹中可能有該範圍內的附加元素)，如果

就在右子樹中遞歸搜尋。

搜尋引擎是指根據一定的策略，運用特定的電腦程式從網際網路上蒐集信息，在對信息進行組織和處理後，為用戶提供檢索服務，將用戶檢索的相關信息傳輸到用戶的系統。搜尋引擎包括全文索引、目錄索引、元搜尋引擎、垂直搜尋引擎、集合式搜尋引擎、門戶楷索引擎與免費連結列表等。

第一步：爬行：搜尋引擎是通過運行一種特定規律的軟體來跟蹤網頁的連結，從一個連結追蹤到另外一個連結，就像蜘蛛在蜘蛛網上爬行一樣，所以被稱為“蜘蛛”，也被稱為“機器人”。搜尋引擎“蜘蛛”在網際網路爬行時，它被設定了一定的規則，需要遵守某些命令或文本的規則。

第二步，抓取存儲：搜尋引擎是通過“蜘蛛”跟蹤連結爬行到網頁，並將爬行得來的數據存入原始頁面資料庫。其中的頁面數據與用戶瀏覽器得到的HTMI。是完全一樣的。搜尋引擎“蜘蛛”在抓取頁面時，也對內容做一定的重複性檢測，一旦遇到權重很低的網站上有大量抄襲、採集或者複製的內容，很可能就不再爬行。

第三步，預處理：這是指搜尋引擎將“蜘蛛”抓取回來的頁面進行各種步驟的預處理。

(1)提取文字；

(2)中文分詞；

(3)去停詞；

(4)消除嗓音；

(5)去重；

(6)正向索引；

(7)倒排索引；

(8)連結關係計算；

(9)特殊檔案處理。

第四步，排名：用戶在搜尋框輸入關鍵字後，排名程式調用索引庫數據，計算排名顯示給用戶，排名過程是與用戶直接互動的。由於搜尋引擎獲取的數據量龐大，搜尋引擎的排名規則通常根據日、周、月屬性進行更新。