跳到主要內容

臺灣博碩士論文加值系統

(100.28.132.102) 您好!臺灣時間:2024/06/21 22:17
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:林祐賢
論文名稱:植於中國餘數定理之最佳完美文字赫序函數設計研究
論文名稱(外文):The Study of Letter-Oriented Minimal Perfect Hashing Functions Design Based on the Chinese Remainder Theorem
指導教授:謝建成謝建成引用關係
學位類別:碩士
校院名稱:佛光人文社會學院
系所名稱:資訊學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2003
畢業學年度:91
語文別:中文
論文頁數:63
中文關鍵詞:中國餘數定理最佳完美赫序函數台語拼音
外文關鍵詞:Chinese Remainder TheoremMinimal Perfect Hashing FunctionsTaiwanese Phonetic Transcription
相關次數:
  • 被引用被引用:0
  • 點閱點閱:170
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
本論文探討利用分析關鍵字字集的特性,來改進植於中國餘數定理(Chinese Remainder Theorem)之最佳完美文字赫序函數(Letter-Oriented Minimal Perfect Hashing Function)的設計。有別於傳統文字赫序法則使用經驗法則(Heuristic)來選擇關鍵字集的字元配對,本論文提出一種較為系統化的方法,藉由簡單的資料分析程序,可以對於大量的關鍵字字集,解析出其可利用之特性,並據以設計出簡單有效的最佳完美赫序函數。這些資料分析的方法實施在3028台語拼音組,不僅只需要使用到9個質數,就可以設計出植於中國餘數定理之最佳完美赫序函數,其中常數C的最大值其位數只有9位數,同時其負載係數亦可提高到0.71,此為利用中國餘數定理設計出之赫序函數中負載係數最高者。

摘 要 II
目 錄 III
圖目錄 IV
表目錄 V
第一章 赫序函數介紹 1
第一節 赫序函數的應用與分類 3
第二節 赫序函數的效能分析 9
第二章 文獻探討 17
第一節 適於處理文字資料的赫序函數法則 17
第二節 植於中國餘數定理之最佳完美赫序函數 33
第三章 建構處理台語拼音系統之最佳完美赫序函數 44
第一節 台語拼音系統 44
第二節 處理台語拼音系統之最佳完美赫序函數設計 46
第三節 關鍵字字集資料分析 47
第四節 建構赫序函數 52
第五節 台語拼音組實驗結果分析 55
第四章 結論 58
參考文獻 59
附錄A 注音符號系統之赫序函數參數表 A-1
附錄B 台語拼音系統之赫序表及參數值 B-1

1. 沈進富,「彙音寶鑑」,文藝學社,二十五版,民國68年。
2. Anderson, M. R. and Anderson, M. G., “Comments on Perfect Hashing Functions: A Single Proble Retrieving Method for Static Sets,” communications of the ACM, Vol. 22, No. 2, pp. 104-105, Feb. 1979.
3. Aho, A. V., Hopcroft, J. E., and Ullman, J. D., The Design and Analysis of Computer Algoritms. Addison-Wesley Pub. Co., Reading, Mass., 1974.
4. Atici, M., Magliveras, S. S., Stinson, D. R., and Wei W. -D. “Some Recursive Constructions for Perfect Hash Families.” Journal of Combinatorial Designs 4, pp. 353-363, 1996.
5. Alon, Tardos, “Linear Hash Functions”, Journal of the ACM, Vol. 46, No. 5, pp. 667-683, Sep. 1999.
6. Atici, M., Magliveras, S. S., Stinson, D. R. and Wei W. -D. “Some Recursive Constructions for Perfect Hash Families.” Journal of Combinatorial Designs 4, pp. 353-363, 1996.
7. Alon, Tardos, “Linear Hash Functions”, Journal of the ACM, Vol. 46, No. 5, pp. 667-683, Sep. 1999.
8. Alon, Dietzfelbinger, Miltersen, Petrank and Tardos, “Is Linear Hashing Good?” Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing, pp. 465 - 474, May 1997.
9. Brian, M.D. and Tarp, A.L., “Perfect Hashing Using Sparse Matrix Packing,” Information Systems, Vol. 5, No. 3, pp. 281-290, 1990.
10. Chang, C.C. “An Ordered Minimal Perfect Hashing Scheme Based Upon Euler’s Theorem,” Information Sciences, Vol. 32, No. 3, pp. 165-172, 1984.
11. Chang, C.C. ”The Study of an Ordered Minimal Perfect Hashing Scheme,” Communications of the Association for Computing Machinery, 27(4), pp. 384-387, Apr. 1984.
12. Chang, C.C. ”The Study of a Letter Oriented Minimal Perfect Hashing Scheme,” The Proceedings of Data Organization, Kyoto, Japan, pp. 61-65, May, 1985.
13. Chang, C.C. and Shieh, J.C. “On The Design of Letter Oriented Minimal Perfect Hashing Functions,” Journal of the Chinese Institute of Engineers, 8(3), pp. 285-297, 1985.
14. Chang, C.C. and Shieh, J.C., ”A Fast Algorithm for Constructing Reciprocal Hashing Functions,” Proceedings of International Symposium on New Directions in Computing, IEEE, Trondheim, Norway, pp. 232-236, Aug. 1985.
15. Chang, C.C. and Lin, C.H., “On the Difficulty of Construction Perfect Hashing Functions,” Proceedings of 1986 IEEE International Symposium on Information Theory, Kobe, Japan, Jun 1986.
16. Chang, C.C. and Shieh, J.C. “On the Design of Ordered Minimal Perfect Hashing Functions,” Proceedings of 2nd International Conference on Data Engineering, IEEE, Los Angeles, U. S. A., pp. 112-115, Feb. 1986.
17. Chang, C.C., Lin, J.F., and Jan, J.K., ”A Chinese Data Compression Scheme,” Journal of Computers, Vol. 2, No. 2, Summer 1989, pp. 1-9 (invited paper), 1989.
18. Chang, C.C., Jan, J.K., and Lin, J.F., “A Chinese Syllables Compression Scheme Based upon Perfect Hashing,” Journal of Computers, Vol. 2, No. 3, pp. 1-17, Sep. 1990.
19. Chang, C.C. and Lee, C.F., ”Retrieving Chinese Characters Using DAYI Chinese Input Method,” Proceedings of 17th International Conference on Computer Processing of Oriental Languages, Hong Kong, pp. 387-391, Apr. 1997.
20. Chang, C.C. and Hong, K.L. “Signature-Based Chinese Character Retrieval Schemes Using DAYI Input Method,” Proceedings of the 1998 ICS Workshop on Software Engineering and Database System, Dec. 1998, Tainan, Taiwan, R.O.C., pp. 109-114, 1998.
21. Chang, C.C., Chen, T.S., and Lin. Y, “An Efficient Accessing Technique of Chinese Characters Using Boshiamy Chinese Input System,” International Workshop on Information Retrieval for Asian Languages (IRAL'2000), Hong Kong, pp. 61-67, Sep. 2000.
22. Chang, C.C. and Wu, H.C. ”A Fast Chinese Characters Accessing Technique Using Mandarin Phonetic Transcriptions,” International Journal of Pattern Recognition and Artificial Intelligence, 2(1), pp. 105-137, 1986.
23. Chang, C.C. and Wu, H.C., “A New Chinese Characters Retrieval Scheme Based upon Chinese Radical Spatial Relationships,” Journal of Electrical Engineering, Vol. 34, No. 2, pp. 93-98, Apr. 1990.
24. Chang, C.C. and Wu, H.C., “A Letter-oriented Perfect Hashing Scheme Based Upon Sparse Table Compress,” Software: Practice and Experience, Vol. 21, No. 1, pp. 35-49, Jan. 1991.
25. Chen, C.Y. and Chang, C.C. “On the Design of Bucket Address Hashing Files for Concurrent Information Retrieval Among Two Disks,” Proceedings of the ICS 1988, Taipei, Taiwan, pp. 89-93, Dec. 1988.
26. Chichelli, R.J. “Minimal Perfect Hash Functions Made Simple,” Communications of ACM, Vol.23, No.1, pp. 17-19, 1980.
27. Czech, Zbigniew J., Havas, George and Majewski, Bohdan S. “An optimal algorithm for generating minimal perfect hash functions,” Information Processing Letters 43, pp. 257-264, 1992.
28. Czech, Zbigniew J., Havas, George and Majewski, Bohdan S. “Perfect Hashing,” Theoretical Computer Science 182, pp. 1-143, 1997.
29. Edward I., Heath, L.S., Chen, Qi Fan, Daoud and Amjad M. “Practical Minimal Perfect Hash Functions for Large Database,” Communications of ACM, Vo1.35, No.1, pp. 105-121, Jan. 1992.
30. Fox, Edward A., Chen, Qi Fan and Heath, Lenwood S. “A Faster Algorithm for Constructing Minimal Perfect Hash Functions”, Proceedings of the Fifteenth Annual International ACM SIGIR conference on Research and Development in Information Retrieval, pp. 266-273, Jun. 1992.
31. Gettys, Thomas, “Generating Perfect Hash Functions,” Dr. Dobb's Journal: Software Tools for the Professional Programmer, Vol. 26 Issue 2, pp. 151-152, Feb, 2001.
32. Goldreich, Oded and Wigderson, Avi, “On the Circuit Complexity of Perfect Hashing,” Electronic Colloquium on Computational Complexity, Vol. 3, No. 41, 1996.
33. Haitsma, J. and Kalker T. “A Highly Robust Audio Fingerprinting System”, 3rd International Conference on Music Information Retrieval ISMIR 2002 (http://ismir2002.ircam.fr/), Paris, France, Oct. 13-17, 2002.
34. Havas, George and Majewski, Bohdan S. “Optimal Algorithms for Minimal Perfect Hashing,” Technical Report 234, The University of Queensland, 1992.
35. Havas, George and Majewski, Bohdan S. “Graph Theoretic Obstacles to Perfect Hashing,” Congressus Numerantium 98, pp. 81-93, 1993.
36. Havas, George and Majewski, Bohdan S., Wormald, Nicholas C. and Czech, Zbigniew J. “Graphs, Hypergraphs and Hashing”, Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science 790, pp. 153-165, 1994.
37. Jan, J.K. and Chang, C.C. “Addressing for Letter-ordered Keys,” Journal of the Chinese Institute of Engineers, Vol. 11, No. 3, pp. 279-284, 1988.
38. Jan, J.K. and Chang, C.C., ”Toward the Compression of Chinese Phonetic Textual Files,” Proceedings of 1989 International Conference on Computer Processing of Chinese and Oriental Languages, Changsha, Hunan, China, pp. 393-397, 1989.
39. Knuth, D. E., The Art of Computer Programming, Vol. 3 published as 2nd ed, v. 3. Sorting and Searching, Reading, Mass., Addison-Wesley, c1998.
40. Majewski, Bohdan S., Wormald, Nicholas C., Havas, George and Czech, Zbigniew J., “A Family of Perfect Hashing Methods,” Computer Journal, 39, pp. 547-554, 1996.
41. Park, J.S., Chen, M.S. and Yu, P.S., “Using A Hash-based Method With Transaction Trimming for Mining Association Rules,” IEEE Transactions on Knowledge and Data Engineering, Vol. 9, No. 5, pp. 812-825, 1997.
42. Pearson, Peter K., “Fast Hashing of Variable-Length Text Strings, “ Communications of the ACM, Vol. 33 Issu. 6, pp. 677-680, Jun. 1990.
43. Preiss, Bruno R., Data Structures and Algorithms with Object-Oriented Design Patterns in Java, New York, John Wiley, 2000.
44. Ramakrishna, M. V., “Hashing Practice-Analysis of Hashing and Universal Hashing,” Proceedings of the 1988 ACM SIGMOD International Conference on Management of Data, pp. 191-199, Jun. 1988.
45. Rei Safavi-Naini and Wang Huaxiong, “New Constructions for Multicast re-keying Schemes Using Perfect Hash Families,” Proceedings of the 7th ACM Conference on Computer and Communications Security, pp. 228-234, Nov. 2000.
46. Sager, T., “A Polynomial Time Generator for Minimal Perfect Hashing Functions,” Communications of ACM, Vol. 28, No. 5, pp. 523-523, May 1985.
47. Sartaj, Sahni, Data Structures, Algorithms, and Applications in Java, Chapter 8, Boston, McGraw-Hill, 2000.
48. Shieh, J.C., “General Extensions of Minimal Perfect Hashing Schemes for Large Letter-Oriented Data Sets,” Proc. 8th International Symposium Information Management, pp. 776-782, 1997.
49. Sprugnoli, R., “Perfect Hashing Functions: An Aingle Probe Retrieving Methods for Static Sets,” Communications of ACM, Vol. 20, No. 11, pp. 841-850, Nov. 1977.
50. Tarjan, R.E. and Yao, A.C.C., “Sorting a Asparse Table,” Communications of the ACM, Vol. 22, No. 11, pp. 606-611, Nov. 1979.
51. Thorup, Mikkel, “Even Strongly Universal Hashing is Pretty Fast,” Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文