ترميز طول التشغيل

ترميز طول التشغيل ( RLE ) هو شكل من أشكال ضغط البيانات بدون فقدان، حيث تُخزَّن سلاسل البيانات (التكرارات المتتالية لنفس قيمة البيانات) كقيمة واحدة وعدد مرات تكرارها، بدلاً من تخزينها كسلسلة أصلية. على سبيل المثال، يمكن اختصار سلسلة "أخضر أخضر أخضر أخضر أخضر" في صورة مكونة من نقاط ملونة إلى "أخضر × 5".

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

قد يشير مصطلح RLE أيضًا إلى تنسيقات صور محددة تستخدم هذا الترميز. يُعد RLE تنسيقًا مبكرًا لملفات الرسومات، كان مدعومًا من قِبل CompuServe لضغط الصور بالأبيض والأسود، وقد حل محله لاحقًا تنسيق تبادل الرسومات (GIF). وهو أيضًا اسم تنسيق صور قليل الاستخدام في نظام التشغيل Windows 3.x ، يُحفظ بامتداد الملف .RLE rle، ويتكون من صورة نقطية مُرمّزة بطول التشغيل؛ وقد استُخدم كتنسيق لشاشة بدء تشغيل Windows 3.x.

استُخدمت تقنيات ترميز طول التشغيل (RLE) في نقل إشارات التلفزيون التناظرية منذ عام 1967. ^{[ 1 ]} وفي عام 1983، حصلت شركة هيتاشي على براءة اختراع لترميز طول التشغيل . ^{[ 2 ] [ 3 ] [ 4 ]} يُعدّ ترميز طول التشغيل مناسبًا بشكل خاص للصور النقطية المعتمدة على لوحة الألوان (التي تستخدم عددًا قليلًا نسبيًا من الألوان) مثل أيقونات الكمبيوتر ، وكان طريقة شائعة لضغط الصور في الخدمات الإلكترونية المبكرة مثل CompuServe قبل ظهور تنسيقات أكثر تطورًا مثل GIF . ^{[ 5 ]} لا يُجدي نفعًا مع الصور ذات التدرج اللوني المتواصل (التي تستخدم عددًا كبيرًا جدًا من الألوان) مثل الصور الفوتوغرافية، على الرغم من أن JPEG يستخدمه على المعاملات المتبقية بعد تحويل كتل الصورة وتكميمها .

تشمل التنسيقات الشائعة لبيانات الترميز اللوني Truevision TGA و PackBits (من Apple، المستخدم في MacPaint ) و PCX و ILBM . كما يصف الاتحاد الدولي للاتصالات معيارًا لترميز الألوان في أجهزة الفاكس ، يُعرف باسم T.45. ^{[ 6 ]} يُعدّ معيار ترميز ألوان الفاكس هذا، الذي يُدمج مع تقنيات أخرى في ترميز هوفمان المُعدّل ، فعالًا نسبيًا لأن معظم المستندات المرسلة عبر الفاكس تتكون أساسًا من مساحات بيضاء، مع وجود فواصل سوداء بين الحين والآخر.

يبلغ تعقيد المساحة لـ RLE ⁠${\displaystyle O(n)}$، حيث n هو حجم بيانات الإدخال.

from itertools import repeat , compress , groupbydef ilen ( iterable ): """  يُرجع عدد العناصر الموجودة في العنصر القابل للتكرار. >>> ilen(x for x in range(1000000) if x % 3 == 0)  333334  """ # استخدام zip() لتغليف المدخلات بأزواج أحادية، والتي تقرأها compress() كقيم صحيحة. return sum ( compress ( repeat ( 1 ), zip ( iterable )))

def rle_encode ( iterable , * , length_first = True ): """  >>> "".join(rle_encode("AAAABBBCCDAA"))  '4A3B2C1D2A'  >>> "".join(rle_encode("AAAABBBCCDAA", length_first=False))  'A4B3C2D1A2'  """ return ( f " { ilen ( g ) }{ k } " if length_first else f " { k }{ ilen ( g ) } " # ilen(g): طول الكائن القابل للتكرار g for k , g in groupby ( iterable ) )

from itertools import chain , repeat , batched

def rle_decode ( iterable , * , length_first = True ): """  >>> "".join(rle_decode("4A3B2C1D2A"))  'AAAABBBCCDAA'  >>> "".join(rle_decode("A4B3C2D1A2", length_first=False))  'AAAABBBCCDAA'  """ return chain.from_iterable ( repeat ( b , int ( a ) ) if length_first else repeat ( a , int ( b ) ) for a , b in batched ( iterable , 2 ) )

تخيل شاشة تحتوي على نص أسود عادي على خلفية بيضاء. ستلاحظ وجود العديد من سلاسل البكسلات البيضاء الطويلة في المساحة الفارغة، والعديد من سلاسل البكسلات السوداء القصيرة داخل النص. قد يُقرأ سطر المسح الافتراضي ، حيث يُمثل B بكسلًا أسود و W بكسلًا أبيض، على النحو التالي:

WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

بتطبيق خوارزمية ضغط البيانات باستخدام ترميز طول التشغيل (RLE) على خط المسح الافتراضي المذكور أعلاه، يمكن عرضه على النحو التالي:

12W1B12W3B24W1B14W

يمكن تفسير هذا على أنه تسلسل من اثني عشر حرفًا من نوع W، ثم حرف واحد من نوع B، ثم اثني عشر حرفًا من نوع W، ثم ثلاثة أحرف من نوع B، وهكذا، وهو يمثل الأحرف الـ 67 الأصلية في 18 حرفًا فقط. مع أن التنسيق الفعلي المستخدم لتخزين الصور هو عادةً تنسيق ثنائي وليس تنسيق ASCII كما في هذا المثال، إلا أن المبدأ يبقى نفسه. حتى ملفات البيانات الثنائية يمكن ضغطها بهذه الطريقة؛ إذ غالبًا ما تحدد مواصفات تنسيق الملفات وجود بايتات متكررة في الملفات كمساحة حشو. مع ذلك، تستخدم طرق الضغط الأحدث، مثل DEFLATE، خوارزميات تعتمد على LZ77 ، وهي تعميم لترميز طول التشغيل، والذي يمكنه الاستفادة من سلاسل الأحرف المتتالية (مثل BWWBWWBWWBWW).

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

WW12BWW12BB3WW24BWW14

سيتم تفسير هذا على أنه سلسلة من اثني عشر حرف W، وحرف B، وسلسلة من اثني عشر حرف W، وسلسلة من ثلاثة أحرف B، وما إلى ذلك. في البيانات التي تكون فيها السلاسل أقل تكرارًا، يمكن أن يؤدي هذا إلى تحسين معدل الضغط بشكل كبير.

هناك مسألة أخرى تتعلق بتطبيق خوارزميات ضغط إضافية. فحتى مع استخراج التسلسلات، قد تكون ترددات الأحرف المختلفة كبيرة، مما يسمح بمزيد من الضغط؛ إلا أنه إذا كُتبت أطوال التسلسلات في الملف في المواقع التي حدثت فيها، فإن وجود هذه الأرقام يعيق التدفق الطبيعي ويجعل الضغط أكثر صعوبة. وللتغلب على هذه المشكلة، تفصل بعض برامج ترميز أطوال التسلسلات البيانات ورموز الهروب عن أطوال التسلسلات، بحيث يمكن التعامل مع كليهما بشكل مستقل. بالنسبة لبيانات المثال، سينتج عن ذلك مخرجان: السلسلة النصية " WWBWWBBWWBWW" والأرقام ( 12,12,3,24,14).

• معالجة البيانات التسلسلية من اليسار إلى اليمين: تعالج هذه الطريقة البيانات سطرًا سطرًا، بالمسح من اليسار إلى اليمين. وهي شائعة الاستخدام في ضغط الصور. تشمل الاختلافات الأخرى لهذه التقنية مسح البيانات عموديًا أو قطريًا أو على شكل كتل.
• تقنية RLE مع فقدان البيانات: في هذا النوع، يتم حذف بعض البتات عمدًا أثناء الضغط (غالبًا عن طريق ضبط بت أو اثنين مهمين من كل بكسل إلى 0). يؤدي هذا إلى معدلات ضغط أعلى مع تأثير ضئيل على الجودة المرئية للصورة.
• تقنية RLE التكيفية: تستخدم أنظمة ترميز مختلفة تبعًا لطول عمليات التشغيل لتحسين نسب الضغط. على سبيل المثال، قد تستخدم عمليات التشغيل القصيرة تنسيق ترميز مختلفًا عن عمليات التشغيل الطويلة.

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

• ترميز طول التشغيل مُطبق في لغات برمجة مختلفة (على برنامج Rosetta Code )
• مكتبة ترميز طول التشغيل ذات الرأس الواحد هي أصغر تطبيق ممكن (حوالي 20 SLoC) في ANSI C. FOSS، متوافقة مع Truevision TGA ، وتدعم عناصر 8 و16 و24 و32 بت أيضًا.