Course4搜尋Search

1、Course 4Course 4搜尋搜尋SearchSearch國立聯(lián)合大學(xué) 資訊管理學(xué)系 演算法課程 (陳士杰)2 Outlinesu本章重點(diǎn)nSearch分類觀點(diǎn)Linear SearchBinary SearchInterpolation SearchnAdvanced TreeBinary Search TreeAVL TreeM-way Search TreeB-treeExtended Binary TreepWeighted External Path Length (W. E. P. L) & Minimum W. E. P. L國立聯(lián)合大學(xué) 資訊管理學(xué)系 演算法課程

2、(陳士杰)3uInternal Search v.s. External Search.uStatic Search v.s. Dynamic Search. Search 分類觀點(diǎn)分類觀點(diǎn)國立聯(lián)合大學(xué) 資訊管理學(xué)系 演算法課程 (陳士杰)4Internal Search v.s. External Searchu觀點(diǎn): uInternal Search:nDef: 資料量少，可以一次全部置於中進(jìn)行search之工作uExternal Search:nDef: 資料量大，無法一次全置於Memory中，須藉助輔助儲(chǔ)存體 (E.g. Disk)，進(jìn)行分段search之工作B-treeM-way S

3、earch tree國立聯(lián)合大學(xué) 資訊管理學(xué)系 演算法課程 (陳士杰)5u被搜尋的資料集合、資料的搜尋範(fàn)圍、或資料所存在的表格，其內(nèi)容是否 (如: 是否常做資料的插入、刪除或更新) ?n否: Static紙本的字典、電話簿n是: Dynamic日常交易資料、電腦字典Static Search v.s. Dynamic Search國立聯(lián)合大學(xué) 資訊管理學(xué)系 演算法課程 (陳士杰)6uDef:n又稱。n自左到右 (或右到左)，逐一比較各個(gè)記錄的鍵值與搜尋鍵值是否相同。n若有找到，則Found (成功搜尋); 若Search完整個(gè)資料範(fàn)圍仍未找到，謂之失敗 (Not found)。u特質(zhì):n檔案記

4、錄n可由 (e.g., Array) 或 (e.g., Link List) 機(jī)制支援nTime Complexity: ，n為資料個(gè)數(shù) (線性) Linear Search (線性搜尋線性搜尋)國立聯(lián)合大學(xué) 資訊管理學(xué)系 演算法課程 (陳士杰)7uLinear Search的演算法可分成兩種:nNon-Sential (無崗哨) Linear SearchnSential Linear Search國立聯(lián)合大學(xué) 資訊管理學(xué)系 演算法課程 (陳士杰)8Non-Sential Linear Search/記錄個(gè)數(shù)/Array of records (file of records)/欲搜尋的鍵值

5、/輸出的結(jié)果 : location指出記錄的所在位置 : location重設(shè)為042n531Slocation國立聯(lián)合大學(xué) 資訊管理學(xué)系 演算法課程 (陳士杰)9分析分析u平均比較次數(shù) (針對(duì) “成功” 的搜尋): (1+2+3+n)/n = n(n+1)/21/n = (n+1)/2 Time: 國立聯(lián)合大學(xué) 資訊管理學(xué)系 演算法課程 (陳士杰)10Sential Linear Search/記錄個(gè)數(shù)/Array of records (file of records)/欲搜尋的鍵值/輸出的結(jié)果 : location表示出記錄的所在位置 : location為0locationu觀念: 多

6、一個(gè)S0記錄，其鍵值設(shè)定為x42n531S0 x國立聯(lián)合大學(xué) 資訊管理學(xué)系 演算法課程 (陳士杰)11分析分析u以而言:n由於少了 “” 之比較 (即: )，所以當(dāng)n極大時(shí)，大約可以省下 的比較時(shí)間。u以而言:n由於仍然是線性搜尋，所以時(shí)間複雜度還是 。國立聯(lián)合大學(xué) 資訊管理學(xué)系 演算法課程 (陳士杰)12 Binary Search (二分搜尋二分搜尋)u實(shí)施前提:n檔案中記錄須事先排序過n須由之機(jī)制支援 (e.g., Array)u觀念:n每次皆與Search範(fàn)圍的進(jìn)行比較!while ( l u )比較 (k, Sm) case “=”: found, i = m, return i;

7、case “”: = m+1;recurn 0;小小 大大 2middleul 2mullumiddleulmmS/找到了找到了/要找的資料在要找的資料在左半部左半部/要找的資料在要找的資料在右半部右半部國立聯(lián)合大學(xué) 資訊管理學(xué)系 演算法課程 (陳士杰)13uRecursion Version:Algorithm國立聯(lián)合大學(xué) 資訊管理學(xué)系 演算法課程 (陳士杰)14uIteration Version:國立聯(lián)合大學(xué) 資訊管理學(xué)系 演算法課程 (陳士杰)15分析分析u利用Time function T(n) = T(n/2) + O(1) = T(n/2) + c = (T(n/4 + c) +

8、 c = T(n/4) + 2c = (T(n/8) + c) + 2c = T(n/8) +3c = = T(n/n) + log2nc = T(1) + c log2n (T(1) = 1, c 為大於 0 的常數(shù)) = 1 + c log2n T(n) = O(log2n)國立聯(lián)合大學(xué) 資訊管理學(xué)系 演算法課程 (陳士杰)16 Interpolation Search (插補(bǔ)搜尋插補(bǔ)搜尋)u比較符合人類Search之行為u實(shí)施前提:n檔案中記錄須事先排序過n須由之機(jī)制支援 (e.g., Array)u作法:while ( l u & i = 0)比較 (x, Smid) case

9、 “=”: found, i = mid, return i; case “”: = mid+1;recurn 0;小小 大大) 1(lulSuSlSxm) 1(lulSuSlSxlmidluS/找到了找到了/要找的資料在要找的資料在左半部左半部/要找的資料在要找的資料在右半部右半部l + m( m 是一個(gè)比較的距離)國立聯(lián)合大學(xué) 資訊管理學(xué)系 演算法課程 (陳士杰)17Algorithm/若S數(shù)列中只有一個(gè)數(shù)字時(shí)，防止分母為0Case Case Case 國立聯(lián)合大學(xué) 資訊管理學(xué)系 演算法課程 (陳士杰)18分析分析u其時(shí)間分析的效能是與鍵值分佈有關(guān)。一般而言，Uniform Distrib

10、ution有Best effect.uTime Complexity: n最佳情況: 同Binary Search 每一次都切一半n最差情況: 同線性Search 第一次切割後，會(huì)剩下 (n-1); 第二次切割後，會(huì)剩下 (n-2)筆; 依此類推。即每一次切割後，只有一筆資料被摒除於下一次的搜尋資料之外。國立聯(lián)合大學(xué) 資訊管理學(xué)系 演算法課程 (陳士杰)19 Hashing (雜湊雜湊)uDef: 為一種資料貯存與搜尋的技術(shù)。若要存取某筆資料x，則先將x經(jīng)過計(jì)算，得出，再到對(duì)應(yīng)的中進(jìn)行存取x的動(dòng)作。uHash Table的結(jié)構(gòu)n由一組Buckets所組成，每個(gè)Buckets由一組Slot所組成

11、，每個(gè)Slot可存一筆記錄。n圖示: Hash Table Size = b sHash TableBucket (桶子桶子)Slot (槽槽)b 個(gè)個(gè)s 個(gè)個(gè)xHashingFunctionH(x)(Hash Address)存存 / 取取國立聯(lián)合大學(xué) 資訊管理學(xué)系 演算法課程 (陳士杰)20國立聯(lián)合大學(xué) 資訊管理學(xué)系 演算法課程 (陳士杰)21u優(yōu)點(diǎn):n資料搜尋時(shí)，記錄不需要事先排序n在沒有collision及overflow情況下，資料搜尋的Time為 O(1)與資料量 n 無關(guān)n保密性高若不知Hashing function，則無法存取資料n可作資料壓縮之用國立聯(lián)合大學(xué) 資訊管理學(xué)系

12、演算法課程 (陳士杰)22相關(guān)術(shù)語相關(guān)術(shù)語uIdentifier Density 與 Loading DensitynDef: 令T為identifier總數(shù)，n為目前使用者的identifier個(gè)數(shù)，b為Hash Table之Bucket數(shù)目，S為Bucket中之Slot數(shù)目，則:Identifier Density = n/TLoading Density = n/(bS) = p 愈大，則表示Hash Table Utilization高，但相對(duì)地Collision / Overflow機(jī)率也變高。uCollisionnDef: 不同的資料 (e.g., x與y) 在經(jīng)由Hashing

13、Function計(jì)算，竟得出相同的Hashing Address (即 H(x) = H(y) 稱之。國立聯(lián)合大學(xué) 資訊管理學(xué)系 演算法課程 (陳士杰)23uOverflownDef: 當(dāng)Collision產(chǎn)生，且Bucket中無多餘的Slot可存資料稱之。n有Collision並不一定有Overflow，但有Overflow，則必有Collision發(fā)生。n若Bucket只有一個(gè)Slot，則Collision = Overfloww H(w)wx H(x)xy H(y)yz H(z)z: Overflow國立聯(lián)合大學(xué) 資訊管理學(xué)系 演算法課程 (陳士杰)24Hashing Function設(shè)

14、計(jì)設(shè)計(jì)u一個(gè)良好的Hashing Function須滿足下列三個(gè)準(zhǔn)則:Ex: x mod 2就是不好的Hashing Function! (不是0就是1，會(huì)經(jīng)常發(fā)生Collision)會(huì)引發(fā) “空間利用度差” 與 “Collision上升” 的缺失u上述準(zhǔn)則導(dǎo)引出兩個(gè)名詞: (完美的雜湊函數(shù))Def: 此Hashing Function 絕對(duì)不會(huì)有Collision發(fā)生前提: 須先知道所有資料 (for Static Search) (均勻的雜湊函數(shù))Def: 此種Hashing Function計(jì)算所得出的Hashing Address，對(duì)應(yīng)到每個(gè)Bucket No.的機(jī)率皆相等。(不會(huì)有局

15、部偏重的情況)國立聯(lián)合大學(xué) 資訊管理學(xué)系 演算法課程 (陳士杰)254種常見的種常見的Hashing FunctionuMiddle Square (平方值取中間位數(shù))uMod (餘數(shù)，或 Division)uFolding Addition (折疊相加)uDigits Analysis (位數(shù)值分析)國立聯(lián)合大學(xué) 資訊管理學(xué)系 演算法課程 (陳士杰)26uDef: 將Key值取，依Hashing Table Bucket數(shù)目，選取作為Hash Address。ne.g., 假設(shè)有1000個(gè)Bucket，範(fàn)圍編號(hào)為000999，若有一數(shù)值x = 8125，試?yán)肕iddle Square求其適

16、當(dāng)之Hash AddressnSol: x = 8125 66015625 取中間三位 = Hash Address (取亦可)Middle Square (平方值取中間位數(shù)平方值取中間位數(shù))國立聯(lián)合大學(xué) 資訊管理學(xué)系 演算法課程 (陳士杰)27uDef: H(x) = x mod mum的選擇之注意事項(xiàng):nm不宜為 “2”求得的位址僅有0或1，collision的機(jī)會(huì)很大nm的選擇最好是質(zhì)數(shù) (除盡1和除盡自已)Mod (餘數(shù)，或餘數(shù)，或 Division)國立聯(lián)合大學(xué) 資訊管理學(xué)系 演算法課程 (陳士杰)28uDef: 將資料鍵值切成幾個(gè)相同大小的片段，然後將這些片段相加，其總和即為Has

17、hing Addressu相加方式有兩種:nShift (移位)nBoundary (邊界)u若有一資料x = 12320324111220，請(qǐng)利用兩種不同的Folding Addition方法求Hashing Address (假設(shè)片段長度為3)。Folding Addition (折疊相加折疊相加)國立聯(lián)合大學(xué) 資訊管理學(xué)系 演算法課程 (陳士杰)29uSol:nx=12320324111220 are partitioned into three decimal digits long.P1 = 123, P2 = 203, P3 = 241, P4 = 112, P5 = 20.nSh

18、ift folding:nFolding at the boundaries: 5169920112241203123)(iiPxh123 203 24111220123302211241h(x) = 123 + 302 + 241 + 211 + 20 = 897020國立聯(lián)合大學(xué) 資訊管理學(xué)系 演算法課程 (陳士杰)30Digits Analysis (位數(shù)值分析位數(shù)值分析)uDef: 當(dāng)，則可以選定基底r，然後分析每個(gè)資料之。n若很，則該位; n若很，則該位，而挑選的位數(shù)值集合成Hashing Address。uEx:國立聯(lián)合大學(xué) 資訊管理學(xué)系 演算法課程 (陳士杰)314種常見的種常見

19、的Overflow處理方式處理方式uLinear Probing (線性探測(cè))uQuadratic Probing (二次方探測(cè))uRehashing (再雜湊)uLink List (鏈結(jié)串列，或稱Chain)國立聯(lián)合大學(xué) 資訊管理學(xué)系 演算法課程 (陳士杰)32Linear Probing (線性探測(cè)線性探測(cè))uDef: 又稱Linear Open Addressing。當(dāng)H(x)發(fā)生overflow，則循著H(x)+1, H(x)+2, , H(x)-1順序，逐步搜尋，直到:n遇見有空的Bucketn已搜尋完一圈為止 (表示Hash Table Full，無法store)u圖示:x國立聯(lián)

20、合大學(xué) 資訊管理學(xué)系 演算法課程 (陳士杰)33uHash Table有11個(gè)buckets (編號(hào): 010)，每個(gè)bucket只有一個(gè)slot，假設(shè)Hashing Function = ，並採取 “Linear Probing”處理overflow。試依照下列資料次序存入Hash Table，會(huì)得到什麼結(jié)果?5, 16, 33, 21, 22, 27, 38, 17uSol:u缺點(diǎn): 易形成現(xiàn)象，增加Searching Time033122234556167278389171021 H(33) H(22) H(5) H(16) H(27) H(38) H(17) H(21)。原。原本應(yīng)該屬

21、於位置本應(yīng)該屬於位置 “6”的資料的資料17，被擠到很，被擠到很遠(yuǎn)的地方，要翻山越遠(yuǎn)的地方，要翻山越嶺才能找到它嶺才能找到它! Search Time增加增加!國立聯(lián)合大學(xué) 資訊管理學(xué)系 演算法課程 (陳士杰)34Quadratic Probing (二次方探測(cè)二次方探測(cè))uDef: 為改善Clustering現(xiàn)象而提出。當(dāng)H(x)發(fā)生overflow時(shí)，則探測(cè) (H(x) i2) mod b，b為bucket數(shù)，1 i (b-1)/2u圖示: H(x)空位的探測(cè)次序空位的探測(cè)次序:國立聯(lián)合大學(xué) 資訊管理學(xué)系 演算法課程 (陳士杰)35u承接上題，並改採 “Quadratic Probing”

22、處理overflow。則Hash Table內(nèi)容為何?5, 16, 33, 21, 22, 27, 38, 17uSol:033122234275561671789381021 H(33) H(22) H(5) H(16) H(27) H(38) H(17) H(21)國立聯(lián)合大學(xué) 資訊管理學(xué)系 演算法課程 (陳士杰)3603312224434275561671789381021u承接上題，44 ?uSol: H(44) = 0 (0+12) mod 11 = 1 (0-12) mod 11 = 10 (0+22) mod 11 = 4 (0-22) mod 11 = 7 (0+32) mod 11 = 9 (0-32) mod 11 = 負(fù)值需先加上負(fù)值需先加上，再取，再取mod!國立聯(lián)合大學(xué) 資訊管理學(xué)系 演算法課程 (陳士杰)37Rehashing (再雜湊再雜湊)uDef: 提供一系列的Hashing Functions: f1, f2, f3,