مسافة جارو وينكلر
قبل الخوض في التفاصيل، في علم الحاسوب والإحصاءات، فإن مسافة جارو وينكلر هي مقياس سلسلة يقيس مسافة التعديل بين سلسلتين. هو البديل الذي اقترحه في سنة 1990 من قبل وليام إي وينكلر من مقياس مسافة جارو (1989، ماثيو أ. جارو). وفيما يلي تفاصيل أوسع عن ذلك.
وعلى صعيد آخر، تستعمل مسافة جارو وينكلر مقياس البادئة الذي يعطي تقييمات أكثر ملاءمة للسلاسل التي تتطابق منذ البداية مع طول البادئة المحدد .
ومن ناحية أخرى، كلما قلت المسافة بين جارو وينكلر عن السلسلتين، كلما كانت الخيوط أكثر تشابهًا. يتم تطبيع النتيجة بحيث يعني 0 تطابقًا تامًا و1 يعني عدم وجود تشابه. تشابه جارو وينكلر هو الانعكاس، (1 - مسافة جارو وينكلر).
تشابه جارو
وعلى صعيد آخر، على الرغم من أنه غالبًا ما يشار إليه بمقياس دالة المسافة، فإن مسافة جارو وينكلر ليست مقياسًا بالمعنى الرياضي لهذا المصطلح لأنها لا تطيع متباينة المثلث.
تعريف
تشابه جارو من سلسلتين و يكون
وفي السياق ذاته، كل حرف مقارنة مع جميع الحروف المطابقة في . عدد الأحرف المطابقة (ولكن ترتيب تسلسل مختلف) مقسومًا على 2 يحدد عدد عمليات النقل. مثلًا، عند مقارنة CRATE بـ TRACE، فقط الأحرف "R" "A" "E" هي الأحرف المتطابقة، أي m = 3. على الرغم من ظهور "C" "T" في كلا السلسلتين، إلا أنهما أبعد من 1 (نتيجة ). لذلك، t = 0. في DwAyNE مقابل DuANE، تكون الحروف المطابقة بالفعل بنفس الترتيب D-A-N-E، لذلك لا حاجة إلى عمليات تبديل.
وفي هذا الصدد، حرفان من و على التوالي، تعتبر مطابقة فقط إذا كانت متطابقة وليست بعيدة عن الأحرف بصرف النظر.
- حيث:
- هو طول السلسلة .
- هو عدد الأحرف المطابقة (انظر أدناه).
- هو نصف عدد عمليات النقل (انظر أدناه).
التشابه بين جارو وينكلر
مسافة جارو وينكلر تعرف ب.
من جهة ثانية، يستعمل تشابه جارو وينكلر مقياس البادئة الذي يعطي تقييمات أكثر ملاءمة للسلاسل التي تتطابق من البداية لطول بادئة محدد . نظرا لسلسلتين و، تشابههم بين جارو وينكلر يكون:
ومن ناحية أخرى، على الرغم من أنه غالبًا ما يشار إليه بمقياس المسافة، فإن مسافة جارو وينكلر ليست مقياسًا بالمعنى الرياضي لهذا المصطلح لأنها لا تطيع متباينة المثلث. كما أن مسافة جارو وينكلر لا ترضي بديهية الهوية .
في هذا الإطار، هو عامل تحجيم ثابت لمدى تعديل النتيجة لأعلى للحصول على بادئات مشتركة. يجب ألا يتجاوز 0.25، وإلا يمكن أن يصبح التشابه أكبر من 1. القيمة القياسية لهذا الثابت في عمل وينكلر هي .
- حيث:
- هو تشابه جارو للسلاسل و.
- هو طول البادئة الشائعة في بداية السلسلة بحد أقصى أربعة أحرف.
العلاقة مع مقاييس مسافة التعديل الأخرى
- انظرأيضًا
- ربط السجلات
- إحصاء السكان
- هوامش
- مراجع
وفي هذا الصدد، هناك مقاييس شائعة أخرى لمسافة التعديل، والتي يتم حسابها باستخدام مجموعة مختلفة من عمليات التحرير المسموح بها. مثلًا:
علاوةً على ذلك، عادة ما يتم تعريف مسافة التعديل كمقياس قابل للمعلمة محسوب مع مجموعة محددة من عمليات التنعديل المسموح بها، ويتم تعيين تكلفة لكل عملية (ربما لا نهائية). يتم تعميم هذا كذلك عن طريق خوارزميات التراصف التسلسلي للحمض النووي مثل خوارزمية سميث - ووترمان، والتي تجعل تكلفة العملية تعتمد على مكان تطبيقها.
- تسمح مسافة ليفينشتين بالحذف والإدخال والاستبدال.
- تسمح مسافة Damerau-Levenshtein بالإدخال والحذف والاستبدال ونقل حرفين متجاورين.
- أطول تسلسل مشترك (LCS) تسمح فقط بالإدخال والحذف، وليس الاستبدال.
ومن ناحية أخرى، تسمح مسافة هامينج بالاستبدال فقط، وبالتالي، فهي لا تنطبق إلا على سلاسل بنفس الطول.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟