演算法課程 (Algorithms) Course 4 搜尋 Search 國立聯合大學資訊管理學系陳士杰老師
2 Outlines 本章重點 Search 分類觀點 Linear Search Binary Search Interpolation Search Hashing
3 Search 分類觀點 Internal Search v.s. External Search. Static Search v.s. Dynamic Search. Partial Partial Key v.s.. Whole Key Actual Actual Key v.s.. Transformation Key
4 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
5 Static Search v.s. Dynamic Search 被搜尋的資料集合 資料的搜尋範圍 或資料所存在的表格, 其內容是否經常異動 ( 如 : 是否常做資料的插入 刪除或更新 )? 否 : Static 紙本的字典 電話簿 是 : Dynamic 日常交易資料 電腦字典
6 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 為資料個數 ( 線性 )
7 Linear Search 的演算法可分成兩種 : Non-Sential ( 無崗哨 ) Linear Search Sential Linear Search
8 Non-Sential Linear Search // 記錄個數 //Array of records (file of records) // 欲搜尋的鍵值 // 輸出的結果 Found: location 指出記錄的所在位置 Not Found: location 重設為 0 1 2 S 1 2 3 4 5 n location
9 分析 平均比較次數 ( 針對 成功 的搜尋 ): (1+2+3+ +n)/n = n(n+1)/2 1/n = (n+1)/2 Time: O(n)
10 Sential Linear Search 觀念 : 多一個 S[0] 記錄, 其鍵值設定為 x 0 1 2 3 4 5 n S x location 1 // 記錄個數 //Array of records (file of records) // 欲搜尋的鍵值 // 輸出的結果 Found: location 表示出記錄的所在位置 Not Found: location 為 0
11 以實際的執行時間實際的執行時間而言 : 分析 由於少了 測試 Search 範圍是否結束 之比較 ( 即 : location <= n), n 所以當 n 極大時, 大約可以省下 ½ 的比較時間 以 Time Complexity 分析而言 : 由於仍然是線性搜尋, 所以時間複雜度還是 O(n)
12 Binary Search ( 二分搜尋 ) 實施前提 : 檔案中記錄須事先由小到大由小到大排序過 須由 Random ( 或 Direct) access 之機制支援 (e.g., Array) 觀念 : 每次皆與 Search 範圍的中間記錄中間記錄進行比較!! S l 小 m u middle l m u 大 middle = l + 2 u while ( l u ) m = l + 2 比較 (k, S[m]) case = : found, i = m, return i; case < : u = m-1; case > : l = m+1; recurn 0; u // 找到了 // 要找的資料在左半部 // 要找的資料在右半部
13 Algorithm Recursion Version:
14 Iteration Version:
15 分析 利用 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) + log 2 n c = T(1) + c log 2 n (T(1) = 1, c 為大於 0 的常數 ) = 1 + c log 2 n T(n) = O(log 2 n)
16 Interpolation Search ( 插補搜尋 ) 比較符合人類 Search 之行為 實施前提 : 檔案中記錄須事先由小到大由小到大排序過 須由 Random ( 或 Direct) access 之機制支援 (e.g., Array) 作法 : 小 while ( l u && i == 0) ( m 是一個比較的距離 ) l m l + m S x S[ l] mid = l + ( u l + 1) S[ u] S[ l] 比較 (x, S[mid]) case 1 = : found, i = mid, return i; case 2 < : u = mid-1; case 3 > : l = mid+1; recurn 0; u 大 // 找到了 // 要找的資料在左半部 // 要找的資料在右半部 x S[ l] m = ( u l + 1) S[ u] S[ l]
17 Algorithm // 若 S 數列中只有一個數字時, 防止分母為 0 Case 1 Case 2 Case 3
18 分析 其時間分析的效能是與鍵值分佈有關 一般而言, Uniform Distribution 有 Best effect. Time Complexity: O(log 2 n) ~ O(n) 最佳情況 : 同 Binary Search O(log 2 n) 每一次都切一半 最差情況 : 同線性 Search O(n) 第一次切割後, 會剩下 (n-1); 第二次切割後, 會剩下 (n-2) 筆 ; 依此類推 即每一次切割後, 只有一筆資料被摒除於下一次的搜尋資料之外
19 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 ( 桶子 ) x Hashing Function 存 / 取 H(x) (Hash Address) b 個 Slot ( 槽 ) s 個
20 優點 : 資料搜尋時, 記錄不需要事先排序 在沒有 collision 及 overflow 情況下, 資料搜尋的 Time 為 O(1) 與資料量 n 無關 保密性高 若不知 Hashing function, 則無法存取資料 可作資料壓縮之用
21 相關術語 Identifier Density 與 Loading Density Def: 令 T 為 identifier 總數,n 為目前使用者的 identifier 個數,b 為 Hash Table 之 Bucket 數目,S 為 Bucket 中之 Slot 數目, 則 : Collision Identifier Density = n/t Loading Density = n/(b S) = α α 愈大, 則表示 Hash Table Utilization 高, 但相對地 Collision / Overflow 機率也變高 Def: 不同的資料 (e.g., x 與 y) 在經由 Hashing Function 計算, 竟得出相同的 Hashing Address ( 即 H(x) = H(y)) 稱之
22 Overflow Def: 當 Collision 產生, 且 Bucket 中無多餘的 Slot 可存資料稱之 w H(w) x H(x) y H(y) w x y z: Overflow z H(z) 有 Collision 並不一定有 Overflow, 但有 Overflow, 則必有 Collision 發生 若 Bucket 只有一個 Slot, 則 Collision = Overflow
23 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. 的機率皆相等 ( 不會有局部偏重的情況 )
24 4 種常見的 Hashing Function Middle Square ( 平方值取中間位數 ) Mod ( 餘數, 或 Division) Folding Addition ( 折疊相加 ) Digits Analysis ( 位數值分析 )
25 Def: 將 Key 值取平方, 依 Hashing Table Bucket 數目, 選取適當的中間位數值適當的中間位數值作為 Hash Address e.g., 假設有 1000 個 Bucket, 範圍編號為 000~999, 若有一數值 x = 8125, 試利用 Middle Square 求其適當之 Hash Address Sol: ( 取平方 ) x = 8125 66015625 Middle Square ( 平方值取中間位數 ) 取中間三位 156 = Hash Address ( 取 015 亦可 )
26 Mod ( 餘數, 或 Division) Def: H(x) = x mod m m 的選擇之注意事項 : m 不宜為 2 求得的位址僅有 0 或 1,collision 的機會很大 m 的選擇最好是質數 ( 除盡 1 和除盡自已 )
27 Def: 將資料鍵值切成幾個相同大小的片段, 然後將這些片段相加, 其總和即為 Hashing Address 相加方式有兩種 : Shift ( 移位 ) Boundary ( 邊界 ) Folding Addition ( 折疊相加 ) 若有一資料 x = 12320324111220, 請利用兩種不同的 Folding Addition 方法求 Hashing Address ( 假設片段長度為 3)
28 Sol: x=12320324111220 are partitioned into three decimal digits long. P1 = 123, P2 = 203, P3 = 241, P4 = 112, P5 = 20. Shift folding: h( x) = i= 1 = 123 + 203 Folding at the boundaries: 5 P i + 241 + 112 + 20 = 699 123 203 241 112 20 123 302 241 h(x) = 123 + 302 + 241 + 211 + 20 = 897 211 020
29 Digits Analysis ( 位數值分析 ) Def: 當資料事先已知, 則可以選定基底 r, 然後分析每個資料之同一位數值同一位數值 Ex: 若很集中, 則捨棄捨棄該位 ; 若很分散, 則挑選挑選該位, 而挑選的位數值集合成 Hashing Address
30 4 種常見的 Overflow 處理方式 Linear Probing ( 線性探測 ) Quadratic Probing ( 二次方探測 ) Rehashing ( 再雜湊 ) Link List ( 鏈結串列, 或稱 Chain)
31 Linear Probing ( 線性探測 ) Def: 又稱 Linear Open Addressing 當 H(x) 發生 overflow, 則循著 H(x)+1, H(x)+2,, H(x)-1 順序, 逐步搜尋, 直到 : 遇見有空的 Bucket 已搜尋完一圈為止 ( 表示 Hash Table Full, 無法 store) 圖示 : x
32 Hash Table 有 11 個 buckets ( 編號 : 0~10), 每個 bucket 只有一個 slot, 假設 Hashing Function = x mod 11, 並採取 Linear Probing 處理 overflow 試依照下列資料次序存入 Hash Table, 會得到什麼結果? Sol: 屬於 5 的部落 原本應該屬於位置 6 的資料 17, 被擠到很遠的地方, 要翻山越嶺才能找到它!! Search Time 增加!! 0 33 1 22 2 3 4 5 5 6 16 7 27 8 38 9 17 10 21 5, 16, 33, 21, 22, 27, 38, 17 H(33) H(22) H(5) H(16) H(27) H(38) H(17) H(21) 缺點 : 易形成資料群聚 (Clustering) 現象, 增加 Searching Time
33 Quadratic Probing ( 二次方探測 ) Def: 為改善 Clustering 現象而提出 當 H(x) 發生 overflow 時, 則探測 (H(x) ± i 2 ) mod b,b 為 bucket 數,1 i (b- 1)/2 圖示 : 空位的探測次序 : 4 3 2 1 H(x)
34 承接上題, 並改採 Quadratic Probing 處理 overflow 則 Hash Table 內容為何? Sol: 5, 16, 33, 21, 22, 27, 38, 17 0 33 1 22 2 3 4 27 5 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)
35 承接上題,44? Sol: H(44) = 0 (0+1 2 ) mod 11 = 1 負值需先加上 11 的適當倍數, 再取 mod!! (0-1 2 ) mod 11 = 10 (0+2 2 ) mod 11 = 4 (0-2 2 ) mod 11 = 7 (0+3 2 ) mod 11 = 9 (0-3 2 ) mod 11 = 2 0 33 1 22 2 44 3 4 27 5 5 6 16 7 17 8 9 38 10 21
36 Rehashing ( 再雜湊 ) Def: 提供一系列的 Hashing Functions: f 1, f 2, f 3, f n 若使用 f 1 發生 overflow, 則改用 f 2 ; 以此類推, 直到 : 沒有 overflow 發生 全部 function 用完
37 將具有相同 Hashing Address 的資料, 以 Link list 方式串連在同一 Bucket 中 承接上題, 並改採 Quadratic Probing 處理 overflow 則 Hash Table 內容為何? Sol: Link List ( 鏈結串列, 或稱 Chain) 5, 16, 33, 21, 22, 27, 38, 17 H(38) H(27) H(22) H(33) H(16) H(5) H(17) H(21) 0 33 1 2 3 4 5 5 6 17 7 8 9 10 21 22 16 27 38
38 補充
39 補 1: Decision Tree for Binary Search 目的 : 用以描述與了解 Binary Search 的比較行為 一定是二元樹 給出 n = 31 筆記錄之 Binary Search 的決策樹 Sol: l m 1 8 16 24 31 u l [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] 欲搜尋記錄在第 18 筆, 則比較 4 次才能找到 最多之比較次數為何 ( 比較幾次後, 即知失敗 )? 5 次 n 筆記錄, 最多的比較次數 = log 2 (n+1) = 高度 u
40 範例練習 繪出 n=12 筆記錄, 執行 Binary Search 之 Decision Tree 有下列資料,26, 55, 77, 19, 13, 2, 5, 49 以 Binary Search 找 55 須比較幾次?