ما هي مسافة هامنج Hamming Distance؟ من الفكرة إلى التنفيذ والتطبيقات العملية

Hamming Distance أو مسافة هامنج هي مقياس بسيط للاختلاف بين سلسلتين متساويتين في الطول. وهي تساوي عدد المواضع التي تختلف فيها القيم المناظرة بين السلسلتين.

تظهر هذه الفكرة في الخوارزميات، ونظرية الترميز، واكتشاف الأخطاء، والاتصالات، والبيانات الثنائية، وبعض تطبيقات تعلم الآلة.

الفكرة الأساسية

لنقارن:

karolin
kathrin

موضعاً بموضع:

k a r o l i n
k a t h r i n
    ↑ ↑ ↑

هناك ثلاثة اختلافات، لذلك:

Hamming Distance = 3

في التعريف الكلاسيكي يجب أن يكون طول السلسلتين متساوياً.

التعريف

لسلسلتين x وy بطول n:

H(x, y) = Σ [x[i] ≠ y[i]]

كل موضع مختلف يضيف 1 إلى النتيجة.

مثال:

x = 1011101
y = 1001001

يوجد اختلافان، إذن:

H(x, y) = 2

خطوات الخوارزمية

1. التحقق من تساوي الطولين.
2. إنشاء عداد يبدأ من صفر.
3. المرور على جميع المواضع.
4. زيادة العداد عند اختلاف القيم.
5. إرجاع العداد.

function hammingDistance(a, b):
    if length(a) != length(b):
        error

    distance = 0

    for i from 0 to length(a) - 1:
        if a[i] != b[i]:
            distance++

    return distance

تنفيذ TypeScript

function hammingDistance(a: string, b: string): number {
  if (a.length !== b.length) {
    throw new Error("Inputs must have the same length.");
  }

  let distance = 0;

  for (let i = 0; i < a.length; i++) {
    if (a[i] !== b[i]) {
      distance++;
    }
  }

  return distance;
}

التعقيد

Time Complexity: O(n)
Space Complexity: O(1)

نمر على كل عنصر مرة واحدة ولا نحتاج إلى بنية بيانات إضافية.

Hamming Distance للأعداد الثنائية

عند مقارنة عددين صحيحين، يمكن استخدام XOR.

1010
XOR
1110
----
0100

كل بت قيمته 1 في ناتج XOR يعني أن البتين الأصليين مختلفان.

لذلك:

Hamming Distance = عدد البتات 1 في (x XOR y)

function hammingDistanceBits(x: number, y: number): number {
  let value = x ^ y;
  let distance = 0;

  while (value !== 0) {
    value &= value - 1;
    distance++;
  }

  return distance;
}

التعبير value & (value - 1) يحذف بتاً واحداً قيمته 1 في كل دورة.

تطبيقات عملية

اكتشاف وتصحيح الأخطاء

تُستخدم مسافة هامنج في Error Detection وError-Correcting Codes لتقدير مقدار التغيير بين الكلمات الثنائية.

الأنظمة الرقمية والشبكات

يمكن استخدامها لمقارنة أنماط البتات واكتشاف اختلافات في البيانات المنقولة.

الرؤية الحاسوبية

عند تمثيل خصائص الصورة باستخدام Binary Descriptors يمكن مقارنة الخصائص بسرعة بواسطة Hamming Distance.

تعلم الآلة

يمكن استخدامها مع Binary Feature Vectors أو البيانات الفئوية المشفرة.

A = [1, 0, 1, 1, 0]
B = [1, 1, 1, 0, 0]

Distance = 2

Hamming Distance مقابل Levenshtein Distance

Hamming Distance تقارن المواضع المناظرة فقط وتتطلب عادةً أطوالاً متساوية.

أما Levenshtein Distance فتسمح بعمليات:

• Insert
• Delete
• Replace

مثلاً بين cat وcats لا تنطبق مسافة هامنج الكلاسيكية، بينما Levenshtein Distance تساوي 1.

متى نستخدمها؟

استخدم Hamming Distance عندما تكون السلاسل متساوية الطول، ويكون موضع العنصر مهماً، وتريد حساب عدد الاختلافات فقط، خصوصاً مع البيانات الثنائية.

إذا كان الإدراج والحذف مهمين أيضاً، فغالباً تكون Levenshtein Distance أنسب.

سؤال مقابلات شائع

إذا طُلب حساب عدد البتات التي يجب تغييرها لتحويل العدد x إلى y:

1. احسب x XOR y
2. احسب عدد البتات 1

مثال:

1 = 0001
4 = 0100
XOR = 0101

إذن المسافة تساوي 2.

الخلاصة

يمكن تلخيص Hamming Distance بهذه العبارة:

هي عدد المواضع التي تختلف فيها سلسلتان متساويتان في الطول.

بالنسبة إلى السلاسل نستخدم حلقة بسيطة، وبالنسبة إلى الأعداد الثنائية غالباً نستخدم XOR + Bit Counting. وبفضل بساطتها وكفاءتها فهي مفيدة في الخوارزميات والاتصالات والترميز ومعالجة البيانات ومسائل المقابلات التقنية.