算法第7章時空權衡(李靜)

1、算法設計與分析基礎 introduction to the design and analysis of algorithms 第七章第七章 時空權衡時空權衡 2021-5-62 教學內容教學內容 時空權衡的方法時空權衡的方法 計數排序計數排序 串匹配中的輸入增強技術 散列法散列法 b樹 要求 掌握時空權衡的概念及基本方法，掌握時空權衡的方法掌握時空權衡的概念及基本方法，掌握時空權衡的方法 在常見問題中的應用。在常見問題中的應用。 本章主要內容本章主要內容 第七章第七章 時空權衡時空權衡 2021-5-63 時空權衡算法思想時空權衡算法思想 時空權衡在算法設計中是一個眾所周知的問題 對問題的部

2、分或全部輸入做對問題的部分或全部輸入做預處理預處理，然后對獲得，然后對獲得 的額外信息進行存儲，以加速后面問題的求解的額外信息進行存儲，以加速后面問題的求解 輸入增強輸入增強 使用使用額外空間額外空間來實現(xiàn)更快和（或）更方便的數據來實現(xiàn)更快和（或）更方便的數據 存取存取預構造預構造 第七章第七章 時空權衡時空權衡 2021-5-64 時空權衡時空權衡 輸入增強 計數排序計數排序 字符串匹配中的輸入增強技術字符串匹配中的輸入增強技術 預構造 散列法散列法 b樹樹 時空權衡時空權衡是指在算法的設計中，對算法的時間和 空間作出權衡。 常見的以空間換取時間的方法有：常見的以空間換取時間的方法有： 第七

3、章第七章 時空權衡時空權衡 2021-5-65 計數排序計數排序 針對待排序列表中的每個元素，算出列表中 小于該元素的元素個數，并把結果記錄在一 張表中。 這個這個“個數個數”指出了元素在有序列表中的位置指出了元素在有序列表中的位置 可以用這個信息對列表的元素排序，這個算法可以用這個信息對列表的元素排序，這個算法 稱為稱為“比較計數比較計數” 第七章第七章 時空權衡時空權衡 2021-5-66 計數排序計數排序 思路：針對待排序列表中的每一個元素，算出列表中 小于該元素的元素個數，把結果記錄在一張表中。 第七章第七章 時空權衡時空權衡 2021-5-67 算法 comparison(a0n-1

4、) /用比較計數法對數組排序 for(i=0;i n;i+) counti=0; for(i=0;i n-1;i+) for(j=i+1;j n; j+) if(aiaj) countj+; else counti+; for(i=0;i n ; i +) scounti = ai; return s; 2 )1( )1( 1)1()1( 1)(c 2 0 2 0 2 0 1 1 nn in in n n i n i n i n ij 第七章第七章 時空權衡時空權衡 2021-5-68 計數排序計數排序 該算法執(zhí)行的鍵值比較次數和選擇排序一樣多，并且還 占用了線性數量的額外空間，所以幾乎不能來

5、做實際的 應用 但在一種情況下還是卓有成效的待排序的元素值來 自一個已知的小集合 如待排序集合只有多個如待排序集合只有多個1 1，2 2元素（更一般：元素位于下界元素（更一般：元素位于下界l l 和上界和上界u u之間的整數）之間的整數） 那么我們可以使用計數排序方法，掃描列表中那么我們可以使用計數排序方法，掃描列表中1 1和和2 2的數目，的數目， 然后重排列就可以了（只有我們可以改寫給定的元素時才然后重排列就可以了（只有我們可以改寫給定的元素時才 成立）成立） 第七章第七章 時空權衡時空權衡 2021-5-69 計數排序計數排序 另一種更現(xiàn)實的情況：待排序的數組元素有一些 其他信息和鍵值相

6、關（不能改寫列表的元素） 將將a數組元素復制到一個新數組數組元素復制到一個新數組s0n-1中中 a中元素的值如果中元素的值如果等于最小的值等于最小的值l l，就被復制到，就被復制到s的的 前前f0個元素中，即位置個元素中，即位置0到到f0-1中中 值等于值等于l+1l+1的元素的元素被復制到被復制到位置位置f0至至(f0+f1)-1， 以此類推。以此類推。 因為這種頻率的累積和在統(tǒng)計中稱為分布分布，這個 方法也稱為“分布計數分布計數”。 第七章第七章 時空權衡時空權衡 2021-5-610 計數排序算法分析實例計數排序算法分析實例 131112131212 數組值 111213 頻率 132

7、分布值 146 算法 distributioncountingt(a0.n-1,l，u) for(j0 to u-l) dj0; for(i0 to n-1) dai-ldai-l+1; for(j1 to u-l) djdj-1+dj; for(in-1 downto 0) jai-l; sdj-1ai; djdj-1; return s; 第七章第七章 時空權衡時空權衡 2021-5-611 算法 distributioncounting(a0n-1,l,u) /分布計數法對有限范圍整數的數組排序 for(j=0;j = u-l ;+i) dj=0;/初始化頻率數組 for(i=0;i n

8、; +i) dai-l+;/計算頻率值 for(j=1;j =0;-i) j = ai l ; sdj-1 = ai; dj-; return s; 假設數組值的范圍是固定的， 那么這是一個線性效率的算法 但重點是：除了空間換時間之 外，分布技術排序的這種高效是 因為利用了輸入列表獨特的自然 屬性！ 第七章第七章 時空權衡時空權衡 2021-5-612 字符串匹配字符串匹配 字符串匹配問題：要求在一個較長的n個字符的串 （稱為文本文本）中，尋找一個給定的m個字符的串 （稱為模式模式）。 蠻力法：簡單地蠻力法：簡單地從左到右從左到右比較模式和文本中每一個對應比較模式和文本中每一個對應 的字符，如

9、果不匹配，把文本向右移動一格，再進行下的字符，如果不匹配，把文本向右移動一格，再進行下 一輪嘗試，一輪嘗試，最差效率為最差效率為o(nm)，隨機文本的平均效率，隨機文本的平均效率o(n) 輸入增強技術：對模式進行預處理以得到它的一些信息，輸入增強技術：對模式進行預處理以得到它的一些信息， 把這些信息存儲在表中，然后在給定文本中實際查找模把這些信息存儲在表中，然后在給定文本中實際查找模 式的時候使用這些信息式的時候使用這些信息knuth-morris_pratt(kmp)算算 法和法和boyer-moore(bm)算法算法 第七章第七章 時空權衡時空權衡 2021-5-613 字符串匹配的輸入增

10、強技術字符串匹配的輸入增強技術 knuth-morris_pratt算法和boyer-moore算法的主要區(qū)別在 于：前者是從左到右前者是從左到右，后者是從右到左后者是從右到左 但因為后者更簡單，所以我們只考慮我們只考慮boyer-mooreboyer-moore算法算法： 開始的時候把模式和文本的開頭字符對齊。如果第一次嘗開始的時候把模式和文本的開頭字符對齊。如果第一次嘗 試失敗了，把模式向右移。試失敗了，把模式向右移。 只是每次嘗試過程中的只是每次嘗試過程中的比較是從右向左的比較是從右向左的，即從模式的最，即從模式的最 后一個字符開始后一個字符開始 horspool算法和算法和boyer-

11、moore算法的簡化版算法的簡化版 第七章第七章 時空權衡時空權衡 2021-5-614 horspool算法算法 從模式的最后一個字符開始從右向左，比較 模式和文本的相應字符 如果模式中所有的字符都匹配成功，就找到如果模式中所有的字符都匹配成功，就找到 了一個匹配子串，就可以停止了了一個匹配子串，就可以停止了 如果遇到一對不匹配的，把模式右移如果遇到一對不匹配的，把模式右移 s0csn-1 barber 第七章第七章 時空權衡時空權衡 2021-5-615 horspool算法算法 根據對齊模式的最后一個字符最后一個字符c的不同情況確定移動的距 離： 情況情況1：模式中不存在：模式中不存在c

12、，模式安全移動的幅度模式安全移動的幅度就是它的全就是它的全 部長度部長度 情況情況2：模式中存在：模式中存在c，但它不是模式的最后一個字符，移，但它不是模式的最后一個字符，移 動時應該把模式中最右邊的動時應該把模式中最右邊的c和文本中的和文本中的c對齊對齊 情況情況3：c正好是模式的最后一個字符，但是在模式的其他正好是模式的最后一個字符，但是在模式的其他 字符中不包含字符中不包含c，移動的情況：，移動的情況：移動幅度等于模式長度移動幅度等于模式長度m 情況情況4：c正好是模式的最后一個字符，而且在模式的前正好是模式的最后一個字符，而且在模式的前m- 1個字符中包含個字符中包含c，移動的情況：把

13、模式中前，移動的情況：把模式中前m-1個字符中個字符中 的的c和文本中的和文本中的c對齊對齊 第七章第七章 時空權衡時空權衡 2021-5-616 horspool算法算法 考慮在某些文本中查找模式barber s0s1 . c . sn-1 barber s0s1 . s . sn-1 barber barber s0s1 . b . sn-1 barber barber s0s1 . mer . sn-1 leader leader s0s1 . or . sn-1 reorder reorder 移動幅度等于模式長度 移動幅度等于模式長度 模式中最右邊的字符最右邊的字符c 和文本中的c對

14、齊 把模式中前m-1個字符 中的c和文本中的c對齊 情況1：模式中不存在c 第七章第七章 時空權衡時空權衡 2021-5-617 horspool算法算法 比起蠻力法每次只移動一個位置，該算法移動的更遠 但如果為了移動的更遠就需要每次都檢查模式中的每個 字符，它的優(yōu)勢也會喪失 時空權衡時空權衡：預先算出每次移動的距離并把它們存在表中，：預先算出每次移動的距離并把它們存在表中， 將距離填入表中的單元格中將距離填入表中的單元格中 這個表是這個表是以文本中所有可能遇到的字符為索引以文本中所有可能遇到的字符為索引的的 對于每個字符對于每個字符c可用公式算出移動距離：可用公式算出移動距離： m(cm-1

15、) ( ) cm-1 t c 模式的長度如果 不包含在模式前個字符中 模式前個字符中到模式最后一個字符的的距離最右邊 第七章第七章 時空權衡時空權衡 2021-5-618 horspool算法算法 例如模式為“barber”，那么文本中除了e,b,r, a 的單元格分別為1,2,3,4外，其他的都為6 有一個簡單的算法用來計算移動表中每個單元格的 值： 初始時，把所有的單元格都置為模式的長度初始時，把所有的單元格都置為模式的長度m 然后從左到右掃描模式，將下列步驟重復然后從左到右掃描模式，將下列步驟重復m-1次次 對于模式中的第j個字符，將他在表中的單元格改寫 為m-1-j，這是該字符到模式右

16、端的距離 第七章第七章 時空權衡時空權衡 2021-5-619 horspool算法算法 第一步：對于給定的長度為m的模式和在模式及文本中用到的字母 表，按照上面的描述構造移動表 第二步：將模式與文本的開始處對齊 第三步：重復下面的過程，直到發(fā)現(xiàn)了一個匹配子串或者模式到達 了文本的最后一個字符以外。 從模式的最后一個字符開始，比較模式和文本中的相應字符，從模式的最后一個字符開始，比較模式和文本中的相應字符， 直到：要么所有直到：要么所有m個字符都匹配（然后停止），要么遇到了一個字符都匹配（然后停止），要么遇到了一 對不匹配的字符。對不匹配的字符。 后者，如果后者，如果c是當前文本中的和模式的最

17、后一個字符相對齊的是當前文本中的和模式的最后一個字符相對齊的 字符，從移動表的第字符，從移動表的第c列中取出單元格列中取出單元格t(c)的值，然后將模式沿的值，然后將模式沿 著文本向右移動著文本向右移動t(c)個字符的距離個字符的距離 第七章第七章 時空權衡時空權衡 2021-5-620 horspool算法算法 算法 shifttable(p0.m-1) /用horspool算法和boyer-moore算法填充移動表 /輸入：模式p0.m-1以及一個可能出現(xiàn)字符的字符表 /輸出：以字母表中字符為索引的數組table0.size-1 把table中的所有元素初始化為m； for(j0 to m

18、-2 ) do tablepjm-1-j; return table; 第七章第七章 時空權衡時空權衡 2021-5-621 horspool算法效率分析算法效率分析 horspool算法的最差效率(mn) why? 習題7.2-4 對于隨機文本，它的效率為(n) 第七章第七章 時空權衡時空權衡 2021-5-622 p202 習題習題7.2-4 4. 用horspool算法在一個長度為n的文本中查找一個長度 為m的模式,請分別給出下面兩種例子. a.最差輸入 b.最優(yōu)輸入 a.a. 在在n n個個”0 0”組成的文本中查找組成的文本中查找”10.010.0”( (長度為長度為 m), m),

19、 查找次數查找次數c(worst)=m(n-m+1)c(worst)=m(n-m+1) b. b. 在在n n個個”0 0”組成的文本中查找由組成的文本中查找由m m個個”0 0”組成的組成的 模式模式, ,查找次數查找次數c(best)=mc(best)=m 第七章第七章 時空權衡時空權衡 2021-5-623 boyer-moore算法算法 如果在遇到一個不匹配字符之前在遇到一個不匹配字符之前，如果已經有如果已經有 k(0km)k(0k0個成功匹配的 字符所確定。稱為好后綴移動好后綴移動 把模式的結尾部分叫做模式的長度為k的后綴， 記作suff(k) 情況1：當模式中存在兩個以上suff(

20、k)的情況 時，移動距離d2就是從有數到第二個suff(k)到 最右邊的距離。 第七章第七章 時空權衡時空權衡 2021-5-626 26 boyer-moore算法算法 情況2：當模式中存在1個suff(k)的情況時： k=3 移動6 k=3 移動？次 第七章第七章 時空權衡時空權衡 2021-5-627 boyer-moore算法算法 為了避免情況2的出現(xiàn)，我們需要找出長度為lk的最 長前綴，它能夠和長度同樣為l的后綴完全匹配。 如果存在這樣的前綴，我們通過求出這樣的前綴和后 綴之間的距離來作為移動距離d2的值，否則移動距離 就是m 第七章第七章 時空權衡時空權衡 2021-5-628 b

21、oyer-moore算法算法 第七章第七章 時空權衡時空權衡 2021-5-629 / school of computer science and technology, swust 29 boyer-moore算法舉例算法舉例 在一個由英文字母和空格構成的文本中查找baobab cabcd.o.z- t1(c)126663666 壞符號 移動表 好后綴 移動表 第七章第七章 時空權衡時空權衡 2021-5-630 散列法散列法 考慮一種非常高效的實現(xiàn)字典的方法 字典是一種抽象數據類型，即一個在其元素上定義了查字典是一種抽象數據類型，即一個在其元素上定

22、義了查 找、插入和刪除操作的元素集合找、插入和刪除操作的元素集合 集合的元素可以是容易類型的，一般為記錄集合的元素可以是容易類型的，一般為記錄 散列法的基本思想是：把鍵分布在一個稱為散列表的一 維數組h0，m-1中。 可以通過對每個鍵計算某些被稱為可以通過對每個鍵計算某些被稱為“散列函數散列函數”的預定的預定 義函數義函數h的值，來完成這種發(fā)布的值，來完成這種發(fā)布 該函數為每個鍵指定一個稱為該函數為每個鍵指定一個稱為“散列地址散列地址”的位于的位于0到到m- 1之間的整數之間的整數 第七章第七章 時空權衡時空權衡 2021-5-631 散列法散列法 散列函數需要滿足兩個要求： 散列函數需要把鍵

23、在散列表的單元格中盡可能均散列函數需要把鍵在散列表的單元格中盡可能均 勻地分布（所以勻地分布（所以m常被選定為質數，甚至必須考常被選定為質數，甚至必須考 慮鍵的所有比特位）慮鍵的所有比特位） 散列函數必須容易計算散列函數必須容易計算 散列的主要版本： 開散列（分離鏈）開散列（分離鏈） 閉散列（開式尋址）閉散列（開式尋址） 第七章第七章 時空權衡時空權衡 2021-5-632 開散列（分離鏈）開散列（分離鏈） 鍵被存儲在附著于散列表單元格上的鏈表中， 散列地址相同的記錄存放于同一單鏈表中 查找時：首先根據鍵值求出散列地址，然后在 該地址所在的單鏈表中搜索； 第七章第七章 時空權衡時空權衡 202

24、1-5-633 開散列（分離鏈）開散列（分離鏈） 查找效率取決于鏈表的長度，而這個長度又取 決于字典和散列表的長度以及散列函數的質量 若散列函數大致均勻地將若散列函數大致均勻地將n個鍵分布在散列表的個鍵分布在散列表的m 個單元格中，每個鏈表的長度大約相當于個單元格中，每個鏈表的長度大約相當于n/m個個 比率比率=n/m稱為散列表的負載因子稱為散列表的負載因子 一般我們希望負載因子不要和1差太遠。 如果太小就意味著有很多空鏈表；如果太大就使鏈表 太長； 如果和1相差無幾的話就能到達驚人的效率：平均只要 一兩次比較就能完成查找 成功查找和不成功查找中平均需檢查的個 數s和u： 之所以能得到這樣卓越

25、的效率，不僅是因 為這個方法本身就非常精巧，而且也是以額 外的空間為代價的 插入和刪除在平均情況下都是屬于(1) u 2 1s 第七章第七章 時空權衡時空權衡 2021-5-634 閉散列（開式尋址）閉散列（開式尋址） 所有的鍵值都存儲在散列表本身中，而沒有 使用鏈表（這表示表的長度m至少必須和鍵的 數量一樣大） 解決碰撞：有多種方法，例如線性探測 插入和查找：簡單而直接 刪除操作：“延遲刪除”，用一個特殊的符 號來標記曾被占用過的位置，以把它們和那 些從未被只用過的位置區(qū)別開來 2 1 1 1 2 1 1 1 1 2 1 s ）（ ）（ u 第七章第七章 時空權衡時空權衡 2021-5-63

26、5 閉散列（開式尋址）閉散列（開式尋址） 所有鍵都存儲在散列表本身，采用線性探查解決沖突，即碰撞發(fā)生時，如果下一個單所有鍵都存儲在散列表本身，采用線性探查解決沖突，即碰撞發(fā)生時，如果下一個單 元格空，則放下一個單元格，如果不空，則繼續(xù)找到下一個空的單元格，如果到了表元格空，則放下一個單元格，如果不空，則繼續(xù)找到下一個空的單元格，如果到了表 尾，則返回到表首繼續(xù)。尾，則返回到表首繼續(xù)。 鍵afoolandhismoneyaresoonparted 散列地址196107111112 0123456789101112 afool afool aandfoolhis aandfoolhis aandm

27、oneyfoolhis aandmoneyfoolhisare aandmoneyfoolhisaresoon paetedaandmoneyfoolhisaresoon 第七章第七章 時空權衡時空權衡 2021-5-636 / school of computer science and technology, swust 36 散列法散列法 散列法的基本思想： 把鍵分布在一個稱為散列表的一維數組把鍵分布在一個稱為散列表的一維數組h0.m-1中。中。 可以利用可以利用來計算每個鍵的值，該函數為每個鍵指定來計算每個鍵的值，該函數為每個鍵指定 一個稱為一個

28、稱為的值，該值是位于的值，該值是位于0到到m-1之間的整數。之間的整數。 如果如果鍵鍵是一個非負整數，則是一個非負整數，則h(k)=k mod m 如果如果鍵鍵是某個字母表中的字母，則可以把該字母在字母表中是某個字母表中的字母，則可以把該字母在字母表中 的位置指定個鍵，記為的位置指定個鍵，記為ord(k) 如果如果鍵鍵是一個字符串是一個字符串c0c1.cs-1，則定義，則定義 h(k)=(ord(ci) mod m 或者h0; for i0 to s-1 do h(h*c+ord(ci) mod m 第七章第七章 時空權衡時空權衡 2021-5-637

29、/ school of computer science and technology, swust 37 散列法散列法 一個散列函數必須滿足的兩個要求： 需要把鍵在散列表的單元中盡可能的均勻分布需要把鍵在散列表的單元中盡可能的均勻分布 必須是容易計算的必須是容易計算的 碰撞 當三列表的長度當三列表的長度m小于鍵的數量小于鍵的數量n時，會有兩個或多個鍵被三列到時，會有兩個或多個鍵被三列到 同一個單元中同一個單元中 即時即時m相對于相對于n足夠大，碰撞還是會發(fā)生足夠大，碰撞還是會發(fā)生 散列法的兩個版本 開散列（分離鏈）開散列（分離鏈） 閉散列（開式尋址）閉散列（開式尋址） 第七章第七章 時空權衡

30、時空權衡 2021-5-638 / school of computer science and technology, swust 38 開散列（分離鏈）開散列（分離鏈） 在開散列中，鍵被存放于散列表單元的鏈表中。 a,fool,and,his,money,are,soon,parted 鍵afoolandhismoneyaresoonparted 散列地址196107111112 第七章第七章 時空權衡時空權衡 2021-5-639 / school of computer science and techno

31、logy, swust 39 開散列（分離鏈）分析開散列（分離鏈）分析 一般來說，查找的效率取決于鏈表的長度，而這個長度有取決于 字典和散列表的長度以及散列函數的質量。 如果該散列函數大致均勻地將n個鍵分布在散列表的m個單元中， 每個鏈表的長度大約相當于n/m，其 =n/m稱為散列表的 。 成功查找中平均需檢查的指針個數s=1+ /2 不成功查找中平均需檢查的指針個數u= 通常情況下，我們希望負載因子和1不要相差太大。 第七章第七章 時空權衡時空權衡 2021-5-640 / school of computer science and technology, swust 40 閉散列（開式尋址）閉散列（開式尋址） 所有鍵都存儲在三列表本身，采用線性探查解決沖突，即碰撞發(fā)生時，所有鍵都存儲在三列表本身，采用線性探查解決沖突，即碰撞發(fā)