مسافة هامينغ

تمثل مسافة هامينغ بين سلسلتين متساويتين في الطول عدد المواضع التي تختلف فيها الرموز المناظرة في السلسلتين.

وبعبارة أبسط، فإنها تقيس أقل عدد من عمليات استبدال الرموز اللازمة لتحويل إحدى السلسلتين إلى الأخرى.

إذا كانت لدينا سلسلتان $ s $ و $ t $ طول كل منهما $ n $، فإن مسافة هامينغ $ D_H(s, t) $ تُعرَّف كما يأتي:

$$ D_H(s, t) = \sum_{i=1}^{n} \delta(s_i, t_i) $$

حيث يمثل $ s_i $ و $ t_i $ الرمزين الموجودين في الموضع $ i $ من السلسلتين $ s $ و $ t $، بينما تمثل $ \delta(s_i, t_i) $ دالةً تعطي القيمة 1 إذا كان $ s_i \neq t_i $، وتعطي القيمة 0 إذا كان الرمزان متطابقين.

ولا تُعرَّف مسافة هامينغ إلا بين السلاسل المتساوية في الطول.

مثال عملي
الطوبولوجيا المترية المستحثة بمسافة هامينغ

مثال عملي

لنفترض أن لدينا السلسلتين:

$$ s = \text{"karbon"} $$

$$ t = \text{"carbon"} $$

تبلغ مسافة هامينغ بين $ s $ و $ t $ القيمة 1، لأن الاختلاف الوحيد بينهما يقع في الموضع الأول (k بدلًا من c).

المثال الثاني

يوضح المثال التالي كلمتين باللغة الإنجليزية تفصل بينهما مسافة هامينغ مقدارها 2:

$$ s = \text{"thing"} $$

$$ t = \text{"thank"} $$

يظهر الاختلاف في موضعين:

الحرف الثالث، حيث يقابل الحرف “i” في “thing” الحرف “a” في “thank”، والحرف الخامس، حيث يقابل الحرف “g” الحرف “k”.

الطوبولوجيا المترية المستحثة بمسافة هامينغ

تحدد مسافة هامينغ فضاءً متريًا لأنها تحقق الخصائص الأساسية الآتية لكل السلاسل $ x $ و $ y $ و $ z $ المتساوية في الطول:

عدم السلبية
$$ D_H(x, y) \geq 0 \quad \text{and} \quad D_H(x, y) = 0 \ \text{if and only if} \ x = y $$

بما أن مسافة هامينغ تمثل عدد مواضع الاختلاف، فلا يمكن أن تكون سالبة. كما أنها تساوي صفرًا إذا وفقط إذا كانت السلسلتان متطابقتين تمامًا.
التناظر
$$ D_H(x, y) = D_H(y, x) $$

لا تعتمد مسافة هامينغ على ترتيب السلسلتين، ولذلك فإن المسافة من $ x $ إلى $ y $ تساوي دائمًا المسافة من $ y $ إلى $ x $.
متباينة المثلث
$$ D_H(x, z) \leq D_H(x, y) + D_H(y, z) $$

لا يمكن أن تتجاوز المسافة المباشرة بين $ x $ و $ z $ مجموع المسافتين بين $ x $ و $ y $، وبين $ y $ و $ z $. ويرجع ذلك إلى أن كل اختلاف بين $ x $ و $ z $ يظهر بالضرورة في واحدة على الأقل من هاتين المقارنتين.

وبما أن مسافة هامينغ تحقق هذه الخصائص، فإنها تُعرّف فضاءً متريًا على مجموعة جميع السلاسل ذات الطول الثابت.

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

لذلك، يمكن استخدام مسافة هامينغ أيضًا لتعريف طوبولوجيا مترية.

إذا كانت $ x $ سلسلة طولها $ n $، وكان $ r $ نصف قطر، فإن الكرة المفتوحة $ B $ ذات المركز $ x $ تُعرَّف بأنها مجموعة جميع السلاسل التي تقل مسافة هامينغ بينها وبين $ x $ عن $ r $.

$$ B(x, r) = \{y \mid D_H(x, y) < r\}. $$

وتشكّل هذه الكرات المفتوحة أساس الطوبولوجيا المترية، لأن أي مجموعة مفتوحة يمكن الحصول عليها من اتحاد عدد كيفي من هذه الكرات.

ملاحظة. بما أن مجموعة جميع السلاسل الثنائية، أو سلاسل الرموز، ذات الطول الثابت $ n $ مجموعة منتهية، فإن الطوبولوجيا المستحثة بمسافة هامينغ تكون طوبولوجيا متقطعة. ويعني ذلك أن كل سلسلة تمثل في الوقت نفسه مجموعة مفتوحة ومجموعة مغلقة. ويحدث ذلك لأنه يمكن اختيار نصف قطر صغير جدًا، مثل $ r = 1 $، بحيث تحتوي الكرة المفتوحة على سلسلة واحدة فقط.

وعليه، فإن مسافة هامينغ تولد طوبولوجيا مترية تكون، بالنسبة إلى أي مجموعة منتهية من السلاسل المتساوية في الطول، طوبولوجيا متقطعة.

مثال

لننظر إلى المجموعة التالية من السلاسل الثنائية ذات الطول ثلاثة:

$$ X = \{000, 001, 011, 110, 111 \} $$

لإنشاء الطوبولوجيا المستحثة عند نصف القطر $ r = 2 $، نحسب الكرات المفتوحة حول كل سلسلة:

$$ B(x, r) = \{y \mid D_H(x, y) < 2 \} $$

أي إن كل كرة مفتوحة تضم السلاسل التي تختلف عن مركزها في موضع واحد على الأكثر.

الكرة المفتوحة ذات المركز $ 000 $: $$ B(000,2)=\{000,001\} $$ تختلف السلسلة $001$ عن $000$ في موضع واحد فقط.
الكرة المفتوحة ذات المركز $ 001 $: $$ B(001,2)=\{001,000,011\} $$ تختلف السلسلتان $000$ و$011$ عن $001$ في موضع واحد.
الكرة المفتوحة ذات المركز $ 011 $: $$ B(011,2)=\{011,001,111\} $$ تختلف السلسلتان $001$ و$111$ عن $011$ في موضع واحد.
الكرة المفتوحة ذات المركز $ 110 $: $$ B(110,2)=\{110,111\} $$ تختلف السلسلة $111$ عن $110$ في موضع واحد فقط.
الكرة المفتوحة ذات المركز $ 111 $: $$ B(111,2)=\{111,011,110\} $$ تختلف السلسلتان $011$ و$110$ عن $111$ في موضع واحد.

وتكوّن هذه الكرات المفتوحة أساس الطوبولوجيا المستحثة، إذ يمكن الحصول على جميع المجموعات المفتوحة الأخرى من خلال اتحادها.

ملاحظة. عندما يكون $ r = 2 $، فإن الشرط $ D_H(x,y)<2 $ يعني أن السلسلتين تختلفان في موضع واحد على الأكثر، لأن الكرة المفتوحة لا تشمل عناصر الحد. أما إذا أردنا تعريف كرة مغلقة، فنستخدم المتباينة:

$$ C(x,r)=\{y \mid D_H(x,y)\le 2\} $$

فعلى سبيل المثال، يكون اتحاد الكرتين المفتوحتين:

$$ B(000,2)\cup B(110,2) $$

وبما أن:

$$ B(000,2)=\{000,001\} $$

$$ B(110,2)=\{110,111\} $$

فإن اتحادهما يساوي:

$$ B(000,2)\cup B(110,2)=\{000,001,110,111\} $$

ومن ثم، فإن المجموعة $ \{000,001,110,111\} $ تعد أيضًا مجموعة مفتوحة في هذه الطوبولوجيا.

وبوجه عام، تتكون جميع المجموعات المفتوحة في هذه الطوبولوجيا من اتحادات الكرات المفتوحة المعرفة بواسطة مسافة هامينغ.

وتستمر العملية بالطريقة نفسها مع بقية السلاسل.