演講綱要 1. 簡介資料結構 2. Hashing (赫序) 模式 3. 如何存取小群的文字資料 4. 如何存取大群的文字資料

Presentation on theme: "演講綱要 1. 簡介資料結構 2. Hashing (赫序) 模式 3. 如何存取小群的文字資料 4. 如何存取大群的文字資料"— Presentation transcript:

1 演講綱要 1. 簡介資料結構 2. Hashing (赫序) 模式 3. 如何存取小群的文字資料 4. 如何存取大群的文字資料
1. 簡介資料結構 2. Hashing (赫序) 模式 3. 如何存取小群的文字資料 4. 如何存取大群的文字資料 5. 結論與有趣問題大公開

2 1.簡介資料結構 ■ 資料結構─為方便資料存取的組織型態 Linear Organization (線型結構)
　 (甲) 非序列結構 (sequential list) 35,18,24,12,27,44,33 (乙)序列結構(ordered list) 12,18,24,27,33,35,44 (丙)串列結構(linked list) First

3 ii) Non-linear Organization (非線型結構)
如： binary tree

4 2.Hashing (赫序模式) The set of keys ■ Hashing function ■ Collision
INFO A record K1 K2 K3 … Kn The set of keys ■ Hashing function ■ Collision ■ Perfect Hashing ■ Minimal Perfect Hashing

5 給了一組關鍵字 k={k1,k2, …, kn} H(Ki) = 餘數 (C/P(Ki)) 條件： P(Ki) 與 P(Kj) 兩兩互質
H(k)=餘數 (1417/P(k)) P 20, 33, 149, 238 4 5 7 9 1 2 3 4 因為

6 幾個疑問？ (1) 為什麼 h(ki) = 餘數(C/P(Ki))，可以為“1-1”且“onto” (2) 有沒有很有效的方法可以讓
k={k1,k2, …, kn}  P(k1), P(k2 ), …, P(kn ) 而且兩兩互質？ (3) 如何求C？

7 回答(1)：中國餘式定理 Let r1,r2, …, rn be integers an integer C s.t.
If (mi, mj) = 1 Ex: m1=4 m2=5 m3=7 m4=9 r1=1 r2=2 r3=3 r4=4

8 回答(2)： 利用Prime Number Functions 甲：P(x) = x2 – x + 17 for 1 x 16

9 回答(3)： 其中 且

10 例：m1=4, m2=5, m3=87, m4=9 M1=5*4*9=315 M2=4*7*9=252
B1= B2= B3= B4=4 因此

11 假設 有沒有很有效的方法求 “b” 此為聯考常考題 Mx+My=1 求 (x,y)?

12 「今有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二，問物幾何」
(孫武 孫子算經) 亦即求正整數 C，使得 兩個疑問？ C 是否存在 如何求得 C

13 Let r1,r2, …, rn be integers 回答 (1)： 孫子定理(又稱中國餘數定理) an integer C s.t.
If (mi, mj) = 1 Ex: 令m1=3，m2=5，m3=7，且令r1=2，r2=3，r3=2

14 回答(2)： 「三人同行七十稀， 五樹梅花廿一枝， 七子團圓正半月， 除百零五便得知。」 ~(程大位 算法統宗(1593)) 亦即
~(程大位 算法統宗(1593)) 亦即 70*2 + 21*3 + 15*2 = = 233 233 / 105 = ■ 餘 23