第九章　搜尋 9-1 搜尋簡介 9-2 常見的搜尋方法 9-3 雜湊搜尋法.

Presentation on theme: "第九章　搜尋 9-1 搜尋簡介 9-2 常見的搜尋方法 9-3 雜湊搜尋法."— Presentation transcript:

1 第九章　搜尋 9-1 搜尋簡介 9-2 常見的搜尋方法 9-3 雜湊搜尋法

2 搜尋的分類 和排序法一樣，若依資料量大小來區分，搜尋可分為： 1.內部搜尋：資料量較小的檔案，可以直接全部載入記憶體中進行搜尋。
2.外部搜尋：資料量大的檔案，無法一次載入記憶體處理，而需使用到輔助記憶體來分次處理。

3 以搜尋過程中被搜尋的表格或資料是否異動，區分為靜態搜尋(Static Search)及動態搜尋(Dynamic Search)。
靜態搜尋是指資料在搜尋過程中，該搜尋資料不會有增加、刪除、或更新等行為，例如符號表搜尋就屬於一種靜態搜尋。 動態搜尋則是指所搜尋的資料，在搜尋過程中會經常性地增加、刪除、或更新。例如B-tree搜尋就屬於一種動態搜尋。

4 常見的搜尋方法 循序搜尋法 二元搜尋法 內插搜尋法 費氏搜尋法

5 循序搜尋法 又稱線性搜尋法，是一種最簡單的搜尋法。 優點是檔案在搜尋前不需要作任何的處理與排序，缺點為搜尋速度較慢。
如果資料沒有重覆，找到資料就可中止搜尋的話，在最差狀況是未找到資料，需作n次比較，最好狀況則是一次就找到，只需1次比較。

6 循序法分析 1. 時間複雜度：如果資料沒有重覆，找到資料就可 中止搜尋的話，在最差狀況是未找到資料，需作 n次比較，時間複雜度為O(n)。
2. 在平均狀況下，假設資料出現的機率相等，則需 (n+1)/2次比較。 3. 當資料量很大時，不適合使用循序搜尋法。但如 果預估所搜尋的資料在檔案前端則可以減少搜尋 的時間。

7 範例程式：ch09_01.java

8 二元搜尋法 二分搜尋法是將資料分割成兩等份，再比較鍵值與中間值的大小，如果鍵值小於中間值，可確定要找的資料在前半段的元素，否則在後半部。
如此分割數次直到找到或確定不存在為止。

9 例如以下已排序數列 2、3、5、8、9、11、12、16、18 ，而所要搜尋值為11時：
首先跟第五個數值 9 比較： 因為11＞9，所以和後半部的中間值 12 比較： 因為 11＜12，所以和前半部的中間值 11比較： 因為 11=11，表示搜尋完成，如果不相等則表示找不到。

10 二元法分析 時間複雜度：因為每次的搜尋都會比上一次少一 半的範圍，最多只需要比較[log2n]+1或[log2(n+1)]
(參考書本的表示方式)，時間複雜度為O(log n)。 2. 二分法必須事先經過排序，且資料量必須能直接在 記憶體中執行。 3. 此法適合用於不需增刪的靜態資料。

11 範例程式：ch09_02.java

12 內插搜尋法 它是依照資料位置的分佈，利用公式預測資料的所在位置，再以二分法的方式漸漸逼近。
使用內插法是假設資料平均分佈在陣列中，而每一筆資料的差距是相當接近或有一定的距離比例。 其內插法的公式為： Mid=low + (( key - data[low] ) / ( data[high] - data[low] ))* ( high - low )

13 插補搜尋法的步驟如下： 將記錄由小到大的順序給予1,2,3…n的編號。 令low=1，high=n
令Mid=low + (( key - data[low] ) / ( data[high] - data[low] ))* ( high - low ) 若key<keyMid且high≠Mid-1則令high=Mid-1 若key＝keyMid表示成功搜尋到鍵值的位置 若key>keyMid且low≠Mid+1則令low=Mid+1

14 內插法分析 1. 一般而言，內插搜尋法優於循序搜尋法，而如果資 料的分佈愈平均，則搜尋速度愈快，甚至可能第一
次就找到資料。此法的時間複雜度取決於資料分佈 的情況而定，平均而言優於O(log n)。 2. 使用內插搜尋法資料需先經過排序。

15 範例程式：ch09_03.java

16 費氏搜尋法 費氏搜尋法(Fibonacci Search)又稱費伯那搜尋法，此法和二分法一樣都是以切割範圍來進行搜尋，不同的是費氏搜尋法不以對半切割而是以費氏級數的方式切割。 費氏級數F(n)的定義如下： F0=0 ,F1=1 Fi=Fi-1+Fi-2，i≧2

17 費氏樹搜尋原則 費氏樹的左右子樹均亦為費氏樹。
當資料個數n決定，若想決定費氏樹的階層k值為何，我們必須找到一個最小的k值，使得費氏級數的Fib(k+1)≧n+1。 費氏樹的樹根定為一費氏數，且子節點與父節點的差值絕對值為費氏數。 當k2時，費氏樹的樹根為Fib(k)，左子樹為(k-1)階費氏樹(其樹根為Fib(k-1))，右子樹為(k-2)階費氏樹(其樹根為Fib(k)+Fib(k-2))。 若n+1值不為費氏數的值，則可以找出存在一個m使用Fib(k+1)-m=n+1，m=Fib(k+1)-(n+1)，最後費氏樹的各節點再減去差值m即可，並把小於1的節點去掉即可。

18 k費氏樹示意圖

19 費氏法分析 1.平均而言，費氏搜尋法的比較次數會少於二元搜尋法，但在最壞的情況下則二元搜尋法較快。其平均時間複雜度為O(log2N)
2.費氏搜尋演算法較為複雜，需額外產生費氏樹。

20 雜湊搜尋法 雜湊法不僅被用於資料的搜尋外，在資料結構的領域中，您還能將它應用在資料的建立、插入、刪除與更新。
符號表依其特性可分為二類：靜態表(Static Table)和「動態表」(Dynamic Table)。 「雜湊表」(Hash Table)則是屬於靜態表格中的一種，我們將相關的資料和鍵值儲存在一個固定大小的表格中。

21 雜湊法(Hashing)就是將本身的鍵值，經由特定的數學函數運算或使用其他的方法，轉換成相對應的資料儲存位址。
而雜湊所使用的數學函數就稱為「雜湊函數」(Hashing function)。

22 雜湊法簡介 雜湊函數的相關名詞 bucket(桶)：雜湊表中儲存資料的位置，每一個位置對應到唯一的一個位址(bucket address)。桶就好比一筆記錄。 slot(槽)：每一筆記錄中可能包含好幾個欄位，而slot指的就是「桶」中的欄位。 collision(碰撞)：若兩筆不同的資料，經過雜湊函數運算後，對應到相同的位址時，稱為碰撞。 溢位：如果資料經過雜湊函數運算後，所對應到的bucket已滿，則會使bucket發生溢位。

23 雜湊表：儲存記錄的連續記憶體。雜湊表是一種類似資料表的索引表格，其中可分為n個bucket，每個bucket又可分為m個slot，如下圖所示：
↑ May 0003 Jacky 0002 Allen 0001 → 電話 姓名 索引 bucket slot slot

24 載入密度(Loading Factor):所謂載入密度是指識別字的使用數目除以雜湊表內槽的總數：
同義字(Synonym):當兩個識別字I1及I2，經雜湊函數運算後所得的數值相同，即f(I1)=f(I2)，則稱I1與I2對於f這個雜湊函數是同義字。 載入密度(Loading Factor):所謂載入密度是指識別字的使用數目除以雜湊表內槽的總數： 如果α值愈大則表示雜湊空間的使用率越高，碰撞或溢位的機率會越高。 n(識別字的使用數目) α(載入密度)= s(每一個桶內的槽數)b(桶的數目)

25 完美雜湊(perfect hashing):指沒有碰撞又沒有溢位的雜湊函數。 通常在設計雜湊函數應該遵循底下幾個原則：
1. 降低碰撞及溢位的產生。 2. 雜湊函數不宜過於複雜，越容易計算越佳。 3. 儘量把文字的鍵值轉換成數字的鍵值，以利雜湊函 數的運算。 4. 所設計的雜湊函數計算而得的值，儘量能均勻地分 佈在每一桶中，不要太過於集中在某些桶內，這樣 就可以降低碰撞，並減少溢位的處理。

26 常見的雜湊函數 除法 最簡單的雜湊函數是將資料除以某一個常數後，取餘數來當索引。
例如在一個有13個位置的陣列中，只使用到7個位址，值分別是12,65,70,99,33,67,48。 那我們就可以把陣列內的值除以13，並以其餘數來當索引，我們可以用下例這個式子來表示： h(key)=key mod B

27 一般而言，會建議各位在選擇B時，B最好是質數。 而上例所建立出來的雜湊表為：
索引 資料 65 1 2 67 3 4 5 70 6 7 33 8 99 9 48 10 11 12 在這個例子中，我們所使用的B=13。 一般而言，會建議各位在選擇B時，B最好是質數。 而上例所建立出來的雜湊表為：

28 中間平方法 中間平方法和除法相當類似，它是把資料乘以自己，之後再取中間的某段數字做索引。
在下例中我們用中間平方法，並將它放在100位址空間，其操作步驟如下： 將12,65,70,99,33,67,51平方後如下： 取佰位數及十位數作為鍵值，分別為 144,4225,4900,9801,1089,4489,2601 14、22、90、80、08、48、60

29 數位分析法 數位分析法適用於資料不會更改，且為數字型態的靜態表。 電話 索引 07-772-2234 234 07-772-4525 525
604 651 285 101 699 694

30 碰撞問題 線性探測法 平方探測 再雜湊 鏈結串列

31 線性探測法 線性探測法是當發生碰撞情形時，若該索引已有資料，則以線性的方式往後找尋空的儲存位置，一找到位置就把資料放進去。
線性探測法通常把雜湊的位置視為環狀結構，如此一來若後面的位置已被填滿而前面還有位置時，可以將資料放到前面。

32 範例程式：ch09_04.java

33 平方探測 在平方探測中，當溢位發生時，下一次搜尋的位址是(f(x)+i2) mod B與(f(x)-i2) mod B，即讓資料值加或減i的平方，例如資料值key，雜湊函數f： 第一次尋找：f(key) 第二次尋找：(f(key)+12)%B 第三次尋找：(f(key)-12)%B 第四次尋找：(f(key)+22)%B 第五次尋找：(f(key)-22)%B ． 第n次尋找：(f(key)±((B-1)/2)2)%B，其中，B必須為4j+3型的質數，且1≦i≦(B-1)/2

34 再雜湊 再雜湊就是一開始就先設置一系列的雜湊函數，如果使用第一種雜湊函數出現溢位時就改用第二種。
如果第二種也出現溢位則改用第三種，一直到沒有發生溢位為止。 例如h1為key%11，h2為key*key，h3為key*key%11，h4……。

35 鏈結串列 如果發生溢位就把相同位址之鍵值鍵結在串列首的後面，形成一個鍵結串列，直到所有的可用空間全部用完為止。如下圖：

36 範例程式：ch09_05.java

37 雜湊法整合範例 在上例中我們直接把原始資料值存在雜湊表中，如果現在要搜尋一個資料，只需將它先經過雜湊函數的處理後，直接到對應的索引值串列中尋找，如果沒找到表示資料不存在。 如此一來可大幅減少讀取資料及比對資料的次數，甚至可能一次的讀取比對就找到想找的資料。

38 範例程式：ch09_06.java