Най-простите алгоритми за компресиране RLE и LZ77

компресиране
Отдавна, когато все още бях наивен ученик, внезапно ми стана страшно любопитно: как магически данните в архивите заемат по-малко място? След като оседлах верния си телефон, започнах да сърфирам в интернет в търсене на отговор и намерих много статии с доста подробно представяне на информацията, която ме интересува. Но никой от тях тогава не ми се стори лесен за разбиране - кодовите листи изглеждаха китайска грамотност и опитите за разбиране на необичайна терминология и различни формули бяха неуспешни.

Следователно целта на тази статия е да даде представа за най-простите алгоритми за компресиране на онези, които поради своите знания и опит все още не им позволяват да разберат веднага повече професионална литература или чийто профил е напълно далеч от такъв тема. Тези. Ще ви разкажа за някои от най-простите алгоритми и ще дам примери за тяхното изпълнение без списъци с километрични кодове.

Веднага ще ви предупредя, че няма да разглеждам подробностите за изпълнението на процеса на кодиране и такива нюанси като ефективно търсене на поява на низ. Статията ще засегне само самите алгоритми и начините за представяне на резултата от тяхната работа.

RLE - компактна еднородност

Пример за изпълнение

Да приемем, че имаме набор от някои целочислени коефициенти, които могат да приемат стойности от 0 до 255. Логично стигнахме до заключението, че е разумно да съхраняваме този набор като масив от байтове:

За мнозина ще бъде много по-познато да виждат тези данни под формата на шестнадесетичен дъмп:
0000: 00 00 00 00 00 00 00 04 02 00 04 04 04 04 04 04 04
0010: 50 50 50 50 00 02 02 02 02 FF FF FF FF FF 00 00

След малко размисъл решихме, че би било добре по някакъв начин да компресираме такива комплекти, за да спестим място. За целта ги анализирахме и разкрихме модел: много често има подпоследователности, състоящи се от едни и същи елементи. Разбира се, RLE е идеален за това.!

Нека да кодираме нашите данни, като използваме новопридобитите знания: 6 × 0, 4, 2, 0, 7 × 4, 4 × 80, 0, 4 × 2, 5 × 255, 2 × 0.

Време е по някакъв начин да представим резултата си в компютърно разбираема форма. За целта в потока от данни трябва по някакъв начин да отделим единични байтове от кодираните низове. Тъй като целият диапазон от байтови стойности се използва от нашите данни, няма да е възможно просто да разпределим някакви диапазони от стойности за нашите цели.

Има поне два изхода от тази ситуация:

  1. Изберете една байтова стойност като индикатор за компресираната верига и в случай на сблъсък с реални данни, избягвайки ги. Например, ако използваме стойността 255 за целите на "услугата", тогава когато срещнем тази стойност във входните данни, ще трябва да напишем "255, 255" и след индикатора да използваме максимум 254.
  2. За структуриране на кодираните данни, като се посочва броят не само за повтарящи се, но и следващи следващи единични елементи. Тогава ще знаем предварително къде какви данни.

Първият метод в нашия случай изглежда не е ефективен, така че може би ще прибегнем до втория.

Така че сега имаме два вида последователности: низове от единични елементи (като "4, 2, 0") и низове от идентични елементи (като "0, 0, 0, 0, 0, 0"). Нека разпределим един бит в "сервизните" байтове за типа последователност: 0 - единични елементи, 1 - идентични. Нека приемем за това, да речем, най-значимият бит.

В останалите 7 бита ще съхраним дължините на последователностите, т.е. максималната дължина на кодираната последователност е 127 байта. Бихме могли да разпределим например два байта за нужди от услуги, но в нашия случай такива дълги последователности са изключително редки, така че е по-лесно и по-икономично просто да ги разбием на по-къси.

Оказва се, че в изходния поток първо ще напишем дължината на последователността, а след това или една повтаряща се стойност, или верига от неповторими елементи с определена дължина.

Първото нещо, което трябва да привлече вниманието ви, е, че в тази ситуация имаме няколко неизползвани стойности. Не може да има последователности с нулева дължина, така че можем да увеличим максималната дължина до 128 байта, като извадим една от дължината при кодиране и добавим такава при декодиране. По този начин можем да кодираме дължини от 1 до 128 вместо дължини от 0 до 127.

Второто нещо, което може да се забележи е, че няма последователности от еднакви елементи с единична дължина. Следователно ще извадим още една от дължината на такива последователности по време на кодирането, като по този начин ще увеличим максималната им дължина до 129 (максималната дължина на верига от единични елементи все още е равна на 128). Тези. вериги от еднакви елементи могат да имат дължина от 2 до 129.

Нека отново да кодираме данните си, но вече в компютърно разбираема форма. Ще запишем горните байтове като [T | L], където T е видът на последователността, а L е дължината. Веднага ще вземем предвид, че дължините записваме в модифицирана форма: при T = 0 изваждаме една от L, при T = 1 - две.

[1 | 4], 0, [0 | 2], 4, 2, 0, [1 | 5], 4, [1 | 2], 80, [0 | 0], 0, [1 | 2], 2, [1 | 3], 255, [1 | 0], 0

Нека се опитаме да декодираме нашия резултат:

  • [1 | 4]. T = 1, което означава, че следващият байт ще се повтори L + 2 (4 + 2) пъти: 0, 0, 0, 0, 0, 0.
  • [0 | 2]. T = 0, така че просто четем L + 1 (2 + 1) байта: 4, 2, 0.
  • [1 | 5]. T = 1, повтаряме следващия байт 5 + 2 пъти: 4, 4, 4, 4, 4, 4, 4.
  • [1 | 2]. T = 1, повторете следващия байт 2 + 2 пъти: 80, 80, 80, 80.
  • [0 | 0]. T = 0, прочетете 0 + 1 байт: 0.
  • [1 | 2]. T = 1, повторете байт 2 + 2 пъти: 2, 2, 2, 2.
  • [1 | 3]. T = 1, повторете байт 3 + 2 пъти: 255, 255, 255, 255, 255.
  • [1 | 0]. T = 1, повторете байт 0 + 2 пъти: 0, 0.