ضغط ماركوف الديناميكي

_{يتكون مُشفِّر حسابي ثنائي، مثل DMC ،} من مُكوِّنَين : مُتنبئ ومُشفِّر حسابي. يستقبل المُتنبئ سلسلة إدخال مكونة من n بت، x = x₁ _x₂ ... _xₙ ، ويُعيِّن لها احتمالًا p ( x )، مُعبَّرًا عنه كحاصل _ضرب سلسلة من التنبؤات، p ( x₁ ₎ p ( x₂ | x₁ ) p ( _x₃ | _{x₁ x₂} ) ... p ( xₙ _| x₁ x₂ ... xₙ _{- 1 ) . يحتفظ} المُشفِّر الحسابي برقمين ثنائيين عاليي الدقة، _pₜ و pₜ ، يُمثِّلان النطاق المُحتمل للاحتمال الكلي الذي قد يُعيِّنه النموذج لجميع السلاسل الأقل معجميًا من x _، بالنظر _إلى بتات x التي تمت _رؤيتها حتى الآن. الشفرة المُضغوطة لـ x هي pₜx _، وهي أقصر سلسلة بت تُمثِّل عددًا بين pₜ و pₜ . من الممكن دائمًا إيجاد عدد في هذا النطاق لا يزيد طوله عن بت واحد عن _{حد شانون} ، log₂ ₁ / p ( x ) . يمكن الحصول على أحد هذه الأرقام من p _high عن طريق حذف جميع البتات اللاحقة بعد البت الأول الذي يختلف عن p _low . 

تتم عملية الضغط على النحو التالي: يتم ضبط النطاق الأولي على p_{_low} = 0 و p_{_high} = 1. لكل بت، يُقدّر المُتنبئ احتمالية الحصول على 0 أو 1 على التوالي، وذلك باستخدام p _₀ = p ( xi = 0 | x _{₁ x₂} ... x _{_{i - 1}} ) و p _₁ = 1 - p _₀. ثم يقوم المُشفّر الحسابي بتقسيم النطاق الحالي ( p _{_low} , p _{_high} ) إلى جزأين بنسبة p _₀ و p _₁. بعد ذلك، يصبح النطاق الفرعي المُقابل للبت التالي xi _هو النطاق الجديد.   

في عملية فك الضغط، يقوم المتنبئ بإجراء سلسلة متطابقة من التنبؤات، بناءً على البتات التي تم فك ضغطها حتى الآن. يقوم المشفر الحسابي بإجراء سلسلة متطابقة من تقسيمات النطاق، ثم يختار النطاق الذي يحتوي على p _x ويُخرج البت x _i المقابل لهذا النطاق الفرعي.

عمليًا، ليس من الضروري الاحتفاظ بقيمتي p _{المنخفضة} و p _{العالية} في الذاكرة بدقة عالية. فمع تضييق النطاق، ستكون البتات الأولى لكلا الرقمين متطابقة، ويمكن إخراجها فورًا.

مُتنبئ DMC عبارة عن جدول يربط السياقات (على مستوى البت) بزوج من القيم، _n₀ و n₁ ، _{يُمثلان} عدد الأصفار والآحاد التي لوحظت سابقًا في هذا السياق. وبالتالي، يتنبأ بأن البت التالي سيكون 0 باحتمالية _p₀ = n₀ / n = n₀ _/ ( n₀ + n₁ ) _{، و 1 باحتمالية p₁ = 1 − p₀ = n₁ /} n . بالإضافة _إلى ذلك ، يحتوي _كل مدخل في الجدول _{على زوج من المؤشرات إلى السياقات التي تم الحصول عليها بإضافة إما 0 أو 1 إلى يمين السياق الحالي (مع إمكانية حذف بتات من اليسار). لذا} ، ليس من الضروري أبدًا البحث عن السياق الحالي في الجدول؛ يكفي الاحتفاظ بمؤشر إلى السياق الحالي واتباع الروابط.    

في تطبيق DMC الأصلي، يُمثل الجدول الأولي مجموعة جميع السياقات التي يتراوح طولها بين 8 و15 بتًا والتي تبدأ عند حد بايت. الحالة الأولية هي أي من سياقات الـ 8 بتات. أما العدّات فهي أعداد عشرية مُهيأة بقيمة ثابتة صغيرة غير صفرية، مثل 0.2. لا تُهيأ العدّات إلى الصفر للسماح بترميز القيم حتى لو لم يسبق رؤيتها في السياق الحالي.

عملية النمذجة هي نفسها بالنسبة للضغط وفك الضغط. لكل بت، يتم حساب p ₀ و p _{1 ، ويتم ترميز أو فك ترميز البت} x _i ، ويتم تحديث النموذج بإضافة 1 إلى العدد المقابل لـ x _i ، ويتم العثور على السياق التالي من خلال اجتياز الرابط المقابل لـ x _i .

تُعادل خوارزمية DMC الموصوفة أعلاه نموذج سياق من الرتبة الأولى. مع ذلك، من المعتاد إضافة سياقات أطول لتحسين الضغط. إذا كان السياق الحالي هو A، وكان السياق التالي B سيحذف بتات من اليسار، فقد تُضيف خوارزمية DMC (تستنسخ) سياقًا جديدًا C من B. يُمثل C نفس سياق A بعد إضافة بت واحد إلى اليمين كما هو الحال مع B، ولكن دون حذف أي بتات من اليسار. وبالتالي، سينتقل الرابط من A من B ليشير إلى C. سيُقدم كل من B وC نفس التنبؤ، وسيشير كلاهما إلى نفس زوج الحالات التالية. سيكون العدد الإجمالي، _{n = n₀ + n₁، لـ C مساويًا للعدد nₓ لـ} A ( للبت المدخل x ₎ ، وسيتم طرح هذا العدد من B.   

على سبيل المثال، لنفترض أن الحالة A تمثل السياق 11111. عند إدخال البت 0، تنتقل الحالة A إلى الحالة B التي تمثل السياق 110، والذي يتم الحصول عليه بحذف 3 بتات من اليسار. في السياق A، كانت هناك 4 بتات صفرية وعدد من البتات الآحادية. في السياق B، كانت هناك 3 بتات صفرية و7 بتات آحادية ( n  =  10)، مما يشير إلى أن _p1 = 0.7.

تم استنساخ C من B. وهو يمثل السياق 111110. يتوقع كل من B وC أن تكون قيمة p ₁ = 0.7، وينتقل كلاهما إلى نفس الحالات التالية، E وF. عدد مرات تكرار C هو n = 4، وهو يساوي n ₀ بالنسبة لـ A. وهذا يترك n = 6 بالنسبة لـ B.

تُستنسخ الحالات قبل الانتقال إليها مباشرةً. في خوارزمية DMC الأصلية، يُشترط لاستنساخ حالة ما أن يكون الانتقال من الحالة A إلى الحالة B على الأقل 2، وأن يكون عدد مرات الانتقال إلى الحالة B أكبر من ذلك بمقدار 2 على الأقل. (عندما يكون الحد الثاني أكبر من 0، يضمن ذلك أن الحالات الأخرى ستنتقل إلى الحالة B بعد الاستنساخ). تسمح بعض التطبيقات، مثل hook، بتحديد هذه الحدود كمعاملات. في paq8l، تزداد هذه الحدود مع استهلاك الذاكرة لإبطاء معدل نمو الحالات الجديدة. في معظم التطبيقات، عند استنفاد الذاكرة، يُهمل النموذج ويُعاد تهيئته إلى النموذج الأصلي ذي الترتيب البايتي 1.