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

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

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

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

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

تعريف

تشابه جارو

تشابه جارو $si{m}_j$ من سلسلتين $s_1$ و$s_2$ يكون

$si{m}_j=\{\begin{array}{cc}0& m=0\\ (\frac{m}{\left|s_1\right|}+\frac{m}{\left|s_2\right|}+\frac{m-t}{m})& \end{array}$

حيث:

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

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

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

التشابه بين جارو وينكلر

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

$si{m}_w=si{m}_j+\ell p(1-si{m}_j),$

حيث:

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

مسافة جارو وينكلر $d_w$  تعرف ب$d_w=1-si{m}_w$.

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

العلاقة مع مقاييس مسافة التعديل الأخرى

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

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

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

انظرأيضًا

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

مراجع

• Cohen، W. W.؛ Ravikumar، P.؛ Fienberg، S. E. (2003). "A comparison of string distance metrics for name-matching tasks" (PDF). KDD Workshop on Data Cleaning and Object Consolidation. ج. 3: 73–8. مؤرشف من الأصل (PDF) في 2016-10-18.
• Jaro, M. A. (1989). "Advances in record linkage methodology as applied to the 1985 census of Tampa Florida". Journal of the American Statistical Association. ج. 84 ع. 406: 414–20. DOI:10.1080/01621459.1989.10478785.
• Jaro, M. A. (1995). "Probabilistic linkage of large public health data file". Statistics in Medicine. ج. 14 ع. 5–7: 491–8. DOI:10.1002/sim.4780140510. PMID:7792443.
• Winkler, W. E. (1990). "String Comparator Metrics and Enhanced Decision Rules in the Fellegi-Sunter Model of Record Linkage" (PDF). Proceedings of the Section on Survey Research Methods. American Statistical Association: 354–359. مؤرشف من الأصل (PDF) في 2017-03-03.

• Winkler, W. E. (2006). "Overview of Record Linkage and Current Research Directions" (PDF). Research Report Series, RRS. مؤرشف من الأصل (PDF) في 2017-07-27.

روابط خارجية

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