การวิเคราะห์เปรียบเทียบกลวิธีในการลดความยาวของ URL

ประเสริฐ วิชชุโอภาส

Please use this identifier to cite or link to this item: https://cuir.car.chula.ac.th/handle/123456789/65999

Title:	การวิเคราะห์เปรียบเทียบกลวิธีในการลดความยาวของ URL
Other Titles:	Comparative study of algorithms for reducing URL length
Authors:	ประเสริฐ วิชชุโอภาส
Advisors:	ณัฐวุฒิ หนูไพโรจน์
Other author:	จุฬาลงกรณ์มหาวิทยาลัย. คณะวิศวกรรมศาสตร์
Advisor's Email:	natawut.n@chula.ac.th
Subjects:	เวิลด์ไวด์เว็บ ยูอาร์แอล การเข้ารหัสลับข้อมูล อัลกอริทึม World Wide Web URL ‪(Universal resource locator)‬ Data encryption ‪(Computer science)‬ Algorithms
Issue Date:	2544
Publisher:	จุฬาลงกรณ์มหาวิทยาลัย
Abstract:	การทำงานของพร็อกซี่แคชเกี่ยวข้องกับการประมวลผลยูอาร์แอลเป็นจำนวนมาก ทั้งการระบุว่าข้อมูลที่เครื่องลูกข่ายต้องการอยู่ในแคชของตนหรือไม่ และการสอบถามข้อมูลระหว่างพร็อกซี่แคชด้วยกัน ล้วนแล้วแต่ ต้องประมวลผลยูอาร์แอลทั้งสิ้น ถ้าหากสามารถเพิ่มประสิทธิภาพโดยรวมของการประมวลผลยูอาร์แอลก็จะเป็นการเพิ่มประสิทธิภาพพร็อกซี่แคชด้วยเช่นกัน จากการศึกษาในเบื้องต้นพบว่า การเข้ารหัสยูอาร์แอลที่ใช้งานใน การทำงานพร็อกชี่แคช มีความต้องการคุณสมปติของวิธีการเข้ารหัสที่แตกต่างกัน พร็อกซี่แคชในปัจจุบันมีการใช้วิธีการเข้ารหัสที่ชื่อว่า MD5 ในการย่อยูอาร์แอลก่อนนำไปประมวลผลหรือสอบถามข้อมูลระหว่างพร็อกซี่แคช ด้วยกัน แต่ยังไม่มีงานวิจัยใดที่ทำการศึกษาวิธีการเข้ารหัสอื่น ๆ ดังนั้นในงานวิจัยนี้จึงได้เลือกวิธีการเข้ารหัสแบบต่าง ๆ ขึ้นมาจำนวนหนึ่ง ทำการเข้ารหัสยูอาร์แอลเพื่อเปรียบเทียบ เวลาที่ใช้ในการเข้ารหัส ความยาวรหัส และ ปริมาณการชนกันของรหัส ของแต่ละวิธีการ และนำมาใช้ในการเสนอแนะแนวทางในการเลือกใช้วิธีการเข้ารหัสยูอาร์แอลที่มีประสิทธิภาพ สำหรับพร็อกซี่แคช ข้อมูลยูอาร์แอลที่ใช้ในการทดสอบนำมาจากข้อมูลการใช้เว็บของจุฬาลงกรณ์มหาวิทยาลัย ข้อมูลนี้ถูกนำมาเข้ารหัสด้วยวิธีการเข้ารหัสต่าง ๆ ซึ่งเลือกขึ้นมา 12 วิธีการ โดยวิธีการเข้ารหัสเหล่านั้นเป็นที่รู้จักกันดี รวมทั้งวิธีการ MD5 ผลการทดลองทำให้ทราบว่าวิธีการเข้ารหัสที่มีความซับซ้อนน้อยใช้เวลาในการเข้ารหัสน้อยกว่าวิธีการที่มีความซับซ้อนมากและมีโอกาสที่เกิดการชนของรหัสมากกว่า วิธีการเข้ารหัสที่มีขนาดของรหัสที่สั้นมีโอกาสเกิดการชนกันของผลลัพธ์มากกว่า วิธีการที่เลือกมาทดสอบในการวิจัยไม่มีวิธีการเข้ารหัสใดที่ดีที่สุดการพิจารณาว่าวิธีการใดเหมาะสมจะพิจารณาจากความต้องการของแอปพลิเคชั่นเป็นหลัก โดยแอปพลิเคชั่นที่ต้องการความเร็วในการเข้ารหัสและรหัสที่สั้น ควรเลือกวิธีการ CRC -16, Digit Analysis method, Folding method แอปพลิเคชั่นที่ต้องการความเร็วในการเข้ารหัสและไม่ต้องการให้มีการชนกันของรหัสเลย ควรเลือกวิธีการในกลุ่ม MD หรือ Huffman Coding แต่ถ้าหากยอมให้มีการชนกันของรหัสได้บ้าง ควรเลือกวิธีการ CRC-32 หรือ Folding method และสำหรับแอปพลิเคชั่นที่ต้องการรหัสที่สั้นและมีปริมาณการชนกันของรหัสน้อย ควรเลือกวิธีการ CRC-32, Division method และ Folding method นอกจากนี้ บังพบว่าวิธีการ CRC-32 และ Folding method ใช้เวลาในการเข้ารหัสน้อย รหัสที่ได้มีขนาดสั้น และมีการชนกันของรหัสน้อยมาก จึงอาจปรับปรุงโดยการรวมวิธีการทั้งสองเข้าด้วยกันเพื่อหาวิธีการใหม่ที่มีประสิทธิภาพมากขึ้นได้
Other Abstract:	Webs Proxy Caches usually process large amounts of URLs to identify if requested pages are in the caches and to communicate among shared Web Caches. Improving URL processing can greatly enhance the performance of Web Caches. The preliminary study of this thesis shows that the requirements of URL processing for web caching application are varied. Typically, many Web Proxy Caches use a hashing function, MD5, to encode URL. However, there is no study of a suitable algorithm for URL. In this study, we choose some well-known encoding or hashing algorithms, use them to encode URL in web access log and compare their encoding time, encoded length, and number of collisions. The comparison of the result is used as a guideline to select suitable URL encoding algorithm. In our experiment, 12 well known coding and hashing algorithms include MD5 are selected to encode the cacheable URL from web access log of Office of Information Technology, Chulalongkorn University. We found that complicated algorithms use more time to encode URL but their encoded keys have less number of collisions. In addition, we found that algorithms that generate shorter length encoded keys lead to more number of collisions. Our studies indicate that there is no algorithm that can be considered the best for every Web Cache Applications. The algorithm that is suitable for each Web Cache Application is determined by their core requirements. For example, applications that speed and key length are critical should use CRC-16, Digit Analysis method, or Folding method as their main coding algorithm. Applications that require no collision and focus on fast speed should use a MD2, MD4, or MD5 algorithm. However, if some collisions are allowed, CRC-32 and Folding method are suitable. For the applications that require short length key and tolerate some collisions, CRC-32, Division method and Folding method should be selected. We also found that the CRC-32 and Folding method are faster than other algorithms and their encoded keys have very low collision rates. Therefor, combining these 2 algorithms may create a new powerful algorithm for Web Cache Application.
Description:	วิทยานิพนธ์ (วท.ม.)--จุฬาลงกรณ์มหาวิทยาลัย, 2544
Degree Name:	วิทยาศาสตรมหาบัณฑิต
Degree Level:	ปริญญาโท
Degree Discipline:	วิทยาศาสตร์คอมพิวเตอร์
URI:	http://cuir.car.chula.ac.th/handle/123456789/65999
ISBN:	9740303811
Type:	Thesis
Appears in Collections:	Eng - Theses

Files in This Item:

File	Size	Format
Prasert_vi_front_p.pdf	779.5 kB	Adobe PDF	View/Open
Prasert_vi_ch1_p.pdf	849.65 kB	Adobe PDF	View/Open
Prasert_vi_ch2_p.pdf	780.45 kB	Adobe PDF	View/Open
Prasert_vi_ch3_p.pdf	818.93 kB	Adobe PDF	View/Open
Prasert_vi_ch4_p.pdf	1.36 MB	Adobe PDF	View/Open
Prasert_vi_ch5_p.pdf	1.31 MB	Adobe PDF	View/Open
Prasert_vi_ch6_p.pdf	662.24 kB	Adobe PDF	View/Open
Prasert_vi_back_p.pdf	779.7 kB	Adobe PDF	View/Open

Show full item record