بصلح

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

تُبنى القواعد النحوية باستبدال أكثر زوج من الأحرف تكرارًا في النص بشكل متكرر. وعندما لا يتكرر أي زوج من الأحرف، تُستخدم السلسلة الناتجة كمسلّمة للقواعد النحوية. وبالتالي، تكون القواعد النحوية الناتجة بحيث تحتوي جميع القواعد، باستثناء المسلّمة، على رمزين في الجانب الأيمن.

تم تقديم Re-Pair لأول مرة بواسطة NJ Larsson و A. Moffat ^{[ 1 ]} في عام 1999.

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

تُظهر الصورة على اليمين كيف تقوم الخوارزمية بضغط السلسلة${\displaystyle w=xabcabcy123123zabc}$.

خلال التكرار الأول، الزوج${\displaystyle ab}$، وهو ما يحدث ثلاث مرات في${\displaystyle w}$، يتم استبدالها برمز جديد${\displaystyle R_{1}}$في التكرار الثاني، يكون الزوج الأكثر تكرارًا في السلسلة${\displaystyle w=xR_{1}cR_{1}cy123123zR_{1}c}$، وهو${\displaystyle R_{1}c}$، يتم استبدالها برمز جديد${\displaystyle R_{2}}$وبالتالي، في نهاية التكرار الثاني، تكون السلسلة المتبقية هي${\displaystyle w=xR_{2}R_{2}y123123zR_{2}}$في التكرارين التاليين، الأزواج${\displaystyle 12}$و${\displaystyle R_{3}3}$يتم استبدالها برموز${\displaystyle R_{3}}$و${\displaystyle R_{4}}$على التوالي. وأخيراً، السلسلة${\displaystyle w=xR_{2}R_{2}yR_{4}R_{4}zR_{2}}$لا يحتوي على أي زوج متكرر، وبالتالي يتم استخدامه كمسلمة لقواعد الإخراج.

لتحقيق تعقيد زمني خطي، تتطلب عملية إعادة الاقتران هياكل البيانات التالية

• تسلسل يمثل سلسلة الإدخال. الموضع${\displaystyle i}$يحتوي جزء من التسلسل على الرمز رقم i من سلسلة الإدخال بالإضافة إلى مرجعين إلى مواقع أخرى في التسلسل. تشير هذه المراجع إلى المواقع التالية/السابقة، على سبيل المثال${\displaystyle k}$و${\displaystyle m}$بحيث تبدأ السلسلة الفرعية نفسها عند${\displaystyle w[i]}$،${\displaystyle w[k]}$و${\displaystyle w[m]}$ويتم التقاط جميع الحالات الثلاث بواسطة نفس المرجع (أي أن هناك متغيرًا في القواعد النحوية التي تولد السلسلة).
• قائمة انتظار ذات أولوية . كل عنصر في هذه القائمة عبارة عن زوج من الرموز (أطراف أو أزواج مُعرَّفة مسبقًا) تظهر تباعًا في التسلسل. تُحدَّد أولوية الزوج بعدد مرات ظهوره في التسلسل المتبقي. في كل مرة يُنشأ فيها زوج جديد، تُحدَّث قائمة الانتظار ذات الأولوية.
• جدول تجزئة لتتبع الأزواج المُعرّفة مسبقاً. يتم تحديث هذا الجدول في كل مرة يتم فيها إنشاء زوج جديد أو حذفه.

بما أن جدول التجزئة وقائمة الانتظار ذات الأولوية يشيران إلى العناصر نفسها (الأزواج)، فيمكن تنفيذهما باستخدام بنية بيانات مشتركة تُسمى PAIR، تحتوي على مؤشرات لجدول التجزئة (h_next) وقائمة الانتظار ذات الأولوية (p_next و p_prev). علاوة على ذلك، يشير كل زوج PAIR إلى بداية أول (f_pos) وآخر (b_pos) ظهور للسلسلة التي يمثلها هذا الزوج في التسلسل. يوضح الشكل التالي نظرة عامة على بنية البيانات هذه.

تُظهر الصورتان التاليتان مثالاً على شكل هياكل البيانات هذه بعد التهيئة وبعد تطبيق خطوة واحدة من عملية الاقتران (لا يتم عرض المؤشرات إلى NULL):

num_rules_encoded = 256 // بشكل افتراضي، تكون مجموعة أحرف ASCII الموسعة هي نهايات القواعد النحوية.writeSymbol ( symbol s ) { bitslen = log ( num_rules_encoded ); // مبدئيًا 8، لوصف أي حرف ASCII موسع ، اكتب s بالثنائي باستخدام bitslen bits }void encodeCFG_rec ( symbol s ) { if ( s ليس رمزًا نهائيًا وهذه هي المرة الأولى التي يظهر فيها الرمز s ) { take rule s → X Y ; write bit 1 ; encodeCFG_rec ( X ) ; encodeCFG_rec ( Y ) ; assign to symbol s value ++ num_rules_encoded ; } else { write bit 0 ; writeSymbol ( terminal / value assigned ) } }void encodeCFG ( symbol s ) { encodeCFG_rec ( s ); write bit 1 ; }

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

تحسين	سنة	تطبيق	وصف
تصفح العبارات [ 2 ]	2003		بدلاً من معالجة سلسلة الإدخال كسلسلة من الأحرف، تقوم هذه الأداة أولاً بتجميع الأحرف في عبارات (مثل الكلمات). تعمل خوارزمية الضغط على غرار خوارزمية إعادة التجميع، ولكنها تعتبر العبارات المحددة بمثابة نهايات القواعد النحوية. تقبل الأداة خيارات متعددة لتحديد نوع العبارات التي سيتم أخذها في الاعتبار، وتقوم بتشفير القواعد النحوية الناتجة في ملفين منفصلين: أحدهما يحتوي على البديهية والآخر على بقية القواعد.
إبداعي	2011		هذه إحدى أكثر تطبيقات Re-Pair شيوعًا. تستخدم هذه الطريقة هياكل البيانات الموضحة هنا (التي تم اقتراحها عند نشرها لأول مرة [ 1 ] )، وتُشفّر القواعد النحوية الناتجة باستخدام طريقة التشفير الضمني. معظم الإصدارات اللاحقة من Re-Pair مبنية على هذا الإصدار.
التشفير [ 3 ]	2013		بدلاً من طريقة التشفير الضمنية، يستخدم هذا التنفيذ طريقة تحويل الطول المتغير إلى الطول الثابت، حيث يتم تشفير كل قاعدة (ممثلة بسلسلة ذات طول متغير) باستخدام رمز ذي طول ثابت.
استخدام الذاكرة [ 4 ]	2017		تُنفَّذ الخوارزمية على مرحلتين. خلال المرحلة الأولى، تُؤخذ في الاعتبار الأزواج عالية التردد ، أي تلك التي تحدث أكثر من${\displaystyle \lceil {\sqrt {n}}/3\rceil }$في بعض الأحيان، بينما تُؤخذ أزواج التردد المنخفض في الاعتبار في الثانية. ويكمن الاختلاف الرئيسي بين المرحلتين في تطبيق قوائم الانتظار ذات الأولوية المقابلة.
الضغط [ 5 ]	2017		تُعدّل هذه النسخة طريقة اختيار الزوج التالي المراد استبداله. فبدلاً من الاكتفاء بالنظر إلى الزوج الأكثر تكراراً، تستخدم هذه النسخة أسلوباً استدلالياً يُعاقب الأزواج التي لا تتوافق مع تحليل ليمبل-زيف لسلسلة الإدخال.
الضغط [ 6 ]	2018		تُقلل هذه الخوارزمية حجم القواعد النحوية المُولّدة بواسطة Re-Pair عن طريق استبدال التكرارات القصوى أولًا. عندما يُحدد زوجٌ ما على أنه الزوج الأكثر تكرارًا، أي الزوج الذي سيتم استبداله في الخطوة الحالية من الخوارزمية، تُوسّع MR-repair هذا الزوج للعثور على أطول سلسلة نصية تتكرر بنفس عدد مرات تكرار الزوج المراد استبداله. يُشفّر التطبيق المُقدّم القواعد النحوية ببساطة عن طريق سرد القواعد كنص، لذا فإن هذه الأداة مخصصة لأغراض البحث فقط ولا يُمكن استخدامها للضغط كما هي.

• ترميز أزواج البايت
• خوارزمية سيكويتر