Quick-skip search hybrid algorithm for the exact string matching problem
Other Title(s)
خوارزمية (القفز-السريع) الهجينة لحل مشكلة البحث عن تطابق السلسلة التام
Author
Source
Issue
Vol. 2012, Issue 17 (31 Jan. 2012), pp.119-134, 16 p.
Publisher
Publication Date
2012-01-31
Country of Publication
Iraq
No. of Pages
16
Main Subjects
Information Technology and Computer Science
Topics
Abstract AR
مشكلة البحث عن تطابق السلسلة تحتل حجر الزاویة في العدید من مجالات علوم الحاسبات بسبب الدور الأساسي الذي تلعبه في مجال تطبیقات الحاسوب المختلفة.
لذالك، فقد تم اقتراح العدید من الخوارزمیات لحل هذه المشكلة و تطبیقھا في معظم نظم التشغیل و استرجاع المعلومات و محركات البحث على الانترنت و أنظمة حمایة الحاسبات و البحث عن سلسلة معینة من الأحماض الإمینیة في قواعد بیانات سلسلة الجینوم و البروتین.
هناك عدة عوامل مهمة یجب مراعاتها خلال عملیة البحث عن التطابق مثل عدد الرموز التي یجب مقارنتها و عدد مرات التطابق و الوقت المستهلك في عملیة البحث عن سلسلة معینة.
ھذا البحث یقدم خوارزمیة تطابق ھجینة من خلال الجمع بین الخصائص الجیدة لخوارزمیة البحث السریع و خوارزمیة القفز و إیجاد أفضل طریقة لحل مشكلة البحث عن التطابق بسرعة عالیة و كلفة اقل.
حیث تم اختبار الخوارزمیة الھجینة باستخدام أنواع مختلفة من البیانات القیاسیة حیث ان الخوارزمیة الھجینة و فرت نتائج كفوءة و ذات موثوقیة عالیة مقارنة مع الخوارزمیات الأصلیة من حیث توفیر عدد اقل من المقارنات خلال عملیة البحث وعدد اقل من محاولات التطابق عند تطبیق الخوارزمیة الھجینة باستخدام أنماط مختلة الأطوال.
بالإضافة إلى ذلك، تتیح الخوارزمیة الھجینة المقترحة نوعیة أداء أفضل من حیث التعقید في أسوأ و أفضل حالات المقارنة حینما تقارن مع خوارزمیات ھجینة أخرى.
Abstract EN
The string matching problem occupies a corner stone in many computer science fields because of the fundamental role it plays in various computer applications.
Thus, several string matching algorithms have been produced and applied in most operating systems, information retrieval, editors, internet searching engines, firewall interception and searching nucleotide or amino acid sequence patterns in genome and protein sequence databases.
Several important factors are considered during the matching process such as number of character comparisons, number of attempts and the consumed time.
This research proposes a hybrid exact string matching algorithm by combining the good properties of the Quick Search and the Skip Search algorithms to demonstrate and devise a better method to solve the string matching problem with higher speed and lower cost.
The hybrid algorithm was tested using different types of standard data.
The hybrid algorithm provides efficient results and reliability compared with the original algorithms in terms of number of character comparisons and number of attempts when the hybrid algorithm applied with different pattern lengths.
Additionally, the hybrid algorithm produced better quality in performance through providing less time complexity for the worst and best cases comparing with other hybrid algorithms.
American Psychological Association (APA)
Nasir, Mustafa Abd al-Sahib. 2012. Quick-skip search hybrid algorithm for the exact string matching problem. al-Mansour،Vol. 2012, no. 17, pp.119-134.
https://search.emarefa.net/detail/BIM-301387
Modern Language Association (MLA)
Nasir, Mustafa Abd al-Sahib. Quick-skip search hybrid algorithm for the exact string matching problem. al-Mansour No. 17 (2012), pp.119-134.
https://search.emarefa.net/detail/BIM-301387
American Medical Association (AMA)
Nasir, Mustafa Abd al-Sahib. Quick-skip search hybrid algorithm for the exact string matching problem. al-Mansour. 2012. Vol. 2012, no. 17, pp.119-134.
https://search.emarefa.net/detail/BIM-301387
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references : p. 133
Record ID
BIM-301387