أنظمة الأرقام غير المتناظرة

📅 آخر تحديث: ٢٨ يوليو ٢٠٢٦
✍️ نُشر في: ٢٨ يوليو ٢٠٢٦
📷 يحتوي على 75 صور
الموسوعة الحرة

تُعدّ أنظمة الأرقام غير المتناظرة ( ANS ) [ 1 ] [ 2 ] عائلةً من طرق ترميز الإنتروبيا، قدّمها ياروسلاف (جاريك) دودا [ 3 ] من جامعة ياغيلونيا ، وتُستخدم في ضغط البيانات منذ عام 2014 [ 4 ] نظرًا لأدائها المُحسّن مقارنةً بالطرق السابقة. [ 1 ] تجمع أنظمة الأرقام غير المتناظرة بين نسبة ضغط الترميز الحسابي (الذي يستخدم توزيعًا احتماليًا دقيقًا تقريبًا )، وتكلفة معالجة مماثلة لترميز هوفمان . [ 1 ] في صيغة أنظمة الأرقام غير المتناظرة المُجدولة (tANS)، يتحقق ذلك من خلال إنشاء آلة ذات حالات محدودة للعمل على أبجدية كبيرة دون استخدام الضرب. [ 2 ]

من بين أمور أخرى، يُستخدم ANS في ضاغط Zstandard الخاص بفيسبوك [ 2 ] [ 3 ] (ويُستخدم أيضًا، على سبيل المثال ، في نواة لينكس [ 4 ] ، ومتصفح جوجل كروم [ 5 ] ، ونظام التشغيل أندرويد [ 6 ] ، وقد نُشر كمعيار RFC 8478 لـ MIME [ 7 ] و HTTP [ 8 ] )، وضاغط LZFSE الخاص بآبل [ 9 ] ، وضاغط Draco 3D الخاص بجوجل [ 10 ] (يُستخدم، على سبيل المثال، في تنسيق وصف المشهد العالمي من بيكسار [ 11 ] )، وضاغط صور PIK [ 12 ] ، وضاغط CRAM DNA [ 13 ] من أدوات SAMtools [ 14 ] ، ومكتبة ضغط NVIDIA nvCOMP عالية السرعة [ 15 ] ، وضاغط DivANS الخاص بدروب بوكس ​​[ 16 ] ، وضاغط نسيج BCPack الخاص بمايكروسوفت DirectStorage [ 17 ] ، و JPEG XL طويل المدى [ 18 ] ، وJPEG AI القائم على التعلم [ 19 ]. برامج ضغط الصور. 

الفكرة الأساسية هي ترميز المعلومات في عدد طبيعي واحدx{\displaystyle x}[ ‡ 2 ] في نظام الأرقام الثنائية القياسي، يمكننا إضافة بتs∈{0،1}{\displaystyle s\in \{0,1\}}معلومات لـx{\displaystyle x}عن طريق الإلحاقs{\displaystyle s}في نهايةx{\displaystyle x}وهذا يعطيناx′=2x+s{\displaystyle x'=2x+s}بالنسبة لمشفّر الإنتروبيا، يكون هذا هو الأمثل إذابرو(0)=برو(1)=1/2{\displaystyle \Pr(0)=\Pr(1)=1/2}تعمم ANS هذه العملية لمجموعات الرموز العشوائيةs∈S{\displaystyle s\in S}مع توزيع احتمالي مصاحب(صs)s∈S{\displaystyle (p_{s})_{s\in S}}في نظام الإجابة على الأسئلة، إذا كانت المعلومات منs{\displaystyle s}يُلحق بـx{\displaystyle x}لينتج عن ذلكx′{\displaystyle x'}، ثمx′≈x⋅صs-1{\displaystyle x'\approx x\cdot p_{s}^{-1}}أو بعبارة أخرى،سجل2⁡(x′)≈سجل2⁡(x)+سجل2⁡(1/صs){\displaystyle \log _{2}(x')\approx \log _{2}(x)+\log _{2}(1/p_{s})}، أينسجل2⁡(x){\displaystyle \log _{2}(x)}يمثل عدد بتات المعلومات المخزنة في الرقمx{\displaystyle x}، وسجل2⁡(1/صs){\displaystyle \log _{2}(1/p_{s})}يمثل عدد البتات الموجودة في الرمزs{\displaystyle s}. [ ‡ 2 ]

بالنسبة لقاعدة التشفير، تُقسّم مجموعة الأعداد الطبيعية إلى مجموعات فرعية منفصلة تُقابل رموزًا مختلفة - مثل الأعداد الزوجية والفردية - ولكن بكثافات تتوافق مع التوزيع الاحتمالي للرموز المراد تشفيرها. ثم تُضاف المعلومات من الرمز s{\displaystyle s}في المعلومات المخزنة بالفعل في الرقم الحاليx{\displaystyle x}ننتقل إلى الرقمx′=ج(x،s)≈x/ص{\displaystyle x'=C(x,s)\approx x/p}كونه موقعx{\displaystyle x}الظهور رقم - منs{\displaystyle s}المجموعة الفرعية رقم -th. [ ‡ 2 ]

توجد طرق بديلة لتطبيقها عمليًا - صيغ رياضية مباشرة لخطوات التشفير وفك التشفير (متغيرات uABS و rANS)، أو يمكن وضع السلوك بأكمله في جدول (متغير tANS). [ ‡ 1 ] تُستخدم إعادة التطبيع لمنع x{\displaystyle x}الانتقال إلى ما لا نهاية - نقل البتات المتراكمة من وإلى تدفق البتات. [ ‡ 2 ] 

ترميز الإنتروبيا

لنفترض أننا نريد ترميز سلسلة من 1000 صفر وواحد، وهو ما يتطلب 1000 بت لتخزينها مباشرةً. ولكن، إذا عُلم بطريقة ما أنها تحتوي على صفر واحد فقط و999 واحدًا، فسيكون كافيًا ترميز موضع الصفر، وهو ما يتطلب فقط⌈سجل2⁡(1000)⌉≈10{\displaystyle \lceil \log _{2}(1000)\rceil \approx 10}بتات هنا بدلاً من الألف بت الأصلية.

بشكل عام، مثل هذه المتتاليات ذات الطولن{\displaystyle n}يحتوي علىصن{\displaystyle pn}أصفار و(1-ص)ن{\displaystyle (1-p)n}واحد، لبعض الاحتمالاتص∈(0،1){\displaystyle p\in (0,1)}تُسمى هذه المجموعات بالتوافيق . وباستخدام تقريب ستيرلينغ، نحصل على عددها التقاربي وهو

(نصن)≈2نح(ص) للكبير ن و ح(ص)=-صسجل2⁡(ص)-(1-ص)سجل2⁡(1-ص)،{\displaystyle {n \choose pn}\approx 2^{nh(p)}{\text{ لقيم n الكبيرة و }}h(p)=-p\log _{2}(p)-(1-p)\log _{2}(1-p),}

تسمى إنتروبيا شانون . [ 20 ]

لذا، لاختيار إحدى هذه المتتاليات، نحتاج تقريبًا إلىنح(ص){\displaystyle nh(p)}أجزاء. لا يزالن{\displaystyle n}بتات إذاص=1/2{\displaystyle p=1/2}ومع ذلك، يمكن أن يكون أصغر بكثير. على سبيل المثال، نحتاج فقط≈ن/2{\displaystyle \approx n/2}قطع لـص=0.11{\displaystyle p=0.11}.

يُتيح مُشفّر الإنتروبيا ترميز سلسلة من الرموز باستخدام ما يُقارب عدد بتات إنتروبيا شانون لكل رمز. على سبيل المثال، يُمكن استخدام خوارزمية ANS مباشرةً لحصر التوليفات: تعيين عدد طبيعي مختلف لكل سلسلة من الرموز ذات النسب الثابتة بطريقة شبه مثالية. [ ‡ 2 ]

على عكس تركيبات التشفير، يتغير توزيع الاحتمالية هذا عادةً في ضواغط البيانات. ولهذا الغرض، يمكن اعتبار إنتروبيا شانون بمثابة متوسط ​​مرجح: رمز للاحتماليةص{\displaystyle p}يتضمنسجل2⁡(1/ص){\displaystyle \log _{2}(1/p)}أجزاء من المعلومات. يقوم نظام ANS بتشفير المعلومات إلى عدد طبيعي واحدx{\displaystyle x}، والتي تم تفسيرها على أنها تحتويسجل2⁡(x){\displaystyle \log _{2}(x)}معلومات جزئية. إضافة معلومات من رمز الاحتماليةص{\displaystyle p}يزيد هذا المحتوى المعلوماتي إلىسجل2⁡(x)+سجل2⁡(1/ص)=سجل2⁡(x/ص){\displaystyle \log _{2}(x)+\log _{2}(1/p)=\log _{2}(x/p)}وبالتالي، يجب أن يكون الرقم الجديد الذي يحتوي على كلتا المعلومتين هوx′≈x/ص{\displaystyle x'\approx x/p}. [ ‡ 2 ]

أمثلة محفزة

لنفترض مصدراً يتكون من 3 أحرف A وB وC، باحتمالات 1/2 و1/4 و1/4 على التوالي. من السهل إنشاء رمز البادئة الأمثل في النظام الثنائي: A = 0، B = 10، C = 11. عندئذٍ، يتم ترميز الرسالة كالتالي: ABC -> 01011.

نلاحظ أن الطريقة المكافئة لتنفيذ عملية التشفير هي كما يلي:

  • ابدأ بالرقم 1، وقم بإجراء عملية حسابية على الرقم لكل حرف من حروف الإدخال.
  • أ = اضرب في 2؛ ب = اضرب في 4، أضف 2؛ ج = اضرب في 4، أضف 3.
  • عبّر عن الرقم بالنظام الثنائي، ثم احذف الرقم الأول 1.

لنفترض مصدرًا أكثر عمومية يحتوي على k حرفًا، باحتمالات نسبيةن1/شمال،...،نك/شمال{\displaystyle n_{1}/N,...,n_{ك}/N}ثم يتطلب إجراء الترميز الحسابي على المصدر عمليات حسابية دقيقة فقط مع الأعداد الصحيحة. [ ‡ 1 ]

بشكل عام، يُعد نظام الأرقام التناظرية تقريبًا للترميز الحسابي الذي يُقارب الاحتمالات الحقيقيةر1،...،رك{\displaystyle r_{1},...,r_{k}}حسب الأعداد النسبيةن1/شمال،...،نك/شمال{\displaystyle n_{1}/N,...,n_{ك}/N}بمقام صغيرشمال{\displaystyle N}. [ ‡ 2 ]

المفاهيم الأساسية للإجابة

مقارنة بين مفهوم الترميز الحسابي (يسار) ونظام الأعداد الطبيعية (يمين). يُمكن اعتبار كليهما تعميمًا لأنظمة الأعداد القياسية، المُثلى لتوزيع احتمالي منتظم للأرقام، إلى أنظمة مُحسّنة لتوزيع احتمالي مُختار. يتوافق الترميز الحسابي أو ترميز النطاق مع إضافة معلومات جديدة في الموضع الأكثر أهمية، بينما يُعمم نظام الأعداد الطبيعية إضافة المعلومات في الموضع الأقل أهمية. قاعدة الترميز فيه هي: " ينتقل x إلى الظهور رقم x لمجموعة فرعية من الأعداد الطبيعية التي تُقابل الرمز المُرمّز حاليًا". في المثال المُقدّم، تم ترميز التسلسل (01111) إلى العدد الطبيعي 18، وهو أصغر من 47 المُستخرج باستخدام النظام الثنائي القياسي، نظرًا لتوافقه الأفضل مع ترددات التسلسل المراد ترميزه. تكمن ميزة نظام الأعداد الطبيعية في تخزين المعلومات في عدد طبيعي واحد، على عكس عددين يُحددان نطاقًا.

تخيل أن هناك بعض المعلومات مخزنة في عدد طبيعيx{\displaystyle x}على سبيل المثال، كتسلسل بتات لتوسيعها الثنائي. لإضافة معلومات من متغير ثنائيs{\displaystyle s}يمكننا استخدام وظيفة الترميزx′=ج(x،s)=2x+s{\displaystyle x'=C(x,s)=2x+s}، مما يؤدي إلى إزاحة جميع البتات موضعًا واحدًا للأعلى، ووضع البت الجديد في الموضع الأقل أهمية. الآن وظيفة فك التشفيرد(x′)=(⌊x′/2⌋،مoد(x′،2)){\displaystyle D(x')=(\lfloor x'/2\rfloor ,\mathrm {mod} (x',2))}يُتيح ذلك استعادة السابقx{\displaystyle x}وهذه الإضافة:د(ج(x،s))=(x،s)، ج(د(x′))=x′{\displaystyle D(C(x,s))=(x,s),\ C(D(x'))=x'}يمكننا أن نبدأ بـx=1{\displaystyle x=1}الحالة الأولية، ثم استخدمج{\displaystyle C}دالة على البتات المتتالية لتسلسل بتات محدود للحصول على نتيجة نهائيةx{\displaystyle x}رقم يخزن هذه السلسلة بأكملها. ثم باستخدامد{\displaystyle D}تؤدي الوظيفة عدة مرات حتىx=1{\displaystyle x=1}يسمح باسترجاع تسلسل البتات بترتيب عكسي. [ ‡ 2 ]

الإجراء المذكور أعلاه هو الأمثل لتوزيع الاحتمالات المنتظم (المتماثل) للرموز.برو(0)=برو(1)=1/2{\displaystyle \Pr(0)=\Pr(1)=1/2}. يقوم نظام ANS بتعميمه لجعله الأمثل لأي توزيع احتمالي (غير متماثل) مختار للرموز:برو(s)=صs{\displaystyle \Pr(s)=p_{s}}. بينماs{\displaystyle s}في المثال أعلاه، كان الاختيار بين الزوجي والفرديج(x،s){\displaystyle C(x,s)}في نظام ANS، يتم استبدال هذا التقسيم الزوجي/الفردي للأعداد الطبيعية بالتقسيم إلى مجموعات جزئية ذات كثافات تتوافق مع التوزيع الاحتمالي المفترض.{صs}s{\displaystyle \{p_{s}\}_{s}}: حتى الوضعx{\displaystyle x}يوجد ما يقاربxصs{\displaystyle xp_{s}}تكرارات الرمزs{\displaystyle s}. [ ‡ 2 ]

وظيفة الترميزج(x،s){\displaystyle C(x,s)}يعيدx{\displaystyle x}الظهور رقم -th من هذه المجموعة الفرعية المقابلة للرمزs{\displaystyle s}إن فرضية الكثافة تعادل الشرطx′=ج(x،s)≈x/صs{\displaystyle x'=C(x,s)\approx x/p_{s}}بافتراض أن عددًا طبيعيًاx{\displaystyle x}يتضمنسجل2⁡(x){\displaystyle \log _{2}(x)}معلومات متفرقة،سجل2⁡(ج(x،s))≈سجل2⁡(x)+سجل2⁡(1/صs){\displaystyle \log _{2}(C(x,s))\approx \log _{2}(x)+\log _{2}(1/p_{s})}ومن هنا جاء رمز الاحتماليةصs{\displaystyle p_{s}}يتم ترميزها على أنها تحتوي على≈سجل2⁡(1/صs){\displaystyle \approx \log _{2}(1/p_{s})}معلومات جزئية كما هو مطلوب من مشفري الإنتروبيا . [ ‡ 2 ]

المتغيرات

متغير ثنائي موحد (uABS)

لنبدأ بالأبجدية الثنائية وتوزيع الاحتمالاتبرو(1)=ص{\displaystyle \Pr(1)=p}،برو(0)=1-ص{\displaystyle \Pr(0)=1-p}حتى الوضعx{\displaystyle x}نريد تقريبًاص⋅x{\displaystyle p\cdot x}نظائر الأعداد الفردية (لـs=1{\displaystyle s=1}يمكننا اختيار هذا العدد من الظهورات كـ⌈x⋅ص⌉{\displaystyle \lceil x\cdot p\rceil }، الحصولs=⌈(x+1)⋅ص⌉-⌈x⋅ص⌉{\displaystyle s=\lceil (x+1)\cdot p\rceil -\lceil x\cdot p\rceil }يُطلق على هذا المتغير اسم uABS ويؤدي إلى وظائف فك التشفير والترميز التالية: [ 21 ]

فك التشفير:

s = ceil (( x + 1 ) * p ) - ceil ( x * p ) // 0 إذا كان fract(x * p) < 1 - p، وإلا 1 إذا كانت s = 0 فإن new_x = x - ceil ( x * p ) // D(x) = (new_x, 0)، وهذا هو نفسه new_x = floor(x * (1 - p)) إذا كانت s = 1 فإن new_x = ceil ( x * p ) // D(x) = (new_x, 1)

التشفير:

إذا كانت s = 0، فإن new_x = ceil (( x + 1 ) / ( 1 - p )) - 1 // C(x,0) = new_x. إذا كانت s = 1، فإن new_x = floor ( x / p ) // C(x,1) = new_x.

لص=1/2{\displaystyle p=1/2}وهو ما يعادل النظام الثنائي القياسي (مع عكس 0 و1)، لأمر مختلفص{\displaystyle p}يصبح هذا الحل الأمثل لتوزيع الاحتمالات المحدد. [ 21 ] على سبيل المثال، بالنسبة لـص=0.3{\displaystyle p=0.3}تؤدي هذه الصيغ إلى جدول للقيم الصغيرة لـx{\displaystyle x}:

ج(x،s){\displaystyle C(x,s)}01234567891011121314151617181920
s=0{\displaystyle s=0}012345678910111213
s=1{\displaystyle s=1}0123456

الرمزs=1{\displaystyle s=1}يتوافق مع مجموعة فرعية من الأعداد الطبيعية ذات الكثافةص=0.3{\displaystyle p=0.3}وهي في هذه الحالة المناصب{0،3،6،10،13،16،20،23،26،...}{\displaystyle \{0,3,6,10,13,16,20,23,26,\ldots \}}. مثل1/4<0.3<1/3{\displaystyle 1/4<0.3<1/3}تزداد هذه المناصب بمقدار 3 أو 4. لأنص=3/10{\displaystyle p=3/10}هنا، يتكرر نمط الرموز كل 10 مواضع.

البرمجةج(x،s){\displaystyle C(x,s)}يمكن إيجادها عن طريق أخذ الصف المقابل لرمز معينs{\displaystyle s}واختيار المعطىx{\displaystyle x}في هذا الصف. ثم يوفر الصف العلويج(x،s){\displaystyle C(x,s)}. على سبيل المثال،ج(7،0)=11{\displaystyle C(7,0)=11}من الصف الأوسط إلى الصف العلوي.

لنفترض أننا نرغب في ترميز التسلسل '0100' بدءًا منx=1{\displaystyle x=1}. أولاًs=0{\displaystyle s=0}يأخذنا إلىx=2{\displaystyle x=2}، ثمs=1{\displaystyle s=1}لx=6{\displaystyle x=6}، ثمs=0{\displaystyle s=0}لx=9{\displaystyle x=9}، ثمs=0{\displaystyle s=0}لx=14{\displaystyle x=14}باستخدام وظيفة فك التشفيرد(x′){\displaystyle D(x')}في هذه المرحلة النهائيةx{\displaystyle x}يمكننا استرجاع تسلسل الرموز. باستخدام الجدول لهذا الغرض،x{\displaystyle x}يُحدد الصف الأول العمود، ثم يُحدد الصف غير الفارغ والقيمة المكتوبة العمود المقابل.s{\displaystyle s}وx{\displaystyle x}.

متغيرات النطاق (rANS) والبث

يستخدم متغير النطاق أيضًا الصيغ الحسابية، ولكنه يسمح بإجراء العمليات على أبجدية كبيرة. [ ‡ 2 ] وبشكل بديهي، يقسم مجموعة الأعداد الطبيعية إلى نطاقات ذات أحجام مختلفة.2ن{\displaystyle 2^{n}}، ويقسم كل منها بطريقة متطابقة إلى نطاقات فرعية بنسب محددة بواسطة التوزيع الاحتمالي المفترض.

نبدأ بتقسيم التوزيع الاحتمالي إلى خطوات من2-ن{\displaystyle 2^{-n}}، حيث يتم اختيار n (عادةً 8-12 بت):صs≈و[s]/2ن{\displaystyle p_{s}\approx f[s]/2^{n}}بالنسبة لبعض الأعداد الطبيعيةو[s]{\displaystyle f[s]}(أحجام النطاقات الفرعية).

دلقناع=2ن-1{\displaystyle {\text{mask}}=2^{n}-1}ودالة التوزيع التراكمي:

صندوق الدفاع المدني⁡[s]=∑أنا<sو[أنا]=و[0]+⋯+و[s-1].{\displaystyle \operatorname {CDF} [s]=\sum _{i<s}f[i]=f[0]+\cdots +f[s-1].}

لاحظ هنا أن هذه الدالة ليست دالة توزيع تراكمي حقيقية ، إذ لا يتضمن تعبيرها احتمال الرمز الحالي. بدلاً من ذلك، يُمثل الاحتمال الكلي لجميع الرموز السابقة. مثال: بدلاً من التعريف المعتاد لـ ، يتم تقييمها على أنها ، لعدم وجود رموز سابقة.CDF[s]CDF[s]CDF[0]=f[0]CDF[0]=0

لy∈[0،2ن-1]{\displaystyle y\in [0,2^{n}-1]}تشير إلى الدالة (عادةً ما تكون مُجدولة)

الرمز ( y ) = s بحيث يكون CDF [ s ] <= y < CDF [ s + 1 ]

أما وظيفة الترميز فهي:

C ( x , s ) = ( floor ( x / f [ s ]) << n ) + ( x % f [ s ]) + CDF [ s ]

فك التشفير:

s = symbol ( x & mask ) D ( x ) = ( f [ s ] * ( x >> n ) + ( x & mask ) - CDF [ s ], s )

بهذه الطريقة، يمكننا ترميز سلسلة من الرموز إلى عدد طبيعي كبير x . ولتجنب استخدام العمليات الحسابية على الأعداد الكبيرة، تُستخدم في الممارسة العملية متغيرات التدفق التي تفرضx∈[ل،ب⋅ل-1]{\displaystyle x\in [L,b\cdot L-1]}عن طريق إعادة التطبيع: إرسال البتات الأقل أهمية من x إلى أو من تدفق البتات (عادةً ما تكون L و b قوى للعدد 2). [ ‡ 2 ]

في صيغة rANS، يمكن أن يكون x عددًا صحيحًا من 32 بت على سبيل المثال. بالنسبة لإعادة التطبيع من 16 بت (x∈[216،232-1]{\displaystyle x\in [2^{16},2^{32}-1]})، يقوم جهاز فك التشفير بإعادة ملء البتات الأقل أهمية من تدفق البتات عند الحاجة:

إذا كان ( x < ( 1 << 16 )) { x = ( x << 16 ) + read16bits () }

متغير جدولي (tANS)

مثال بسيط لآلة ANS ذات 4 حالات، حيث احتمال ظهور الرمز a يساوي  3/4  واحتمال ظهور الرمز b يساوي 1/4. يحتوي الرمز b  على 2 بت من المعلومات (-lg(1/4)) ، لذا فهو يُنتج دائمًا بتّين. في المقابل، يحتوي الرمز a على 0.415 بت تقريبًا (-lg(3/4)) ، لذا فهو يُنتج أحيانًا بتًا واحدًا (من الحالتين 6 و7)، وأحيانًا لا يُنتج أي بت (من الحالتين 4 و5)، مما يزيد فقط من قيمة الحالة التي تعمل كمخزن مؤقت يحتوي على عدد كسري من البتات: lg( x ). يبلغ عدد الحالات عمليًا 2048 حالة، على سبيل المثال، لأبجدية حجمها 256 (لترميز البايتات مباشرةً).     

يضع متغير tANS السلوك الكامل (بما في ذلك إعادة التطبيع) لـx∈[ل،2ل-1]{\displaystyle x\in [L,2L-1]}إلى جدول ينتج عنه آلة ذات حالات محدودة تتجنب الحاجة إلى الضرب. [ ‡ 2 ]

وأخيرًا، يمكن كتابة خطوة حلقة فك التشفير على النحو التالي:

t = decodingTable ( x ) ; x = t.newX + readBits ( t.nbBits ) ; // انتقال الحالة writeSymbol ( t.symbol ) ; // الرمز المُفكَّك

خطوة حلقة التشفير:

s = ReadSymbol (); nbBits = ( x + ns [ s ]) >> r ; // عدد البتات لإعادة التطبيع writeBits ( x , nbBits ); // إرسال البتات الأقل أهمية إلى دفق البتات x = encodingTable [ start [ s ] + ( x >> nbBits )];

يتم تحديد ترميز tANS المحدد عن طريق تعيين رمز لكل[ل،2ل-1]{\displaystyle [L,2L-1]}يجب أن يتناسب عدد مرات ظهور كل رمز مع احتمالاته المفترضة. على سبيل المثال، يمكن اختيار التوزيع الاحتمالي "abdacdac" لتوزيع احتمالي Pr(a)=3/8، Pr(b)=1/8، Pr(c)=2/8، Pr(d)=2/8. إذا تم تعيين الرموز ضمن نطاقات أطوالها قوى العدد 2، فسنحصل على ترميز هوفمان . على سبيل المثال، سيتم الحصول على رمز البادئة a->0، b->100، c->101، d->11 لـ tANS مع تعيين الرموز "aaaabcdd". [ ‡ 1 ]

مثال على إنشاء جداول tANS لأبجدية حجمها m = 3 وعدد حالاتها L = 16، ثم تطبيقها لفك تشفير التدفق. أولًا، نقارب الاحتمالات باستخدام كسر مقامه عدد الحالات. ثم نوزع هذه الرموز بشكل شبه منتظم، ويمكن أن تعتمد التفاصيل اختياريًا على مفتاح التشفير للتشفير المتزامن. بعد ذلك، نحصي الظهورات بدءًا من القيمة التي تمثل عددها لرمز معين. ثم نعيد ملء البتات الأحدث من التدفق للعودة إلى النطاق المفترض لـ x (إعادة التطبيع).

ملاحظات

أما بالنسبة لترميز هوفمان، فإن تعديل التوزيع الاحتمالي لـ tANS مكلف نسبيًا، لذا يُستخدم بشكل أساسي في الحالات الثابتة، عادةً مع أحد مخططات ليمبل-زيف (مثل ZSTD، [ 2 ] LZFSE [ 9 ] ). في هذه الحالة، يُقسّم الملف إلى كتل ، حيث تُحسب ترددات الرموز لكل كتلة على حدة، ثم تُكتب بعد التقريب (التكميم) في رأس الكتلة وتُستخدم كتوزيع احتمالي ثابت لـ tANS. [ ‡ 1 ] 

في المقابل، يُستخدم rANS عادةً كبديل أسرع لترميز النطاق (مثل CRAM ، [ 13 ] LZNA، ​​Draco [ 10 ] ). يتطلب الضرب، ولكنه أكثر كفاءة في استخدام الذاكرة ومناسب لتكييف توزيعات الاحتمالات ديناميكيًا. [ ‡ 2 ]

تُجرى عمليتا التشفير وفك التشفير في نظام ANS في اتجاهين متعاكسين، مما يُشكل مكدسًا للرموز. عادةً ما يُحل هذا الإشكال بالتشفير في الاتجاه العكسي، ثم فك التشفير في الاتجاه الأمامي. [ ‡ 2 ] بالنسبة للأنظمة المعتمدة على السياق، مثل نموذج ماركوف ، يحتاج المُشفِّر إلى استخدام السياق من منظور فك التشفير اللاحق. ولتحقيق التكيف، ينبغي على المُشفِّر أولًا أن يتقدم للأمام لإيجاد الاحتمالات التي سيستخدمها (يتوقعها) المُفكِّك، وتخزينها في مُخزن مؤقت، ثم التشفير في الاتجاه العكسي باستخدام الاحتمالات المُخزنة. [ ‡ 2 ]

تُعدّ الحالة النهائية للترميز ضرورية لبدء فك التشفير، لذا يجب تخزينها في الملف المضغوط. يمكن تعويض هذه التكلفة بتخزين بعض المعلومات في الحالة الابتدائية للمُشفِّر. على سبيل المثال، بدلاً من البدء بالحالة "10000"، ابدأ بالحالة "1****"، حيث تمثل "*" بتات إضافية مُخزَّنة، يمكن استرجاعها في نهاية عملية فك التشفير. بدلاً من ذلك، يمكن استخدام هذه الحالة كمجموع اختباري عن طريق بدء الترميز بحالة ثابتة، ثم اختبار ما إذا كانت الحالة النهائية لفك التشفير هي الحالة المتوقعة. [ ‡ 2 ]

جدل براءات الاختراع

كان مؤلف خوارزمية ANS الجديدة ومتغيراتها tANS وrANS ينوي تحديدًا أن يكون عمله متاحًا مجانًا في الملكية العامة، لأسباب إنسانية. لم يسعَ إلى الربح منها، واتخذ خطوات لضمان عدم تحولها إلى "حقل ألغام قانوني"، أو تقييدها من قِبل الآخرين، أو استغلالها لتحقيق الربح. [ 1 ] في عام 2015، نشرت جوجل براءة اختراع أمريكية، ثم عالمية، لـ"ترميز معاملات ANS المختلط بين الرموز المنطقية". [ 22 ] في ذلك الوقت، طلبت جوجل من البروفيسور دودا مساعدتها في ضغط الفيديو، لذا كان على دراية تامة بهذا المجال، حيث كان المؤلف الأصلي يساعدهم.

لم يكن دودا سعيدًا باكتشافه (عن طريق الصدفة) نوايا جوجل بشأن براءة الاختراع، نظرًا لأنه كان قد أوضح رغبته في جعلها ملكية عامة، وقدّم المساعدة لجوجل تحديدًا على هذا الأساس. [ 1 ] وقدّم دودا لاحقًا طلبًا من طرف ثالث [ 5 ] إلى مكتب براءات الاختراع الأمريكي طالبًا رفض الطلب. رفض المكتب طلبه في عام 2018، وتخلّت جوجل بعد ذلك عن براءة الاختراع. [ 23 ]

في يونيو 2019، قدمت مايكروسوفت طلب براءة اختراع بعنوان "ميزات ترميز وفك ترميز نظام الأرقام غير المتماثل النطاقي". [ 24 ] أصدر مكتب براءات الاختراع والعلامات التجارية الأمريكي (USPTO) رفضًا نهائيًا للطلب في 27 أكتوبر 2020. [ 24 ] ومع ذلك، في 2 مارس 2021، قدمت مايكروسوفت إلى مكتب براءات الاختراع والعلامات التجارية الأمريكي (USPTO) مذكرة توضيحية جاء فيها: "يختلف مقدم الطلب مع قرار الرفض". [ 25 ] ساعيةً إلى نقض قرار الرفض النهائي بموجب برنامج "البرنامج التجريبي 2.0 بعد النظر النهائي". [ 26 ] بعد إعادة النظر، وافق مكتب براءات الاختراع والعلامات التجارية الأمريكي (USPTO) على الطلب في 25 يناير 2022. [ 24 ]

انظر أيضاً

مراجع

  1. 1 2 3 "اتهام جوجل بمحاولة تسجيل براءة اختراع لتقنية متاحة للعموم" . بليبينج كمبيوتر . 11 سبتمبر 2017.
  2. 1 2 ضغط بيانات أصغر وأسرع مع Zstandard ، فيسبوك، أغسطس 2016.
  3. ↑ 5 طرق لتحسين فيسبوك للضغط على نطاق واسع باستخدام Zstandard ، فيسبوك، ديسمبر 2018.
  4. ↑ ضغط Zstd لأنظمة Btrfs و Squashfs تم إعداده لنظام Linux 4.14، مستخدم بالفعل داخل فيسبوك ، Phoronix، سبتمبر 2017.
  5. ↑ جديد في Chrome 123 (ترميز المحتوى) ، جوجل، مارس 2024.
  6. ↑ "إصدار Zstd في نظام Android P" . مؤرشف من الأصل بتاريخ 26 أغسطس 2020. تم الاطلاع عليه بتاريخ 29 مايو 2019 .
  7. ↑ ضغط Zstandard ونوع الوسائط application/zstd (معيار البريد الإلكتروني) .
  8. ↑ معلمات بروتوكول نقل النص التشعبي (HTTP) ، IANA .
  9. 1 2 أبل تفتح خوارزمية الضغط الجديدة الخاصة بها LZFSE ، InfoQ، يوليو 2016.
  10. 1 2 مكتبة ضغط الصور ثلاثية الأبعاد من جوجل دراكو .
  11. ↑ أضافت جوجل وبيكسار ضغط دراكو إلى تنسيق وصف المشهد العالمي (USD) .
  12. ↑ جوجل PIK: تنسيق صور جديد مضغوط للإنترنت .
  13. 1 2 مواصفات تنسيق CRAM (الإصدار 3.0) .
  14. ↑ تشين و، إليوت إل تي (2021). "ضغط بيانات علم الوراثة السكانية من خلال إنتروبيا الحالة المحدودة" . مجلة المعلوماتية الحيوية وعلم الأحياء الحاسوبي . 19 (5) 2150026. doi : 10.1142/S0219720021500268 . PMID 34590992 . 
  15. ↑ ضغط البيانات عالي السرعة باستخدام وحدات معالجة الرسومات من إنفيديا .
  16. ↑ بناء ضغط أفضل مع DivANS .
  17. ↑ نظرة عامة على خدمة التخزين المباشر من مايكروسوفت .
  18. ^ راتوشنياك، الكسندر. واسنبرغ، يناير؛ سنيرز، جون؛ ألاكويجالا، جيركي؛ فانديفين، لود؛ فيرساري، لوكا؛ أوبريك، روبرت؛ زابادكا، زولتان؛ كليوتشنيكوف، إيفجيني؛ كومسا، يوليا ماريا؛ بوتيمبا، كرزيستوف؛ بروس، مارتن. فيرشينج، موريتز؛ خاسانوفا، ريناتا؛ رود فان أسيلدونك؛ بوكرت، سامي؛ جوميز، سيباستيان. فيشباخر، توماس (2019). “مسودة لجنة نظام ترميز الصور JPEG XL”. أرخايف : 1908.03565 [ eess.IV ].
  19. ↑ اسنليك، سميح؛ تشانغ، كاي. أسينسو، جواو (2025). “نظرة عامة على معيار ترميز الصور المعتمد على التعلم JPEG AI”. أرخايف : 2510.13867 [ eess.IV ].
  20. ↑ كوفير، توماس م.؛ توماس، جوي أ. (2006). عناصر نظرية المعلومات ( الطبعة الثانية). وايلي. ص 13-14 . ISBN   978-0-471-24195-9.
  21. شرح ضغط البيانات 1 2 ، مات ماهوني
  22. ↑ "الترميز المختلط للرموز المنطقية والمعاملات" . تم الاطلاع عليه بتاريخ 14 يونيو 2021 .
  23. ↑ نازر، دانيال (30 أغسطس 2018). "بعد رفض مكتب براءات الاختراع، حان الوقت لشركة جوجل للتخلي عن محاولتها تسجيل براءة اختراع لاستخدام خوارزمية من الملكية العامة" . مؤسسة الحدود الإلكترونية .
  24. 1 2 3 "خصائص ترميز وفك ترميز نظام الأرقام غير المتماثل النطاقي" . تم الاطلاع عليه بتاريخ 14 يونيو 2021 .
  25. ↑ كلابورن، توماس (13 مارس 2021). "هل المحاولة الثالثة ضارة؟ مايكروسوفت تحاول تمرير براءة اختراع ضغط البيانات المرفوضة مرتين أمام فاحصين متشككين" . ذا ريجستر . تم الاطلاع عليه بتاريخ 14 يونيو 2021 .
  26. ↑ "المشروع التجريبي 2.0 بعد الدراسة النهائية" . مكتب براءات الاختراع والعلامات التجارية بالولايات المتحدة . تم الاطلاع عليه بتاريخ 14 يونيو 2021 .

المصادر الأولية

في النص، تسبق هذه المراجع علامة خنجر مزدوجة (‡):

  1. 1 2 3 4 5 6 J. Duda, K. Tahboub, NJ Gadil, EJ Delp, The use of asymmetric numeral systems as accurate replacement for Huffman coding , Picture Coding Symposium, 2015.
  2. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 J. Duda , Asymmetric numeral systems : entropy coding combine speed of Huffman coding with compression rate of arithmetic coding , arXiv:1311.2540, 2013.
  3. ^ "دكتور ياروسلاف دودا (جاريك دودا)" . معهد الفيزياء النظرية . جامعة جاجيلونيان في كراكوف . تم الاسترجاع في 2 أغسطس 2021 .
  4. ↑ دودا، جاريك (6 أكتوبر 2019). "قائمة الضواغط التي تستخدم ANS، والتطبيقات، ومواد أخرى" . تم الاطلاع عليه بتاريخ 6 أكتوبر 2019 .
  5. ↑ "احتجاج على جوجل" (ملف PDF) . معهد الفيزياء النظرية. جامعة ياغيلونيا في كراكوف، بولندا . البروفيسور ياروسلاف دودا.