مطابقة السلاسل التقريبية

في علوم الحاسوب ، تُعرف مطابقة السلاسل التقريبية (والتي تُسمى أيضًا البحث عن السلاسل الضبابية ) بأنها تقنية لإيجاد سلاسل نصية تُطابق نمطًا معينًا تقريبًا (بدلًا من مطابقته تمامًا). وتنقسم مشكلة مطابقة السلاسل التقريبية عادةً إلى مشكلتين فرعيتين: إيجاد تطابقات تقريبية للسلاسل الفرعية داخل سلسلة نصية معينة، وإيجاد سلاسل نصية في القاموس تُطابق النمط تقريبًا.

تُقاس درجة التطابق بعدد العمليات الأساسية اللازمة لتحويل السلسلة إلى تطابق تام. يُسمى هذا العدد مسافة التحرير بين السلسلة والنمط. العمليات الأساسية الشائعة هي: ^{[ 1 ]}

• إدخال: cot → co a t
• حذف: co a t → cot
• الاستبدال: co a t → co s t

يمكن تعميم هذه العمليات الثلاث كأشكال من الاستبدال عن طريق إضافة حرف فارغ (يرمز إليه هنا بـ *) أينما تم حذف حرف أو إدراجه:

• الإدخال: co * t → co a t
• الحذف: co a t → co * t
• الاستبدال: co a t → co s t

تعتبر بعض أدوات المطابقة التقريبية عملية التبديل ، التي يتم فيها تبديل موضع حرفين في السلسلة، عملية أولية. ^{[ 1 ]}

• تبديل: co st → co ts

تفرض مُطابقات التقريب المختلفة قيودًا مُتباينة. تستخدم بعض المُطابقات تكلفة إجمالية غير مُرجّحة، أي إجمالي عدد العمليات الأساسية اللازمة لتحويل التطابق إلى النمط. على سبيل المثال، إذا كان النمط هو "coil" ، فإن "foil" يختلف باستبدال واحد، و "coils" بإضافة واحدة، و "oil" بحذف واحد، و "foal" باستبدالين. إذا تم احتساب جميع العمليات كوحدة تكلفة واحدة، وتم ضبط الحد الأقصى على واحد، فسيتم احتساب "foil" و "coils " و "oil" كتطابقات، بينما لن يتم احتساب "foal" .

تُحدد بعض أدوات المطابقة عدد العمليات لكل نوع على حدة، بينما تُحدد أخرى التكلفة الإجمالية مع السماح بتخصيص أوزان مختلفة للعمليات المختلفة. كما تسمح بعض أدوات المطابقة بتعيين حدود وأوزان منفصلة لمجموعات محددة في النمط.

أحد التعريفات الممكنة لمشكلة مطابقة السلاسل التقريبية هو التالي: بالنظر إلى سلسلة نمطية${\displaystyle P=p_{1}p_{2}...p_{m}}$وسلسلة نصية${\displaystyle T=t_{1}t_{2}\dots t_{n}}$ابحث عن سلسلة فرعية${\displaystyle T_{j',j}=t_{j'}\dots t_{j}}$في T ، والتي من بين جميع السلاسل الفرعية لـ T ، لديها أصغر مسافة تحرير إلى النمط P.

يتمثل أحد الأساليب المباشرة في حساب مسافة التحرير إلى P لجميع السلاسل الفرعية من T ، ثم اختيار السلسلة الفرعية ذات أقصر مسافة. ومع ذلك، فإن وقت تشغيل هذه الخوارزمية سيكون ^O ( n³m ) . 

يعتمد الحل الأفضل، الذي اقترحه سيلرز ^{[ 2 ]} ، على البرمجة الديناميكية . ويستخدم صياغة بديلة للمشكلة: لكل موضع j في النص T ولكل موضع i في النمط P ، احسب أقصر مسافة تحرير بين الأحرف i الأولى من النمط.${\displaystyle P_{i}}$وأي سلسلة فرعية${\displaystyle T_{j',j}}$من T التي تنتهي عند الموضع j .

لكل موضع j في النص T ، ولكل موضع i في النمط P ، نمر على جميع السلاسل الفرعية من T التي تنتهي عند الموضع j ، ونحدد أيها يمتلك أقصر مسافة تحرير إلى الأحرف i الأولى من النمط P. نكتب هذه المسافة الدنيا على شكل E ( i , j ). بعد حساب E ( i , j ) لجميع قيم i و j ، يمكننا بسهولة إيجاد حل للمسألة الأصلية: إنها السلسلة الفرعية التي تكون فيها E ( m , j ) في أدنى قيمة لها ( حيث m هو طول النمط P ).   

إن حساب E ( m , j ) يشبه إلى حد كبير حساب مسافة التحرير بين سلسلتين نصيتين. في الواقع، يمكننا استخدام خوارزمية حساب مسافة ليفنشتاين لحساب E ( m , j )، والفرق الوحيد هو أنه يجب علينا تهيئة الصف الأول بالأصفار، وحفظ مسار الحساب، أي ما إذا كنا قد استخدمنا E ( i - 1, j ) أو E( i , j - 1) أو E ( i - 1, j - 1) في حساب E ( i , j ).           

في المصفوفة التي تحتوي على قيم E ( x , y )، نختار القيمة الدنيا في الصف الأخير، ولتكن E ( x ₂ , y ₂ )، ونتبع مسار الحساب عكسيًا، وصولًا إلى رقم الصف 0. إذا كان الحقل الذي وصلنا إليه هو E (0, y ₁ )، فإن T [ y ₁ + 1] ... T [ y ₂ ] هي سلسلة فرعية من T ذات أقصر مسافة تحرير إلى النمط P.       

يستغرق حساب مصفوفة E ( x , y ) وقتًا قدره O ( mn ) باستخدام خوارزمية البرمجة الديناميكية، بينما تستغرق مرحلة العمل العكسي وقتًا قدره O ( n + m ).   

توجد أيضًا خوارزميات يعتمد وقت تشغيلها على k ، وهو حد أقصى لمسافة التحرير المطلوبة، وتكون هذه الخوارزميات أفضل عندما تكون قيمة k صغيرة نسبيًا مقارنةً بطول السلاسل النصية. في عام 1989، قدم لاندو وفيشكين ...${\displaystyle O(nk)}$تعتمد هذه الخوارزمية على مصفوفة البرمجة الديناميكية المذكورة أعلاه، ولكنها تملأها بطريقة ذكية على طول الأقطار. [ ^{3 ] في} عام 2002، وباستخدام خوارزمية أكثر تعقيدًا، حقق كول وهاريهاران مستوى تعقيد قدره${\displaystyle O({\frac {k^{4}}{m}}+n+m)}$لاحظ أن هذا يكون أفضل عندما${\displaystyle k^{3}\ll nm}$[ ^{4 ]​}

تُعرَّف مشكلة مطابقة الأنماط مع k من حالات عدم التطابق المتخصصة بمنع عمليات الإضافة والحذف في مطابقة النمط مع النص. وبالتالي، يجب ألا تتجاوز مسافة هامينغ للنمط إلى الجزء المقابل من النص k . وقد تم حل هذه المشكلة بتعقيد زمني قدره${\displaystyle O(n{\sqrt {k\log k}})}$[ ^{5 ]​}

من الأفكار الحديثة الأخرى الربط القائم على التشابه. عند مطابقة قواعد البيانات مع كميات هائلة من البيانات، لا يمكن لخوارزمية البرمجة الديناميكية، التي تستغرق وقتًا قدره O ( mn )، أن تعمل بكفاءة ضمن وقت محدود. لذا، تكمن الفكرة في تقليل عدد أزواج السلاسل النصية المرشحة، بدلًا من حساب تشابه جميع أزواج السلاسل. تعتمد الخوارزميات الشائعة الاستخدام على التحقق من التصفية، والتجزئة، والتجزئة الحساسة للموقع (LSH)، وخوارزميات البحث ، وغيرها من الخوارزميات الجشعة والتقريبية. صُممت معظم هذه الخوارزميات لتتوافق مع إطار عمل معين (مثل MapReduce) لإجراء العمليات الحسابية المتزامنة.

تُصنّف خوارزميات مطابقة السلاسل التقريبية تقليديًا إلى فئتين: خوارزميات متصلة بالإنترنت وخوارزميات غير متصلة بالإنترنت. في الخوارزميات المتصلة بالإنترنت، يُمكن معالجة النمط قبل البحث، بينما لا يُمكن معالجة النص نفسه. بعبارة أخرى، تُجري التقنيات المتصلة بالإنترنت البحث دون فهرس. اقترح كلٌّ من واغنر وفيشر ^{[ 6 ]} وسيلرز ^{[ 2 ]} خوارزميات مبكرة للمطابقة التقريبية المتصلة بالإنترنت. تعتمد كلتا الخوارزميتين على البرمجة الديناميكية ، لكنهما تحلان مشكلات مختلفة. تبحث خوارزمية سيلرز تقريبًا عن سلسلة فرعية في النص، بينما تحسب خوارزمية واغنر وفيشر مسافة ليفنشتاين ، وهي مناسبة فقط للبحث التقريبي في القاموس.

شهدت تقنيات البحث عبر الإنترنت تحسينات متكررة. ولعلّ أبرز هذه التحسينات خوارزمية bitap (المعروفة أيضًا بخوارزمية "الإزاحة-أو" أو "الإزاحة-و")، والتي تتميز بكفاءتها العالية في التعامل مع سلاسل الأنماط القصيرة نسبيًا. تُعدّ خوارزمية bitap أساس أداة البحث agrep في نظام يونكس . وقد أجرى جي. نافارو مراجعة شاملة لخوارزميات البحث عبر الإنترنت. ^{[ 7 ]}

على الرغم من وجود تقنيات سريعة جدًا للبحث عبر الإنترنت، إلا أن أداءها على البيانات الضخمة ضعيف. تُسرّع معالجة النصوص أو فهرستها عملية البحث بشكل كبير. وقد طُرحت اليوم مجموعة متنوعة من خوارزميات الفهرسة، من بينها أشجار اللواحق ^{[ 8 ]} ، والأشجار المترية ^{[ 9 ]} ، وطرق n -gram ^{[ 10 ] [ 11 ]} . وقدّم نافارو وآخرون [10] دراسة تفصيلية لتقنيات الفهرسة التي تُمكّن من العثور على أي سلسلة فرعية في النص. ^{كما قدّم بويتسوف [ 12 ] دراسة حسابية لطرق القاموس (أي الطرق التي تسمح بالعثور على} جميع كلمات القاموس التي تُطابق نمط البحث تقريبًا) ^.

تشمل التطبيقات الشائعة للمطابقة التقريبية التدقيق الإملائي . ^{[ 8 ]} ومع توفر كميات هائلة من بيانات الحمض النووي، أصبحت مطابقة تسلسلات النيوكليوتيدات تطبيقًا مهمًا. ^{[ 1 ]} كما تُستخدم المطابقة التقريبية في تصفية البريد العشوائي . ^{[ 8 ]} ويُعد ربط السجلات تطبيقًا شائعًا حيث تتم مطابقة السجلات من قاعدتي بيانات مختلفتين.

لا يمكن استخدام مطابقة السلاسل النصية لمعظم البيانات الثنائية، مثل الصور والموسيقى. فهي تتطلب خوارزميات مختلفة، مثل البصمة الصوتية .

fzfتُستخدم أداة سطر الأوامر الشائعة غالبًا لدمج البحث التقريبي عن السلاسل النصية في تطبيقات سطر الأوامر المختلفة. ^{[ 13 ]}

• مشروع فلامنجو
• مشروع معالجة استعلامات التشابه بكفاءة مع التطورات الحديثة في مطابقة السلاسل التقريبية بناءً على عتبة مسافة التحرير.
• مشروع StringMetric عبارة عن مكتبة Scala لمقاييس السلاسل النصية والخوارزميات الصوتية.
• مشروع Natural هو مكتبة لمعالجة اللغة الطبيعية مكتوبة بلغة جافا سكريبت، وتتضمن تطبيقات لمقاييس السلاسل النصية الشائعة.