| published |
| DOI
http://dx.doi.org/10.25098/2.2.33 |
Ammar Waysi AlTuhafi
Computer Science Department , Cihan university- Sulaimaniya , Kurdistan Region , Iraq
Received : 4-1-2018 Revised: 3-3-2018
Accepted : 4-3-2018 Published :31-12-2018
Abstract
String matching became important application nowadays, the increasing of database such as websites, document, DNA, etc., leads to the urgent needs for string matching; string matching has many applications such as DNA, protein matching, internet search engine, all these types of application of string matching, beside the huge amount of database lead to increase the need to fast and efficient string matching algorithms. This study is about comparing among most well-known string matching algorithms; it focuses on four types of string matching algorithms, each one of them working in a different way. The four are tested with four types of data; ASCII (256 character), English alphabet (26 characters), DNA (4 character), and protein (20 character), with different pattern length (100, 50, 20, 10, 5) results shown based on number of comparisons and time.
Keywords: string matching, DNA, Protein, Boyer-Moore, Knuth-Morris-Pratt, Rabin-Karp.
پوخته
:هاوتاكردنی زنجیره‌كان بووه به یه‌كێك له به‌رنامه گرنگه‌كانی رۆژگار , زیادكردنی داتابه‌یس وه‌ك ماڵپه‌ری ئه‌لیكترۆنی و به‌ڵگه‌كان و ترشی ناوه‌كی … هتد , ئه‌م هه‌موو فاكته‌رانه وای خواستووه ب به‌رنامه‌یه‌كی هاوتاكردنی زنجیره‌كان , زۆر به‌رنامه هه‌یه كه له‌م بواره‌دا به‌كاردێت وه‌ك هاوتاكردنی ترشی ناوه‌كی و هاوتاكردنی پرۆتین و بزوێنه‌ری گه‌ران له‌سه‌ر ئینته‌رنێت , سه‌رجه‌می ئه‌م به‌رنامانه مامه‌ڵه ده‌كات له‌گه‌ڵ برێكی زۆر له زانیاری كه وا ده‌خوازێت ئه‌لگۆریتمی خێرا و به‌توانا هه‌بێت بۆ هاوتاكردنی زنجیره‌كان. ئه‌م تویژینه‌وه‌یه بنیات نراوه له‌سه‌ر به‌راوردكردنی چوار له هه‌ره به‌ناوبانگترین ئه‌لگۆریتم له‌بواری هاوتا كردنی زانیاری , هه‌ر یه‌ك له‌و زنجیرانه كارده‌كات به رێگای جیاواز وه هه‌ریه‌ك له‌م ئه‌لگۆریتمانه پشكنین بۆ كراوه له‌سه‌ر چوار جۆری داتای جیاواز , ئه‌وانیش پیته‌كانی زمانی ئینگلیزی (26 پیت) و زمانی ASCII (256 پیت) و پیتی ترشی ناوه‌كی ( 4پیت) وه پرۆتین (20 پیت) , له‌گه‌ل به‌كارهینانیزنجیره‌ی جیاواز له دریژیدا ( 5, 10, 20, 50, 100) ئه‌نجامه‌كان بنیات نراوه له‌سه‌ر كۆمه‌ڵێك به‌راوردكردن و كاتی خایه‌نراو بۆ ئه‌و پرۆسه‌یه.
الملخص
مطابقة السلاسل اصبحت من التطبيقات المهمة هذه الايام, زيادة قواعد البيانات مثل مواقع صفحات الانترنيت والوثائق والحمض النووي .. الخ, كل هذه العوامل ادت الى الحاجة الملحة الى تطبيقات تطابق السلاسل, هناك العديد من التطبيقات المستخدمة في هذا المجال مثل مطابقة الحمض النووي ومطابقة البروتين ومحركات البحث في الانتريت، كل هذه التطبيفات تتعامل مع كمية هائلة من البيانات مما يؤدي الى الحاجة الى خوازيمات سريعة وكفوءة لمطابقة السلاسل. هذه الدراسة مبنية على المقارنة بين اربعة من اشهر الخوارزيمات في مطابقة السلاسل، كل سلسلة من هذه السلاسل تعمل وفق طريقة مختلفة، هذه الخوارزميات الاربعة تم فحص كل واحدة منهم على اربع انواع من البيانات وهي: احرف اللغة الانكليزية (26 حرف) و احرف ال ASCII (256 حرف) والحمض النووي (4 حرف) واخيراً البروتين (20 احرف)، مع استخدام اطوال مختلفة للسلسة (5, 10, 20, 50, 100) النتائج كانت معتمدة على عدد المقارانات والوقت المستغرق في عملية المقارنة.
.
REFERENCES
[1] D. Gussfield, “Algorithms on strings, trees, and sequences,” Computer Science and Computional Biology (Cambrigde, 1999), 1997.
[2] G. Navarro, “A guided tour to approximate string matching,” ACM computing surveys (CSUR), vol. 33, pp. 31-88, 2001.
[3] C. C.-T. Lecroq. (1997, 22/5). EXACT STRING MATCHING ALGORITHMS. Available: http://www-igm.univ-mlv.fr/~lecroq/string/
[4] Oracle. (2016). Comparison: Exact String Match. Available: http://www.oracle.com/webfolder/technetwork/data-quality/edqhelp/Content/processor_library/matching/comparisons/exact_string_match.htm
[5] D. E. Knuth, et al., “Fast pattern matching in strings,” SIAM journal on computing, vol. 6, pp. 323-350, 1977.
[6] K. A. Berman and J. L. Paul, Algorithms: sequential, parallel, and distributed: Course Technology Ptr, 2005.
[7] R. S. Boyer and J. S. Moore, “A fast string searching algorithm,” Communications of the ACM, vol. 20, pp. 762-772, 1977.
[8] C. Charras and T. Lecroq, Handbook of exact string matching algorithms: King’s College, 2004.
.
