خوارزمية مطابقة السلاسل ثنائية الاتجاه

في علوم الحاسوب ، تعد خوارزمية مطابقة السلاسل ثنائية الاتجاه خوارزمية بحث عن السلاسل ، اكتشفها ماكسيم كروشيمور ودومينيك بيرين في عام 1991. ^{[ 1 ]} تأخذ نمطًا بحجم m ، يسمى "إبرة"، وتعالجه مسبقًا في وقت خطي O ( m )، مما ينتج معلومات يمكن استخدامها بعد ذلك للبحث عن الإبرة في أي سلسلة "كومة قش"، وتستغرق وقتًا خطيًا O( n ) فقط حيث n هو طول كومة القش.

يمكن اعتبار الخوارزمية ثنائية الاتجاه مزيجًا من خوارزمية كنوت-موريس-برات الأمامية (KMP) وخوارزمية بوير-مور للبحث عن السلاسل العكسية (BM). وكما هو الحال في هاتين الخوارزميتين، تقوم الخوارزمية ثنائية الاتجاه بمعالجة النمط مسبقًا للعثور على النقاط المتكررة جزئيًا، ثم تحسب "الإزاحات" بناءً عليها، مما يشير إلى موضع "القفز" في كومة القش عند مصادفة حرف معين.

على عكس خوارزميتي BM وKMP، لا تستخدم هذه الخوارزمية سوى مساحة إضافية قدرها O (log m ) لتخزين معلومات حول التكرارات الجزئية: يُقسّم نمط البحث إلى جزأين (تحليله الحرج)، ويُمثّل كل جزء منهما بموقع هذا التقسيم. ولأن هذا العدد أقل من m ، يمكن تمثيله بـ ⌈log₂ m⌉ بت. يُعتبر هذا أحيانًا "قريبًا بما يكفي من O(1) عمليًا"، لأن حجم المؤشر محدود بحجم الذاكرة القابلة للعنونة ؛ أما الحمل الزائد فهو عدد يمكن تخزينه في سجل واحد، ومعاملته على أنه O(1) يُشبه معاملة حجم عداد الحلقة على أنه O(1) بدلًا من لوغاريتم عدد التكرارات. تُجري عملية المطابقة الفعلية 2n − m مقارنة على الأكثر. ^{[ 2 ]}

نشر بريسلاور لاحقًا نسختين محسّنتين تقومان بمقارنات أقل، على حساب تخزين بيانات إضافية حول الإبرة المعالجة مسبقًا: ^{[ 3 ]}

• يُجري الأول على الأكثر n + ⌊( n − m )/2⌋ مقارنة، أي أقل بمقدار ⌈( n − m )/2⌉ من العملية الأصلية. ومع ذلك، يجب عليه تخزين ⌈log_{${\displaystyle \varphi }$}m ⌉ إزاحات إضافية في الإبرة، باستخدام مساحة O(log ² m ).
• أما الثاني فيُكيّفها لتخزين عدد ثابت فقط من هذه الإزاحات، يُرمز له بـ c ، ولكن يجب أن يُجري n + ⌊( 1 ⁄ 2 + ε) * ( n − m )⌋ مقارنة، حيث ε = 1 ⁄ 2 ( F _{c +2} − 1) ⁻¹ = O(${\displaystyle \varphi }$^{− c} ) يؤول إلى الصفر بسرعة أسية مع زيادة c .

تُعتبر هذه الخوارزمية فعّالة إلى حدٍ كبير عمليًا، فهي مُلائمة لذاكرة التخزين المؤقت وتستخدم العديد من العمليات التي يُمكن تنفيذها في إجراءات فرعية مُحسّنة. تستخدمها مكتبات لغة C القياسية glibc و newlib و musl لتنفيذ عائلة دوال السلاسل الفرعية memmem و strstr . ^{[ 4 ] [ 5 ] [ 6 ]} وكما هو الحال مع معظم خوارزميات البحث المتقدمة عن السلاسل، قد يكون التنفيذ البسيط أكثر كفاءة في الحالات الصغيرة نسبيًا؛ ^{[ 7 ]} ويصدق هذا بشكل خاص إذا لم يتم البحث عن النص المطلوب في مجموعات بيانات متعددة، مما يُقلل من تكلفة المعالجة المسبقة.

قبل أن نحدد مفهوم التحليل الحرج، ينبغي أن نحدد ما يلي: ^{[ 1 ]}

• التحليل إلى عوامل هو تجزئة${\displaystyle (u,v)}$من سلسلة نصية x . على سبيل المثال،("Wiki","pedia")هي تحليل لـ"Wikipedia".
• دورة السلسلة x هي عدد صحيح p بحيث تكون جميع الأحرف التي تفصل بينها مسافة p متساوية. بتعبير أدق، x [ i ] = x [ i + p ] صحيحة لأي عدد صحيح 0 < i ≤ len( x ) − p . يُسمح لهذا التعريف أن يكون صحيحًا بشكل بديهي، بحيث يكون لأي كلمة طولها n دورة n . على سبيل المثال، الكلمة المكونة من 8 أحرف لها دورة 6 بالإضافة إلى الدورات البسيطة 8 وما فوق. يُرمز إلى الحد الأدنى لدورة x بـ ⁠"educated"${\displaystyle p(x)}$⁠ .
• تكرار w في ⁠​${\displaystyle (u,v)}$⁠ سلسلة غير فارغة بحيث:
  • w لاحقة لـ u أو u لاحقة لـ w ؛
  • w هي بادئة لـ v أو v هي بادئة لـ w ؛

  بمعنى آخر، يظهر w على جانبي القطع مع احتمال حدوث تجاوز على أي من الجانبين. ومن الأمثلة "an"على ذلك : ("ban","ana")و . يحتوي كل تحليل بشكل بديهي على تكرار واحد على الأقل: السلسلة vu . ^{[ 2 ]}"voca"("a","vocado")

• الفترة المحلية هي طول التكرار في${\displaystyle (u,v)}$. أصغر فترة محلية في${\displaystyle (u,v)}$يُشار إليه بـ${\displaystyle r(u,v)}$بما أن التكرار التافه vu مضمون الوجود وله نفس طول x ، فإننا نرى أن${\displaystyle 1\leq r(u,v)\leq \mathrm {len} (x)}$⁠ .

وأخيرًا، التحليل الحرج هو تحليل${\displaystyle (u,v)}$من x بحيث​​${\displaystyle r(u,v)=p(x)}$إن وجود تحليل حرج مضمون بشكل قاطع. ^{[ 1 ]} بالنسبة لإبرة طولها m في أبجدية مرتبة، يمكن حسابها في 2m مقارنة ، وذلك بحساب اللاحق الأكبر معجميًا من بين لاحقتين أقصى مرتبتين، معرفتين للرتبة ≤ و ≥. ^{[ 6 ]}

تبدأ الخوارزمية بحساب التحليل الحرج للإبرة n كخطوة تمهيدية. تُنتج هذه الخطوة فهرس (نقطة البداية) النصف الأيمن الدوري، ودورة هذا الامتداد. يتبع حساب اللاحقة هنا صياغة المؤلفين. يمكن حسابها بدلاً من ذلك باستخدام خوارزمية دوفال ، وهي أبسط وتستغرق وقتًا خطيًا، ولكنها أبطأ عمليًا. ^{[ 8 ]}

اختصار لعملية الانعكاس. دالة cmp(a, b) إذا كان a > b تُرجع 1، إذا كان a = b تُرجع 0، إذا كان a < b تُرجع -1

دالة maxsuf(n, rev) الطول ← طول(ن) cur_period ← 1 الفترة المعروفة حاليًا. period_test_idx ← 1 مؤشر لاختبار الفترة، 0 < period_test_idx <= cur_period. maxsuf_test_idx ← 0 مؤشر لاختبار الحد الأقصى للقيمة. أكبر من الحد الأقصى. maxsuf_idx ← -1 مؤشر البداية المقترح للحد الأقصى للقيمة

بينما maxsuf_test_idx + period_test_idx < length cmp_val ← cmp( n[maxsuf_test_idx + period_test_idx], n[maxsuf_idx + period_test_idx] ) إذا كان عائدًا cmp_val *= -1 إذا كانت قيمة cmp_val أقل من 0، فإن اللاحقة (maxsuf_test_idx + period_test_idx) هي الأصغر. الفترة هي البادئة الكاملة حتى الآن. maxsuf_test_idx += period_test_idx period_test_idx ← 1 الفترة_الحالية ← أقصى_مؤشر_اختبار_الحد_الأقصى - أقصى_مؤشر_الحد_الأقصى وإلا إذا كانت قيمة المقارنة تساوي صفرًا، فهما متطابقتان، لذا يجب المتابعة. إذا كان مؤشر اختبار الفترة يساوي الفترة الحالية، فقد انتهينا من فحص هذه الفترة من الفترة الحالية. أعد ضبط مؤشر اختبار الفترة. maxsuf_test_idx += cur_period period_test_idx ← 1 آخر period_test_idx += 1 وإلا فإن اللاحقة أكبر. ابدأ من هنا. maxsuf_idx ← maxsuf_test_idx maxsuf_test_idx += 1 الفترة_الحالية ← 1 period_test_idx ← 1 return [maxsuf_idx, cur_period]

دالة crit_fact(n) [idx1, per1] ← maxsuf(n, false) [idx2, per2] ← maxsuf(n, true) إذا كان idx1 > idx2، فأرجع [idx1, per1] ، وإلا فأرجع [idx2, per2].

تتم المقارنة بمطابقة الجانب الأيمن أولاً، ثم الجانب الأيسر إذا تطابق. ويتم تخطي الوقت الخطي باستخدام الفترة.

دالة مطابقة (إبرة، كومة قش) needle_len ← len(needle) haystack_len ← len(haystack) [الطول، الفترة الحالية] ← عامل حاسم (الإبرة) النتائج ← {} مجموعة من النتائج.

طابق اللاحقة. استخدم دالة مكتبة مثل memcmp، أو اكتب حلقة تكرار خاصة بك. إذا كان needle[0] ... needle[length] == needle[length + 1] ... needle[length + cur_period] المباريات ← {} الموضع ← 0 s ← 0

ملاحظة: على الأقل ضع علامة التخطي.