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

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

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

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

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

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

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

9、來判重和統(tǒng)計數(shù)目,28,字符串處理：,29,sscanf(),30,sscanf(),31,sscanf(),32,sscanf(),33,sscanf(),34,網(wǎng)絡(luò)爬蟲：,網(wǎng)絡(luò)爬蟲是什么？ 怎樣爬？ 整體框架 核心算法 算法改進,35,怎樣搜集?, , , ,網(wǎng)頁為節(jié)點 網(wǎng)頁中的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,網(wǎng)絡(luò)爬蟲是什

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

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