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

خوارزمية فيرهوف ^{[ 1 ]} هي مجموع اختباري للكشف عن الأخطاء، وقد نشرها لأول مرة عالم الرياضيات الهولندي جاكوبوس فيرهوف في عام 1969. ^{[ 2 ] [ 3 ]} كانت أول خوارزمية رقم فحص عشري تكشف جميع أخطاء الرقم الواحد، وجميع أخطاء التبديل التي تتضمن رقمين متجاورين، ^{[ 4 ]} وهو ما كان يُعتقد في ذلك الوقت أنه مستحيل باستخدام مثل هذا الرمز.

تم اكتشاف هذه الطريقة بشكل مستقل من قبل إتش. بيتر غوم في عام 1985، وهذه المرة تضمنت برهانًا رسميًا وامتدادًا لأي قاعدة. ^{[ 5 ]}

كان هدف فيرهوف إيجاد رمز عشري - يكون فيه رقم التحقق رقمًا عشريًا واحدًا - يكشف جميع أخطاء الرقم الواحد وجميع عمليات تبديل الأرقام المتجاورة. في ذلك الوقت، ساهمت البراهين المفترضة على عدم وجود هذه الرموز ^{[ 6 ]} في انتشار رموز الأساس 11، كما هو الحال في رقم التحقق في رقم ISBN .

كانت أهدافه عملية أيضًا، وقد اعتمد في تقييمه للرموز المختلفة على بيانات حية من نظام البريد الهولندي، مستخدمًا نظام نقاط مُرجّحة لأنواع الأخطاء المختلفة. وقد صنّف التحليل الأخطاء إلى عدة فئات: أولًا، حسب عدد الأرقام الخاطئة؛ فبالنسبة للأخطاء التي تحتوي على رقمين، هناك تبديلات ( ab → ba )، وتوأمات ( aa → bb )، وتبديلات قفزية ( abc → cba ) ، وأخطاء صوتية ( 1a → a0 )، وتوأمات قفزية ( aba → cbc ). بالإضافة إلى ذلك، هناك أرقام محذوفة وأخرى مضافة. وعلى الرغم من أن تكرار بعض هذه الأنواع من الأخطاء قد يكون ضئيلًا، إلا أن بعض الرموز قد تكون محصنة ضدها، إلى جانب الهدف الأساسي المتمثل في اكتشاف جميع الأخطاء الفردية والتبديلات.

أظهرت الأخطاء الصوتية على وجه الخصوص تأثيرات لغوية، لأنه في اللغة الهولندية، تُقرأ الأرقام عادةً في أزواج؛ وأيضًا في حين أن 50 تبدو مشابهة لـ 15 في اللغة الهولندية، فإن 80 لا تبدو مثل 18.

على سبيل المثال، ذكر فيرهوف التصنيف التالي للأخطاء:

تتلخص الفكرة العامة للخوارزمية في تمثيل كل رقم من الأرقام (من 0 إلى 9) كعنصر من عناصر _{المجموعة} ثنائية السطوح D5 . أي، يتم ربط الأرقام بـ D5 _، ثم إجراء بعض التعديلات عليها، ثم إعادة ربطها بالأرقام الأصلية. ولتكن هذه العملية m : [0, 9] → _D5 

${\displaystyle m={\begin{pmatrix}0&1&2&3&4&5&6&7&8&9\\e&r&r^{2}&r^{3}&r^{4}&s&rs&r^{2}s&r^{3}s&r^{4}s\end{pmatrix}}}$

ليكن الرقم النوني هو a _n وليكن عدد الأرقام k .

على سبيل المثال، إذا كان الرمز 942 فإن k هو 3 و a ₃ = m (2) = r ² .

الآن، عرّف التبديل f  : D ₅ → D ₅

${\displaystyle f={\begin{pmatrix}e&r&r^{2}&r^{3}&r^{4}&s&rs&r^{2}s&r^{3}s&r^{4}s\\r&s&r^{2}s&rs&r^{2}&r^{3}s&r^{3}&e&r^{4}s&r^{4}\end{pmatrix}}}$

على سبيل المثال،${\displaystyle f(r^{3})=rs}$مثال آخر هو${\displaystyle f^{2}(r^{3})=r^{3}}$منذ${\displaystyle f(f(r^{3}))=f(rs)=r^{3}}$.

باستخدام الترميز الضربي لعملية المجموعة D ₅ ، يكون رقم التحقق ببساطة قيمة c بحيث

${\displaystyle f^{0}(c)\cdot f^{1}(a_{k})\cdot \ldots \cdot f^{k-1}(a_{2})\cdot f^{k}(a_{1})=e}$

يُعطى العدد c صراحةً بواسطة المعكوس الضربي:

${\displaystyle c=\left(\prod _{n=1}^{k}f^{n}(a_{k+1-n})\right)^{-1}}$

على سبيل المثال، رقم التحقق للعدد 942 هو 7. وللتحقق من ذلك، استخدم الربط مع D ₅ وأدخله في الطرف الأيسر من المعادلة السابقة.

${\displaystyle f^{0}(r^{2}s)\cdot f^{1}(r^{2})\cdot f^{2}(r^{4})\cdot f^{3}(r^{4}s)=e}$

لتقييم هذا التبديل بسرعة، استخدم ذلك

${\displaystyle f^{3}(r^{4}s)=f^{2}(r^{4})=f^{1}(r^{2})=f^{0}(r^{2}s)=r^{2}s}$

للحصول على ذلك

${\displaystyle r^{2}s\cdot r^{2}s\cdot r^{2}s\cdot r^{2}s=e}$

هذا هو نفس الانعكاس الذي يتم ضربه بشكل متكرر. استخدم حقيقة أن الانعكاسات هي معكوساتها. ^{[ 7 ]}

${\displaystyle (r^{2}s\cdot r^{2}s)\cdot (r^{2}s\cdot r^{2}s)=e^{2}=e}$

عمليًا، تُنفَّذ الخوارزمية باستخدام جداول بحث بسيطة دون الحاجة إلى فهم كيفية توليد هذه الجداول من نظرية الزمر والتباديل الأساسية. ويُعتبر هذا، بشكل أدق، عائلة من الخوارزميات، إذ تعمل تباديل أخرى أيضًا. ويشير فيرهوف إلى أن التبديل المذكور أعلاه مميزٌ لأنه يتميز بقدرته على كشف 95.3% من الأخطاء الصوتية. ^{[ 8 ]}

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

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

يمكن تنفيذ خوارزمية فيرهوف باستخدام ثلاثة جداول: جدول الضرب d ، وجدول المعكوس inv، وجدول التبديل p .

الجدول الأول، d ، مبني على الضرب في المجموعة ثنائية السطوح D5 _. [ ^{7 ] وهو} ببساطة جدول كايلي للمجموعة. لاحظ أن هذه المجموعة ليست تبديلية ، أي أنه بالنسبة لبعض قيم j و k ، فإن d ( j , k ) ≠ d ( k , j ) .

يمثل الجدول العكسي inv المعكوس الضربي للرقم، أي القيمة التي تحقق d ( j , inv( j )) = 0 .

يطبق جدول التباديل p تبديلاً على كل رقم بناءً على موقعه في العدد. وهذا في الواقع تبديل واحد (1 5 8 9 4 2 7 0)(3 6) يُطبق بشكل تكراري؛ أي p ( i + j , n ) = p ( i , p ( j , n )) .

يتم إجراء حساب مجموع التحقق لفيرهوف على النحو التالي:

1. قم بإنشاء مصفوفة n من الأرقام الفردية للعدد، مأخوذة من اليمين إلى اليسار (الرقم الموجود في أقصى اليمين هو n ₀ ، إلخ).
2. قم بتهيئة مجموع التحقق c إلى الصفر.
3. لكل فهرس i من المصفوفة n ، بدءًا من الصفر، استبدل c بـ d ( c , p ( i mod 8, n _i )) .

يكون الرقم الأصلي صالحاً إذا وفقط إذا كانت قيمة c تساوي صفرًا .

لإنشاء رقم تحقق، أضف 0، وقم بإجراء العملية الحسابية: رقم التحقق الصحيح هو inv( c ).

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

• الأوراق النقدية للمارك الألماني ^{[ 10 ]}
• أرقام أدهار الهندية ^{[ 11 ]}
• مشغل نظام تسجيل العدادات الأيرلندي ^{[ 12 ]}
• قاموس المصطلحات السريرية SNOMED ^{[ 13 ]}

• خوارزمية لوهن – صيغة التحقق البسيطة 
• خوارزمية دام – خوارزمية رقم التحقق 

• وصف تفصيلي لخوارزمية فيرهوف، مؤرشف بتاريخ ٢٦ أبريل ٢٠٠٦ في أرشيف الإنترنت (Wayback Machine).