admin 的部落格

"

資工三甲 493511101 史兆欣

term project

                  

 

     每種演算法適合不同的資料,沒有一種演算法是絕對的最快,也沒有一種演算法是完全無用武之地的,有些演算法看似相似的演算法,也許處理數字之後,會發現原來跑出來的時間差異非常大,這次的term project我想研究的是一直被拿來做比較的兩個演算法-merge sort quick sort。其實若要講到這兩個演算法的原理,可以說幾乎不太一樣,但是因為他們同樣使用divideandconquer的方法來將數字切割。以下就為大家來介紹到底他們相似的地方在哪,相異的地方在哪,誰效率好,誰適合處理什麼樣的資料。

  首先,先跟大家介紹divideandconquer:

.Divide: If the input size is smaller than a certain threshold(say, one or two elements), solve the problem directly using a straightforward method and return the solution so obtained. Otherwise, divide the input data int two or more disjoint.

2. Recur: Recursively solve the subproblems associated with the subsets.

3. Conquer: Take the soluteions to the subproblems and “merge” them int a soluteion to the original problem.

Merge Sort:

1.Divide: If S has zero or one element, return S immediately; it is already sorted. Otherwise(S has at least two elements), remove all the elements from S and put them into two sequences, S1 and S2, each containing about half of the elements of S; that is, S1 contains the first ┌n/2┐ elements of S, and S2 contains the remaining └n/2┘ elements.

2.Recur: Recursively sort sequences S1 and S2.

3. Conquer: Put back the elements int S by merging the sorted sequences S1 and S2 into a sorted sequence.

 

Algorithm merge(S1,S2,S):

  Input: Sorted sequences S1 and s2 and an empty sequence S, all of which are implemented as arrays.

  Output: Sorted sequence S containing the elements from S1 and S2.

   i j 0while i < S1.size() and j<S2.size() do  if S1.elemAtRank(i)S2.elemAtRank(j) then

    S.insertLast(S1.elemAtRank(i))  //copy ith element of S1 to end of S

    i i + 1  else     S.insertLast( S2.elemAtRank(j))  //copy jth element of S2 to end of S    j j + 1While i<S1.size() do   //copy the remaining elements of S1 to S    S.intsertLast(S1.elemAtRank(i))

    i i + 1

  While j<S2.size() do   //copy the remaining elements of S2 to S    S.intsertLast(S2.elemAtRank(j))

    j j + 1

 

  Merge sort演算法可以重新安排線性串列(Linear List),資料成為指定順序的資料,這是一種外部儲存裝置最常使用的外部排序方法,因為儲存在磁帶或循序檔案上資料的,就是一種線性串列。

   Merge sort最主要的操作是將兩個以排序的子集合,合併成一個排序的集合,例如:集合A是{1,4,5,6},集合B是{2,3,7,8},並且有一個集合C足以儲存集合A和B的所有元素,如下圖所示:


上述圖例的集合A和B,分別擁有指標指向目前處理的鍵值,合併鍵值是儲存在集合C。其作法是比較指標指向的兩個鍵值,將較小的鍵值存入合併的集合,首先比較集合A的鍵值1和集合B的鍵值2,如下圖所示:

上述集合A的鍵值1比集合B的鍵值2小,所以將鍵值1存入合併的集合C,並且將集合A的指標移到第二個鍵值4。接著比較鍵值2和4,因為鑑值2比較小所以再次存入合併的集合C,如下圖所示:

繼續比較鍵值3和4,將鍵值3存入合併集合C,接著是鍵值4和7、5和7、6和7,鍵值3、4、5、6依序存入合併的集合C,如下圖所示:

上述集合A已經沒有鍵值,集合B仍有鍵值,直接將集合B剩下的鍵值存入合併的集合C,可以得到最後排序結果的集合C,如下圖所示:

合併排序法就是使用以上敘述合併操作為基礎來執行排序,將排序的鍵值持續分割成小集合,然後再一一合併起來,可以歸納出排序的步驟,如下所示:

Step 1: n個鍵值的排序分割成箱等大小的兩部份2/n。

Step 2: 繼續分割成4/n、8/n……直到只有一個元素的集合。

Step 3: 將各小集合依序合併成大集合,就可以完成排序。

上述合併排序法的操作步驟滿足遞迴條件,因為每次分割都是將排序的集合分成兩半,直到無法繼續分割為止。

The running Time: O(n/2^1)

 

Quick Sort:

1.Divide: If S has at least two elements (nothing needs to be done if S has zero or one element), select a specific element x from S, which is called the pivot. As is common practice, choose the pivot x to be the last element in S. Remove all the elements from S and put them into three sequences:

  ● L, storing the elements in S less than x

  ● E, soring the elements in S equal to x

  ● G, storing the element in S greater than x.

  Of course, if the elements of S are all distinct, then E holds just one element-the pivot itself.

2.Recur:Recursively sort sequences L and G..

3. Conquer: Put back the elements into S into S in order by first inserting the elements of L, then those od E, and finally those of G.

 

Algorithm: Quicksort(S):

  Input: A sequence S implemented as an array or linked list

  Output: The sequence S in sorted order

If S.size()1 then      

  return        //S is already sorted in this case

p S.last().element()       //the pivotLet L,E,and g be empty list-based sequencesWhile !S.isEmpty() do          //scan S backwards , dividing it into L,E,Gif S.last().element() < p then  L.insertLast(S.remove(S.last()))else if S.last().element() = p then  L.insertLast(S.remove(S.last()))Else              //the last element in S is greater than p  G.insertLast(S.remove(S.lst()))

QuickSort(L)      //Recur on the elements less than p

QuickSort(G)      //Recur on the elements greater than p

While !L.isEmpty() do          //copy back to S the sorted elements less than p  S.insertLast(L.remove(L.first()))While !E.isEmpty() do          //copy back to S the sorted elements equal p  S.insertLast(E.remove(E.first()))While !G.isEmpty() do          //copy back to S the sorted elements greater than p  S.insertLast(G.remove(G.first()))Return                      //S is now in sorted order   C.A.R Hoare提出的快速排序法(quick sort)是目前公認最佳的排序演算法,雖然快速排序法和泡沫排序法,一樣是使用交換方式進行排序,但是透過分割技巧,快速排序法的執行效率顯著提升,遠遠超越泡沫排序法.  快速排序法和合併排序法一樣是分割資料,其分割的方式是選擇一個鍵值作為分割標準,將鍵值分成兩半的兩個集合,一半是比標準值大的鍵值集合,另一半是比較小或相等的集合。  接著每一半的鍵值使用相同的方法分割,直到分割的部份無法在分割為止,此時所有鍵值就完成排序。例如:字元陣列data[],如下圖所示:  由於上面已有詳細的圖示及文字介紹如何分割的,所以在這邊我將簡單的以圖來表示quick sort的方法: divide        And

 

Conquer             

上面介紹完了這兩個演算法的演算法以及實作方法,接下來開始比較他們兩個程式跑的速度,我以同樣的數據去跑出來,雖然我在執行的時候電腦同時在執行很多程式,不過兩個程式去跑的條件是一樣的,所以應該是不會影響到太多,數字是我隨機去跑出來的。

10個數字:

Merge sort: 10028907585ns

Quick sort: 2764123932  ns

100個數字(接下來由於數字過於龐大,因此沒有貼圖,直接寫出執行時間):

Merge sort: 3032779306 ns

Quick sort: 3839287396 ns

1000個數字:

Merge sort: 3230144334 ns

Quick sort: 3062099792 ns

2000:

Merge sort: 3585564366 ns

Quick sort: 11924927889 ns

3000:

Merge sort: 4737911662ns

Quick sort: 6222006428 ns

4000:

Merge sort: 4560034864 ns

Quick sort: 4214760815 ns

5000:

Merge sort:5819523990 ns

Quick sort: 456389876 ns

6000:

Merge sort:7871766105 ns

Quick sort: 5382071744 ns

7000:

Merge sort:5572017952 ns

Quick sort: 637440098  ns

8000:

Merge sort:9660947411 ns

Quick sort: 6688213726 ns

9000:

Merge sort:6241101034 ns

Quick sort: 5816027736 ns

10000:

Merge sort:9013426288 ns

Quick sort: 9380205864 ns

20000:

Merge sort:9014416916 ns

Quick sort: 7197901968 ns

後面因為資料型態設定的關係,所以數字太大沒辦法跑!!

有些數字特別低或是特別高,也許是因為那時候CPU較忙碌,所以數字會有些許的波折,不過整體而言,還是可以看出quick sort在大部分時候都比merge sort要來的快多了!!以下為將數值做成表格後的比較結果:

參考資料:

資料結構 - 陳會安

Data structure and algorithm in java  - Michael T. GoodrichRoberto Tamassia

 附錄A

Merge sort’s code:

import java.io.*;public class quicksort {   // 遞迴方法: 快速排序法的遞迴函數   static void q_sort(char[] data, int left, int right) {      char partition;             // 分割的字元      char temp;      int i, j, k;      if ( left < right ) {// 遞迴中止條件, 是否繼續分割         i = left;                // 分割的最左索引         j = right + 1;           // 分割的最右索引         partition = data[left];  //

"

RSA Algorithm

  • 定義:

    • 明文:M

    • 密文:C

    • 加密:C Me mod n

    • 解密:M Cd mod n (Me)d mod n Med mod n

    • 公開鑰匙:KU = {e, n}

    • 私有鑰匙:KD = {d, n}

    • 尋找出適合的 n、e  與  d

推論  M Med mod n

  • 必須合乎下列條件:

    1. 必須找出 ed n 的值,對所有 M < n,都能滿足 Med M mod n

    2. 對任何 M < n 而言,計算 Me Cd都必須非常容易。

    3. 如果給定 e n,要計算出 d 是非常困難的;反之亦然。

  • 由 Euler 定理:

    • mψ(n)+1 m mod n 

    • ψ(n)=(p-1)(q-1) 其中 n = pq 則:

    • mψ(n)+1 = m(p-1)(q-1)+1 m mod n

  • 如果:m n 互質的話(gcd(m, n) = 1)則:

    • gcd(m, n) =1 表示 m n 之間無法整除

    • n = pq,如果 m/n = m/pq  不可以整除的話,則 m/p m/q 是否可以或無法整除。

    • 假設兩個條件:

      • m = pc,其中 c 為任何整數。

      • gcd(m, p)1 gcd(m, q) =1

  • 其中 gcd(m, q) =1,表示 m q 之間是互質的關係:

    • 依照 Euler 定理:aψ(n) 1 mod n,則:

    • mψ(q) 1 mod q

    • 利用同餘運算規則:

      [mψ(q)]ψ(p) 1 mod q

      mψ(p)×ψ(q) 1 mod q

      m(p-1)×(q-1) 1 mod q;又ψ(n) = (p-1)×(q-1) 則:

    • mψ(n) 1 mod q

    • mψ(n) = 1 + kq

    • 如果等號雙邊各乘以 m,其中 m = cp n = pq,則:

      mψ(n)+1 = m + kcpq = m + kcn

      相當於:m 除以 n,而得到的商是 kc、餘數是 m,因此,可改寫成:

      mψ(n)+1 m mod n

    • 再利用:aψ(n) 1 mod n 推導出:

      [mψ(n)]k 1 mod n

      mkψ(n) 1 mod n

      mkψ(n)+1 = mk(p-1)(q-1)+1 m mod n

  • 又 n = pq,且 p 與 q 皆為質數

                      Mkψ(n)+1 M mod n

    給定:  

              ed = kψ(n) +1

    則:   

               Med M mod n  ;得到推演結果

    於是:

                      ed 1 mod ψ(n)

                       d e-1 mod ψ(n)

  • 推論結果歸類
    • RSA 演算法相關參數

      •  p q 兩質數:自行選擇的私有值。

      • n=pq:計算而得的公開值。

      • 選擇 e,需滿足 gcd(ψ(n), e)=11 < e <ψ(n):自選公開值。(一般都固定值 3 或其他數值)

      • d e-1 mod ψ(n):計算出私有值。

      • 公開鑰匙:KU = {e, n}

      • 私有鑰匙:KD = {d, n}

  • 驗證推演結果

    • 假設參數:

      1. 選定兩個質數,p = 7q = 17

      2. 計算 n = pq = 7 × 17 = 119

      3.  計算ψ(n) = (p-1) × (q-1) = 6 × 16 = 96

      4.  選定

"

資工三甲 493511371 徐雅怡

 題目:資料探勘<Data Mining>

一、動機

        大二下時,我上了網路資料庫與應用,當時在課堂上老師有講解有關一些資料探勘的資料,而當時的我卻沒有很認真的去研讀其內容,因此我就想說藉這個機會來好好研究資料探勘(Data Mining)的內容。

二、前言

        資料探勘(data mining)是從1997年左右被提倡,當時在國際間引起一股新潮流的觀念,但直到19982000年之間才在國際間成立一些相關領域與學術思想,資料探勘是指說在一大群資料中擷取較有意義的一部分資訊,也就是將隱藏中的資料挖掘出來已達成所需求的一種資料分析方法。資料探勘的學術意義是利用各個Algorithm半自動或自動化的將資料進行分析並且從中擷取出具有資訊價值的一種方法。在2000Berry and Linoff等人把資料探勘的功能分為下列六項:分類、推理、預測、關聯分組以、同質分組及描述。

        資料探勘(data mining)是一項電腦應用領域的新名詞,在講究即時且競爭激烈的網路時代,對學者來說,一開始要先了解資料探勘有哪些方式可以使用,他的技術可以分類為三種,第一種方式是用傳統的統計方式由上到下,例如主成份分析、假設檢定等等,第二種方式是用AI技術由下而上,此種方法又稱Knowledge Discovery,例如有決策樹、基因演算法、類神經演算法等等,第三種方式是混成技術,此種方式主要是結合了第一種和第二種方式的整合應用為主。

三、資料探勘功能

        資料探勘可分為六個功能:分類(classification)、推估(estimation)、預測(prediction)、關聯分組(affinity grouping)、同質分組(clustering)、序列型樣(Sequential Pattern),這些功能的使用方法和意思如下:

分類

        根據用戶的屬性分門別類定加以定義,將其歸入於某一特定的class,此方法可使用於決策樹(decision tree)、記憶基礎推理(memory - based reasoning)naive Bayesian classifiersk-最近鄰居等演算法等等。

推估

        又稱Sequential Analysis,是根據一些輸入的資料,可以從中推算出一些連續性變數,來獲取某一未知的值。例如:統計方法上之相關分析、迴歸分析及類神經網路方法等等。

預測

        根據對象的屬性去觀察與推估未來的數值,像可以根據某一活動上觀眾的反應度來預測其未來著新活動的回應率。例如:迴歸分析、時間數列分析及類神經網路方法。

關聯分組

        根據物件的發生率,有可能在同時間發生的把他們擺在一起,此發法最早應用在超市購物籃分析(Market Basket Analysis),藉由顧客的交易記錄,找出商品間彼此的關聯性,以做為超市商品擺設及進貨存貨之參考。

同質分組

        將一群異質的群組區隔為同質性較高的群組,其中他與分類不同的地方是,同質分組不用事先知道用戶的屬性來進行分類,他們是根據相似性來區分在一起。例如:k-means方法及agglomeration方法

序列型樣

        根據時間來區分,以此技術來探討不同時間點上的相關性。例如:如果做了 X 手術,則 Y 病菌在手術後感染的機率是 45%

四、資料探勘的方法

        資料探勘的工具是利用資料來建構模擬真實世界的模式(Model),依據這些Model可以表現出資料中的PatternsRelations。而這些Model有幾個用處,第一個是資料的Patterns可以幫助我們做預測,例如:美容師可以從一份化妝品調查問卷中可以知道哪些客人對他做推銷他會對我們自己有利,如此我們就可以不用浪費許多時間在口舌上而沒得到任何利益。

資料探勘可以建立六種模式:

Classification:根據用戶的屬性分門別類定加以定義,將其歸入於某一特定的class

Regression:根據一些輸入的資料,可以從中推算出一些連續性變數,來獲取某一未知的值。

Time Series:用現有的數據來預測未來的數值。

Clustering:將一群異質的群組區隔為同質性較高的群組,再根據其相似性來區分在一起

Association:根據物件的發生率,有可能在同時間發生的把他們擺在一起。

Sequence:根據時間來區分,以此技術來探討不同時間點上的相關性。

五、資料探勘的技術

        目前資料探勘的技術可以利用各種的電腦應用領域的人工智慧方法,例如:遺傳基因演算法(Genetic Algorithms)、類神經網路(Neural Networks)、決策樹 (Decision Tree)等等,不管用哪一方法最終的目的都是要找出消費者的消費行為模式(consuming behavior patterns),再利用此種模式進行目標市場行銷(target marketing),因此可以將模式放入網路伺服器,與伺服器的網頁結合,每當有符合模式內某個規則的訪客進入網站,就產生對應的行銷手法,或者將模式放入郵件伺服器,針對不同的族群消費者寄送不同的電子郵件等(如下圖)。

 

        有一點需要注意的是,沒有一種資料探勘工具可以應付各種要求,對於某一種問題,資料本身的特性與性質會影響到所選用的工具,所以可能就需要從一些不同的工具以及技術從資料中找到最佳的模式。Classification 模式是最常使用的模式,所以就來介紹建立此種模式的一些常見方法。

        Classification 通常會牽涉到兩種統計方法:Logistic Regression 以及 Discriminant Analysis,因為資料探勘越來越普遍,所以 Neural Nets 以及 Decision Tree 也漸漸受到採用,雖然這些統計方法本身都十分複雜,但使用者並不會牽涉到這些繁雜的統計。

        Neural Nets 使用許多參數(每個參數代表 Net 上的一個 Node)來建立一個模式,這個模式接受一組輸入值來預測出一個連續值或分類值。每一個節點都是一個函數,這個函數是使用輸入該節點的相鄰節點值的加權總和(Weighted Sum)做運算。在建立一個模式的過程中,我們要用一些資料來給這個網路,訓練它來找到一組能夠產生最佳輸出結果的加權值。有一種最常用的訓練法稱為 Back-Propagation,它是把輸出結果與一個已知的正確結果相比。每次相比之後就產生另一組調整過的 Weights,然後再產生一個新的輸出值再與該已知值相比。這個過程經過反覆的執行後,這個 Neural Net 就被訓練得能夠相當正確的做預測了。可是 Neural Net 有兩個問題。首先,Neural Net 最受質疑的是曖昧不明的特性,也就是它做的預測所根據的因素並不明確。第二,Neural Net 對測試資料可以做相當正確的預測,但是對真實資料預測的準確性則較差。但是現在已經有一些新的技術可以改正這個缺點。 Decision Tree 則是利用一系列的規則來得到一個類別或數值。例如,你想把申請貸款的人歸類成風險高與風險低兩種。有了這個 Desicion Tree,銀行的放款人員就可以審查申請人的條件,決定該人是屬於高風險或低風險群。例如收入高於40000而且高負債的人會被歸為高風險之類,而收入低於40000而且工作超過5年則會被歸為低風險之類。 Desicion Tree現在相當普遍,因為它所做的預測相當正確,而且又比 Neural Net 容易瞭解。 Desicion Tree Neural Net 也可以用來做 Regression,某些種類的 Neural Net 甚至可以用來做 ClusteringIBM Intelligent Miner 可支援 Decision Tree 以及 Neural Net

六、資料探勘的應用

6-1   決策樹 (Decision Tree)

        決策樹演算法在樹狀中建立一系列分岔 (亦稱為節點) 來建立資料探勘模型。每次發現輸入資料行與可預測資料行有明顯地相互關聯時,此演算法就會在模型中加入一個節點。演算法決定分岔的方式不同,視它預測連續資料行或分隔資料行而定。

--預測分隔資料行

決策樹演算法為分隔可預測資料行建立樹狀的方式,可使用長條圖來示範。

               


當演算法在模型中加入新節點時,就會形成樹狀結構。樹狀的最上層節點描述母體擴展之可預測資料行的細分。當模型繼續成長時,演算法會考量所有資料行。

             

                    


--預測連續資料行

決策樹演算法依據連續可預測資料行建立樹狀時,每一個節點會包含一個迴歸公式。分岔會出現在迴歸公式中的非線性點上。

                       

 

用單線來表示資料,效果較差。相對地,如果使用雙線,則模型更能做好模擬資料的作業。兩條線交叉的點就是非線性點,也是在決策樹模型中之節點會分岔的那個點。例如,對應至上面圖表中之非線性點的節點可由下列圖表來表示。兩個方程式代表兩條線的迴歸方程式。

                    

6-2   類神經網路 (Neural Network)

 

        類神經網路是由腦與神經系統研究所引發資訊處理的技術,其是由人工神經元(Neuron)與它連結而成,由於類神經網路具有高速運算、記憶、學習與過濾雜訊、容錯等能力,因此能夠解決許多複雜的分類、預測問題。其中類神經網路模型可分為三層輸入層、隱藏層及輸出層,輸入層是用來輸入外在環境的值給外在環境,輸出層是用來輸入外在環境的值給外在環境,隱藏層則是提供類神經網路表現處理單元間的交互作用與問題的內在結構能力。

      

6-3   基因演算法 (Genetic Algorithms)

 

        基因演算法是一種新的資料探勘方法,通常實際被應用於為實體的經銷商來做商店的設計與後勤的安排,也常常與類神經網路這樣技術來做結合的應用,而其最初概念是由John Holland1975年提出,其主要目的如下:

1. 以嚴密而具象的科學方法解釋自然界「物競天擇、適者生存」的演化過程。

2. 將生物界中遺傳演化重要機制以資訊科學軟體實作模擬。 由達爾文進化論的  觀點來看,物種靠不斷的演化而產生最適合生存的下一代。

        基因演算法即是由此一論點出發,模擬自然界的演化方式,對既定問題求取最佳解。它是應用演算法的適應函數來決定搜尋的方向,再運用一些擬生物化的人工運算過程,因此其主要的運算子有選擇(selection)、複製(reproduction)、交配(crossover)和突變(mutation)等進行演化,週而復始地進行一代一代的演化,以求得一個最佳的結果。

        基因演算法的流程與基本架構:

1. 產生一堆String,形成一個大族群。2. 評估每個String的分數,檢查結束條件是否成立。3. 選擇優秀的String

4. 進行字串間的交配演化動作,已產生下一代的String

                

七、資料探勘建置的注意事項 

1. 資料來源:一般的交易資料可能不足以用來估計銀行活期存款帳戶之流失

            率,必須再蒐集資料,以瞭解客戶流失之原因。

2. 資料需求的界定:找出針對與特定問題相關原因與象徵之資訊。

 

3. 訪談人員需求:訪談之被訪人可能包括服務中心人員,分行經理、及行銷分

               析人員等。從事訪談的人員則以從事流失模型建立之分析為宜。

4. 模型建立:模型的種類可以涵蓋簡單的OLAP,以致複雜的類神經網路。

 

5. 資料整理:不同的模型有不同的資料需求,資料整理方式也不同。例如在類

            神經網路模型的情況,可能要將原始資料轉換成以01為範圍之 

            數列。

6. 軟體需求:利用的原有的交易資料及額外蒐集的資料後必須利用專業的軟體

            建立模型。所需要的軟體可能包括SQL queries及特殊的分析軟體。

 

" 

BT演算法分析與影音串流實現 

1.前言

2.1BT演算法介紹

2.2BT的核心PiecePicker

2.3Rarest-first 

2.4In-order

3.結語

4.參考資料

1.前言


以往使用多媒體串流服務時,大多是以client/server的架構為主,其缺點在於所有client需要的多媒體資料都是由server下載而來,當server服務的人數一多,機器的負荷與網路頻寬限制會影響整個串流服務的品質,即使架設多個server在系統中,整體server的運算能力與網路頻寬還是是固定的,只要client數目超過server所能負荷的程度,某些client就無法取得多媒體串流,嚴重的話可能使server當機,整個串流服務也就癱瘓。近來出現一種新的網路應用,在網路上的每個node同時擔任serverclient的角色,不只下載自己需要的資料,同時服務其他client提供下載,稱為Peer-to-Peer,簡稱P2PP2P的出現為client/server的缺點帶來解決的方法。而目前P2P的應用上最有名的就是BT了,BT不同於client/server的地方在於,因為網路上每個node同時為clientserver,等於把server的負擔分散到整個網路中的每個參與者,即使加入網路的人再多,也能夠讓整個網路能夠正常運作,比起傳統架構更能容納許多使用者加入。然而目前BT的使用大多是在檔案分享上,對於多媒體串流的應用上就比較沒有如此廣泛的被使用,然而從BT的特性來看,其實是很適合與多媒體串流做結合的,對於多媒體服務的質量而言都可以有大幅的提升。若BT能與多媒體串流結合在一起,就能讓網路上每個人都能分享多媒體內容,而不會受到server的運算能力及網路頻寬的限制。


2.1BT演算法介紹

          BT是基於P2P系統下的主流分享軟體,他的優點在於可以實現多點對多點的分享,尤其是當檔案分享人數越多的時候每個人的DOWNLOAD也越快,這完全是因為BT內將檔案分享時的演算法,以下就介紹BT的演算法。

          BT在交換檔案時,會將整個檔案細分成更小的單位,稱做piecepiece的大小可以由使用者自訂,一般為256 kbytes。在下載之前,會選擇下一個要下載的piece。為了因應p2p network上使用者進出頻繁的狀況,BT在選擇下載的piece時,會先統計網路上所有piece擁有的人數,然後選擇最稀有的piece優先下載,以避免擁有稀有piece的用戶太早離開而造成整個網路都無法完成全部pieces的下載,而完成稀有poece的下載後也能提供給更多peer來下載,這樣的策略叫做rarest-first。基本上,BT是根據rarest-first的策略來下載檔案。

2.2BT的核心PiecePicker

BT主要負責作檔案切格的檔案PiecePicker。 Choker在選擇了解除一個連接的阻塞後,Upload.unchoke()將會執行,Connection對象的send_unchoke()也在此被執行。當網絡的另一端收到這條消息後,它對應的SingleDownload.got_unchoke()將會開始進行處理。它再檢查自己的interested狀態,如果自己也感興趣的話,那麼就用_request_more()開始向對方請求數據了。

    _request_more()可以給一個indices作為參數,這個參數是一個列表,意思就是說優先下載號碼在這個列表中的塊。如果這個參數為None,那意思就是說你自己看著辦吧,覺得下哪塊合適就下哪塊。首先檢查自己的active_requests,就是當前連接中已經發出去的請求,如果已經發出去的請求太多了(而還沒有數據返回),就暫時不發出新的請求了而是直接返回。下面檢查endgame,如果已經進入這個階段則按照這個階段的方式去下載(fix_download_endgame(),收尾階段特殊方式下載)。

    接下來就開始生成請求了,首先檢查indices,如果是None,那麼讓PiecePicker來挑一塊,否則,逐個的檢查indices中的值,如果這個號碼的塊對方有(have[i])而自己又想要(do_I_have_requests(i)),那麼就是它了。PiecePicker如何進行塊的選取的策略我們稍後再分析,現在我們知道的就是它已經決定下載某一塊了。然後要檢查interested,如果有必要,還要通知一下對方。下面一段就是不斷向StorageWrapper要網絡請求的參數,new_request根據自己在硬盤上的某一塊的擁有情況,不斷得返回塊內相對偏移和長度。在這裡,我們可以看出,對等客戶之間要求傳輸實際的數據的請求有三個參數,即第幾塊,塊內偏移多少,長度多少。而這個長度是根據配置文件中的參數決定的,通常就是一個slice,它要能一次下載完。當然,一塊的長度不一定是slice的整數倍,因此最後一個slice的長度要短一些,不過,這些細節在StorageWrapper中已經處理好了。從StorageWrapper得到請求後,就把它加到自己的active_requests中,然後讓自己的Connection對像去send_request()。現在我們也應該更加清楚active_requests和inactive_requests的意義了,即平時StorageWrapper根據實際情況,準備好inactive_requests,然後在SingleDownload對像中請求發出時,把它們逐漸轉移到自己的active_requests中。

    在兩個while循環的下面,檢查active_requests,意思就是說如果經過以上的所有過程,如果active_requests還是空的,那麼說明什麼呢?只能說明對方根本就沒有(或者說曾經有,但是現在已經沒有了)自己感興趣的數據,而如果自己還是interested的話,要調用一個send_not_interested(),意思是我不再對你感興趣了。下面檢查lost_interests中的值,這些都是在下載過程中曾經是自己想要的,但是現在已經不想要了(主要原因是自己已經擁有了)。接下來這個for循環的意思就是檢查所有的SingleDownload對象,告訴它們某一塊已經有了,不用再去下了,而且有些SingleDownload要因此發出NOT_INTERESTED。最後再次檢查是否進入endgame階段,如果是,則按照這種階段的行為進行處理。

    現在我們就可以來研究PiecePicker這個塊選擇策略控制器的行為了,從前面的分析我們知道,每個PiecePicker對應一個_SingleTorrent,使用它時經歷了以下幾步:首先是初始化,然後根據自己已經有的塊,把它告訴給PiecePicker(complete(i)),以後就不要從這中間選了,還有就是當一個SingleDownload對像獲取對方的塊擁有狀況位圖時,也要告訴PiecePicker(got_have(i)),意思是這一塊有人有了。最後當需要PiecePicker做出選擇時,只要調用其next函數,它需要一個判斷函數(_want),以及一個對方是否是種子的標誌(self.have.numfalse == 0),_want函數就是這樣的一個函數,當PiecePicker選了一塊後,要拿給它檢查,看看這一塊是不是它確實想要的,如果不是的話,PiecePicker會重新選擇。而_want()函數的判斷標準很簡單,那就是別人有而自己又想要的。

    PiecePicker的初始化工作主要是對自己的內部變量進行。這裡要解釋一下這些變量的作用,這樣能夠更加方便地對後面的部分進行理解。numpieces,總的塊數。interests是按照擁有者的數量排序的塊列表的列表,就是說,它是一個列表,列表中的第0個元素是所有的自己感興趣而沒有人有的塊的列表,第1個元素是所有的自己感興趣而只有一個人有的塊的列表,等。pos_in_interests,就是每一塊在interests中的對應元素所表示的列表中的位置,如果某一塊比如說i,自己已經有了,那麼pos_in_interests[i]的值沒有意義。numinterests的值就是某塊有多少人擁有(不包括自己),以上三個變量保持這樣的關係:如果一塊i,自己沒有,那麼interests[numinterests[i]][pos_in_interests[i]]=i。have是一個布爾數組,表示自己已經有那塊,在初始化完成後,它應該和StorageWrapper中的實際情況保持一致。crosscount則是一個統計情況數組,即有多少塊沒有人擁有,有多少塊有一個人擁有,等,自己擁有的某一塊也在這裡參加計數。numgot,已經得到的塊數。scrambled,一個包含從0到numpieces-1的序列,但是被隨機打亂了。

    現在來看PiecePicker.complete,即自己有了某塊,首先have中的值要設置,然後從numinterests中查到自己原來有多少人擁有,把crosscount中對應的項減一,然後把它下一項加一,如果沒有下一項,那麼就在後面添加一項。由此我們可以看到,crosscount數組是逐漸增大的。然後它做的事情是把interests中的對應的項刪除掉,因為它已經不在自己感興趣的範圍內了,其它幾行代碼是為了保持這些變量值的一致性。然後試圖從started和seedstarted中刪除這一塊(如果沒有這一塊也無所謂,什麼也不用做)。

    PiecePicker.got_have,處理的情況是別人有了某一塊。首先還是保持crosscount的一致,然後處理interests列表。調用_shift_over把piece從interests列表中的一個元素轉移到另一個元素(同時還要保持其它變量的值的意義的一致性)。_shift_over做的事情就是從第一個列表中刪除一個元素,然後將其插入第二個元素隨機的位置,同時維護pos_in_interests值的意義。

    PiecePicker.requested,哪一塊已經開始下載了,這個在SingleDownload中會被調用,它只是維護兩個列表,started和seedstarted。

    PiecePicker.next,可以說是PiecePicker中提供的最重要的功能,選擇一塊進行下載。它選擇的第一條原則是,已經開始下載的優先把它下載完(return choice(bests)及其前面的代碼)。它檢查選擇的兩個數組,根據對方是否是種子選擇一個數組。然後在所有的這個數組中選擇出自己想要的,檢查它們的numinterests,即擁有此塊的人數,選出擁有人數最少的塊,放入bests中,如果有並列的,則添加到bests,因此在這裡結束後,bests中的元素是所有正在下載的且自己想要的塊中擁有人數最少的塊的列表,那麼就從中間隨機選擇一個返回即可。選擇的第二條原則是,當自己擁有的塊數少於一定的數量時,隨機選擇自己想要的塊進行下載(第一階段結束後的那個if塊),因此它用到了那個scrambled列表,而當自己所擁有的塊數超過一定的值(config['rarest_first_cutoff'])後,執行第三階段的方案。選擇的第三條原則是,優先選擇下載擁有的人數最少的塊,我們看到,它從interests中第1個元素開始檢查,選擇最先找到的自己想要的塊,第0個元素不用檢查,因為沒有人擁有的塊肯定下載不到。我們可以看出,它的選擇原理是比較簡單但是又很有效的,優先下載擁有人數最少的塊就能夠保證所有的塊能夠在最短的時間內盡可能得讓更多的人擁有,換一個術語說就是能盡快提高要下載的內容的副本率。

2.3Rarest-first 比較過BTmedia streaming的差異之後可以發現,BT採用rarest-first來選擇piece download,但media streaming因為需要即時播放,必須根據時間順序來下載(稱做in -order),要如何更改BT download piece的策略以符合media streaming是我們首要考慮的事。最簡單的作法是,讓BT的下載策略與media streaming相同,由media的檔頭開始下載,循序下載直到檔尾,這樣所下載得到的piece就能被player播放出來。然而,在P2P網路中根據檔案片段先後次序來下載,這樣的缺點如同前面提過rarest-first所要避免的情況,整個網路的用戶群中可能無法保留一個完整的copy,對於P2P網路來說不是一個好的策略。

           由此可見,in-orderrarest-first可以說是屬於下載策略的兩個極端,要想辦法符合media streaming的需求,並且要有rarest-first的效果以優化整個P2P網路,也就是再兩者之間要取得一個平衡,那麼就讓兩者交替執行,也許是一個可行的作法。             在進一步討論之前先說明BT download strategy的細節。在BT開始一個新的下載任務之前,選擇前n個要下載的piece是隨機選擇的(n可由使用者指定),稱作random first,選擇完後開始下載,在所選的piece還未下載完之前,下載的策略都是選擇以下載但未完成的piece,此為download unfinished。當一開始所選的npieces下載完成後,就開始rarest-first的下載,在所選的piece還沒完成下載之前,下載的策略都是選擇那些未完成的puece來下載(Figure 07所示) BT’s downloading strategy 因為media streaming的下載有即時性,所以原本BTrarest-first

"

資工四甲 491511626 周榆峻

Table of contents:

1.      Preface……………………………………………………………………………......................1

2.      Table of contents………………………………………………………………….................2

3.      Simple introduction of Cryptographic algorithm………………………….………3

4.      Introducing Diffie-Hellman key exchange algorithm…………………………..4

5.      How Diffie-Hellman key exchange works………………………………………......5

6.      Normal example (Only 2 participants: Alice and Bob)………………………..6

7.      Eavesdropping (3 participants: Alice, Bob and Eve) example……………7

8.      Security Issues…………………………………………………………………….................8

9.      Example of real problems in security issues……………………………………….9

10.  Another example…………………………………………………………………...............11

11.  List of difficult words……………………………………………………………..............12

12.  Conclusion………………………………………………………………………...................12

13.  References………………………………………………………………………...................13

Simple Introduction Of Cryptographic Algorithm

 

Cryptography or cryptology name is from Greek which means hidden write and then it translates to the study of message secrecy.

Cryptography’s primary purpose is to hide the meaning of a message, not usually the existence of such message.

Cryptography also known as encryption. Encryption is the process of converting ordinary information (plaintext) into a ciphertext (the encrypted result). Decryption is the reverse, moving from the encrypted text (ciphertext) to ordinary information (plaintext). A cipher (cypher) is a pair of algorithms which perform this encryption and the reversing decryption. The detailed operation of a cipher is controlled both by the algorithm and a key. Usually this key known only between the communicants. Keys are the most important part because ciphers without variable keys are unbreakable and so rather less than useful. Historically, ciphers were often used directly for encryption or decryption without additional procedures. Before the modern era, cryptography was concerned solely with message confidentiality (encryption) rendering it unreadable by interceptors or eavesdroppers without secret knowledge (namely, the key needed for decryption). For an example: In the film of The Da Vinci Code there is a cryptex, the key only known to the key maker and the communicant but in this film the key maker was dead before he/she can tell what the key is, so he/she left a riddle about what the key is. We can say that the riddle is the public key and the code from the riddle is the private key, well it almost the same as cryptography but not exactly the same but I think this is all known example.

In recent decades, the field has expanded beyond confidentiality concerns to include techniques for authentication of message integrity or sender/receiver identity, digital signatures, interactive proofs, and secure computation.



Introducing Diffie-Hellman key exchange algorithm

 

Diffie-Hellman (D-H) key exchange is a cryptographic protocol that allows two users or devices to generate a shared private key with which they can then exchange information across an insecure channel. The key can be used to encrypt subsequent communications using a symmetric key cipher.

The scheme was first published to public by Whitfield Diffie and Martin Hellman in 1976 although that few years earlier had been discovered by GCHQ (Government Communications Headquarters), the British signals intelligence agency, by Malcolm J. Williamson but it was kept classified. And in 2002, Martin Hellman suggested the algorithm to be called Diffie-Hellman-Merkle key exchange because of the contribution from Ralph Merkle's inventing of public-key cryptography.

Diffie-Hellman key exchange also known as Diffie-Hellman key agreement, Diffie-Hellman key establishment, Diffie-Hellman key negotiation and exponential key exchange. The D-H key exchange method was followed by RSA, another implementation of public key cryptography using asymmetric algorithms.

 

How Diffie-Hellman key exchange works

Alice and Bob want to be able to generate a key to use for subsequent message exchange. The key generating exchange can take place over an unsecured channel that allows eavesdropping (intercepting the conversations by unknown/unwanted participant). The ingredients to the protocol are: p, a large prime and g, a primitive mod p. (Mod (modulo) means the integers between 0 and p − 1 are used with normal addition, subtraction, multiplication, and exponentiation, except that after each operation the result keeps only the remainder after dividing by p). These two numbers don’t need to be kept secret.

Normal example (Only 2 participants: Alice and Bob):

1.          First Alice and Bob have an agreement to use p = 53 (prime number) and base g = 8 (primitive mod p).

2.          Then Alice chooses a secret integer a = 6 and sends Bob 86 mod 53 = 6 (ga mod p).

3.          After that Bob chooses a secret integer b = 15 and then sends Alice 815 mod 53 = 41 (gb mod p).

4.          If Alice wants to get the private key, Alice should computes 416 mod 53 = 17 ((gb mod p)a mod p) and if Bob wants to get the private key, Bob computes 615 mod 53 = 17 ((ga mod p)b mod p).

 

Both Alice and Bob already compute and get the same value (gab and gba are equal). Note: only a, b and gab = gba are kept secret and all other values are sent using unsecured channel so it’s obviously known by everyone else. Once Alice and Bob compute the shared secret key that only known to them, they can use it as an encryption key and sending messages across the same open communications channel. Of course, much larger values of a, b, and p would be needed to make this example secure, since it is easy to try all the possible values of gab mod 53. If p was a prime of at least 300 digits, and a and b were at least 100 digits long, then even the best known algorithms today could not find a given only g, p, and ga mod p, even using all of mankind's computing power. The problem is known as the discrete logarithm problem and note that g don’t need to be large at all.

Eavesdropping (3 participants: Alice, Bob and Eve) example:

For example:

1.      p is public (prime) number and p = 53

2.      g is public base and g = 8

3.      s is a shared secret key and s =17

4.      a is Alice's private key and a = 6

5.      b is Bob's private key and b = 15

If Alice or Bob wants to solve one another private key, they would meet difficulty time because they do not know each other private key so does eve. Even if Eve is able to see every message passed between the principals, it is mathematically infeasible for her to deduce the secret key because eve does not know any of their private key, Eve only knows their prime number and the public base number. If Alice or Bob can solve one another private key so does eve. Eve can trying to substitute her own private / public key pair, put Bob's public key into her private key so that can produce a fake shared secret key and solve for Bob's private key (and use that to solve for the shared secret key. Eve may attempt to choose a public / private key pair that will make it easy for her to solve for Bob's private key).


Security Issues

The protocol of Diffie-Hellman key exchange can be considered secure against the eavesdroppers if G and g are chosen properly. The eavesdropper must solve the DHP (Given an element g and the values of ga and gb then what is the value of to gab ?) obtain gab. To solved this problem is currently considered difficult but if the eavesdropper know or can write an efficient algorithm to solve the discrete logarithm problem then the eavesdropper can easily to compute a or b and solve the Diffie-Hellman problem. And if Alice and Bob use random number generators to make the public key or private key which the outputs that’s generated are not completely random and can be predicted, then Eve's task is much easier.

The private key from Alice and Bob (a and b) are become unused at the end of their exchange session. Therefore, Diffie-Hellman key exchange by itself trivially achieves perfect forward secrecy because no long-term private keying material exists to be disclosed.

Diffie-Hellman exchange key is vulnerable to man in the middle attack because the exchange key protocol doesn’t provide any authentication of the participants. In algorithm course, Dr. Mei already mention about man in the middle attack when teaching about RSA Network Security. The man-in-the-middle may establish two distinct Diffie-Hellman keys, one with Alice and the other with Bob, and then try to masquerade as Alice to Bob and/or vice-versa, perhaps by decrypting and re-encrypting messages passed between them. That’s why it needs some authentication method between participants. When Alice and Bob have a public key infrastructure they may digitally sign the agreed key, or ga and gb, as in MQV, STS and the IKE component of the IPsec protocol suite for securing Internet Protocol communications. When Alice and Bob share a password, they may use a password-authenticated key agreement form of Diffie-Hellman. Some method to authenticate these parties to each other is generally needed.


Example of Real Problem in Security Issues

This example is originally from nchiper website.

In some circumstances, Diffie-Hellman keys generated by an HSM (hierarchical storage management) may be less secure than previously thought. An attack which recovers a vulnerable private key is (for typical parameters), expensive but possible. Keys subject to this vulnerability should be replaced. In addition, a firmware upgrade is available which removes the root cause of the generation of vulnerable keys; alternatively an upgrade to the key generation software provides a (verifiable) workaround.

1. Cause

When an HSM generates a set of Diffie-Hellman group parameters - specifically when generating a DHPrivate/DHPublic keypair where the 'DiscreteLogGroup' parameters are not passed in - it may choose random parameters with undesirable properties. These properties enable an algorithmic attack to recover the private key with significantly less effort than by brute force, given the ability to make Diffie-Hellman queries using the key. Because of the website doesn’t write anything about the attack so I can’t be sure what kind of attack that the attacker do. In most situations, Diffie-Hellman keys will be generated using group parameters fixed in advance (communicating parties must use keys with identical group parameters for the algorithm to succeed). Where these parameters are fixed to known 'good' values, the attack will not succeed. The 'Oakley' groups published in RFC2412 and RFC3526 are suitable good values.

2. Impact

An attacker who has access to an HSM containing a loaded and vulnerable Diffie-Hellman private key can, with significant probability, extract information which enables the private key value to be discovered. If successful, previous and future communications established using this key can be deciphered. No particular privilege, beyond the ability to make chosen queries and retrieve the results, is required to mount the attack. Keys subject to this vulnerability cannot be 'fixed' and must be discarded and replaced.

 

3. Who Is *Not* Affected

Some example of nChiper hardware that’s not affected by the attack

  • Any nCipher hardware module supplied with or upgraded to V10 firmware 2.22.6.
  • Any nFast or nForce Ultra module - as these either have no nCipher key management or have modules with fixed firmware.
  • miniHSM PCI or any other product utilizing the miniHSM - as these are supplied with firmware revision 2.22.6 or later.

4. Who May Be Affected

Some example of nChiper hardware that affected by the attack:

  • Diffie-Hellman keys were generated using the 'generatekey' utility, the MSCAPI or JCECSP provider, or via CHIL from nCipher software CD versions *before* v9.0
  • Diffie-Hellman keys were generated by an application which uses the nCore API directly

Keys subject to this problem must be discarded and replaced with freshly-generated keys which are not vulnerable. Such keys can be generated by either of the following:

  • Any software which uses an nCipher HSM upgraded to version 2.22.6 or higher firmware. This firmware is supplied on nCipher support CDs v10.x and higher.
  • The generatekey utility, the MSCAPI or JCECSP provider from nCipher software CD version v9.0 or later.



List of Difficult Words

Alice and Bob is also known as A and B (person or device)

Eve is an eavesdropper also known as a passive attacker.

DHP is Diffie-Hellman problem (Given an element g and the values of gx and gy, what is the value of gxy ?). g is an element of some participants and x and y are integers chosen but unknown to the eavesdropper.

MQV (Menezes-Qu-Vanstone) is an authenticated protocol for key agreement based on the Diffie-Hellman key exchange.

Station-to-Station (STS) protocol is a cryptographic key agreement scheme that provides mutual key and entity authentication based on classic Diffie-Hellman key exchange.

Internet key exchange (IKE) is the protocol used to set up a security association (SA) in the IPsec protocol suite.

HSM is hierarchical storage management, a data storage system that automatically moves data between high-cost and low-cost storage media. HSM systems exist because high-speed storage devices, such as hard disk drives, are more expensive (per byte stored) than slower devices, such as optical discs and magnetic tape drives.

nChiper is a company that protects critical enterprise data for many of the world's most security-conscious organizations. Delivering solutions in the fields of identity management, data protection, enterprise key management and cryptographic hardware, nCipher enables businesses to identify who can access data, to protect data in transit and at rest, and to comply with the growing number of privacy-driven regulations.

Conclusion:

Diffie-Hellman key exchange is not too secure but if we can make it more secure by adding authentication method. But nothing is safe from hacker, as long as hacker exist then we need to secure more such as in Diffie-Hellman key exchange, we can use large prime number and bigger private key (so hard to guess), we also need to use numbers mix together with alphabets (lower case & capitalize) for our password (email, atm, etc) but never use your telephone number, date of birth, your name and anything else that easily to guess for your password.


References:

1.      http://en.wikipedia.org/wiki/Cryptography

"

資工三甲 493511254  葉庭君

 

主題:壓縮演算法

前言

將資料壓縮已成為現代稀疏平常的事,就像在傳送資料時,會因資料過大,將全部資料壓縮在一起,節省浪費的空間,再加上將資料壓縮再傳給對方,也算是一種禮貌,直到現在,資料壓縮處理已經是很平常的技術,電腦界也開發了很多壓縮用的工具可使用,而且使用GUI軟體也越來越多,因此,對電腦不精通者,也能很輕鬆完成資料壓縮的工作。

 

摘要

何謂資料壓縮,是一種將檔案等資料的容量變得更小的處理,可分為可逆壓縮不可逆壓縮兩類型,後者不能保證能夠從已壓縮後的資料轉回原本的資料,也就是會造成資料的遺失,就像聲音、影像、動畫上,雖然可能有些許的資料流失,但資料的價值,取決於人類的感覺,其實有些時候人類是辨別不出來的,因此為了要提高壓縮的效能,或是為了壓縮方便,而把部分資料刪除,或變更資料的值,但是這些都會在人類感官可接受的範圍內。

至於一般來說,通常資料是不容許有誤差的發生的,就像程式碼,不容許有任何一個位元有變更,所以這次研究的主題,會專研在可逆壓縮的範圍上,畢竟要了解不可逆壓縮的演算法前,還是先必須有可逆壓縮的演算法知識,以下會介紹有關基本的資料壓縮演算法,還有利用資料的分布不均勻來做資料壓縮的演算法,也就是將壓縮後的資料解壓縮之後,仍可以得到原本的資料,但前提下,一定要有可以浪費的空間存在,壓縮處理就等於將這些浪費的空間節省下來,達到縮小的目的。

 

 SHAPE  * MERGEFORMAT

不可逆壓縮與可逆壓縮                                                 

可逆壓縮

              壓縮             解壓縮                        

 

 

 

不可逆壓縮

                     壓縮                    解壓縮

 


原資料


原資料


壓縮資料


復原出來的資料


在壓縮的前後,資料一定完全一樣


在壓縮的前後,資料會有所缺損


壓縮資料


復原出來的資料

內容

基本的資料壓縮演算法

Run-Length編碼

概念:Run-Length編碼在資料壓縮法是屬於最簡單的一種,但通用性不高,因為想法簡單,此是一種在資料內有連續的值時,去記錄其連續個數的方法,舉例來說,如果資料上面是「1,1,1,1,1,1,1,1」,我們可以將他寫成「8個1」,將資料攤開來寫,算是一種浪費,將他集結起來表示,可以節省大量空間做重複性的事,但此適用於資料中有連續出現同樣值的情況,否則run-length編碼使用機會不大。

Run-Length編碼

 

(1)原資料

1

1

1

1

0

0

1

1

1

1

2

2

2

1

1

1

3

3

3

 

(2)壓縮資料

4

1

 

2

0

 

4

1

 

3

2

 

3

1

 

3

3

 

 SHAPE  * MERGEFORMAT

「值為1”的資料有4”個」「值為:0”的資料有2”個」……

以此類推,把一樣數值連續出現的區塊歸類在一起

 

Run-Length編碼的處理方法雖然簡單,但在有些資料種類裡面會發揮非常大的效果,另外,因為它的處理方法非常單純,所以只要配合資料的類型來想辦法,一定還有許多提升壓縮率的空間。

 

 

 

 

 

利用資料之分布不均勻來做資料壓縮的演算法

 

概念一 (何謂資料中所含的浪費?):此演算法的基本概念在於資料中所含的浪費是資料的冗長性,此資料的浪費要先提到資料量和資訊量,而資料量指的是資料的實體大小,ex.100MB的資料就是「資料量=100MB」,然而資訊量呢?他指的是不管資料量如何,資料列中所含的真正資訊價值,ex.假設有一個100種字,組成長度為100的字串,而文字是用「1個字=8位元」表示,若以這種方表示字串,而它的資料量就是「8*100=800位元」,但如果在其他環境中,可能1個字=x位元,那所表示的位元數就會有所不同,所以用不同的資料化方法下,產生的資料量會有很大的差距,也就是說,在有些資料類型中,「資訊量<資料量」,而我們所提到的浪費,就是指資訊量和資料量之間的差距,在壓縮處理中,就是要藉由減少資料中所含的冗長性,來達到不損失原本資訊的情況下,減少資料量的目的,也就是說,若原資料中沒有冗長性,我們就無法進行壓縮,因為資訊量是資料量在壓縮處理的理論上限。

"

加密演算法

介紹何謂 演算法?演算法就是用口語化的方式,描述解決問題的步驟,演算法是由有限的步驟組成,只要依其指示的步驟順序執行,一定可以完成某特定的工作。理想的演算法必須滿足輸入、輸出、明確性及有效性等要求。 什麼是 RSARSA全名﹝Rivest-Shamir-Adelman﹞, 1977年美國麻省理工學院Ron Rivest, Adi Shamir Len Adleman三位教授共同發明。 RSA加密 演算法是一種特殊的非對稱密碼法, 利用兩個質數作為加密與解密的兩個鑰匙(key)。這兩個鑰匙分別稱為公開鑰匙 (public key) 和私人鑰匙 (private key 或是 secret key),鑰匙的長度約在 40 個位元到 1024 位元。公開鑰匙作為加密,只有使用私人鑰匙才能解密,解密者只要不洩露私人鑰匙,別人就算有公開鑰匙,也是很難推演算出來私人鑰匙,就算是利用反向工程來解密也不是一件簡單的事,所以 RSA 算是一種十分安全的加密與解密演算法。  RSA的演算法        RSA 演算法推演o        明文:M o        密文:C o        加密:C Me mod n o        解密:M Cd mod n (Me)d mod n Med mod n o        公開鑰匙:KU = {e, n} o        私有鑰匙:KD = {d, n} o        尋找出適合的 n  d  推論  M Med mod n·         必須合乎下列條件:                   1. 必須找出 ed n 的值,對所有 M < n,都能滿足 Med M mod n 2. 對任何 M < n 而言,計算 Me Cd都必須非常容易。 3. 如果給定 e n,要計算出 d 是非常困難的;反之亦然。 ·         Euler 定理: o        mψ(n)+1 m mod n  o        ψ(n)=(p-1)(q-1) 其中 n = pq 則: o        mψ(n)+1 = m(p-1)(q-1)+1 m mod n ·         如果:m n 互質的話(gcd(m, n) = 1)則: o        gcd(m, n) =1 表示 m n 之間無法整除 o        n = pq,如果 m/n = m/pq  不可以整除的話,則 m/p m/q 是否可以或無法整除。 o        假設兩個條件: §         m = pc,其中 c 為任何整數。 §         gcd(m, p)1 gcd(m, q) =1 ·         其中 gcd(m, q) =1,表示 m q 之間是互質的關係: o        依照 Euler 定理:aψ(n) 1 mod n,則: o        mψ(q) 1 mod q o        利用同餘運算規則:[mψ(q)]ψ(p) 1 mod q mψ(p)×ψ(q) 1 mod q m(p-1)×(q-1) 1 mod q;又ψ(n) = (p-1)×(q-1) 則: o        mψ(n) 1 mod q o        mψ(n) = 1 + kq o        如果等號雙邊各乘以 m,其中 m = cp n = pq,則:mψ(n)+1 = m + kcpq = m + kcn相當於:m 除以 n,而得到的商是 kc、餘數是 m,因此,可改寫成:mψ(n)+1 m mod n o        再利用:aψ(n) 1 mod n 推導出:[mψ(n)]k 1 mod n mkψ

"

紅黑樹是一種自平衡二元搜尋樹,是在電腦科學中用到的一種資料結構,典型的用途是實現關聯數組。它是在1972年Rudolf Bayer發明的,他稱之為"對稱二叉B樹",它現代的名字是在 Leo J. Guibas 和 Robert Sedgewick1978年寫的一篇論文中獲得的。它是複雜的,但它的操作有著良好的最壞情況運行時間,並且在實踐中是高效的: 它可以在O(log n)時間內做查找,插入和刪除,這裡的n 是樹中元素的數目。

用途和好處

 

紅黑樹和AVL樹一樣都對插入時間、刪除時間和查找時間提供了最好可能的最壞情況擔保。這不只是使它們在時間敏感的應用如即時應用(real time application)中有價值,而且使它們有在提供最壞情況擔保的其他資料結構中作為建造板塊的價值;例如,在計算幾何中使用的很多資料結構都可以基於紅黑樹。

 

紅黑樹在函數式編程中也特別有用,在這裡它們是最常用的持久資料結構之一,它們用來構造關聯數組和集合,在突變之後它們能保持為以前的版本。除了O(log n)的時間之外,紅黑樹的持久版本對每次插入或刪除需要O(log n)的空間。

 

紅黑樹是 2-3-4樹的一種等同。換句話說,對於每個 2-3-4 樹,都存在至少一個數據元素是同樣次序的紅黑樹。在 2-3-4 樹上的插入和刪除操作也等同於在紅黑樹中顏色翻轉和旋轉。這使得 2-3-4 樹成為理解紅黑樹背後的邏輯的重要工具,這也是很多介紹演算法的教科書在紅黑樹之前介紹 2-3-4 樹的原因,儘管 2-3-4 樹在實踐中不經常使用。

 

性質

 

紅黑樹是每個節點都帶有顏色屬性的二元搜尋樹,顏色或紅色或黑色。在二元搜尋樹強制一般要求以外,對於任何有效的紅黑樹我們增加瞭如下的額外要求:

 

性質1. 節點是紅色或黑色。

 

性質2. 根是黑色。

 

性質3. 所有葉子都是黑色(包括NIL)。

 

性質4. 每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)

 

性質5. 從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。

 

這些約束強制了紅黑樹的關鍵性質: 從根到葉子的最長的可能路徑不多於最短的可能路徑的兩倍長。結果是這個樹大致上是平衡的。因為操作比如插入、刪除和查找某個值的最壞情況時間都要求與樹的高度成比例,這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的,而不同於普通的二元搜尋樹。

 

要知道為什麼這些特性確保了這個結果,注意到屬性4導致了路徑不能有兩個毗連的紅色節點就足夠了。最短的可能路徑都是黑色節點,最長的可能路徑有交替的紅色和黑色節點。因為根據屬性5所有最長的路徑都有相同數目的黑色節點,這就表明了沒有路徑能多於任何其他路徑的兩倍長。

 

在很多樹資料結構的表示中,一個節點有可能只有一個子節點,而葉子節點包含數據。用這種範例表示紅黑樹是可能的,但是這會改變一些屬性並使演算法複雜。為此,本文中我們使用 "nil 葉子" 或"空(null)葉子",如上圖所示,它不包含數據而只充當樹在此結束的指示。這些節點在繪圖中經常被省略,導致了這些樹好象同上述原則相矛盾,而實際上不是這樣。與此有關的結論是所有節點都有兩個子節點,儘管其中的一個或兩個可能是空葉子。

 

操作

 

因為每一個紅黑樹也是一個特化的二元搜尋樹,因此紅黑樹上的只讀操作與普通二元搜尋樹上的只讀操作相同。然而,在紅黑樹上進行插入操作和刪除操作會導致不再符合紅黑樹的性質。恢復紅黑樹的屬性需要少量(O(log n))的顏色變更(實際是非常快速的)和不超過三次樹旋轉(對於插入操作是兩次)。雖然插入和刪除很複雜,但操作時間仍可以保持為 O(log n) 次。

 

插入

 

我們首先以二元搜尋樹的方法增加節點並標記它為紅色。(如果設為黑色,就會導致根到葉子的路徑上有一條路上,多一個額外的黑節點,這個是很難調整的。但是設為紅色節點後,可能會導致出現兩個連續紅色節點的衝突,那麼可以通過顏色調換(color flips)和樹旋轉來調整。)下面要進行什麼操作取決於其他臨近節點的顏色。同人類的家族樹中一樣,我們將使用術語叔父節點來指一個節點的父節點的兄弟節點。注意:

 

    * 性質1和性質3總是保持著。

    * 性質4只在增加紅色節點、重繪黑色節點為紅色,或做旋轉時受到威脅。

    * 性質5只在增加黑色節點、重繪紅色節點為黑色,或做旋轉時受到威脅。

 

在下面的示意圖中,將要插入的節點標為N,N的父節點標為P,N的祖父節點標為G,N的叔父節點標為U。在圖中展示的任何顏色要麼是由它所處情形所作的假定,要麼是這些假定所暗含的。

 

對於每一種情況,我們將使用 C示例代碼來展示。通過下列函數,可以找到一個節點的叔父和祖父節點:

 

node grandparent(node n) {

    return n->parent->parent;

}

 

node uncle(node n) {

    if (n->parent == grandparent(n)->left)

        return grandparent(n)->right;

    else

        return grandparent(n)->left;

}

 

 

情形1: 新節點N位於樹的根上,沒有父節點。在這種情形下,我們把它重繪為黑色以滿足性質2。因為它在每個路徑上對黑節點數目增加一,性質5符合。

 

void insert_case1(node n) {

    if (n->parent == NULL)

        n->color = BLACK;

    else

        insert_case2(n);

}

 

情形2: 新節點的父節點P是黑色,所以性質4沒有失效(新節點是紅色的)。在這種情形下,樹仍是有效的。性質5受到威脅,因為新節點N有兩個黑色葉子兒子;但是由於新節點N是紅色,通過它的每個子節點的路徑就都有同通過它所取代的黑色的葉子的路徑同樣數目的黑色節點,所以這個性質依然滿足。

 

void insert_case2(node n) {

    if (n->parent->color == BLACK)

        return; /* 樹仍舊有效 */

    else

        insert_case3(n);

}

 

注意: 在下列情形下我們假定新節點有祖父節點,因為父節點是紅色;並且如果它是根,它就應當是黑色。所以新節點總有一個叔父節點,儘管在情形4和5下它可能是葉子。

 

情形3: 如果父節點P和叔父節點U二者都是紅色,則我們可以將它們兩個重繪為黑色並重繪祖父節點G為紅色(用來保持性質5)。現在我們的新節點N有了一個黑色的父節點P。因為通過父節點P或叔父節點U的任何路徑都必定通過祖父節點G,在這些路徑上的黑節點數目沒有改變。但是,紅色的祖父節點G的父節點也有可能是紅色的,這就違反了性質4。為了解決這個問題,我們在祖父節點G上遞歸地進行情形1的整個過程。

 

void insert_case3(node n) {

    if (uncle(n) != NULL && uncle(n)->color == RED) {

        n->parent->color = BLACK;

        uncle(n)->color = BLACK;

        grandparent(n)->color = RED;

        insert_case1(grandparent(n));

    }

    else

        insert_case4(n);

}

 

注意: 在餘下的情形下,我們假定父節點P 是其父親G 的左子節點。如果它是右子節點,情形4和情形5中的左和右應當對調。

 

情形4: 父節點P是紅色而叔父節點U是黑色或缺少; 還有,新節點N是其父節點P的右子節點,而父節點P又是其父節點的左子節點。在這種情形下,我們進行一次左旋轉調換新節點和其父節點的角色; 接著,我們按情形5處理以前的父節點P。這導致某些路徑通過它們以前不通過的新節點N或父節點P中的一個,但是這兩個節點都是紅色的,所以性質5沒有失效。

 

void insert_case4(node n) {

    if (n == n->parent->right && n->parent == grandparent(n)->left) {

        rotate_left(n->parent);

        n = n->left;

    } else if (n == n->parent->left && n->parent == grandparent(n)->right) {

        rotate_right(n->parent);

        n = n->right;

    }

    insert_case5(n);

}

 

情形5: 父節點P是紅色而叔父節點U 是黑色或缺少,新節點N 是其父節點的左子節點,而父節點P又是其父節點G的左子節點。在這種情形下,我們進行針對祖父節點P 的一次右旋轉; 在旋轉產生的樹中,以前的父節點P現在是新節點N和以前的祖父節點G 的父節點。我們知道以前的祖父節點G是黑色,否則父節點P就不可能是紅色。我們切換以前的父節點P和祖父節點G的顏色,結果的樹滿足性質4。性質5也仍然保持滿足,因為通過這三個節點中任何一個的所有路徑以前都通過祖父節點G ,現在它們都通過以前的父節點P。在各自的情形下,這都是三個節點中唯一的黑色節點。

 

void insert_case5(node n) {

    n->parent->color = BLACK;

    grandparent(n)->color = RED;

    if (n == n->parent->left && n->parent == grandparent(n)->left) {

        rotate_right(grandparent(n));

    } else {

        /* Here, n == n->parent->right && n->parent == grandparent(n)->right */

        rotate_left(grandparent(n));

    }

}

 

注意插入實際上是原地演算法,因為上述所有調用都使用了尾部遞歸。

 

刪除

 

如果需要刪除的節點有兩個兒子,那麼問題可以被轉化成刪除另一個只有一個兒子的節點的問題(為了表述方便,這裡所指的兒子,為非葉子節點的兒子)。對於二元搜尋樹,在刪除帶有兩個非葉子兒子的節點的時候,我們找到要麼在它的左子樹中的最大元素、要麼在它的右子樹中的最小元素,並把它的值轉移到要刪除的節點中(如在這裡所展示的那樣)。我們接著刪除我們從中複製出值的那個節點,它必定有少於兩個非葉子的兒子。因為只是複製了一個值而不違反任何屬性,這就把問題簡化為如何刪除最多有一個兒子的節點的問題。它不關心這個節點是最初要刪除的節點還是我們從中複製出值的那個節點。

 

在本文餘下的部分中,我們只需要討論刪除只有一個兒子的節點(如果它兩個兒子都為空,即均為葉子,我們任意將其中一個看作它的兒子)。如果我們刪除一個紅色節點,它的父親和兒子一定是黑色的。所以我們可以簡單的用它的黑色兒子替換它,並不會破壞屬性3和4。通過被刪除節點的所有路徑只是少了一個紅色節點,這樣可以繼續保證屬性5。另一種簡單情況是在被刪除節點是黑色而它的兒子是紅色的時候。如果只是去除這個黑色節點,用它的紅色兒子頂替上來的話,會破壞屬性4,但是如果我們重繪它的兒子為黑色,則曾經通過它的所有路徑將通過它的黑色兒子,這樣可以繼續保持屬性4。

 

需要進一步討論的是在要刪除的節點和它的兒子二者都是黑色的時候,這是一種複雜的情況。我們首先把要刪除的節點替換為它的兒子。出於方便,稱呼這個兒子為N,稱呼它的兄弟(它父親的另一個兒子)為S。在下面的示意圖中,我們還是使用P稱呼N的父親,SL稱呼S的左兒子,SR稱呼S的右兒子。我們將使用下述函數找到兄弟節點:

 

node sibling(node n) {

     if (n == n->parent->left)

         return n->parent->right;

     else

         return n->parent->left;

}

 

我們可以使用下列代碼進行上述的概要步驟,這裡的函數 replace_node 替換 child 到 n 在樹中的位置。出於方便,在本章節中的代碼將假定空葉子被用不是 NULL 的實際節點對象來表示(在插入章節中的代碼可以同任何一種表示一起工作)。

 

void delete_one_child(node n) {

    /* Precondition: n has at most one non-null child */

    node child = (is_leaf(n->right)) ? n->left : n->right;

    replace_node(n, child);

    if (n->color == BLACK) {

        if (child->color == RED)

            child->color = BLACK;

        else

            delete_case1(child);

    }

    free(n);

}

 

如果 N 和它初始的父親是黑色,則刪除它的父親導致通過 N 的路徑都比不通過它的路徑少了一個黑色節點。因為這違反了屬性 4,樹需要被重新平衡。有幾種情況需要考慮:

 

情況 1: N 是新的根。在這種情況下,我們就做完了。我們從所有路徑去除了一個黑色節點,而新根是黑色的,所以屬性都保持著。

 

void delete_case1(node n) {

    if (n->parent == NULL)

        return;

    else

        delete_case2(n);

}

 

注意: 在情況2、5和6下,我們假定 N 是它父親的左兒子。如果它是右兒子,則在這些情況下的左和右應當對調。

 

情況 2: S 是紅色。在這種情況下我們在N的父親上做左旋轉,把紅色兄弟轉換成N的祖父。我們接著對調 N 的父親和祖父的顏色。儘管所有的路徑仍然有相同數目的黑色節點,現在 N 有了一個黑色的兄弟和一個紅色的父親,所以我們可以接下去按 4、5或6情況來處理。(它的新兄弟是黑色因為它是紅色S的一個兒子。)

 

void delete_case2(node n) {

    if (sibling(n)->color == RED) {

        n->parent->color = RED;

        sibling(n)->color = BLACK;

        if (n == n->parent->left)

            rotate_left(n->parent);

        else

            rotate_right(n->parent);

    }

    delete_case3(n);

}

 

情況 3: N 的父親、S 和 S 的兒子都是黑色的。在這種情況下,我們簡單的重繪 S 為紅色。結果是通過S的所有路徑, 它們就是以前不通過 N 的那些路徑,都少了一個黑色節點。因為刪除 N 的初始的父親使通過 N 的所有路徑少了一個黑色節點,這使事情都平衡了起來。但是,通過 P 的所有路徑現在比不通過 P 的路徑少了一個黑色節點,所以仍然違反屬性4。要修正這個問題,我們要從情況 1 開始,在 P 上做重新平衡處理。

 

void delete_case3(node n) {

    if (n->parent->color == BLACK &&

        sibling(n)->color == BLACK &&

        sibling(n)->left->color == BLACK &&

        sibling(n)->right->color == BLACK)

    {

        sibling(n)->color = RED;

        delete_case1(n->parent);

    }

    else

        delete_case4(n);

}

 

情況 4: S 和 S 的兒子都是黑色,但是 N 的父親是紅色。在這種情況下,我們簡單的交換 N 的兄弟和父親的顏色。這不影響不通過 N 的路徑的黑色節點的數目,但是它在通過 N 的路徑上對黑色節點數目增加了一,添補了在這些路徑上刪除的黑色節點。

 

void delete_case4(node n) {

    if (n->parent->color == RED &&

        sibling(n)->color == BLACK &&

        sibling(n)->left->color == BLACK &&

        sibling(n)->right->color == BLACK)

    {

        sibling(n)->color = RED;

        n->parent->color = BLACK;

    }

    else

        delete_case5(n);

}

情況 5: S 是黑色,S 的左兒子是紅色,S 的右兒子是黑色,而 N 是它父親的左兒子。在這種情況下我們在 S 上做右旋轉,這樣 S 的左兒子成為 S 的父親和 N 的新兄弟。我們接著交換 S 和它的新父親的顏色。所有路徑仍有同樣數目的黑色節點,但是現在 N 有了一個右兒子是紅色的黑色兄弟,所以我們進入了情況 6。N 和它的父親都不受這個變換的影響。

 

void delete_case5(node n) {

    if (n == n->parent->left &&

        sibling(n)->color == BLACK &&

        sibling(n)->left->color == RED &&

        sibling(n)->right->color == BLACK)

    {

        sibling(n)->color = RED;

        sibling(n)->left->color = BLACK;

        rotate_right(sibling(n));

    }

    else if (n == n->parent->right &&

             sibling(n)->color == BLACK &&

             sibling(n)->right->color == RED &&

             sibling(n)->left->color == BLACK)

    {

        sibling(n)->color = RED;

        sibling(n)->right->color = BLACK;

        rotate_left(sibling(n));

    }

    delete_case6(n);

}

 

情況 6: S 是黑色,S 的右兒子是紅色,而 N 是它父親的左兒子。在這種情況下我們在 N 的父親上做左旋轉,這樣 S 成為 N 的父親和 S 的右兒子的父親。我們接著交換 N 的父親和 S 的顏色,並使 S 的右兒子為黑色。子樹在它的根上的仍是同樣的顏色,所以屬性 3 沒有被違反。但是,N 現在增加了一個黑色祖先: 要麼 N 的父親變成黑色,要麼它是黑色而 S 被增加為一個黑色祖父。所以,通過 N 的路徑都增加了一個黑色節點。

 

此時,如果一個路徑不通過 N,則有兩種可能性:

 

    * 它通過 N 的新兄弟。那麼它以前和現在都必定通過 S 和 N 的父親,而它們只是交換了顏色。所以路徑保持了同樣數目的黑色節點。

    * 它通過 N 的新叔父,S 的右兒子。那麼它以前通過 S、S 的父親和 S 的右兒子,但是現在只通過 S,它被假定為它以前的父親的顏色,和 S 的右兒子,它被從紅色改變為黑色。合成效果是這個路徑通過了同樣數目的黑色節點。

 

在任何情況下,在這些路徑上的黑色節點數目都沒有改變。所以我們恢復了屬性 4。在示意圖中的白色節點可以是紅色或黑色,但是在變換前後都必須指定相同的顏色。

 

void delete_case6(node n) {

    sibling(n)->color = n->parent->color;

    n->parent->color = BLACK;

    if (n == n->parent->left) {

        /* Here, sibling(n)->color == BLACK &&

                 sibling(n)->right->color == RED */

        sibling(n)->right->color = BLACK;

        rotate_left(n->parent);

    }

    else

    {

        /* Here, sibling(n)->color == BLACK &&

                 sibling(n)->left->color == RED */

        sibling(n)->left->color = BLACK;

        rotate_right(n->parent);

    }

}

"

資工三甲 493511199  葉思妤

字串比對問題     
String-matching problem
是一個很常見的問題亦是我們在大一時必寫的其中一個程式-----即在一個文字(text)中找出一個樣式(pattern)的所有出現這樣的功能通常用來在檔中搜尋特定單字或是搜尋DNA序列中的特定樣式       
一般而言這類問題最常見的基本型態為: 假設有一個長度為n其組成元素可能為數字或字母的字串陣列T[1…..n] ; 另有一長度為m(<=n)其組成元素和T[ ]同為數字或字母的字串陣列P[1…..m] 接著我們假設如果0 <= s <= n-m並且T[s+1…s+m] = P[1…m] 則我們說樣式P在文字T內以位移s發生或是說: 樣式P在文字T內從位置s+1開始發生並稱s為一個有效位移(valid shift)      
而所謂字串比對問題即是找出一個樣式P在一個文字T中所發生的所有有效位移 

例如:  T = abcaacbacabc               
   
P = aacba        
則此樣式P在文字T中只出現過一次是發生在有效位移s=3的地方    

用於處理字串比對問題的解法有很多種,差別當然就在其效能之好壞……下面列出幾種常見的演算法: 

演算法  預先處理時間 比對時間
Native 0 O((n-m+1)m)
Rabin-Karp Θ(m) O((n-m+1)m)
Finite automaton O(m|Σ|)  Θ(n)
Knuth-Morris-Pratt Θ(m)  Θ(n)

 : 預先處理為一種事先在樣式P上所執行的動作。   
比對為找出所有有效位移的工作。
 

雖然有這許多種方法,從表中我們似乎也能輕易觀察出哪種演算法較好,但其中最讓我感興趣的卻是—Native algorithm以及Rabin-Karp algorithm    
因為Native algorithm就是我們俗稱最簡單卻也最沒效率的暴力演算法,也就是說Rabin-Karp algorithm應該要比它還好、更為有效率才是但由表中我們卻似乎不是得到這樣的結論因此激發了我想去研究它們差異性的念頭。
  

 Native algorithm    
Native algorithm中,有一個2階式的巢狀回圈在跑---首先將P[1]一一和T[]做比對,如果在T[ ]中找到一個和P[1]相等,在此我們假設T[s+1]= = P[1],接著就開始T[s+1…s+m] = P[1…m]的比對迴圈。如果都相等,則我們說s為一個有效位移。    然後再繼續尋找下一個有效位移。
 

Pseudo code: 

Native-algorithm(T,P)  
Int n=lenth[T]
  
Int m= lenth[P]
  
For(int s=0; s=n-m; s++)
  
{         
 If(P[1…m]= T[s+1…s+m])        
System.out.println(“find s =”+s)
   }    

所以我們知道Native-algorithm的比對時間共花費了O((n-m+1)m)時間,而且在最糟情況時此界線是緊密的。  因為內部迴圈須執行m次來確認s是否為有效位移, 所以如果m = [n/2] ,則Θ((n-m+1)m)會等於Θ(n ) ,即是說:因為沒有作預先處理,所以Native algorithm的執行時間等於其比對時間。    

因此我們得知Native-algorithm是個無效率的String-matching problem演算法,因為在很多情況下,我們其實根本就可以不用再去做判斷。 

例如: 如果P=aaab,並且我們發現s=0是有效的,則我們根本無須再去判斷位移1,2,3….因為那必然都是無效的。

 Rabin-Karp algorithm    
1987
年,Richard M. KarpMichael O. Rabin(1976年圖靈獎獲得者)合作,提出了另一種String-matching problem 的演算法,即: Rabin-Karp algorithm
    
雖然在最糟情況下,它的執行時間和Native-algorithm的最糟情況執行時間一樣都是Θ((n-m+1)m) ,但它在平均情況執行時間以及實作上卻能得到較好的效能,並且可以一般化到相關問題。例如:其他的樣式比對問題。
       

首先介紹Rabin-Karp algorithm中的一大特點就是:它假設每個字元都是十進位數字,於是我們可以將k個連續字元的一串字元字串看作是一個長度為k10進位數字。例如:給定一字元字串34567,則我們可將其看作為34,56710進位數字。    
依此規則,我們回到一開始所給定的文字字串陣列T[1…..n]以及樣式字串陣列P[1…..m] ,然後給予p來表示長度為mP[1…..m] 10進位數值,並且以ts來表示長度為m的子字串T[s+1…..s+m] 10進位數值(s=0,1,2,……,n-m)
     如果T[s+1…..s+m] = P[1…..m] ,即代表ts = p ,也就是說s是一個有效位移。        

接著,我們就要來探討要花多少時間在計算pts:
我們可以使用Horner規則: 
p = P[m] + 10(P[m-1] + 10(P[m-2] + ……+ 10(P[2] + 10P[1])……))    

依此方法,我們可以在Θ(m) 時間內將p計算出來。同樣地,數值ts亦可在Θ(m) 時間內計算出來。因此,我們得知可以在Θ(n-m+1)時間內計算出所有的ts數值,然後再開始比較p與每一個ts  (花費時間為Θ(m) + Θ(n-m+1) = Θ(n)時間內),以找出所有有效位移s     

另外,我們還發現到,如果寫成下列式子:
ts+1 = 10(ts - 10 m-1T[s+1]) + T[s+m+1]    
也就是利用減去(ts - 10 m-1)後乘以10,然後再加上T[s+m+1]的方式,我們即可得到ts+1 ,而且此ts+1 可以在常數時間內從ts 記算得到(前提是常數10 m-1   是預先可計算的, 則方程式ts+1 = 10(ts - 10 m-1T[s+1]) + T[s+m+1]的每個執行花費一個常數數目的算數操作式)

 例如: T[1,2,3,4,5] ; 如果m = 5 ts =12345     
ts+1 = 10(12345 - 10000*1) + 6
    = 23456    

由上述所知,我們可以在Θ(m) 時間內計算出p,以及在Θ(n-m+1)時間內計算出t0 t1…… tn-m,而且我們可以使用Θ(m) 預先處理時間與Θ(n-m+1)比對時間來在文字T[1……n]中找到樣式P[1……m]的所有發生。     

截至目前為止,雖然一切似乎都看似運作正常,但其實此方法中卻存在有一大問題----pts值大太的話,則無法達到好的效能。    

因此為了解決這個問題,我們想到了利用Hash的觀念來將pts同餘於一個適當的模數q (通常是選擇一個質數來作為模數q) 好讓10 m-1 剛好可以填入一個word字組內,藉此讓所有必須的計算以單精度算數來執行。) 

"

A* Algorithm

這次project的題目是有關如何去identify一個optimal path的方法,實際上可以選擇使用的方法有很多種,不過這裡只先談論A*path finding演算法。

A*其實可以想成是Dijkstrabest-first search這兩種的綜合方式,也就是說,它利用下一步總是找最近、最短的路徑,同時也對所有可能的路徑利用cost或是說設定某個weightvalue的方法來找出最佳的選擇,只是判斷過程中的每個node value值都是由兩個特定的值相加而得,一個是由起點到目前所在點的cost總和,另一個則是經由heuristic方式對於剩下路徑部分的評估cost,利用一個path-based evaluationfunction來代表便是f(node) = g(node) + h(node),這種方式只要其中的h(node)可以確定是admissible的話,便不會過度評估路徑的cost,即可保證可以找出到目標的最短路徑,因此如何去評估這段heuristiccost則是決定A*是否有能力做到最佳路徑的搜尋,也是這次主要研究的部份,如果說我們根本不看h(node)而把它設為0,這樣其實就只是在利用類似breadth first search或是說就是Dijkstra的方式在尋找路徑,另外,A*可以達到最好的效率去做heuristic評估,每次路徑延伸下去的方式都是利用最少的nodes,但是同樣必須是在h(node)要是underestimate的狀態下。這種評估方式為了能被稱作A*,則h(node)這個評估的function要是admissible,分析得更細來看的話,如果h(node)評估的方式總是找出能低於或等於從起點到目標實際的cost值,這樣便是代表能找出shortest path,不過過程中所expandnode數會比較多,花費較多的時間;又可能h(node)的評估值恰好都跟實際cost值相等,代表說剛好都依照best path來走所以都沒expand到其他多餘的node,雖然不是每次的情況都能這麼剛好,但每次所提供的information如果都能是非常perfect的話,那評估出來的結果便可以是很完美的;此外,還有一種情況是h(node)估計出來的值是超過那段的路徑cost (overestimate),那麼這樣便無法保證能依照估計的方式找出最短路徑,不過相對的程式所用來記錄nodememory較少,也能較快找到一條路徑,可是有人就提出說這樣就不能稱它是A*了。大致上來說一個最佳的路徑或是普通好的路徑都是可以利用A*的特性來找到的。

在很多遊戲中都是會需要用到,像是玩魔獸3

或是網路遊戲裡使用游標click控制目標移動

都很常見。


有些需要注意的地方,上面有提到像是關於memory使用的方面,因為總是有許多目前路徑所要選擇的node資料(各項cost)要被storememory,為了減少使用memory,可能會包含到使用iterative deepening A*1以及simplified memory A*2。還有就是關於在圖形上節點密度的問題,如果在一個map上想要使用A*可能會因為選擇的距離太長導致中間會有一堆的node等著去通過,如果是短距離可能節點數量不會造成太大的負擔,但是一旦距離變長,我們設定node的密集度可能就要有所變動,為了在遊戲時隨時都能立即判斷出移動的路線,按照地圖的倍率大小去給定node數才能使電腦更能輕易地計算出選擇,這種層次的問題可分成巨觀、微觀的方面來想,一切都取決於當下路徑的需要,最好就是能用大區域計算比較長的路徑,然後在接近目標的時候,切換到使用小格子區域的精細路徑搜尋。想要剛好不忽略地形所造成的障礙並且最佳化node數量,即是提升路徑的精確度以及正確度都必須考量的方面。另外在計算f(node) = g(node) + h(node)的時候,兩種要相加的值也要是同樣單位,因為有可能一個代表的cost是時間,而另一個則是長度,這是需要避免出錯的地方。

實際上開始做這種map的路徑搜尋,還要先透過兩個儲存搜尋區節點的列表,即open listclosed list,想像地圖上被均勻分割成許多塊區域來代表每次可能經過的節點,從開始的那一格起每次增加新的一步,list中的元素便會改變,open list包含著以目前節點周圍附近可能到達或經過的節點列表;closed的則是放從open那邊刪除的點,也就是不需要再去檢查的節點。由此可知道open listmaintenance是十分重要,因為這是A*路徑搜尋法的重要組成部分,每次存取這個列表其實目的就是要找出cost最低的節點,簡單的方法就是把節點元素隨便放,等到要找的時候再按照順序找,不過很明顯當路徑範圍變大時便需要一個改善的作法,我們會藉由維護一個已經排序好的list來作search,並且能有效的做到快速地新增、刪除列表中的元素。另外,如果能預先處理地圖,標示出那地圖中是無法到達的區域像是島嶼或什麼的,才不會導致搜尋了整個地圖浪費cpu時間又找不到路徑;對於比較長的路徑,也可以預先計算好然後在使用到的時候直接套用,如此對於提升A*程式的速度都將有滿大的幫助。

接下來介紹幾種heuristic function通常選擇的距離估計法,Manhattan distanceDiagonal distanceEuclidean distance。其中最常見的就是第一個Manhattan distance,也就是很多時候解8 puzzle時都會用到的heuristic估計,就跟這種移動格子的遊戲規則一樣,它只能計算水平跟垂直兩個方向的移動,若假設每移動一格需要的costC,則h(node) = C * (起始點到目標的水平移動+垂直移動次數)。這種簡單的方式可能產生一個效率不高的問題,對於同樣的h(node)值可能從起始點到目標點的走法會有非常多種,為了消除在heuristic中出現的這種ties的問題,會在其中加入一個tie breaker藉由它來決定路徑的移動方向,比方說可以偏水平方向走,或是特別選擇走對角方向,對於每種方向的走法產生不同的f(node)值,這樣就可以避免上面說的全部走法的cost都相等的狀況,計算模式簡單地說是讓heuristic部分去乘以一個(1+p)的倍數,而p值只是一個很小的0.幾左右的數字,為的只是區別這種ties的問題。

接著是Diagonal distance的方法,顧名思義,它是包含能夠經由通過對角方向的路徑,比方原本要先走3次左,3次下,它只要cost經過3次往左下移動變可到達相同的位置,這時候往對角方向的cost也被考慮進去,有可能cost跟原本垂直水平的相同,也可能比較多不一定,用通式來表示便是h(node) = C2 * h_diagonal(node) + C * (h_straight(node) - 2*h_diagonal(node)))。其中h_diagonal的部份是取水平移動或是垂直移動次數兩者中比較小的那ㄧ個再乘以cost C2h_straight就是原本跟Manhattan distance算法一樣。

另外,還有一種Euclidean distance的計算方式,它是先假設移動方向並不侷限於任何角度,要多少度斜著橫著都可以的話,是可以試著套用這樣的公式來估計,h(node) = C * sqrt((水平移動次數)^2 + (垂直次數)^2)

以下是用實際的圖例來說明並且評估A*每次的走法:

假設我們是要尋找一條由藍色起點通往綠色終點的路徑,並且途中要越過黃色障礙物,規定水平跟垂直移動cost = 10,對角線移動cost=14利用目前f(node)值最小的當作前進路線並且以往下的路線為優先,

step1

                              

step2

 

step3

step4

 

step5

 

step6

   |

   |

   | 

stepN-1

 

final 

 

所有格子上標示的數字便是經過f(node) = g(node) + h(node)計算得到的值,比方說step1裡面40 = 10 + 3054 = 14 + 4060 = 10 + 50以此類推;所以自從第一次將起點加入open list後,便開始重複一個規律的操作,先是搜尋open listf(node)值最低的格子來當作current node,並且把它存到closed list,然後再對於這一格周圍的其他8格去確定是否已在closed list中或者是否為障礙物來判斷要不要忽略掉,如果沒有在上述情況的話則執行以下步驟:如果它也不在open list中,便加入它到open list中,並且把current node當作是這一格的parent然後紀錄fgh各項cost值,如果這一點已經在open list,則拿g值去比較是否走這條更好,如果有比較好的話,則將這點的parent改成current node,並且重新計算此格的fg值,例如step4進入到step5之後,下面原本f直是88的那一格,current變成是上面60那一格,所以將從起點到它的路徑cost(g)改為20,而非原本的必需經過54那一點所cost28。由於某些點的f值可能在此步驟之後發生改變,所以現在是開始重新依照fsorting open list的時候。最後,如果是發生把destination加入closed list的話,便代表已經找到了該走的路徑;但如果是open list已是empty沒有下一格可以走,便代表路徑不存在。到此則結束之前對於current node周圍8格判斷的重複步驟。如果要得到整個路徑的話便是沿著destination開始的每一格的parent找回去即可。以上就是在平面地圖上實作A* algorithm的步驟,雖然有些時候遊戲中的路線可能會受到地形的影響,像是魔獸3裡面也有一些上坡、下坡的地形,這時候就可能得改變這段路徑的移動cost,讓它在評估的時候能夠跟平地的cost有所區別。目前討論到的是以單一移動主體來做路徑的評估,在實際遊戲當中可能還會遇到一群鄰近的移動元素產生像是碰撞或是路徑重疊等問題,這樣的話對於路徑上的每個node又將需要額外加入penalty使那群元素趨向於尋找各自獨立的路線。

總而言之,這種Pathfinding演算法在實際用途方面算是滿多的,像是可以拿來設計機器人方面的控制,讓機器人在無人操控下順利的走過某些特殊的地形,例如在火星上的探測型機器人,雖然無法從地球這邊遠端遙控它,機器人自己本身仍然可以利用攝影機螢幕來判斷週遭的環境並且選擇出穿越各種地形的移動路線,其他也可能是在水中移動或是任何無法接受通訊的地方;比較一般的應用還有在交通工具的移動上,如何找出地圖上兩點間的移動路線並且避免一些路上的障礙或是說避開路段壅塞的區域,這也很類似電腦網路課程講的在internet上傳送資料的routing方法,或是電話線路這類的;還有就是前面也提過在遊戲中人物移動的路線計算,尤其是即時戰略遊戲一定必備的,網路遊戲有些就沒設計這麼完整還可以讓腳色繞過障礙物或什麼的,撞到東西有時候就還要再點一次目標。然而,也並非所有路徑演算法都是能達到最好的功效,可能對於某些情況配合某種路徑搜尋法會達到特別好的效能,但依照各種演算法的特色不同,所帶來的效益可能也都是視情況而定。A*演算法算是pathfinding中滿常使用到的,畢竟它能對於各路徑的評估都非常公平,也能依照各種情況因素作彈性的改變,並且也可以做到大範圍的路徑資料評估;A*內涵Dijkstra的方式能用來找出shortest path,又外加像是BFS一般的heuristic information能有效地評估導向目標,雖然說找出一種適合的heuristic function可能不是一件容易的事,不過heuristic function說起來又不是一定要像algorithm一樣必須能被證明是正確的,這種估計其實是包含者人工智慧中對於過去發生過的information所假設的判斷方式,所以才被稱之為經驗法,所以能依照各種實作層面上的資訊來建構出多樣化的heuristic function,並且可以簡單地由f(node) = g(node) + h(node)這樣一個公式來完成計算,的確是很好用的一種演算法。

 

1Iterative Deepening A*,簡稱IDA*,是A*的一種linear-space的版本同樣是使用相同的cost function,對於搜尋f值執行depth-first search並且有個limit值限制,經由較少的overhead,使其更簡化也更快速,可加速heuristic評估functionperformance 

2Simplified Memory A*,簡稱SMA*,讓A*中儲存f值的memory大小有所限制,如此一來總共要search的數量便不會太多,主要就是把f

頁面