تحويل إلى الواجهة

تُعدّ تقنية نقل البيانات إلى المقدمة (MTF) طريقةً لترميز البيانات (عادةً ما تكون سلسلة من البايتات ) مصممة لتحسين أداء تقنيات ترميز الإنتروبيا المستخدمة في الضغط . وعند تطبيقها بكفاءة، تكون سريعةً بما يكفي لتبرير إضافتها كخطوة إضافية في خوارزمية ضغط البيانات .

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

تتلخص الفكرة الرئيسية في استبدال كل رمز في البيانات بفهرسه في قائمة "الرموز المستخدمة مؤخرًا". على سبيل المثال، تُستبدل السلاسل الطويلة من الرموز المتطابقة بعدد مماثل من الأصفار، بينما يُستبدل الرمز الذي لم يُستخدم لفترة طويلة برقم كبير. وهكذا، تتحول البيانات في النهاية إلى سلسلة من الأعداد الصحيحة؛ وإذا كانت البيانات تُظهر الكثير من الارتباطات المحلية، فإن هذه الأعداد الصحيحة تميل إلى أن تكون صغيرة.

لنقدم وصفًا دقيقًا. لنفترض، تبسيطًا للأمر، أن الرموز في البيانات هي بايتات . يتم ترميز كل قيمة بايت بواسطة فهرسها في قائمة من البايتات، تتغير خلال تنفيذ الخوارزمية. تكون القائمة في البداية مرتبة حسب قيمة البايت (0، 1، 2، 3، ...، 255). لذلك، يتم دائمًا ترميز البايت الأول بقيمته الخاصة. مع ذلك، بعد ترميز بايت، تُنقل قيمته إلى بداية القائمة قبل الانتقال إلى البايت التالي.

سيوضح مثالٌ كيفية عمل التحويل. تخيل أننا بدلاً من البايتات، نقوم بتشفير القيم بالأحرف من a إلى z. نريد تحويل التسلسل التالي:

موزااا

بحسب الاصطلاح، تكون القائمة مبدئيًا (abcdefghijklmnopqrstuvwxyz). الحرف الأول في التسلسل هو b، والذي يظهر في الفهرس 1 (يتم ترقيم القائمة من 0 إلى 25). نضع القيمة 1 في دفق الإخراج.

1

ينتقل الحرف b إلى بداية القائمة، مُنتجًا (bacdefghijklmnopqrstuvwxyz). الحرف التالي هو a، والذي يظهر الآن في الفهرس 1. لذا نضيف 1 إلى سلسلة الإخراج. لدينا:

1.1

ونعيد الحرف "أ" إلى أعلى القائمة. وبمتابعة هذه العملية، نجد أن التسلسل مُشفّر كما يلي:

1,1,13,1,1,1,0,0

من السهل ملاحظة أن عملية التحويل قابلة للعكس. ببساطة، احتفظ بالقائمة نفسها وقم بفك التشفير عن طريق استبدال كل فهرس في التدفق المُشفّر بالحرف الموجود في ذلك الفهرس في القائمة. لاحظ الفرق بين هذه الطريقة وطريقة التشفير: يتم استخدام الفهرس في القائمة مباشرةً بدلاً من البحث عن كل قيمة للحصول على فهرسها.

أي أنك تبدأ من جديد بـ (abcdefghijklmnopqrstuvwxyz). تأخذ الرقم "1" من الكتلة المشفرة وتبحث عنه في القائمة، ما ينتج عنه "b". ثم تنقل "b" إلى البداية ما ينتج عنه (bacdef...). ثم تأخذ الرقم "1" التالي، وتبحث عنه في القائمة، ما ينتج عنه "a"، وتنقل "a" إلى البداية... وهكذا.

تُعدّ تفاصيل التنفيذ مهمة للأداء، وخاصةً لفك التشفير. أما بالنسبة للتشفير، فلا توجد ميزة واضحة لاستخدام قائمة مرتبطة ، لذا فإن استخدام مصفوفة لتخزين القائمة مقبول، مع أداء في أسوأ الحالات O ( nk )، حيث n هو طول البيانات المراد تشفيرها و k هو عدد القيم (وهو ثابت عادةً في أي تنفيذ) .

يكون الأداء النموذجي أفضل لأن الرموز المستخدمة بكثرة تكون على الأرجح في المقدمة، مما يؤدي إلى نتائج أسرع. وهذه هي الفكرة الأساسية وراء قائمة التنظيم الذاتي "نقل إلى المقدمة" .

ومع ذلك، بالنسبة لفك التشفير، يمكننا استخدام هياكل بيانات متخصصة لتحسين الأداء بشكل كبير.

from collections.abc import Generator , Iterableclass MoveToFront : """  >>> mtf = MoveToFront()  >>> list(mtf.encode("Wikipedia"))  [87, 105, 107, 1, 112, 104, 104, 3, 102]  >>> mtf.decode([87, 105, 107, 1, 112, 104, 104, 3, 102])  'Wikipedia'  >>> list(mtf.encode("wikipedia"))  [119, 106, 108, 1, 113, 105, 105, 3, 103]  >>> mtf.decode([119, 106, 108, 1, 113, 105, 105, 3, 103])  'wikipedia'  """ def __init__ ( self , common_dictionary : Iterable [ int ] = range ( 256 )): """  بدلاً من إرسال قاموس "أصلي" دائمًا،  من الأسهل الاتفاق على مجموعة أولية.  هنا نستخدم 256 قيمة ممكنة للبايت.  """ # استهلاك القاموس القابل للتكرار بحيث يمكن استخدامه عدة مرات self . common_dictionary = list ( common_dictionary )def encode ( self , plain_text : str ) -> Generator [ int ]: # تغيير القاموس المشترك فكرة سيئة. أنشئ نسخة منه . dictionary = list ( self.common_dictionary )# اقرأ كل حرف من النص العادي باستخدام ` for c in plain_text.encode ( "latin-1" ): ` # غيّر إلى بايتات لـ 256. # ابحث عن رتبة الحرف في القاموس [O(k)] rank = dictionary.index ( c ) # الحرف المُشفّر yield rank# تحديث القاموس [Θ ( k ) للإدراج ] dictionary.pop ( rank ) dictionary.insert ( 0 , c )دالة فك التشفير ( الذات ، البيانات_المضغوطة : Iterable [ int ] ) -> str : """  دالة عكسية لاستعادة النص الأصلي  """ القاموس = قائمة ( الذات.القاموس_المشترك ) النص_الأصلي = [ ]# اقرأ كل رتبة في النص المشفر for rank in compressed_data : # احذف الحرف الذي يمثل تلك الرتبة من القاموس e = dictionary . pop ( rank ) plain_text . append ( e )# أدرج الحرف في بداية القاموس dictionary.insert ( 0 , e )return bytes ( plain_text ) .decode ( "latin-1" ) # إرجاع السلسلة الأصلية

from itertools import chainدالة block32 ( x ): تُرجع النطاق ( x ، x + 32 )class MoveToFrontMoreCommon ( MoveToFront ): """  >>> mtf = MoveToFrontMoreCommon()  >>> list(mtf.encode("Wikipedia"))  [55, 10, 12, 1, 17, 9, 9, 3, 7]  """ def __init__ ( self ): super () . __init__ ( chain ( # فرز كتل ASCII: block32 ( ord ( "a" ) - 1 ), # أولًا الأحرف الصغيرة، block32 ( ord ( "A" ) - 1 ), # ثم الأحرف الكبيرة، block32 ( ord ( "!" ) - 1 ), # علامات الترقيم/الأرقام، block32 ( 0 ), # رموز التحكم، range ( 128 , 256 ), # وأخيرًا العناصر غير ASCII ) )إذا كان __name__ يساوي " __main__" : استورد doctest doctest.testmod ( )

تستفيد خوارزمية تحويل MTF من الارتباط المحلي للترددات لتقليل إنتروبيا الرسالة. في الواقع، تبقى الأحرف المستخدمة مؤخرًا في مقدمة القائمة؛ وإذا أظهر استخدام الأحرف ارتباطات محلية، فسيؤدي ذلك إلى ظهور عدد كبير من الأرقام الصغيرة مثل "0" و"1" في الناتج.

ومع ذلك، لا تُظهر جميع البيانات هذا النوع من الارتباط المحلي، وبالنسبة لبعض الرسائل، قد يؤدي تحويل MTF في الواقع إلى زيادة الإنتروبيا.

يُعدّ استخدام تحويل MTF في ضغط البيانات باستخدام تحويل Burrows-Wheeler من أهم استخداماته . يتميز تحويل Burrows-Wheeler بقدرته الفائقة على إنتاج تسلسل يُظهر ترابطًا محليًا في الترددات بين النصوص وأنواع بيانات أخرى محددة. ويُحسّن الضغط بشكل كبير من خلال تطبيق تحويل MTF بعد تحويل Burrows-Wheeler قبل خطوة ترميز الإنتروبيا النهائية.

• يُستخدم مصطلح "نقل إلى المقدمة" (MTF) أيضًا في سياق مختلف قليلًا، كنوع من القوائم المرتبطة الديناميكية . في قائمة MTF، يُنقل كل عنصر إلى المقدمة عند الوصول إليه. ^{[ 4 ]} وهذا يضمن، بمرور الوقت، سهولة الوصول إلى العناصر الأكثر استخدامًا.

• "انتقل إلى الأمام" بقلم أرتورو سان إيميتيريو كامبوس