مسافة هامينغ

مسافة هامينغ

معلومات عامة

الطبيعة	دالة المسافة — مفهوم رياضي
فرع من	edit distance — كمية لا بعدية
المخترع	ريتشارد هامينغ
تاريخ الاختراع	1950
سمّي باسم	ريتشارد هامينغ
وصفه	IEC 80000-13:2008 Quantities and units — Part 13: Information science and technology

مسافة هامينغ هو مصطلح في نظرية المعلومات يُستخدم للدلالة على عدد المواضع التي تختلف فيها الرموز المتناظرة بين سلسلتين أو متجهين متساويي الطول، أو بمعنى آخر، هي المسافة التي تقيس الحد الأدنى لعدد عمليات الاستبدال اللازمة لتغيير سلسلة إلى أخرى، أو ما يعادلها، أو تقيس الحد الأدنى لعدد الأخطاء التي كان من الممكن أن تُحوّل سلسلة إلى أخرى.

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

التعريف

تُعرف مسافة هامينغ بين سلسلتين متساويتين من الرموز بأنها تساوي عدد المواضع التي تختلف فيها الرموز المتناظرة. يُمكن أن تكون هذه الرموز عبارة عن أحرف، أو بتات، أو أرقامًا عشرية، من بين احتمالات أخرى. فعلى سبيل المثال:

• مسافة هامينغ بين "karolin" و"kathrin" تساوي 3.
• مسافة هامينغ بين "karolin" و"kerstin" تساوي 3.
• مسافة هامينغ بين "kathrin" و"kerstin" تساوي 4.
• مسافة هامينغ بين 0000 و1111 تساوي 4.
• مسافة هامينغ بين 2173896 و2233796 تساوي 3.

التاريخ

قدم عالم الرياضيات وعالم الحاسوب الأمريكي ريتشارد هامينغ هذا المفهوم لأول مرة عام 1950 في بحثه الأساسي حول ترميز هامينغ، وأكواد اكتشاف الأخطاء وتصحيحها.

التطبيقات

يُستخدم مفهوم مسافة هامينغ وتحليل وزن هامينغ للبتات في العديد من التخصصات مثل علوم الحاسوب والاتّصالات، وبالأخص في نظرية المعلومات، ونظرية الترميز، والتعمية. في مجال الاتصالات، تُستخدم مسافة هامينغ لحساب عدد البتات المقلوبة في كلمة ثنائية ذات طول ثابت كتقدير للخطأ، ولذلك يُطلق عليها أحيانًا مسافة الإشارة. بالنسبة لسلاسل q-ary على أبجدية بحجم q ≥ 2، تُطبّق مسافة هامينغ في حالة القناة المتماثلة q-ary، بينما تُستخدم مسافة لي في مفاتيح إزاحة الطور أو بشكل عام في القنوات المعرضة لأخطاء التزامن لأن مسافة لي تمتلك نسبة خطأ ±1. إذا كانت 𝑞 = 2 أو 𝑞 = 3، فإن المسافتين تتطابقان لأن أي زوج من العناصر من 𝑍 / 2 𝑍 أو 𝑍 / 3 𝑍 يختلف بمقدار 1، ولكن تختلف المسافات بالنسبة لقيم 𝑞 الأكبر.

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

مثال

توضح الدالة التالية، والمكتوبة بلغة بايثون 3، مسافة هامينغ بين سلسلتين نصيتين:

def hamming_distance(string1: str, string2: str) -> int:
    """Return the Hamming distance between two strings."""
    if len(string1) != len(string2):
        raise ValueError("Strings must be of equal length.")
    dist_counter = 0
    for n in range(len(string1)):
        if string1[n] != string2[n]:
            dist_counter += 1
    return dist_counter

أو بصورة مختصرة:

sum(char1 != char2 for char1, char2 in zip(string1, string2, strict=True))

تحسب الدالة hamming_distance()، التي تم تنفيذها باستخدام لغة بايثون 3، مسافة هامينج بين سلسلتين (أو كائنات قابلة للتكرار أخرى) متساويتين في الطول عن طريق إنشاء تسلسل من القيم المنطقية التي تشير إلى عدم التطابق والتطابقات بين المواضع المقابلة في المدخلين، ثم جمع التسلسل مع القيم True وFalse، والتي يتم تفسيرها على أنها واحد وصفر على التوالي.

def hamming_distance(s1: str, s2: str) -> int:
    """Return the Hamming distance between equal-length sequences."""
    if len(s1) != len(s2):
        raise ValueError("Undefined for sequences of unequal length.")
    return sum(char1 != char2 for char1, char2 in zip(s1, s2))

حيث تدمج دالة zip() مجموعتين متساويتين في الطول في أزواج. ستحسب دالة C التالية مسافة هامينغ لعددين صحيحين (يُعتبران قيمتين ثنائيتين، أي تسلسلين من البتات). يتناسب وقت تشغيل هذا الإجراء مع مسافة هامينغ وليس مع عدد البتات في المُدخلات. تحسب الدالة القيمة المطلقة أو لكل بت من المُدخلين، ثم تجد وزن هامينغ للنتيجة (عدد البتات غير الصفرية) باستخدام خوارزمية ويغنر (1960) التي تعثر على البت غير الصفري ذي الترتيب الأدنى وتُزيله بشكل متكرر. تدعم بعض المُجمّعات دالة __builtin_popcount التي يُمكنها حساب ذلك باستخدام أجهزة مُعالجة مُتخصصة عند توفرها.

int hamming_distance(unsigned x, unsigned y)
{
    int dist = 0;

    // The ^ operators sets to 1 only the bits that are different
    for (unsigned val = x ^ y; val > 0; ++dist)
    {
        // We then count the bit set to 1 using the Peter Wegner way
        val = val & (val - 1); // Set to zero val's lowest-order 1
    }

    // Return the number of differing bits
    return dist;
}

يُمكن بدلا من ذلك استخدام أمر التجميع من خلال دالة جوهرية على النحو التالي

// Hamming distance for 32-bit integers
int hamming_distance32(unsigned int x, unsigned int y)
{
    return __builtin_popcount(x ^ y);
}

// Hamming distance for 64-bit integers
int hamming_distance64(unsigned long long x, unsigned long long y)
{
    return __builtin_popcountll(x ^ y);
}

:

الخصائص

مكعب ثنائي ثلاثي البتات لإيجاد مسافة هامينغ

مثلالان لمسافات هامينغ: الرمز 100→011 وله مسافة هامينغ تساوي 3، والرمز 010→111 وله مسافة هامينغ تساوي 2

المسافة الدنيا بين أي رأسين هي مسافة هامينy بين السلسلتين الثنائيتين.

بالنسبة لسلسلتين لهما نفس الطول (ن) تُعدّ مسافة هامينغ مقياسًا لمجموعة الكلمات ذات الطول ن (وهو أيضًا بفضاء هامينغ)، إذ تُحقق شرطي عدم السالبية والتماثل. وتكون مسافة هامينغ لكلمتين صفرًا فقط إذا كانت الكلمتان متطابقتين، وتُحققا أيضًا متباينة المثلث، أي أنه إذا ثبّتنا ثلاث كلمات (أ) و(ب) و(ج)، فكلما وُجد فرق بين الحرف رقم "س" من الكلمة (أ) والحرف رقم "س" من الكلمة (ج)، يجب أن يكون هناك فرق بين الحرف رقم "س" من الكلمة (أ) وبين الحرف رقم "س" من الكلمة (ب)، أو بين الحرف رقم "س" من الكلمة (ب) والحرف رقم "س" من الكلمة (ج). وبالتالي، فإن مسافة هامينغ بين الكلمة (أ) والكلمة (ج) ليست أكبر من مجموع مسافات هامينغ بين الكلمة (أ) والكلمة (ب) وبين الكلمة (ب) والكلمة (ج). يمكن أيضًا اعتبار مسافة هامينغ بين الكلمتين (أ) و(ب) بمثابة وزن هامينغ لـ(أ - ب) لاختيار مناسب للعامل −، تمامًا كما يمكن اعتبار الفرق بين عددين صحيحين كمسافة من الصفر على خط الأعداد.

بالنسبة للسلاسل الثنائية (أ) و(ب)، تساوي مسافة هامينغ عدد الآحاد (عدد السكان) في عملية إكس أور (ب) يُعرف الفضاء المتري للسلاسل الثنائية بطول يساوي n من السلاسل، مع مسافة هامينغ، باسم مكعب هامينغ؛ والذي يكافئ، كفضاء متري به مجموعة المسافات بين الرؤوس في رسم بياني لمكعب فائق. يمكن أيضًا التعبير عن سلسلة ثنائية طولها يساوي n كمتجه في $\mathbb {R} ^{n}$. بمعاملة كل رمز في السلسلة كإحداثي حقيقي؛ وبهذا التضمين، تُشكل السلاسل رؤوس مكعب فائق له n من الأبعاد، وتكون مسافة هامينغ للسلاسل مكافئة لمسافة مانهاتن بين الرؤوس.

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

تعمل مسافة هامينغ كأداة أساسية لتحديد الأخطاء في أنظمة تخزين أو نقل البيانات من خلال مقارنة البيانات المستلمة مع البيانات المرسلة الأصلية، إذ تساعد مسافة هامينغ في تحديد عدد تقلبات البتات أو الأخطاء التي حدثت أثناء عملية الإرسال. تُستخدم مسافة هامينغ الدنيا (أو الحد الأدنى للمسافة) (ويُشار إليها عادةً بالرمز dmin) لتعريف بعض المفاهيم الأساسية في نظرية التعمية، مثل أكواد كشف الأخطاء وتصحيحها. وبشكل خاص، يُقال عن الكود (ج) أنه يكشف الأخطاء (ك) فقط إذا كانت مسافة هامينغ الدنيا بين أي كلمتين من كلماته الرمزية تساوي ك+1 على الأقل. فعلى سبيل المثال، لنفترض أن الكود يتكون من كلمتن أو رمزين هما "000" و"111".، فإن مسافة هامينغ بين هاتين الكلمتين هي 3، وبالتالي يكون معامل كشف الأخطاء ك=2. هذا يعني أنه إذا تم قلب بت واحد أو قلب بتين، يمكن اكتشاف الخطأ. إذا تم قلب ثلاثة بتات، فإن "000" يصبح "111" ولا يمكن اكتشاف الخطأ.

يُمكن اعتبار الكود (ج) هو كود تصحِيح الأخطاء ك إذا وُجدت لكل كلمة ل في فضاء هامينغ هـ، كلمة رمز ج واحدة على الأكثر (من ج)، بحيث تكون مسافة هامينغ بين ل وج تساوي ك على الأكثر. بمعنى آخر، يكون الرمز مُصحِّحًا للأخطاء ك إذا كانت مسافة هامينغ الدنيا بين أي كلمتين من كلماته الرمزية تساوي 2ك+1 على الأقل. يُمكن صياغة ذلك هندسيًا أيضًا إذا افترضنا وجود كرات مغلقة نصف قطرها يساوي ك، وفي مركزها كلمتان رمزيتان منفصلتان. تُسمى هذه الكرات أيضًا بكرات هامينغ.

على سبيل المثال، لنفترض أن نفس الرمز ثلاثي البتات يتكون من كلمتي الرمز "000" و"111". ويتكون فضاء هامينغ من 8 كلمات هي: 000، و001، و010، و011، و100، و101، و110، و111. حيث كلمة المرور "000" وكلمات خطأ البت الواحد "001"، "010"، "100" جميعها أقل من أو تساوي مسافة هامينغ من 1 إلى "000". وبالمثل، كلمة المرور "111" وكلمات خطأ البت الواحد الخاصة بها "110"، "101" و"011" جميعها ضمن مسافة هامينغ واحدة من "111" الأصلية. في هذا الرمز، يكون خطأ البت الواحد دائمًا ضمن مسافة هامينغ واحدة من الرموز الأصلية، ويمكن تصحيح الخطأ في الرمز باستخدام بت قيمته 1، أي أن ك=1. بما أن مسافة هامينغ بين "000" و"111" هي 3، وهي تُشكل مجموعة كلمات المرور الكاملة في الكود، فإن أدنى مسافة هامينغ تساوي 3، وهو ما يُحقق المعادلة 2ك+1 = 3.

وبالتالي، فإن الكود الذي تبلغ أدنى مسافة هامينغ بين كلماته د لا يمكنه اكتشاف أخطاء بين كلماته إلا إذا كان الخطأ يساوي د-1 على الأكثر، ويمكنه تصحيح أخطاء ⌊(د-1)/2⌋. ويُسمى هذا الرقم الأخير أيضًا نصف قطر التعبئة أو قدرة الكود على تصحيح الأخطاء.