A hybrid pattern matching algorithm
Issued Date
2015
Copyright Date
2015
Resource Type
Language
eng
File Type
application/pdf
No. of Pages/File Size
xiii, 103 leaves : ill.
Access Rights
open access
Rights
ผลงานนี้เป็นลิขสิทธิ์ของมหาวิทยาลัยมหิดล ขอสงวนไว้สำหรับเพื่อการศึกษาเท่านั้น ต้องอ้างอิงแหล่งที่มา ห้ามดัดแปลงเนื้อหา และห้ามนำไปใช้เพื่อการค้า
Rights Holder(s)
Mahidol University
Bibliographic Citation
Thesis (M.Sc. (Technology of Information System Management))--Mahidol University, 2015
Suggested Citation
Kanumporn Asawasiriroj A hybrid pattern matching algorithm. Thesis (M.Sc. (Technology of Information System Management))--Mahidol University, 2015. Retrieved from: https://repository.li.mahidol.ac.th/handle/20.500.14594/94092
Title
A hybrid pattern matching algorithm
Alternative Title(s)
การพัฒนาอัลกอริทึมการค้นหาสายอักขระ
Author(s)
Abstract
The pattern matching algorithms are widely used in computer science, including information retrieval, text editors, internet search engines, and biological applications. The research proposed a pattern matching algorithm by the combination of three patterns matching algorithms including Boyer-Moore-Horspool, Quick Search, and Raita algorithm, in order to produce the hybrid pattern matching algorithms, given as: Hybrid Max Shift and Reverse Hybrid Max Shift. The proposed algorithms were improved from Boyer-Moore-Horspool and Quick search algorithm by choosing the maximum of shifting value among them and applying with Raita algorithm's order comparing technique. Four datasets were used to test the proposed algorithms, given as English text, genome sequence, protein sequence, and random texts. The best- and worst- case time complexities were also presented in this research. By the experiments, the proposed algorithms were compared to the other existing algorithms. It was shown that the proposed algorithms outperform other existing pattern matching algorithms in terms of shorter average running time.
อัลกอริทึมเปรียบเทียบรูปแบบถือว่ามีบทบาทสำคัญและแพร่หลายในวงการวิทยาศาสตร์คอมพิวเตอร์ ซึ่งอัลกอริทึมนี้สามารถพบได้ในโปรแกรมประยุกต์ต่างๆ เช่น การค้นคืนสารสนเทศ, โปรแกรม Text Editor, โปรแกรมค้นหาบนอินเตอร์เน็ทและโปรแกรมทางชีววิทยา งานวิจัยนี้ได้นำเสนอวิธีการพัฒนาอัลกอริทึมเปรียบเทียบรูปแบบ โดยใช้การผสมผสานข้อดีของอัลกอริทึม 3 อัลกอริทึมเข้าด้วยกัน ได้แก่ Boyer-Moore-Horspool, Quick Search และ Raita อัลกอริทึมที่พัฒนาขึ้นมานี้ให้ชื่อว่า Hybrid Max Shift และ Reverse Hybrid Max Shift ทั้ง 2 อัลกอริทึมนี้จะใช้การเลือกค่าสูงสุดของการเลื่อนจากการคำนวณที่ได้มาจากอัลกอริทึม Boyer-Moore-Horspool และ Quick Search ร่วมกับการใช้ลำดับการเปรียบเทียบของอัลกอริทึม Raita การทดสอบผลจะทดสอบบนกลุ่มข้อมูล 4 ประเภท ได้แก่ ข้อมูลภาษาอังกฤษ, ข้อมูลของสายพันธุกรรม, ข้อมูลของสายโปรตีนและข้อมูลแบบสุ่ม การวิเคราะห์ประสิทธิภาพทั้งกรณีที่ดีที่สุดและแย่ที่สุดก็ได้ถูกนำมาแสดงในงานวิจัยนี้ นอกจากนั้นอัลกอริทึมที่ได้พัฒนานี้ยังถูกนา มาเปรียบเทียบผลการทำงานร่วมกับอัลกอริทึมอื่นๆ ที่เกี่ยวข้องในงานวิจัย ผลที่ได้จากการทดลอง แสดงผลออกมาว่าอัลกอริทึมที่พัฒนามีประสิทธิภาพในการทำงานที่สูงกว่าอัลกอริทึมอื่นๆ ในแง่ของค่าเฉลี่ยเวลาที่ใช้ ในการทำงาน
อัลกอริทึมเปรียบเทียบรูปแบบถือว่ามีบทบาทสำคัญและแพร่หลายในวงการวิทยาศาสตร์คอมพิวเตอร์ ซึ่งอัลกอริทึมนี้สามารถพบได้ในโปรแกรมประยุกต์ต่างๆ เช่น การค้นคืนสารสนเทศ, โปรแกรม Text Editor, โปรแกรมค้นหาบนอินเตอร์เน็ทและโปรแกรมทางชีววิทยา งานวิจัยนี้ได้นำเสนอวิธีการพัฒนาอัลกอริทึมเปรียบเทียบรูปแบบ โดยใช้การผสมผสานข้อดีของอัลกอริทึม 3 อัลกอริทึมเข้าด้วยกัน ได้แก่ Boyer-Moore-Horspool, Quick Search และ Raita อัลกอริทึมที่พัฒนาขึ้นมานี้ให้ชื่อว่า Hybrid Max Shift และ Reverse Hybrid Max Shift ทั้ง 2 อัลกอริทึมนี้จะใช้การเลือกค่าสูงสุดของการเลื่อนจากการคำนวณที่ได้มาจากอัลกอริทึม Boyer-Moore-Horspool และ Quick Search ร่วมกับการใช้ลำดับการเปรียบเทียบของอัลกอริทึม Raita การทดสอบผลจะทดสอบบนกลุ่มข้อมูล 4 ประเภท ได้แก่ ข้อมูลภาษาอังกฤษ, ข้อมูลของสายพันธุกรรม, ข้อมูลของสายโปรตีนและข้อมูลแบบสุ่ม การวิเคราะห์ประสิทธิภาพทั้งกรณีที่ดีที่สุดและแย่ที่สุดก็ได้ถูกนำมาแสดงในงานวิจัยนี้ นอกจากนั้นอัลกอริทึมที่ได้พัฒนานี้ยังถูกนา มาเปรียบเทียบผลการทำงานร่วมกับอัลกอริทึมอื่นๆ ที่เกี่ยวข้องในงานวิจัย ผลที่ได้จากการทดลอง แสดงผลออกมาว่าอัลกอริทึมที่พัฒนามีประสิทธิภาพในการทำงานที่สูงกว่าอัลกอริทึมอื่นๆ ในแง่ของค่าเฉลี่ยเวลาที่ใช้ ในการทำงาน
Description
Technology of Information System Management (Mahidol University 2015)
Degree Name
Master of Science
Degree Level
Master's degree
Degree Department
Faculty of Engineering
Degree Discipline
Technology of Information System Management
Degree Grantor(s)
Mahidol University