Кодиране по дължина

Какво е кодиране по дължина

Кодирането по дължина (или RLE – Run Length Encoding) е метод за намаляване на размера на повтарящи се поредици от знаци. Обикновено RLE използва по 2 байта за представянето на един знак – брой повторения и самия знак.

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

RLE се използва в множество популярни графични формати (като TIFF, BMP, PCX и други), тъй като графичните данни са много удобни и се поддават на RLE компресия, водеща до добри съотношения между първоначалния размер и размера след компресията (т.е. – високи нива на коефициента на компресия).

Пример

Да разгледаме поредицата от знаци

АААААААААААААААААААА

За нейното съхранение се използват 20 байта. Използвайки RLE можем да я запишем като брой повторения и самия знак :

20A

Което отнема само 2 байта. В този случай коефициентът на компресия е 10:1, което е едно много добро постижение за такъв прост алгоритъм.

Горният пример може и да впечатлява, но той влиза в графата “най-добри случаи”. Ако поредицата от знаци е да кажем

AAAbbbbbbbADDD

то тя се кодира чрез RLE в

3A7b1A3D

В този случай на кодиране 14 байта се превръщат в 8, което води до коефициент на компресия едва 1.75.

Компресирането чрез RLE води и до един друг проблем. Ако компресираните данни не съдържат достатъчно дълги поредици повтаряеми знаци, коефициентът на компресия може да падне по 1. Ако вземем поредицата:

ABCD

тя се превръща в

1A1B1C1D

Тоест – размерът вместо да се намали се увеличава двойно (коефициент на компресия 0.5)

Подобрения на Run Length Encoding – 1 вариант

Един начин за избягване на проблемите от липса на поредици е към единичните знаци да не се прибавя байт за повторение. Използвайки тази идея, една примерна поредица

ABCCCCCCCCCDEEE

може да се запише като

AB9CD3E

което води до коефициент на компресия 2.14. Ако поредицата беше кодирана по конвенционалния начин, коефициентът щеше да бъде 1.5. Използването на тази идея гарантира, че дори при липса на поредици от символи, което е най-лошия случай за RLE компресията, коефициентът на компресия ще бъде 1.0 (т.е. няма да падне под 0 и така да увеличи, вместо да намали размера).

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

Пример

Да разгледаме поредицата от знаци

ААА2BBBBCD

Ако я кодираме съгласно предложената модификация на алгоритъма, тя ще изглежда така:

3A24BCD

При процеса на декомпресия, алгоритъмът ще реши че 24 е броят срещания на знака “B”.

Често използван подход за избягване на този проблем е, числото указващо броя на срещанията да се кодира като байт със знак (т.е. 7 бита стойност, 1 бит за знак), като чрез бита за знак стойността винаги се записва като отрицателна. При един такъв подход компресирания изход от AAA2BBBBCD ще бъде:

(-3)A2(-4)BCD

или коефициент на компресия 1.4 вместо коефициент 1.0, до който води конвенционалната компресия в този случай.

Подобрения на Run Length Encoding – 2 вариант

Вариант на RLE имплементацията е метода, който следи за последователни поредици от стойности и ги групира.

Пример

Да разгледаме поредицата от знаци

ABCABCABCABC

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

ABCABCABCABC

т.е. коефициент 1 или още по-лошо, ако използваме конвенционалния подход (коефициент 0.5) в това подобрение поредицата се кодира като:

4(ABC)

В този случай постигаме доста добро съотношение некомпресиран: компресиран размер, което е 12:4 или коефициент на компресия 3.0

Подобрения на Run Length Encoding – 3 вариант

Този вид подобрение е частен случай, но то дава много високи резултати за определени поредици знаци, в които предишните варианти на RLE са изцяло неприложими.

При този подход се прави анализ на входния поток данни и се търсят поредици от нарастващи стойности. Ако нарастването е и равномерно или по закономерни интервали резултатите са още по-добри.

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

Пример

Да разгледаме поредицата от стойности

1,2,3,5,6,7,9

Тази редица се кодира като се формират разликите между всяка двойка стойности (т.е. 2 – 1 = 1, 3 – 2, = 1, 5 – 3 = 2 и т.н.)

Резултатът е:

1,1,2,1,1,2

Въпреки, че в този случай не печелим нищо освен 1 байт (заради първата стойност на редицата), ако този резултат беше по-дълъг, а нарастването равномерно, можехме да използваме RLE компресия върху вече веднъж компресираната редица и да използваме първото подобрение с отрицателно представяне на еднаквите поредиците.

По-добрият вариант обаче е, вместо да разичтаме на поредици в резултата, направо да приложим второто подобрение на RLE алгоритъма.

Пример

Вземаме редицата от предишния пример

1,2,3,5,6,7,9

Формираме резултата по новия метод:

1,1,2,1,1,2

Прилагаме второто подобрение (обединяване на поредици) и получаваме:

2 (1,1,2)

По този начин получаваме коефициент на компресия 1.75, което е наистина висок коефициент, имайки предвид контекста на входните данни.

Както вече споменахме, кодирането по дължина (RLE) най-често се използва за компресия на изображения. Тъй като предимствата на алгоритъма силно зависият от входните данни, като всеки един алгоритъм той има най-добри и най-лоши случаи на работа.

Следната таблица[1] показва резултата от работата на един RLE алгоритъм спрямо три различни изображения, подбрани за да илюстрират лошия и добрия случай:

Най-добър случай
Най-лош случай
Примерен междинен случай
Първоначален размер :

10 000 байта

Компресиран размер:

200 байта

Коефициент: 50

Първоначален размер :

10 000 байта

Компресиран размер:

10 100 байта

Коефициент: 0.99

Първоначален размер :

10 000 байта

Компресиран размер:

5 713 байта

Коефициент: 1.75

Използването на стандартни RLE алгоритми като цяло се избягва спрямо цветни изображения с голямо количество разнородни по цвят съседни пиксели (например фотографски изображения с високо качество). За прости изображения обаче, методът е изключително ефективен, особено ако се използва негов вариант със загуба на информация.

 



SAM - Science At Manchev.org
science.manchev.org