سيم هاش

الموسوعة الحرة

في علوم الحاسوب ، تُعدّ تقنية SimHash أسلوبًا لتقدير مدى تشابه مجموعتين من البيانات بسرعة. يستخدم برنامج زحف جوجل هذه الخوارزمية للعثور على الصفحات المتشابهة تقريبًا. وقد ابتكرها موسى شاريكار . في عام 2021، أعلنت جوجل عن نيتها استخدام هذه الخوارزمية أيضًا في نظام FLoC (التعلم الموحد للمجموعات) الذي أنشأته حديثًا . [ 1 ]

تطبيق

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

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

تعمل هذه الدالة بتقسيم بيانات الإدخال أولاً إلى مجموعة من الخصائص . ثم تُجرى عملية تجزئة لكل خاصية في المجموعة. تُعرَّف التجزئة الإجمالية بطرح عدد التجزئات التي يكون فيها البت غير مُفعَّل (0) من عدد التجزئات التي يكون فيها البت مُفعَّلاً (1) لكل بت في تجزئات الإدخال. بالنسبة لفهارس التجزئة التي يكون فيها الفرق موجبًا، يكون البت مُفعَّلاً. أما بالنسبة للفهارس التي يكون فيها عدد أكبر من البتات غير المُفعَّلة، فإن البت الموجود في ذلك الفهرس في التجزئة النهائية يكون غير مُفعَّل. [ 2 ]

بمعنى آخر، يتم تعيين كل بت من SimHash الخاص بالبيانات إذا كان مجموع البتات عند هذا الفهرس أكبر من مجموع البتات عند هذا الفهرس لكل تجزئة لمجموعة الميزات في تلك البيانات .

حالات الاستخدام

نتيجةً لذلك، ستكون قيم التجزئة (hashes) لبيانات ذات مجموعات خصائص متشابهة أقل اختلافًا من تلك الخاصة ببيانات ذات مجموعات خصائص متباعدة. إضافةً إلى ذلك، "إذا كانت مسافة هامينغ الثنائية (bitwise Hamming distance) لـ SimHash بين عبارتين منخفضة، فإن معامل جاكارد الخاص بهما يكون مرتفعًا." [ 3 ] يتيح هذا تحسين الكفاءة، بما في ذلك فرز أكثر فعالية (عن طريق مقارنة قيم SimHash للكائنات، بدلًا من مقارنة الكائن بأكمله) واكتشاف أسرع للكائنات المتشابهة من خلال فرز قائمة ومقارنة الكائنات المتجاورة بدلًا من حساب O(n^2) لكل مقارنة في القائمة. [ 4 ]

التقييم والمعايير

أجرت جوجل تقييمًا واسع النطاق في عام 2006 [ 5 ] لمقارنة أداء خوارزميتي Minhash وSimhash [ 6 ] . وفي عام 2007، أفادت جوجل باستخدامها خوارزمية Simhash للكشف عن المحتوى المكرر في عمليات الزحف على الويب [ 7 ] ، واستخدامها خوارزميتي Minhash و LSH لتخصيص أخبار جوجل [ 8 ] .

انظر أيضاً

مراجع

  1. ↑ سايفرز، بينيت (2021-03-03). "مشروع جوجل FLoC فكرة سيئة للغاية" . مؤسسة الحدود الإلكترونية . تم الاطلاع عليه بتاريخ 2021-04-13 .
  2. ↑ كيلسي، مات (2009)، "الجزء 3: خوارزمية سيمهاش"، عقل مات كيلسي....
  3. ↑ كيلسي، مات (2009)، "الجزء 3: خوارزمية سيمهاش"، عقل مات كيلسي....
  4. ↑ كيلسي، مات (2009)، "الجزء 3: خوارزمية سيمهاش"، عقل مات كيلسي....
  5. ↑ هينزينجر، مونيكا (2006)، "إيجاد صفحات ويب شبه متطابقة: تقييم واسع النطاق للخوارزميات"، وقائع المؤتمر الدولي السنوي التاسع والعشرين لجمعية ACM SIGIR حول البحث والتطوير في استرجاع المعلومات ، ص 284، doi : 10.1145/1148170.1148222 ، ISBN  978-1595933690، S2CID 207160068 .
  6. ↑ شاريكار، موسى س. (2002)، "تقنيات تقدير التشابه من خوارزميات التقريب"، وقائع الندوة السنوية الرابعة والثلاثين لجمعية آلات الحوسبة حول نظرية الحوسبة ، الصفحات 380-388 ، doi : 10.1145/509907.509965 ، ISBN  978-1581134957، S2CID 4229473 .
  7. ↑ غورميت سينغ، مانكو؛ جاين، أرفيند؛ داس سارما، أنيش (2007)، "الكشف عن النسخ المتطابقة تقريبًا لزحف الويب"، وقائع المؤتمر الدولي السادس عشر للويب العالمي (ملف PDF) ، ص 141، doi : 10.1145/1242572.1242592 ، ISBN  9781595936547.
  8. ↑ داس، أبهيناندان س.؛ داتار، مايور؛ غارغ، أشوتوش؛ راجارام، شيام؛ وآخرون (2007)، "تخصيص أخبار جوجل: ترشيح تعاوني قابل للتطوير عبر الإنترنت"، وقائع المؤتمر الدولي السادس عشر للويب العالمي ، ص 271، doi : 10.1145/1242572.1242610 ، ISBN   9781595936547، S2CID 207163129 .