排序樹與文件索引結構.ppt

1、排序樹與文件索引結構,2010/05/06,2,本講主要內容：,Hash表（續(xù)） Web Crawler 正則表達式 倒排表與倒排索引 排序樹與AVL樹 文件的索引結構,3,字典的基本概念,字典是一個由數據記錄（record）構成的順序表，其中記錄中有一個特殊的字段，稱為關鍵碼。每條記錄都有唯一的不重復的關鍵碼取值。 字典中的元素之間能夠根據其關鍵碼進行比較與排序，對字典元素的插入、刪除和檢索等操作一般也以關鍵碼為依據進行。 字典可以看成是由關鍵碼值k到數據記錄r的一個對應。唯一的關鍵碼取值可以唯一對應一條數據記錄。,4,根據給定的某個值，在查找表中確定一個其關鍵字等于給定值的數據條目。 順序

2、檢索、二分檢索。 衡量一個字典檢索算法效率的主要標準是檢索過程中對關鍵碼的平均比較次數：,字典的檢索（searching）,5,Dictionary表示抽象數據類型字典， DicElement 表示字典元素類型， KeyType 表示元素中關鍵碼的類型， Position 表示字典中元素的位置。,Dictionary的抽象數據類型,ADT Dictionary operations Dictionary createEmptyDictionary ( void ) /創(chuàng)建一個空字典。 int search(Dictionary dic, KeyType key, Position p) /在字

3、典dic中檢索關鍵碼為key的記錄的位置p。 int insert(Dictionary dic, DicElement ele) /在字典dic中插入記錄ele。* int delete(Dictionary dic, KeyType key) /在字典dic中刪除關鍵碼為key的記錄。 * end ADT Dictionary,6,字典的順序檢索,字典中的元素可以是無序的，但為了實現的方便，可以把字典中的元素按關鍵碼值排序。 從字典的一端開始順序掃描，將字典中元素的關鍵碼和給定值比較： 如果相等，則檢索成功； 當掃描結束時，還未找到關鍵碼等于給定值的元素，則檢索失敗。 順序檢索算法適用于非

4、排序順序存儲或非關鍵碼字段檢索 順序檢索的算法復雜度為O(n)，平均比較次數為n/2。,7,字典的二分查找,二分查找(binary search) 要求： 查找表為有序表，即表中 結點按關鍵字有序排列，并且采用順序存儲結構。 基本思想： 確定搜索區(qū)間的中點位置： 然后將待查的key值與rangemid.key比較：若相等，則查找成功并返回此位置，否則確定新的查找區(qū)間，繼續(xù)二分查找.,8,二分查找算法（非遞歸）,9,二分法檢索每經過一次比較就將檢索范圍縮小一半，第i次比較可能涉及的元素=2i -1。 二分法檢索的最大檢索長度為：log2(n+1) 算法復雜度：log2(n),二分查找性能分析,1

5、0,Hash的思想：一種高效的詞典結構,將數據集合中的所有對象都唯一對應到一個關鍵值，然后通過關鍵值映射到一個表中（哈希表）進行存放，之后可以根據關鍵值實現迅速查找。 其他實現方案： 插入速度 檢索速度 順序表 鏈表,11,Hash表的問題：空間冗余，多對一（碰撞）,確定性問題：關鍵碼分布已知。 編碼-解碼 非確定性問題：關鍵碼分布未知且理論上編碼空間巨大。（vs 實際問題規(guī)模）,12,13,樣例數據：33/40,關鍵碼？Value?,14,文件直接存?。≧andom File Access）,fseek(fileName, offset, origin),file stream,File*

6、fp;,15,文件直接存取函數,rewind() resets the current position to the start of the file rewind(inFile) fseek() allows the programmer to move to any position in the file fseek(fileName, offset, origin) Origin: SEEK_SET, SEEK_CUR, and SEEK_END ftell() returns the offset value of the next character that will be

7、read or written ftell(inFile);,16,17,Hash函數設計：,觀察法：,18,19,20,21,22,如何處理文件中數據記錄的刪除？,23,碰撞及解決方案：,24,00820060 劉艷敏,25,對hash函數的疑問：,以下是我對hash函數的理解。首先要盡可能的不發(fā)生碰撞，同時也要盡可能避免開很大的空間，所以我們要找一個很巧妙的函數，對吧？ 那么對于一個已知的輸入數據，我們可以分析它的特點，然后制定相應的函數。比如作業(yè)題1中給出的那個解決方案，作者考慮到倒數第三位和第一位很特殊，可以直接返回這個兩位數。但是在加入了兩組搗亂的數據后，這個方案明顯出了問題。 但我

8、覺得這個因果關系有點顛倒了，如果我們已知了數據，hash函數甚至可以直接用從小到大的對應的次序，這樣根本不要費盡心機的找一個函數出來。所以我覺得，一個好的函數，是不是應該在數據還未知的情況下，就能有一定的把握，使碰撞次數很少。 如果這樣想的話，就要要求這個函數盡可能散，隨機的把數據投射到另一個集合，但這樣又似乎沒法控制hash表的規(guī)模。而且保證隨機（或者說比較均勻的）也挺麻煩，就像課上說的，平方的話會使一些平方數明顯增多，等等。 然后我就困惑了，像這次的這個作業(yè)題，到底有沒有一個比較厲害的函數，能夠應對幾乎所有的搗亂數據?,26,一般思路：,號碼類 字符串類,27,Hash的用途,詞典索引 用

9、來判重和統(tǒng)計數目,28,字符串處理：,29,sscanf(),30,sscanf(),31,sscanf(),32,sscanf(),33,sscanf(),34,網絡爬蟲：,網絡爬蟲是什么？ 怎樣爬？ 整體框架 核心算法 算法改進,35,怎樣搜集?, , , ,網頁為節(jié)點 網頁中的HyperLink為有向邊 Crawl = 圖遍歷, right?,36,鏈接是哪些？,37,Refer to HTML 4.01 Specification,38,GET Method in HTTP,Refer to RFC 2616,HTTP Made Really Easy,39,Agenda,網絡爬蟲是什

10、么？ 怎樣爬？ 預備知識 整體框架 核心算法 算法改進 Distributed Crawling,40,網絡爬蟲是什么？ 系統(tǒng)框圖,41,42,43,44,還存在什么問題呢？,The real world is not perfect 鏡像與重復網頁 mirrors and duplications url/html syntax error server traps server complains legal issues system crash, power brake,45,URL不唯一性,不同url指向的同一個網頁 IP地址和域名之間的多對多關系 大規(guī)模網站用于負載平衡的技術：內容

11、鏡像 “virtual hosting”和“Proxy pass”：不同的主機名映射到同一個IP地址，發(fā)布多個邏輯網站的需要（Apache支持） 動態(tài)網頁的參數 Session id 上一頁/下一頁,46,“同義”地址,域名與IP對應存在4種情況： 一對一，一對多，多對一，多對多。一對一不會造成重復搜集， 后三種情況都有可能造成重復搜集。 可能是虛擬主機，多個域名共一個IP,內容不同 , - 2 可能是DNS輪轉 - ， - 可能是一個站點有多個域名對應 和等價,47,server traps,防止系統(tǒng)異常 病態(tài)HTML文件 例如，有的網頁含有68 kB null字符 誤導Crawler的網站 用CGI程序產生無限個網頁 用軟目錄創(chuàng)建的很深的路徑 HTTP服務器中的路徑重映射特征,48,自動提取所關注領域的網頁,我覺得可以由用戶提供一個關鍵詞名單，每個關鍵詞有一定分值，網頁文本中若出現此關鍵詞就得到相應的分數；總分高的網頁優(yōu)先顯示。 問題： 關鍵詞名單如何確定？ 關鍵詞分值如何確定？ 如何規(guī)避文本內容與所包含的詞不一致的問題？ 預習：網站上 “倒排表與向量空間模型” 內容。,49,本次作業(yè)：,所有同學繼續(xù)完上一次內容，9號前務必