Course 4 搜尋 Search

▓ Outlines 本章重點 Search 分類觀點 Linear Search Binary Search Interpolation Search Hashing

▓ Search 分類觀點 Internal Search v.s. External Search. Static Search v.s. Dynamic Search. Partial Key v.s. Whole Key Actual Key v.s. Transformation Key

Internal Search v.s. External Search 觀點: 資料量的多寡 Internal Search: Def: 資料量少，可以一次全部置於Memory中進行search之工作 External Search: Def: 資料量大，無法一次全置於Memory中，須藉助輔助儲存體 (E.g. Disk)，進行分段search之工作 B-tree M-way Search tree

Static Search v.s. Dynamic Search 被搜尋的資料集合、資料的搜尋範圍、或資料所存在的表格，其內容是否經常異動 (如: 是否常做資料的插入、刪除或更新) ? 否: Static 紙本的字典、電話簿 是: Dynamic 日常交易資料、電腦字典

▓ Linear Search (線性搜尋) Def: 特質: 又稱Sequential Search。 自左到右 (或右到左)，逐一比較各個記錄的鍵值與搜尋鍵值是否相同。 若有找到，則Found (成功搜尋); 若Search完整個資料範圍仍未找到，謂之失敗 (Not found)。 特質: 檔案記錄不須事先排序 可由Random Access (e.g., Array) 或Sequential Access (e.g., Link List) 機制支援 Time Complexity: O(n)，n為資料個數 (∵線性)

Linear Search的演算法可分成兩種: Non-Sential (無崗哨) Linear Search Sential Linear Search

Non-Sential Linear Search //記錄個數 //Array of records (file of records) //欲搜尋的鍵值 //輸出的結果 ├ Found: location指出記錄的所在位置 └ Not Found: location重設為0   4 2 n … 5 3 1 S location

分析 平均比較次數 (針對 “成功” 的搜尋): (1+2+3+…+n)/n = n(n+1)/21/n = (n+1)/2 Time: O(n)

Sential Linear Search 觀念: 多一個S[0]記錄，其鍵值設定為x 4 2 n … 5 3 1 S  location x  location   //記錄個數 //Array of records (file of records) //欲搜尋的鍵值 //輸出的結果 ├ Found: location表示出記錄的所在位置 └ Not Found: location為0    

分析 以實際的執行時間而言: 以Time Complexity分析而言: 由於少了 “測試Search範圍是否結束” 之比較 (即: location <= n)，所以當n極大時，大約可以省下 ½ 的比較時間。 以Time Complexity分析而言: 由於仍然是線性搜尋，所以時間複雜度還是 O(n)。

▓ Binary Search (二分搜尋) 實施前提: 觀念: 檔案中記錄須事先由小到大排序過 須由Random (或Direct) access之機制支援 (e.g., Array) 觀念: 每次皆與Search範圍的中間記錄進行比較!! while ( l  u ) 比較 (k, S[m]) case “=”: found, i = m, return i; case “<”: u = m-1; case “>”: l = m+1; recurn 0; l m u middle l m u S … 小 大 //找到了 //要找的資料在左半部 //要找的資料在右半部

Algorithm Recursion Version:

Iteration Version:

分析 利用Time function T(n) = T(n/2) + O(1) = T(n/2) + c = (T(n/4 + c)) + c = T(n/4) + 2c = (T(n/8) + c) + 2c = T(n/8) +3c = … = T(n/n) + log2nc = T(1) + c log2n (T(1) = 1, c 為大於 0 的常數) = 1 + c log2n  T(n) = O(log2n)

▓ Interpolation Search (插補搜尋) 實施前提: 檔案中記錄須事先由小到大排序過 須由Random (或Direct) access之機制支援 (e.g., Array) 作法: while ( l  u && i == 0) 比較 (x, S[mid]) case  “=”: found, i = mid, return i; case  “<”: u = mid-1; case  “>”: l = mid+1; recurn 0; ( m 是一個比較的距離) l m l + m u S 小 大 //找到了 //要找的資料在左半部 //要找的資料在右半部

Algorithm //若S數列中只有一個數字時，防止分母為0 Case  Case  Case 

分析 其時間分析的效能是與鍵值分佈有關。一般而言，Uniform Distribution有Best effect. Time Complexity: O(log2 n) ~ O(n) 最佳情況: 同Binary Search– O(log2 n) 每一次都切一半 最差情況: 同線性Search– O(n) 第一次切割後，會剩下 (n-1); 第二次切割後，會剩下 (n-2)筆; …依此類推。 即每一次切割後，只有一筆資料被摒除於下一次的搜尋資料之外。

▓ Hashing (雜湊) Def: 為一種資料貯存與搜尋的技術。若要存取某筆資料x，則先將x經過Hashing Function計算，得出Hashing Address，再到Hash Table對應的Bucket中進行存取x的動作。 Hash Table的結構 由一組Buckets所組成，每個Buckets由一組Slot所組成，每個Slot可存一筆記錄。 圖示:  Hash Table Size = b  s Hash Table Bucket (桶子) b 個 存 / 取 Hashing Function x H(x) (Hash Address) Slot (槽) s 個

優點: 資料搜尋時，記錄不需要事先排序 在沒有collision及overflow情況下，資料搜尋的Time為 O(1) 保密性高 ∵若不知Hashing function，則無法存取資料 可作資料壓縮之用

Identifier Density 與 Loading Density 相關術語 Identifier Density 與 Loading Density Def: 令T為identifier總數，n為目前使用者的identifier個數，b為Hash Table之Bucket數目，S為Bucket中之Slot數目，則: Identifier Density = n/T Loading Density = n/(bS) =   愈大，則表示Hash Table Utilization高，但相對地Collision / Overflow機率也變高。 Collision Def: 不同的資料 (e.g., x與y) 在經由Hashing Function計算，竟得出相同的Hashing Address (即 H(x) = H(y)) 稱之。

Overflow Def: 當Collision產生，且Bucket中無多餘的Slot可存資料稱之。 有Collision並不一定有Overflow，但有Overflow，則必有Collision發生。 若Bucket只有一個Slot，則Collision = Overflow w  H(w) x  H(x) w x y z: Overflow y  H(y) z  H(z)

Hashing Function設計 一個良好的Hashing Function須滿足下列三個準則: 上述準則導引出兩個名詞: 計算簡單 Collision 宜盡量少 Ex: x mod 2就是不好的Hashing Function!! (∵不是0就是1，會經常發生Collision) 不要造成Hashing Table局部儲存 (局部偏重) 的情況 會引發 “空間利用度差” 與 “Collision上升” 的缺失 上述準則導引出兩個名詞: Perfect Hashing Function (完美的雜湊函數) Def: 此Hashing Function 絕對不會有Collision發生 前提: 須先知道所有資料 (for Static Search) Uniform Hashing Function (均勻的雜湊函數) Def: 此種Hashing Function計算所得出的Hashing Address，對應到每個Bucket No.的機率皆相等。(不會有局部偏重的情況)

4種常見的Hashing Function Middle Square (平方值取中間位數) Mod (餘數，或 Division) Folding Addition (折疊相加) Digits Analysis (位數值分析)

Middle Square (平方值取中間位數) Def: 將Key值取平方，依Hashing Table Bucket數目，選取適當的中間位數值作為Hash Address。 e.g., 假設有1000個Bucket，範圍編號為000~999，若有一數值x = 8125，試利用Middle Square求其適當之Hash Address Sol: x = 8125 66015625 取中間三位  156 = Hash Address (取015亦可) (取平方)

Mod (餘數，或 Division) Def: H(x) = x mod m m的選擇之注意事項: m不宜為 “2” 求得的位址僅有0或1，collision的機會很大 m的選擇最好是質數 (除盡1和除盡自已)

Folding Addition (折疊相加) Def: 將資料鍵值切成幾個相同大小的片段，然後將這些片段相加，其總和即為Hashing Address 相加方式有兩種: Shift (移位) Boundary (邊界) 若有一資料x = 12320324111220，請利用兩種不同的Folding Addition方法求Hashing Address (假設片段長度為3)。

Sol: x=12320324111220 are partitioned into three decimal digits long. P1 = 123, P2 = 203, P3 = 241, P4 = 112, P5 = 20. Shift folding: Folding at the boundaries: 123 203 241 112 20 123 302 241 211 h(x) = 123 + 302 + 241 + 211 + 20 = 897 020

Digits Analysis (位數值分析) Def: 當資料事先已知，則可以選定基底r，然後分析每個資料之同一位數值。 若很集中，則捨棄該位; 若很分散，則挑選該位，而挑選的位數值集合成Hashing Address。 Ex:

4種常見的Overflow處理方式 Linear Probing (線性探測) Quadratic Probing (二次方探測) Rehashing (再雜湊) Link List (鏈結串列，或稱Chain)

Linear Probing (線性探測) Def: 又稱Linear Open Addressing。當H(x)發生overflow，則循著H(x)+1, H(x)+2, …, H(x)-1順序，逐步搜尋，直到: 遇見有空的Bucket 已搜尋完一圈為止 (表示Hash Table Full，無法store) 圖示: x

缺點: 易形成資料群聚 (Clustering)現象，增加Searching Time Hash Table有11個buckets (編號: 0~10)，每個bucket只有一個slot，假設Hashing Function = x mod 11，並採取 “Linear Probing”處理overflow。試依照下列資料次序存入Hash Table，會得到什麼結果? 5, 16, 33, 21, 22, 27, 38, 17 Sol: 缺點: 易形成資料群聚 (Clustering)現象，增加Searching Time 33 1 22 2 3 4 5 6 16 7 27 8 38 9 17 10 21  H(33)  H(22) 屬於“5”的部落。原本應該屬於位置 “6”的資料17，被擠到很遠的地方，要翻山越嶺才能找到它!! Search Time增加!!  H(5)  H(16)  H(27)  H(38)  H(17)  H(21)

Quadratic Probing (二次方探測) Def: 為改善Clustering現象而提出。當H(x)發生overflow時，則探測 (H(x) ± i2) mod b，b為bucket數，1 ≤ i ≤ (b-1)/2 圖示: 空位的探測次序:    H(x)  

承接上題，並改採 “Quadratic Probing”處理overflow。則Hash Table內容為何? 5, 16, 33, 21, 22, 27, 38, 17 Sol: 33 1 22 2 3 4 27 5 6 16 7 17 8 9 38 10 21  H(33)  H(22)  H(5)  H(16)  H(27)  H(38)  H(17)  H(21)

承接上題，44  ? Sol: H(44) = 0  (0+12) mod 11 = 1 (0-12) mod 11 = 10 33 1 22 2 44 3 4 27 5 6 16 7 17 8 9 38 10 21 負值需先加上11的適當倍數，再取mod!!

Rehashing (再雜湊) Def: 提供一系列的Hashing Functions: f1, f2, f3, … fn。若使用 f1 發生overflow，則改用 f2; 以此類推，直到: 沒有overflow發生 全部function用完

Link List (鏈結串列，或稱Chain) 將具有相同Hashing Address的資料，以Link list方式串連在同一Bucket中。 承接上題，並改採 “Quadratic Probing”處理overflow。則Hash Table內容為何? 5, 16, 33, 21, 22, 27, 38, 17 Sol: H(22) H(33) 22 33 1 2 3 4 5 6 17 7 8 9 10 21 H(38) H(27) H(16) H(5) 16 27 38 H(17) H(21)

補 充

補 1: Decision Tree for Binary Search 目的: 用以描述與了解Binary Search的比較行為 一定是二元樹 給出n = 31筆記錄之Binary Search的決策樹 Sol: 欲搜尋記錄在第18筆，則比較 4 次才能找到 最多之比較次數為何 (比較幾次後，即知失敗)? 5 次 n筆記錄，最多的比較次數 = log2(n+1) = 高度 l m u 1 31 8 u’ 16 l’ 24 [16] [8] [24] [4] [12] [20] [28] [2] [6] [10] [14] [18] [22] [26] [30] [1] [3] [5] [7] [9] [11] [13] [15] [17] [19] [21] [23] [25] [27] [29] [31]

範例練習 繪出n=12筆記錄，執行Binary Search之Decision Tree 有下列資料，26, 55, 77, 19, 13, 2, 5, 49 以Binary Search找 “55” 須比較幾次?