خوارزمية فيرهويف (Verhoeff Algorithm)

<![CDATA[

مقدمة

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

آلية عمل خوارزمية فيرهويف

تعتمد خوارزمية فيرهويف على مفهوم المجموعة شبه الزمرة (quasigroup) مع عملية غير ترابطية. هذا يعني أن ترتيب العمليات مهم، وهذا يسمح للخوارزمية باكتشاف الأخطاء التي لا يمكن اكتشافها بواسطة خوارزميات التدقيق البسيطة. تتكون الخوارزمية من عدة خطوات رئيسية:

إنشاء جدول الضرب: يتم إنشاء جدول ضرب خاص يمثل المجموعة شبه الزمرة المستخدمة في الخوارزمية. هذا الجدول هو أساس العمليات الحسابية التي تجرى على البيانات.
تطبيق التبديلات: يتم تطبيق سلسلة من التبديلات (permutations) على أرقام الإدخال باستخدام الجدول الذي تم إنشاؤه. هذه التبديلات تساعد في توزيع الأخطاء المحتملة عبر الأرقام.
حساب خانة التحقق: بعد تطبيق التبديلات، يتم حساب خانة التحقق (checksum digit) باستخدام عملية رياضية تعتمد على الجدول والتبديلات التي تم إجراؤها.
التحقق من الصحة: للتحقق من صحة البيانات، يتم إعادة حساب خانة التحقق باستخدام نفس الخطوات، ثم يتم مقارنة النتيجة مع خانة التحقق الأصلية. إذا تطابقت القيمتان، فهذا يشير إلى أن البيانات صحيحة على الأرجح.

مزايا خوارزمية فيرهويف

تتميز خوارزمية فيرهويف بعدة مزايا تجعلها خياراً جذاباً للعديد من التطبيقات:

اكتشاف الأخطاء المتعددة: قادرة على اكتشاف مجموعة واسعة من الأخطاء، بما في ذلك الأخطاء الناتجة عن النقل (transposition errors)، والأخطاء الناتجة عن الإدخال الخاطئ (single-digit errors).
مقاومة لأخطاء النقل: فعالة بشكل خاص في اكتشاف أخطاء النقل، حيث يتم تبديل ترتيب رقمين متجاورين.
سهولة التنفيذ: يمكن تنفيذها بسهولة باستخدام مجموعة متنوعة من لغات البرمجة.
أداء جيد: تتميز بأداء جيد وسرعة في الحساب، مما يجعلها مناسبة للاستخدام في التطبيقات التي تتطلب معالجة سريعة للبيانات.

عيوب خوارزمية فيرهويف

على الرغم من مزاياها العديدة، إلا أن خوارزمية فيرهويف لها بعض العيوب:

التعقيد النسبي: أكثر تعقيداً من خوارزميات التدقيق البسيطة مثل خانة الاختيار.
ليست مضمونة بنسبة 100%: على الرغم من أنها فعالة جداً، إلا أنها ليست مضمونة لاكتشاف جميع أنواع الأخطاء.
تعتمد على جدول الضرب: تعتمد على جدول ضرب محدد، مما قد يحد من مرونتها في بعض التطبيقات.

تطبيقات خوارزمية فيرهويف

تستخدم خوارزمية فيرهويف في مجموعة واسعة من التطبيقات، بما في ذلك:

أرقام الحسابات المصرفية: للتحقق من صحة أرقام الحسابات المصرفية وتقليل مخاطر الاحتيال.
الأرقام التعريفية: للتحقق من صحة الأرقام التعريفية الشخصية وأرقام الهوية الوطنية.
أرقام المسلسلات: للتحقق من صحة أرقام المسلسلات للمنتجات والسلع.
أنظمة إدارة المخزون: للتحقق من صحة أرقام المنتجات في أنظمة إدارة المخزون.
تطبيقات بطاقات الائتمان: في بعض تطبيقات بطاقات الائتمان للتحقق من صحة أرقام البطاقات.

مثال توضيحي

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

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

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

خوارزمية فيرهويف في لغات البرمجة

يمكن تنفيذ خوارزمية فيرهويف بسهولة باستخدام مجموعة متنوعة من لغات البرمجة. فيما يلي مثال بسيط لتنفيذ الخوارزمية في بايثون:


def verhoeff_algorithm(number):
    """
    Calculate the Verhoeff digit for a given number.
    """
    d = (
        (0, 1, 2, 3, 4, 5, 6, 7, 8, 9),
        (1, 2, 3, 4, 0, 6, 7, 8, 9, 5),
        (2, 3, 4, 0, 1, 7, 8, 9, 5, 6),
        (3, 4, 0, 1, 2, 8, 9, 5, 6, 7),
        (4, 0, 1, 2, 3, 9, 5, 6, 7, 8),
        (5, 9, 8, 7, 6, 0, 4, 3, 2, 1),
        (6, 5, 9, 8, 7, 1, 0, 4, 3, 2),
        (7, 6, 5, 9, 8, 2, 1, 0, 4, 3),
        (8, 7, 6, 5, 9, 3, 2, 1, 0, 4),
        (9, 8, 7, 6, 5, 4, 3, 2, 1, 0)
    )

    p = (
        (0, 1, 2, 3, 4, 5, 6, 7, 8, 9),
        (1, 5, 7, 6, 2, 8, 3, 0, 9, 4),
        (5, 8, 0, 3, 7, 9, 6, 1, 4, 2),
        (8, 9, 1, 6, 0, 4, 3, 5, 2, 7),
        (9, 4, 5, 3, 1, 2, 6, 8, 7, 0),
        (4, 2, 8, 6, 5, 7, 3, 9, 0, 1),
        (2, 7, 9, 3, 8, 0, 6, 4, 1, 5),
        (7, 0, 4, 6, 9, 1, 3, 2, 5, 8)
    )

    inv = (0, 4, 3, 2, 1, 5, 6, 7, 8, 9)

    c = 0
    for i, n in enumerate(reversed(number)):
        c = d[c][p[(i % 8)][int(n)]]

    return inv[c]

def generate_verhoeff(number):
    """
    Generate a Verhoeff number by appending the checksum digit to the number.
    """
    checksum_digit = verhoeff_algorithm(number)
    return number + str(checksum_digit)

def validate_verhoeff(number):
    """
    Validate if a given number is a valid Verhoeff number.
    """
    c = 0
    for i, n in enumerate(reversed(number)):
        c = d[c][p[(i % 8)][int(n)]]

    return c == 0

# Example usage:
number = "12345678"
verhoeff_number = generate_verhoeff(number)
print(f"Verhoeff number: {verhoeff_number}")

is_valid = validate_verhoeff(verhoeff_number)
print(f"Is valid: {is_valid}")

يوضح هذا المثال كيفية حساب خانة التحقق وإنشاء رقم فيرهويف صحيح، بالإضافة إلى كيفية التحقق من صحة رقم فيرهويف موجود.

خاتمة

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

المراجع

]]>