TY - JOUR ID - TI - Quick-Skip Search Hybrid Algorithm For The Exact String Matching Problem خوارزمية (القفز- السريع) الهجينة لحل مشكلة البحث عن تطابق السلسة التام AU - Mustafa Abdul Sahib Naser مصطفى عبد الصاحب ناصر PY - 2012 VL - IS - 17 SP - 119 EP - 134 JO - AL-MANSOUR JOURNAL مجلة المنصور SN - 18196489 AB - 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.

مشكلة البحث عن تطابق السلسلة تحتل حجر الزاوية في العديد من مجالات علوم الحاسبات بسبب الدور الأساسي الذي تلعبه في مجال تطبيقات الحاسوب المختلفة. لذالك, فقد تم اقتراح العديد من الخوارزميات لحل هذه المشكلة وتطبيقها في معظم نظم التشغيل واسترجاع المعلومات ومحركات البحث على الانترنيت وانظمة حماية الحاسبات والبحث عن سلسلة معينة من الاحماض الامينية في قواعد بيانات سلسلة الجينوم والبروتين. هناك عدة عوامل مهمة يجب مراعاتها خلال عملية البحث عن التطابق مثل عدد الرموز التي يجب مقارنتها وعدد مرات التطابق والوقت المستهلك في عملية البحث عن سلسلة معينة. هذا البحث يقدم خوارزمية تطابق هجينة من خلال الجمع بين الخصائص الجيدة لخوارزمية البحث السريع و خوارزمية القفز وأيجاد أفضل طريقة لحل مشكلة البحث عن التطابق بسرعة عالية وكلفة اقل. حيث تم اختبار الخوارزمية الهجينة باستخدام أنواع مختلفة من البيانات القياسية حيث ان الخوارزمية الهجينة وفرة نتائج كفوئة وذات موثوقية عالية مقارنة مع الخوارزميات الأصلية من حيث توفير عدد اقل من المقارنات خلال عملية البحث وعدد اقل من محاولات التطابق عند تطبيق الخوارزمية الهجينة بأستخدام انماط مختلة الاطوال. بالإضافة إلى ذلك ، تتيح الخوارزمية الهجينة المقترحة نوعية أداء افضل من حيث التعقيد في أسوأ وافضل حالات المقارنة حينما تقارن مع خوارزميات هجينة اخرى. ER -