تحويل بوروز–ويلر: رتّب النص ثم استعده خطوة بخطوة

تحويل بوروز–ويلر، واختصاره BWT، يعيد ترتيب رموز النص ترتيبًا قابلًا للعكس، وقد يجمع الرموز المتكررة في صورة تلائم الضغط اللاحق. لا يكفي فهمه بوصفه فرزًا لحروف الكلمة؛ إذ يجب أن تبقى طريقة لاسترجاع ترتيبها الأصلي. [3]

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

كوّن الدورانات واحتفظ برقم الصف

الدوران عند الموضع i ينقل المقدمة السابقة له إلى نهاية النص. نكوّن دورانًا لكل موضع، ونرتب الدورانات ترتيبًا معجميًا، ثم نأخذ آخر رمز من كل صف. نحفظ أيضًا موضع الصف المطابق للنص الأصلي؛ يصف التقرير الأصلي هذه النسخة بالزوج المكوّن من العمود الأخير وفهرس الصف. [1]

نبدأ الترقيم من الصفر. في المثال، ترتيب الرموز المستعملة هو ! < A < C < T. لذلك يأتي الصف الذي يبدأ بعلامة التعجب أولًا. وعندما يبدأ صفان بالرمز نفسه، نواصل المقارنة عند الرموز التالية إلى أن يظهر الاختلاف.

اقرأ العمود الأخير من أعلى إلى أسفل لتحصل على ACTTTAAA!. لا نرسل جدولًا من 81 خانة؛ نحتفظ هنا بتسعة رموز والعدد 8. العدد فهرس داخل الجدول، وليس رمزًا عاشرًا نلصقه بالنص دون تعريف تنسيق له.

علامة ! في هذا المثال جزء من المدخل نفسه، لا علامة نهاية أضافتها دالتنا. وجودها مرة واحدة يساعد العين على متابعة الدورانات، لكنه ليس شرطًا للشفرة التي تحفظ فهرس الصف. سنختبر نصًا دوريًا لا يحتويها أيضًا.

برنامج التحويل

هذه صياغة قصيرة تنشئ الدورانات فعليًا. تستعمل rows.index(text) لاختيار أول صف مطابق؛ إذا تطابقت دورانات متعددة لنص دوري، فالصفوف المتطابقة تحمل النص نفسه.

def transform(text):
    if not text:
        return "", 0
    rows = sorted(text[i:] + text[:i] for i in range(len(text)))
    return "".join(row[-1] for row in rows), rows.index(text)

يعطي transform("TATATACA!") الزوج ('ACTTTAAA!', 8). عند كتابة ملف حقيقي يجب تعريف طريقة حفظ طول السلسلة وترميزها وفهرسها؛ عرض الزوج في بايثون هنا وسيلة لرؤية القيم، وليس تصميمًا لتنسيق أرشيف.

أعد بناء النص من العمود الأخير

نبدأ بصفوف فارغة بعدد الرموز. في كل جولة نضيف الرمز رقم i من العمود الأخير أمام الصف رقم i، ثم نفرز الصفوف. نكرر بعدد رموز النص ونختار الفهرس المحفوظ. ترتبط قابلية العكس بترتيب العمودين؛ وتشرح برنستون عكسًا أكفأ بروابط بين المواضع. [2]

def inverse(last, first):
    if not last:
        if first != 0:
            raise ValueError("Empty input requires row index 0")
        return ""
    if not isinstance(first, int) or not 0 <= first < len(last):
        raise ValueError("Row index outside the matrix")
    rows = [""] * len(last)
    for _ in last:
        rows = sorted(last[i] + rows[i] for i in range(len(last)))
    return rows[first]

لنتابع أرقامًا محددة من تنفيذنا. بعد الجولة الأولى تكون الصفوف !, A, A, A, A, C, T, T, T. وبعد الثانية تصبح !T, A!, AC, AT, AT, CA, TA, TA, TA. هذه أجزاء من بدايات الدورانات، وليست أجزاء متتالية تقرأها لتكوين النص.

في الجولة الثالثة نرى !TA, A!T, ACA, ATA, ATA, CA!, TAC, TAT, TAT. يستمر نمو كل صف رمزًا واحدًا في كل جولة؛ بعد الجولة التاسعة يعود الجدول الكامل أعلاه، ويعيد الصف رقم 8 النص TATATACA!.

نقل آخر حرف من كل دوران إلى أوله يعيد مجموعة الدورانات نفسها. بإضافة العمود الأخير إلى البدايات وإعادة فرزها نكشف حرفًا آخر؛ وبعد تسع جولات تكتمل صفوف مثالنا. [1]

لماذا لا نستغني عن فهرس الصف؟

خذ المدخل الآخر ATATACA!T. إنه دوران للمدخل الأول، لذلك مجموعة الدورانات المرتبة لا تتغير، والعمود الأخير يظل ACTTTAAA!. لكن النص المطلوب الآن موجود في الصف رقم 4، لا رقم 8.

إذن، لو احتفظت بالعمود الأخير وحده في نسختنا، فلا تستطيع المفاضلة بين هذين المدخلين من تلك المعلومة وحدها. التحقق من صحة فهرس داخل النطاق لا يثبت أنه الفهرس المقصود: العددان 4 و8 صالحان من حيث النطاق، ويعيدان نصين مختلفين.

الرموز العربية والنصوص الدورية

ترتب بايثون السلاسل ترتيبًا معجميًا بحسب قيم محارف Unicode. هذا ترتيب برمجي، ولا نفترض أنه ترتيب معجم عربي أو ترتيب العلامات كما تظهر بصريًا على الشاشة. [4]

في مثالنا العربي، يعطي transform("بابا") العمود بباا والفهرس 2. لدينا دورانان يساويان «اباب» ودورانان يساويان «بابا»؛ لذلك لا نحذف الصفوف المكررة. الفهرس 2 يختار أول صف مطابق لـ«بابا»، ويعيده العكس كما دخل.

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

ما الذي أثبتته الاختبارات؟

نُفّذ المثال على بايثون 3.12.14. شمل التحقق 1093 سلسلة تمثل جميع السلاسل على الأبجدية A,B,C من الطول صفر إلى ستة، و11 حالة مسماة، و256 مدخلًا مولدًا بطول من واحد إلى أربعين وبذرة ثابتة 20261013.

نجح في الحالات 1360 اختبار inverse(*transform(text)) == text، وفحص تساوي عدد مرات كل رمز قبل التحويل وبعده. وقورنت النتيجة أيضًا بعكس مستقل في ملف التحقق يستعمل ربط الظهور الأول للرمز بالأول، والثاني بالثاني، ثم يتتبع السابق؛ توافق التنفيذان في جميع الحالات.

للنسخة المعروضة اتفاق صريح عند الفراغ: تحول السلسلة الفارغة إلى ("", 0). وتُرفض ثلاثة أمثلة لفهرس غير صالح: فهرس 1 مع مدخل فارغ، وفهرس −1 أو 3 لسلسلة طولها ثلاثة. هذه فحوص محدودة للمدخل؛ ليست وسيلة لكشف كل تلف ممكن في ملف.

أين يقع الضغط، وما حدود هذا التنفيذ؟

يوضح البحث الأصلي أن إعادة الترتيب تسبق مرحلة ترميز تضغط البيانات، ويمكن أن تجعل السياقات المتشابهة تنتج تجمعات من الرموز. التحويل وحده لا يختصر البيانات، ولا يَعِد كل نص بنتيجة أصغر. [1]

في المثال المرئي حصلنا على ثلاثة أحرف T متجاورة وثلاثة أحرف A متجاورة، لكن العدد الكلي بقي تسعة، وفوقه نحتاج فهرس الصف. لا نحسب «نسبة توفير» من طول الجدول الذي استخدمناه للشرح؛ ذلك الجدول لم يكن هو الملف الأصلي أصلًا.

وتبني الشفرة هنا n سلسلة، طول كل منها n، أي n² موضع رمزي في الجدول النهائي، فضلًا عن تكاليف كائنات بايثون. والعكس يعيد البناء والفرز n مرة. لهذا اخترنا تسعة رموز للشرح، ولا نستنتج من نجاح المثال صلاحية هذا الأسلوب لمعالجة كتاب كامل في الذاكرة.

جرّب تغيير المدخل القصير ثم راقب ثلاثة أشياء منفصلة: العمود الأخير، وفهرس الصف، ونتيجة المقارنة بعد العكس. وإذا كان سؤالك العملي هو إنشاء أرشيف وإرساله، فراجع طريقة ضغط الملفات بصيغة ZIP؛ ذلك إجراء استخدام يختلف عن فحص هذه الخوارزمية.