範圍搜索

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

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

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

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

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

。

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

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

就在右子樹中遞歸搜索。 ^[1] 

搜索引擎是指根據一定的策略，運用特定的計算機程序從互聯網上搜集信息，在對信息進行組織和處理後，為用户提供檢索服務，將用户檢索的相關信息傳輸到用户的系統。搜索引擎包括全文索引、目錄索引、元搜索引擎、垂直搜索引擎、集合式搜索引擎、門户楷索引擎與免費鏈接列表等。

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

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

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

(1)提取文字；

(2)中文分詞；

(3)去停詞；

(4)消除嗓音；

(5)去重；

(6)正向索引；

(7)倒排索引；

(8)鏈接關係計算；

(9)特殊文件處理。

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