الترميز إنتروبي RANS أو كيفية كتابة أرشيفك الخاص

قد تكون هذه المقالة مثيرة للاهتمام لأولئك الذين يشاركون في ضغط البيانات أو يرغبون في كتابة أرشيفهم الخاص.



المقالة مكتوبة بشكل أساسي على مواد المدونة ، التي يحتفظ بها فابيان جيسن.

مقدمة

طريقة ترميز entropy rans ( r ange + ANS) هي أخوة خوارزمية FSE ، التي كتبت عنها سابقًا . اختصار ANS يعني أنظمة الأرقام غير المتماثلة ، ومجموعة الكلمات في الاسم تشير إلى تشابه هذه الطريقة مع الترميز الفاصل . مؤلف RANS هو Yarek Duda .

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

أولاً ، سيكون هناك جزء "نظري" طويل ، ثم سنحاول كتابة أرشيف بسيط.

وصف الطريقة

يتم تحديد تشغيل الخوارزمية بواسطة الصيغ البسيطة التالية:

الترميز: C(s,x): x := (x / Fs) * M + Bs + (x % Fs)
فك التشفير: D(x): s = sym[x % M], x := Fs * (x / M) + (x % M) - Bs

دعنا نحللهم بالتفصيل.

تستقبل وظيفة التشفير C (s، x) الحرف s المراد ترميزه (دعه يكون عددًا صحيحًا) والحالة الحالية لجهاز التشفير x (عدد صحيح أيضًا).

F _s - تردد الرمز s . القسمة على Fs أعلاه هي عدد صحيح.
M هي مجموع ترددات جميع رموز الأبجدية ( M = Σ F _s ).
في _s ، بداية الفاصل الزمني المقابل للحرف المشفر (في الشكل أدناه).
x ٪ Fs هي باقي قسمة x على F _s .

مبدأ التشغيل هو نفسه كما هو الحال في الترميز الحسابي : نأخذ المقطع [ 0 ، M) ونقسمه إلى أجزاء بحيث يتوافق كل حرف مع فاصل مساوي في الحجم لتردد الحرف F _s . يدل حدوث القيمة x٪ M في أي فاصل زمني على تشفير الرمز المقابل.


في بداية الترميز ، قم بتهيئة x بقيمة مناسبة تعسفية ، ثم احسب الدالة C (s ، x) لجميع الأحرف المشفرة بالتسلسل.

يزيد كل حساب للوظيفة C (s، x) من قيمة x . عندما يصبح حجمها أكبر من اللازم ، يجب عليك تفريغ البيانات في الإخراج:

 while (x >= x_max) {   writeToStream(x % b); //     x /= b; //  x } 

وتسمى هذه الخطوة إعادة التعمير . بعد ذلك ، يمكنك متابعة الترميز.

في الأعلى في الكود ، ظهرت ثوابت جديدة: x_max و b . من الناحية النظرية ، ترتبط الأرقام M و b و x_max ببعض العلاقات ، ولكن في الممارسة العملية يكون من الأكثر فعالية استخدام القيم التالية إذا تم استخدام الحالة uint32 للحالة x :

M = 2 ^ k ، حيث k <= 16
ب = 2 ^ 16 (نصف حجم uint32)

يرجع اختيار M = 2 ^ k إلى حقيقة أن هناك قسمة على M في وظيفة فك التشفير ، لذلك يمكن استبدال القسمة مع الباقي بعمليات bitwise.

يتم تحديد قيمة k من الاعتبارات التالية: كلما كانت أكبر ، كانت دقة F _s أعلى والضغط أكثر فعالية. في هذه الحالة ، يجب أن تؤخذ بعض النفقات العامة لتخزين جدول التردد في الاعتبار ، لذلك لا يستحق دائمًا استخدام القيم القصوى k .

يجب أن تكون قيمة x_max بحيث لا يحدث تجاوز سعة. استنادًا إلى وظيفة الترميز ، نحصل على x < uint32_max * Fs / M أو بطريقة مختلفة قليلاً: x_max <= ( b * L ) * Fs / M ، حيث L <= uint32_max / b . في الكود الحقيقي ، تأخذ الحالة النموذج x / b> = L / M * Fs لتجنب تجاوز السعة في العمليات الحسابية.

يتم اختيار القيمة b = 2 ^ 16 (نصف حجم uint32) بطريقة بحيث إذا تجاوز x x_max ، فقسمة واحدة ب هي كافية لمواصلة العمل. نتيجة لذلك ، ستنتهي while التكرار بعد التكرار الأول ، مما يعني أنه يمكن استبدالها بحرف if بسيط.

نتيجة لذلك ، تأخذ وظيفة الترميز الشكل التالي:

 typedef uint32_t RansState; constexpr uint32_t RANS_L = 1u << 16; constexpr uint32_t k = 10; //   constexpr uint32_t RANS_M = 1u << k; // M = 2^k //   s void RansEnc(RansState& x, uint32_t s, RansOutBuf& out) {   assert(x >= RANS_L); //        uint32 Fs = freq[s]; //   s   uint32 Bs = range_start[s]; //   s   assert(Fs > 0 && Fs <= RANS_M);     // renormalize   if ((x >> 16) >= (RANS_L >> k) * Fs) { // x / b >=  L / M * Fs       out.put( x & 0xffff );       x >>= 16;   }   x = ((x / Fs) << k) + Bs + (x % Fs); // C(s,x)     assert(x >= RANS_L); //      } 

في نهاية الترميز ، يجب عليك حفظ قيمة x ، لأن فك التشفير سيبدأ منه. ونعم ، سنقوم بفك تشفيرها من النهاية إلى البداية ، أي من آخر حرف مشفر إلى أول. (في مقالة حول FSE ، يتم شرح هذه النقطة بتفاصيل كافية.)

أريد أن أتحدث أكثر قليلاً عن كيفية عمل صيغة الترميز.

 x := (x / Fs) * M + Bs + (x % Fs) 

بعد الحوسبة ( x / Fs) * M ، يحتوي المتغير x على وحدات البت الأقل أهمية (تذكر أن M = 2 ^ k ). تضيف إضافة + Bs + (x % Fs) أساسًا إلى هذه البتات قيمة معينة من الفاصل الزمني للحرف s ، لأن Bs هو بداية الفاصل الزمني ، و (x٪ Fs) هو الرقم داخل هذه الفترة الزمنية (حجم الفاصل الزمني هو Fs). وبالتالي ، عند فك التشفير ، يمكننا تحديد الحرف المشفر بواسطة الفاصل الزمني الذي يقع فيه (x٪ M).

فك التشفير

دعنا ننتقل إلى وظيفة فك التشفير.

 D(x): s = sym[x % M], x := Fs * (x / M) + (x % M) - Bs 

كما فهمنا أعلاه ، يتم تحديد الحرف المرغوب به بواسطة باقي القسم x ٪ M. في الفترة الفاصلة التي انخفضت فيها القيمة (٪ x) ، تم تشفير هذه الشخصية.

في وقت سابق ، حددنا على وجه التحديد M = 2 ^ k لتبسيط وظيفة فك التشفير. انتهى الأمر مثل هذا:

 uint32_t RansDecode(RansState& x, RansInBuf& in) {   assert(x >= RANS_L); //       uint32_t x_mod = x & (RANS_M - 1); // = x % M   //  ,    x_mod,     assert(x_mod < dct.size());   uint32_t s = dct[x_mod]; //     uint32 Fs = freq[s]; //   s   uint32 Bs = range_start[s]; //    s   x = (x >> k) * Fs + x_mod - Bs;     // renormalize   if (x < RANS_L) {       x = (x << 16) | in.read16(); //  16    }     assert(x >= RANS_L); //     return s; } 

يبدأ فك التشفير بنفس x الذي تم الحصول عليه في نهاية التشفير. للقيام بذلك ، يجب حفظه مع البيانات المشفرة.

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

كما ترون ، فك التشفير يعمل بشكل أسرع من الترميز ، حيث لا توجد عمليات تقسيم.

أصعب لحظة في وظيفة فك التشفير هي طريقة تحديد الفاصل الزمني للقيمة التي انخفضت (x٪ M).

الطريقة الأسهل والأسرع هي استخدام الجدول sym [] ، الحجم M. في هذه الحالة ، نحصل على جدول من نفس الحجم كما هو الحال في خوارزمية FSE ، مع اختلاف أنه في rANS ، لا يتم "خلط" الجدول ، والأحرف مرتبة ، ومثل هذا الجدول سهل الإنشاء.

العيب الرئيسي لهذا النهج هو حجم الجدول sym ، الذي ينمو أضعافا مضاعفة مع زيادة ك .

طريقة الاسم المستعار

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


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

وبطبيعة الحال ، يجب أن تكون M قابلة للقسمة على N. وإذا تذكرنا أن لدينا M = 2 ^ k ، فإن حجم الأبجدية يتحول أيضًا إلى قوة اثنين. هذه ليست مشكلة ، حيث يمكنك دائمًا استكمال الحروف الأبجدية بالحجم المرغوب بأحرف غير مستخدمة بتردد صفري.

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

ليس من الصعب تحديد الفاصل الزمني المطلوب: قسّم x على N ، وسقط في أحد الأزواج. بعد ذلك ، نقوم بمقارنة باقي تقسيم x٪ N بالحد الفاصل بين القطاعات في زوج ونقع في فاصل زمني أو في آخر.

نحاول في الممارسة

سوف نستخدم كود المثال النهائي .

نأخذ البيانات للضغط من الملف:

 size_t in_size; uint8_t* in_bytes = read_file("book1", &in_size); 

1. تحتاج أولاً إلى تحديد بنية البيانات .

نستخدم الخيار الأبسط: سنقوم بترميز بايت واحد باستخدام الأبجدية [0 ... 255].

2. الخطوة التالية هي تحديد تواتر حروف الأبجدية:

(دالة stats.count_freqs )

 for (size_t i = 0; i < in_size; i++) {   freqs[in_bytes[i]]++; } 

3. لذلك ، لدينا ترددات الرموز ، ولكن الآن يجب تطبيعها ، أي ، يتم تخفيضها (أو زيادتها) بشكل متناسب بحيث نحصل في المجموع على M = 2 ^ k. هذه ليست مهمة بسيطة كما قد تبدو ، لذلك نستخدم وظيفة جاهزة:

 stats.normalize_freqs(...); 

بالمناسبة ، تحتاج إلى تحديد قيمة ك . نظرًا لأن الحروف الأبجدية لدينا تتكون من 256 حرفًا ، فلا ينبغي أن تؤخذ k أقل من 8 أحرف. أولاً ، خذ الحد الأقصى - 16 ، ثم جرب القيم الأخرى لاحقًا.

4. بناء الجدول الاسم المستعار :

 stats.make_alias_table(); 

5. نحن ترميز من النهاية ، ثم فك التشفير بالترتيب الطبيعي.

 RansState rans; //  rANS,    x RansEncInit(&rans); //    uint8_t* ptr = out_buf + out_max_size; // *end* of output buffer for (size_t i = in_size; i > 0; i--) { // NB: working in reverse!   int s = in_bytes[i - 1];   RansEncPutAlias(&rans, &ptr, &stats, s, prob_bits); } //   .     . RansEncFlush(&rans, &ptr); 

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

كما وعدنا أعلاه ، دعونا نلقي نظرة على نتائج الضغط لقيم مختلفة من k (في الكود هو prob_bits ) ، مع مراعاة الزيادة في الحجم بسبب تسجيل جدول التردد:

( حجم ملف book1 الأصلي: 768771)
ك = 16: 435059 + 512 = 435571 بايت
ك = 15 : 435078 + 480 = 435558 بايت
ك = 14: 435113 + 448 = 435561 بايت
ك = 13: 435239 + 416 = 435655 بايت
ك = 12: 435603 + 384 = 435987 بايت
ك = 11: 436530 + 352 = 436882 بايت
ك = 10: 440895 + 320 = 441215 بايت
ك = 9: 453418 + 288 = 453706 بايت
ك = 8: 473126 + 256 = 473382 بايت

يمكنك أن ترى أن ارتفاع ك ، وأفضل الضغط. لكن عند نقطة معينة (عند k = 16) ، يبدأ الحمل الإضافي لجدول التردد في تفوق فوائد زيادة الدقة. إذا قمت بضغط ملف أصغر ، فسيظهر هذا التأثير على حجم أصغر.

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

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

خاتمة

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

عند تطوير الألعاب في Playrix ، نعتمد غالبًا على الحاجة إلى تقليل حجم الإنشاء. تتطور الألعاب باستمرار ، ويتزايد حجم المحتوى ، والمساحة محدودة.

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

عند تطوير خوارزميات الضغط ، فإن أداة ترميز entropy عالمية ، مثل rANS أو FSE ، هي أداة لا غنى عنها. يتطلب الأمر تمامًا مهمة كتابة الأحرف بأقل عدد من البتات ، مما يسمح للمطور بالتركيز على التفاصيل الرئيسية للخوارزمية. وأيضا يعمل بسرعة كبيرة سواء في الترميز أو فك التشفير.

آمل أن يساعدك هذا المقال في التعرف على RANS والبدء في استخدامه في مشاريعك.

المراجع

يمكنك هنا الاطلاع على أمثلة عملية لتطبيق RANS (مع خيارات تحسين مختلفة):

فابيان جيسين: github.com/rygorous/ryg_rans

يمكنك قراءة تفاصيل وتفاصيل مثيرة للاهتمام على مدونة فابيان (باللغة الإنجليزية):

→ rans تلاحظ
→ rans مع توزيعات الاحتمالات الثابتة
→ فرسان في الممارسة العملية