演講綱要 1. 簡介資料結構 2. Hashing (赫序) 模式 3. 如何存取小群的文字資料 4. 如何存取大群的文字資料 1. 簡介資料結構 2. Hashing (赫序) 模式 3. 如何存取小群的文字資料 4. 如何存取大群的文字資料 5. 結論與有趣問題大公開
1.簡介資料結構 ■ 資料結構─為方便資料存取的組織型態 Linear Organization (線型結構) (甲) 非序列結構 (sequential list) 35,18,24,12,27,44,33 (乙)序列結構(ordered list) 12,18,24,27,33,35,44 (丙)串列結構(linked list) First
ii) Non-linear Organization (非線型結構) 如： binary tree
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
給了一組關鍵字 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 因為
幾個疑問？ (1) 為什麼 h(ki) = 餘數(C/P(Ki))，可以為“1-1”且“onto” (2) 有沒有很有效的方法可以讓 k={k1,k2, …, kn} P(k1), P(k2 ), …, P(kn ) 而且兩兩互質？ (3) 如何求C？
回答(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
回答(2)： 利用Prime Number Functions 甲：P(x) = x2 – x + 17 for 1 x 16
回答(3)： 其中 且
例：m1=4, m2=5, m3=87, m4=9 M1=5*4*9=315 M2=4*7*9=252 B1=-1 B2=-2 B3=3 B4=4 因此
假設 有沒有很有效的方法求 “b” 此為聯考常考題 Mx+My=1 求 (x,y)?
「今有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二，問物幾何」 (孫武 孫子算經) 亦即求正整數 C，使得 兩個疑問？ C 是否存在 如何求得 C
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
回答(2)： 「三人同行七十稀， 五樹梅花廿一枝， 七子團圓正半月， 除百零五便得知。」 ~(程大位 算法統宗(1593)) 亦即 ~(程大位 算法統宗(1593)) 亦即 70*2 + 21*3 + 15*2 = 140+63+30 = 233 233 / 105 = ■ 餘 23