مطابقة الأحرف البديلة

في علوم الحاسوب ، تُعدّ خوارزمية مطابقة الأحرف البديلة (المعروفة أيضًا باسم مطابقة الأحرف البديلة ) مفيدةً في مقارنة سلاسل النصوص التي قد تحتوي على صيغة أحرف بديلة . ^{[ 1 ]} تشمل الاستخدامات الشائعة لهذه الخوارزميات واجهات سطر الأوامر ، مثل Bourne shell ^{[ 2 ]} أو سطر أوامر Microsoft Windows ^{[ 3 ]} أو محرر النصوص أو مدير الملفات، بالإضافة إلى واجهات بعض محركات البحث ^{[ 4 ]} وقواعد البيانات. ^{[ 5 ]} تُعدّ مطابقة الأحرف البديلة جزءًا من مشكلة مطابقة التعابير النمطية ومطابقة السلاسل النصية بشكل عام. ^{[ 6 ]}

يقوم مُطابق الأحرف البديلة باختبار نمط الأحرف البديلة p مقابل سلسلة الإدخال s . ويُجري مطابقة مُثبتة ، ويعيد القيمة "صحيح" فقط عندما يُطابق p سلسلة s بالكامل .

يمكن أن يستند النمط إلى أي صيغة شائعة (انظر globbing )، ولكن في نظام التشغيل Windows يميل المبرمجون إلى مناقشة صيغة مبسطة فقط يدعمها وقت تشغيل C الأصلي: ^{[ 7 ] [ 8 ]}

• لم يتم تعريف أي أحرف هروب
• الأحرف البديلة: ?تطابق ظهورًا واحدًا فقط لأي حرف. *تطابق عددًا غير محدود من الظهورات (بما في ذلك الصفر) لأي حرف.

تتناول هذه المقالة بشكل أساسي صياغة المشكلة في نظام ويندوز، ما لم يُذكر خلاف ذلك.

اعتمدت الخوارزميات المبكرة لمطابقة الأحرف البديلة غالبًا على الاستدعاء الذاتي ، لكن هذه التقنية وُجهت إليها انتقاداتٌ تتعلق بالأداء ^{[ 10 ]} والموثوقية ^{[ 8 ]} . وقد حظيت الخوارزميات غير الاستدعائية لمطابقة الأحرف البديلة بشعبيةٍ متزايدة في ضوء هذه الاعتبارات.

تتباين استراتيجيات تنفيذ عملية مطابقة الأنماط بشكل كبير بين الخوارزميات التكرارية وغير التكرارية، كما يتضح من تنوع الخوارزميات المذكورة أدناه. وقد تم تطبيق تقنيات تطوير حالات الاختبار وتحسين الأداء بشكل واضح على بعض الخوارزميات، لا سيما تلك التي طورها منتقدو الخوارزميات التكرارية.

يحدث التكرار عادةً عند المطابقة *عندما يكون هناك المزيد من اللواحق للمطابقة. وهذا شكل من أشكال التراجع ، والذي تقوم به أيضًا بعض أدوات مطابقة التعبيرات النمطية.

• خوارزمية Wildmat لريتش سالز ( تركيب جملة يشبه sh) ^{[ 14 ]}
• خوارزمية فيليب ^{[ 15 ]} وخوارزمية فينيش موروجيسان ^{[ 16 ]}
• خوارزمية مارتن ريختر ^{[ 9 ]} (مطابقة لـ Snippets ومرتبطة بخوارزمية 7-zip) ^{[ 17 ]}
• تطبيقات مكتبة C fnmatch[...] (تدعم مجموعات الأحرف متعددة البايت):
  • مكتبة BSD libc fnmatch الخاصة بـ Guido van Rossum ، ^{[ 18 ]} وهي أيضًا جزء من مكتبة Apple libc ^{[ 19 ]}
  • Glibc fnmatch ^{[ 20 ]}

تتشابه هذه الخوارزميات في شكلها العام. عند استخدام التكرار، تُقسّم الخوارزمية المدخلات إلى سلاسل فرعية، وتعتبر التطابق قائمًا عندما تُعيد إحدى هذه السلاسل الفرعية تطابقًا إيجابيًا. بالنسبة لـ dowild("*X", "abcX")، ستستدعي الخوارزمية بشكل جشع الدوال dowild("X", "abcX")، و dowild("X", "bcX")، dowild("X", "cX")و dowild("X", "X"). عادةً ما تختلف هذه الخوارزميات في أمور أقل أهمية، مثل دعم الميزات، وفي عوامل أكثر أهمية، مثل التحسينات الطفيفة ولكن الفعّالة للغاية. من بين هذه التحسينات:

• إشارة الإيقاف (ABORT) للحماية من التكرار المفرط (لارس ماثيسن، 1991). على الرغم من صحة التكرار البسيط على جميع السلاسل المتبقية (النمط والنص) *والتأكد من أن إحدى السلاسل الفرعية تُرجع تطابقًا إيجابيًا، إلا أن وقت التشغيل يصبح أُسّيًا عند رفض تطابق مع وجود العديد من التطابقات *في النص. قام لارس ماثيسن بتغيير الإرجاع إلى ثلاث فئات: تطابق، عدم تطابق، وإيقاف (ABORT) (لا يوجد تطابق ممكن على الإطلاق للتكرار باستخدام علامة النجمة). تُرجع قيمة الإيقاف (ABORT) عندما يُستهلك النص مبكرًا جدًا أو عندما يفشل تطابق آخر باستخدام علامة النجمة، مما يضمن أداءً خطيًا بالنسبة لعدد علامات النجمة. (يُضاف إلى ذلك أن التعقيد الإجمالي تربيعي لعدد الأحرف المتبقية للمطابقة). ^{[ 14 ]} كما يغطي إيقاف المطابقة الفارغة (wildmatch) في Git/Rsync المدخلات غير الصالحة. ^{[ 21 ]} ويفعل INN uwildmat الجديد الشيء نفسه. ^{[ 22 ]}
• تحسين استخدام علامة النجمة في الاستدعاء الذاتي. يُعدّ هذا التعديل على المطابقة البديلة طفيفًا نسبيًا. وينطبق عندما يرغب الاستدعاء الذاتي في مطابقة "*X" مع "abcX": فعندما تتبع علامة النجمة قيمة حرفية مثل "X"، من الواضح أن المقارنة الأخيرة فقط ذات الأطوال المتساوية هي التي ستُنتج تطابقًا. ^{[ 21 ]} وقد لوحظ هذا سابقًا في uwildmat عام 2000 ^{[ 22 ]} وبشكل ضمني في دالة fnmatch الخاصة بفان روسوم FNM_PATHNAME.

تُعدّ خوارزمية مارتن ريختر استثناءً لهذه القاعدة، على الرغم من أن العملية برمتها مكافئة. عند استخدام *، تستدعي الخوارزمية دالة تكرارية لزيادة أيٍّ من المؤشرين، وفقًا لصياغة البرمجة الديناميكية للمسألة. كما يُمكن تطبيق تقنية "الإجهاض" عليها أيضًا. ^{[ 9 ]} في الأنماط النموذجية (كما اختبرها كانتاتوري)، تكون أبطأ من تطبيقات الاستدعاء الجشع. ^{[ 10 ]}

تُعدّ الخوارزميات التكرارية أسهل في الفهم عمومًا، ومع تعديل ABORT، يكون أداؤها مقبولًا من حيث تعقيد أسوأ الحالات . أما بالنسبة للسلاسل النصية التي لا تحتوي على علامة *، فإنها تستغرق وقتًا خطيًا يتناسب مع حجم السلسلة النصية للمطابقة نظرًا لوجود علاقة ثابتة بين عنصرين.

تم تطوير ما يلي من قبل منتقدي الخوارزميات التكرارية:

• خوارزمية مطابقة الأحرف البديلة لكيرك جيه كراوس ، المستخدمة من قبل شركة IBM ^{[ 8 ] [ 23 ]}
• مجموعة أليساندرو كانتاتوري من خوارزميات مطابقة الأحرف البديلة ^{[ 10 ]}
• ^{[ 17 ]} خوارزمية المطابقة التكرارية لدوجان كورت وخوارزمية المطابقة NFA الأبطأ.
• خوارزمية سايلر غير الصحيحة (تفشل MATCH("da*da*da*", "daaadabadmanda")) ^{[ 24 ]}

ما يلي ليس كذلك:

• خوارزمية جاك هاندي غير الصحيحة ^{[ 25 ]} (تفشل MATCH("*?", "xx"))

تُنفّذ الدوال التكرارية المذكورة أعلاه عملية التراجع عن طريق حفظ مجموعة قديمة من مؤشرات النمط/النص، والعودة إليها في حال فشل التطابق. ووفقًا لكورت، بما أنه لا يلزم سوى تطابق واحد ناجح، فلا حاجة إلا لحفظ مجموعة واحدة من هذه المجموعات. ^{[ 17 ]}

بالإضافة إلى ذلك، يمكن تحويل مشكلة مطابقة الأحرف البديلة إلى مطابقة التعبيرات النمطية باستخدام أسلوب استبدال نصي بسيط . على الرغم من أن مُطابقات التعبيرات النمطية غير التكرارية، مثل بنية طومسون، أقل استخدامًا عمليًا بسبب افتقارها لدعم المراجع الخلفية، فإن مطابقة الأحرف البديلة عمومًا لا تتمتع بمجموعة ميزات غنية مماثلة. (في الواقع، العديد من الخوارزميات المذكورة أعلاه تدعم فقط الأحرف البديلة ?واللاحقة *). يمكن تعديل تطبيق روس كوكس لخوارزمية طومسون NFA بسهولة لهذا الغرض. ^{[ 26 ]} توفر خوارزمية nrgrep القائمة على BDM لغوستافو نافارو تطبيقًا أكثر تبسيطًا مع التركيز على اللواحق الفعالة. ^{[ 27 ]} انظر أيضًا قسم تطبيقات التعبيرات النمطية  .

• مطابقة الأنماط
• حساب الأنماط
• غلوب (برمجة)
• حرف بديل
• قائمة الخوارزميات