مسافة جارو وينكلر

في علم الحاسوب والإحصاءات، فإن** مسافة جارو وينكلر** هي مقياس سلسلة يقيس مسافة التعديل بين سلسلتين. هو البديل الذي اقترحه في عام 1990 من قبل وليام إي وينكلر من مقياس مسافة جارو (1989، ماثيو أ. جارو).

تستخدم مسافة جارو وينكلر مقياس البادئة p الذي يعطي تقييمات أكثر ملاءمة للسلاسل التي تتطابق منذ البداية مع طول البادئة المحدد \ell.

كلما قلت المسافة بين جارو وينكلر عن السلسلتين، كلما كانت الخيوط أكثر تشابهًا. يتم تطبيع النتيجة بحيث يعني 0 تطابقًا تامًا و1 يعني عدم وجود تشابه. تشابه جارو وينكلر هو الانعكاس، (1 - مسافة جارو وينكلر).

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

## تعريف

### تشابه جارو
تشابه جارو sim_j من سلسلتين s_1 وs_2 يكون

sim_j = \left\{

\begin{array}{l l}
  0 & \text{if }m = 0\\
  \frac{1}{3}\left(\frac{m} + \frac{m} + \frac{m-t}{m}\right) & \text{otherwise} \end{array} \right.

حيث:

* |s_i| هو طول السلسلة s_i.
* m هو عدد الأحرف المطابقة (انظر أدناه).
* t هو نصف عدد عمليات النقل (انظر أدناه).

حرفان من s_1 وs_2 على التوالي، تعتبر مطابقة فقط إذا كانت متطابقة وليست بعيدة عن \left\lfloor\frac{\max(|s_1|,|s_2|)}{2}\right\rfloor-1 الأحرف بصرف النظر.

كل حرف s_1 مقارنة مع جميع الحروف المطابقة في s_2. عدد الأحرف المطابقة (ولكن ترتيب تسلسل مختلف) مقسومًا على 2 يحدد عدد عمليات النقل. على سبيل المثال، عند مقارنة CRATE بـ TRACE، فقط الأحرف "R" "A" "E" هي الأحرف المتطابقة، أي m = 3. على الرغم من ظهور "C" "T" في كلا السلسلتين، إلا أنهما أبعد من 1 (نتيجة \lfloor\tfrac{5}{2}\rfloor - 1). لذلك، t = 0. في DwAyNE مقابل DuANE، تكون الحروف المطابقة بالفعل بنفس الترتيب D-A-N-E، لذلك لا حاجة إلى عمليات تبديل.

### التشابه بين جارو وينكلر
يستخدم تشابه جارو وينكلر مقياس البادئة p الذي يعطي تقييمات أكثر ملاءمة للسلاسل التي تتطابق من البداية لطول بادئة محدد \ell. نظرا لسلسلتين s_1 وs_2، تشابههم بين جارو وينكلر sim_w يكون:

sim_w = sim_j + \ell p (1 - sim_j),

حيث:

* sim_j  هو تشابه جارو للسلاسل s_1  وs_2.
* \ell هو طول البادئة الشائعة في بداية السلسلة بحد أقصى أربعة أحرف.
* p هو عامل تحجيم ثابت لمدى تعديل النتيجة لأعلى للحصول على بادئات مشتركة. p  يجب ألا يتجاوز 0.25، وإلا يمكن أن يصبح التشابه أكبر من 1. القيمة القياسية لهذا الثابت في عمل وينكلر هي p = 0.1.

مسافة جارو وينكلر d_w  تعرف بd_w = 1 - sim_w.

على الرغم من أنه غالبًا ما يشار إليه بمقياس المسافة، فإن مسافة جارو وينكلر ليست مقياسًا بالمعنى الرياضي لهذا المصطلح لأنها لا تطيع متباينة المثلث. كما أن مسافة جارو وينكلر لا ترضي بديهية الهوية  d(x,y)=0 \leftrightarrow x = y.

## العلاقة مع مقاييس مسافة التعديل الأخرى
هناك مقاييس شائعة أخرى لمسافة التعديل، والتي يتم حسابها باستخدام مجموعة مختلفة من عمليات التحرير المسموح بها. على سبيل المثال:

* تسمح مسافة ليفينشتين بالحذف والإدخال والاستبدال.
* تسمح مسافة Damerau-Levenshtein بالإدخال والحذف والاستبدال ونقل حرفين متجاورين.
* أطول تسلسل مشترك (LCS) تسمح فقط بالإدخال والحذف، وليس الاستبدال.
* تسمح مسافة هامينج بالاستبدال فقط، وبالتالي، فهي لا تنطبق إلا على سلاسل بنفس الطول.

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

## انظرأيضًا

* ربط السجلات
* إحصاء السكان

## هوامش

## مراجع

* 
* 
* 
* 
* 

## روابط خارجية

* strcmp.c - Original C implementation by the author of the algorithm

تصنيف:علم الحاسوب
تصنيف:مقاييس التشابه والمسافة