Динамичка Марковљева компресија

Динамичка Марковљева компресија (ДМЦ) је алгоритам за компресију података без губитака који су развили Гордон Кормак и Најџел Хорспул. Овај алгоритам користи предиктивно аритметичко кодирање слично предикцији путем делимичног поклапања (ППМ), са разликом што се унос предвиђа један по један бит (уместо један по један бајт). ДМЦ има добар степен компресије и умерену брзину, слично ППМ, али захтева нешто више меморије и примена му није распрострањена. Неке скорашње примене укључују екперименталне компресионе програме хоок од Нани Франческо Антонија, оцамyд од Френка Швелинџера, а користи се и као подмодел у паq8л од Мета Махонија. Сви ови су засновани на примени у C из 1993 од Гордона Кормака.

Алгоритам

ДМЦ предвиђа и кодира један по један бит. Разликује се од ППМ у томе што кодира битове уместо бајтова, а од алгоритама са мешањем контекста попут ПАQ у томе што ради са само једним контекстом по предвиђању. Бит који је предвиђен се потом кодира аритметичким кодирањем.

Аритметичко кодирање

Аритметички кодер над битовима попут ДМЦ има две компоненте, предиктор и аритметички кодер. Предиктор прихвата улазни низ од н-битова x = x1x2...xн и додељује му вероватноћу п(x), исказану као производ низа предвиђања, п(x1)п(x2|x1)п(x3|x1x2) ... п(xн|x1x2...xн–1). Аритметички кодер утврђује два високо прецизна бинарна броја пдоњи и пгорњи, који представљају могући распон за укупну вероватноћу коју ће модел доделити свим низовима лексикографски мањим од x, узевши у обзир до сада виђене x битове. Компримовани код за x је пx, најкраћи низ битова који представља број између пдоњи и пгорњи. У овом распону је увек могуће наћи број који је не више од једног бита дужи од Шеноновог ограничења, лог2 1/п(x'). Један такав број се може добити од пгорњи тако што се испусте сви преостали битови након првог бита који се разликује од пдоњи.

Компресија тече на следећи начин. Почетни распон је одређен као пдоњи = 0, пгорњи = 1. За сваки бит, предиктор процењује п0 = п(xи = 0|x1x2...xи–1) и п1 = 1 − п0, вероватноћу 0 или 1, тим редом. Аритметички кодер потом дели тренутни распон (пдоњи, пгорњи), на два дела у сразмери са п0 и п1. Потом подраспон који се подудара са следећим битом xи постаје нови распон.

За декомпресију, предиктор обавља идентичан низ предвиђања, узевши у обзир већ декомпримоване битове. Аритметички кодер обавља идентичан низ подела распона, потом одабира распон који садржи пx и износи бит xи који се подудара са тим подраспоном.

У пракси није потребно одржавати високу прецизност пдоњи и пгорњи у меморији. Како се распон сужава водећи битови оба броја ће бити исти и могу се одмах изнети. 

ДМЦ модел

ДМЦ предиктор је табела која мапира (над битовима) контексте према пару вредности, н0 и н1, који представљају број нула и јединица које су претходно посматране у овом контексту. Стога, он предвиђа да ће следећи бит бити 0 са вероватноћом п0 = н0/н = н0/(н0 + н1) или 1 са вероватноћом п1 = 1 − п0 = н1/н. Поред тога, сваки унос на табели има пар показатеља ка контекстима добијеним додавањем било 0 или 1 са десне стране тренутног контекста (са могућим испуштањем битова са леве стране). Зато никада није неопходно тражити тренутни контекст у табели; довољно је пратити показатељ ка тренутном контексту и пратити везе.

У оригиналној ДМЦ примени, почетна табела је сет свих контекста дужине 8 до 15 битова који почињу на граници бајта. Почетно стање је било који од 8-битних контекста. Вредности су бројеви са покретним зарезом започети као мале, веће од нуле, константе попут 0.2. Вредности не почињу од нуле да би се омогућило кодирање вредности чак и ако претходно нису виђене у тренутном контексту.

Моделирање је исто за компресију и декомпресију. За сваки бит, израчунава се п0 анд п1, бит xи се или кодира или декодира, модел се ажурира додавањем 1 вредности која се подудара са xи, и следећи контекст се налази праћењем везе која се подудара са xи. 

Додавање нових контекста

ДМЦ како је горе описан је једнак моделу контекста првог реда. Међутим, нормално је додавати дуже контексте да би се побољшала компресија. Ако је тренутни контекст А, а следећи контекст Б би испустио битове са леве стране, тада ДМЦ може додати (клонирати) нови контекст C из контекста Б. C представља исти контекст као што је А након додавања једног бита са десне стране као што је случај са Б, али без испуштања иједног бита са леве стране. Веза од А ће стога бити премештена са Б да води ка C. Б и C ће оба доносити иста предвиђања, и оба ће водити до истог пара следећих стања. Тотална вредност, н = н0 + н1 за C ће бити једнака вредности нx за А (за унешени бит x), и та вредности ће бити одузета од Б.

На пример, претпоставимо да стање А представља контекст 11111. При уносу бита 0, оно прелази у стање Б које представља контекст 110, добијен испуштањем 3 бита са леве стране. У контексту А, било је 4 нултих битова и неколико битова са јединицом. У контексту Б, било је 3 нуле и 7 јединица (н = 10), што предвиђа п1 = 0.7.

Стате	н0	н1	неxт0	неxт1
А = 11111	4		Б
Б = 110	3	7	Е	Ф

C је клонирано од Б. Оно представља контекст 111110. I Б и C предвиђају п1 = 0.7, и оба прелазе у иста следећа стања, Е и Ф. Вредност за C је н = 4, једнак н0 за А. Ово оставља н = 6 за Б.

Стате	н0	н1	неxт0	неxт1
А = 11111	4		C
Б = 110	1.8	4.2	Е	Ф
C = 111110	1.2	2.8	Е	Ф

Стања се клонирају у тренутку пре преласка у њих. У оригиналном ДМЦ, услов за клонирање стања је када је прелазак из А у Б најмање 2, а вредност за Б је најмање 2 више од тога. (Када је други праг већи од 0, он гарантује да ће друга стања ипак прећи у Б након клонирања). Неке примене попут хоок дозвољавају овим праговима да буду подешени као параметри. У паq8л, ови се прагови повећавају како се меморија попуњава да би се успорила стопа раста нових стања. У већини примена, када се меморија истроши модел се одбацује и поновно иницијализује назад у оригинални модел над бајтовима првог реда.

Спољашње везе

• Дата Цомпрессион Усинг Дyнамиц Марков Моделлинг
• Гоогле Девелоперс YоуТубе цханнел: Цомпрессор Хеад Еписоде 3 (Марков Цхаин Цомпрессион)