البرنامج الذي يقارن نصين لا يقرأ ويحكم على «ما الذي تغيّر» كما يفعل الإنسان. بل يبحث عن طريقة لتحويل قائمة إلى أخرى بأقل عدد ممكن من عمليات الحذف والإضافة. يشرح هذا المقال كيف يحسب diff تلك الإجابة، ولماذا تأتي النتيجة أحيانًا مختلفة عمّا يتوقعه الإنسان.
وحدة المقارنة: السطر والكلمة والحرف
يقسّم diff النص أولًا إلى قائمة من الرموز (tokens). يَعُدّ diff التقليدي وgit كل سطر رمزًا واحدًا. لذلك إذا تغيّر حرف واحد فقط في سطر ما، يظهر السطر كله على أنه «حذف سطر واحد + إضافة سطر واحد».
المقارنة على مستوى السطر سريعة وتناسب مراجعة الكود، لكن في المستندات التي تُكتب فيها الفقرة الطويلة في سطر واحد يصعب معرفة موضع التغيير. لذلك تقارن أدوات كثيرة على مرحلتين.
- تقارن على مستوى السطر لتعثر على الأسطر المتغيرة.
- تقرن الأسطر المتغيرة ببعضها، ثم تقارن محتواها مرة أخرى على مستوى الكلمة أو الحرف.
يعمل هذا الموقع بالطريقة نفسها. ويمكنك اختيار وحدة المقارنة داخل السطر: كلمات، أو مقاطع بين المسافات، أو أحرف.
أطول متتالية جزئية مشتركة (LCS)
النواة الرياضية لـ diff هي أطول متتالية جزئية مشتركة (Longest Common Subsequence، LCS). المتتالية الجزئية هي مجموعة من العناصر المختارة مع الحفاظ على ترتيبها. على سبيل المثال، أطول متتالية جزئية مشتركة بين ABCABBA وCBABAC طولها 4، ومن أمثلتها CABA وBABA.
العناصر الداخلة في LCS هي «ما بقي كما هو»، والباقي إما «محذوف» (موجود في اليسار فقط) أو «مضاف» (موجود في اليمين فقط). كلما طالت LCS قلّت عمليات الحذف والإضافة. إذا كان طولا القائمتين N وM وطول LCS هو L، فإن مجموع عمليات الحذف والإضافة D يساوي:
D = (N - L) + (M - L)في المثال أعلاه N=7 وM=6 وL=4، إذن D = 3 + 2 = 5. تُسمّى D مسافة التحرير (عند السماح بالإدراج والحذف فقط)، وتُسمّى قائمة عمليات الحذف والإضافة نص التحرير (edit script).
رسم التحرير البياني وخوارزمية مايرز
إذا حُسبت LCS بالطريقة المدرسية (البرمجة الديناميكية) فستحتاج إلى جدول بحجم N×M. مقارنة ملفين من 10,000 سطر لكل منهما تعني 100 مليون خانة، وهذا بطيء ويستهلك ذاكرة كبيرة. في عام 1986 قدّم يوجين مايرز (Eugene W. Myers) في بحثه «An O(ND) Difference Algorithm and Its Variations» طريقة أسرع، أصبحت أساس الخوارزمية الافتراضية في GNU diff وgit اليوم.
يحوّل مايرز المقارنة إلى البحث عن أقصر مسار على شبكة.
- ينطلق المسار من الزاوية العلوية اليسرى (0,0) إلى الزاوية السفلية اليمنى (N,M).
- خطوة إلى اليمين = حذف عنصر واحد من النص الأيسر، وخطوة إلى الأسفل = إضافة عنصر واحد من النص الأيمن. تكلفة كل منهما 1.
- في الخانة التي يتطابق فيها العنصران يمكن التحرك قطريًا مجانًا. يُسمّى هذا المقطع القطري المتصل snake («الأفعى»).
المسار الأقل تكلفة هو أقصر نص تحرير. توسّع خوارزمية مايرز على التوالي «أبعد نقطة يمكن بلوغها بتكلفة 0»، ثم «أبعد نقطة بتكلفة 1»… حتى تصل إلى نقطة النهاية فتتوقف. وبما أنه يكفي في كل مرحلة تذكّر أبعد موضع واحد على كل قطر، فإن الوقت المستغرق يتناسب تقريبًا مع (N+M)×D. إذا كان النصان متقاربين جدًا تكون D صغيرة والخوارزمية سريعة جدًا، وإذا كانا مختلفين تمامًا تصبح أبطأ.
الذاكرة الخطية وmiddle snake
لتتبّع المسار رجوعًا يلزم حفظ سجل لكل مرحلة، فقد تزداد الذاكرة بما يتناسب مع D². قدّم مايرز في البحث نفسه صيغة تُجري البحث من البداية ومن النهاية في آن واحد، حتى يلتقي الاتجاهان عند مقطع قطري (middle snake). وبتقسيم المسألة عند تلك النقطة إلى مسألتين أصغر وتكرار ذلك، لا تستهلك الذاكرة إلا ما يتناسب مع حجم المدخلات.
عندما تصبح التكلفة باهظة: الاستدلال التقريبي
إذا كان كل من المدخلين عشرات آلاف الأسطر ومختلفين كثيرًا، تكبر D أيضًا وقد يبلغ (N+M)×D المليارات. تحسّبًا لذلك، يستخدم GNU diff استدلالًا يقطع المسألة عند القطر الذي تقدّم أبعد من غيره حتى الآن إذا تجاوزت مراحل البحث حدًا معينًا. تبقى النتيجة نص تحرير صحيحًا، لكن لا يوجد ضمان بأنه الأقصر. خيار --minimal في GNU diff وفي git يجعل البحث يجد النتيجة الأصغرية ولو استغرق وقتًا أطول.
الأصغر ليس دائمًا الأسهل قراءة
قد توجد عدة مسارات بمسافة التحرير نفسها. مثلًا، إذا أضفت دالة جديدة إلى الكود، فإن قوس الإغلاق } والأسطر الفارغة موجودة في أماكن كثيرة، فقد تقرن الخوارزمية «} الدالة الجديدة» بـ«} دالة قائمة». النتيجة أصغرية، لكنها تبدو غريبة للقارئ. ولهذا يستخدم git افتراضيًا استدلالًا ينقل الحدود بالنظر إلى المسافات البادئة، ويوفّر خوارزميات أخرى مثل patience وhistogram. المقارنة المفصلة في مقال مقارنة خوارزميات diff.
في هذه الأداة
محرك المقارنة في هذا الموقع يطبّق بجافاسكربت صيغة الذاكرة الخطية من خوارزمية مايرز، وينتقل إلى التقسيم التقريبي بطريقة GNU diff نفسها عندما تكون المدخلات كبيرة. تعمل الحسابات في Web Worker، فلا تتجمد الواجهة حتى مع الملفات الكبيرة. بعد الحصول على النتيجة على مستوى السطر، تقرن الأداة الأسطر المتغيرة المتشابهة في المحتوى وتعرضها على أنها «معدَّلة»، ثم تقارن محتواها مرة أخرى بالوحدة المختارة (كلمات أو مقاطع أو أحرف) وتُبرز الفروق.
جرّب إدخال نصين في مقارنة النصوص وغيّر وحدة المقارنة داخل السطر لترى كيف تتغير النتيجة. ولقراءة النتيجة بصيغة git راجع مقال كيف تقرأ unified diff.