Работа с компресирани данни

Друг фактор, влияещ върху степента на излишък, е възприетата система за кодиране. Пример за системи за кодиране могат да бъдат обикновените езици за комуникация, които не са нищо повече от системи за кодиране на концепции и идеи за изразяване на мисли. Така е установено, че кодирането на текстови данни със средствата на българския език дава среден излишък с 20-25% по-голям от кодирането на подобни данни със средствата на английския език.

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

В тази връзка непрекъснато възниква проблемът за намаляване на излишъка иликомпресия на данни. Ако методите за компресиране на данни се прилагат към готови файлове, терминът "архивиране на данни" често се използва вместо термина "компресия на данни", компресираната версия на данните се наричаархив, а софтуерът, който прилага методите за компресиране, се наричаархиватори.

В зависимост от обекта, в който се намират данните за компресиране, има:

1. Компресиране (архивиране) на файлове: използва се за намаляване на размера на файловете при подготовка за предаване по комуникационни канали или за транспортиране на външен носителмалък капацитет;

2. Компресиране (архивиране) на папки: използва се като средство за намаляване на обема на папките преди дългосрочно съхранение, например при архивиране;

3. Компресия (компресия) на дискове: използва се за подобряване на ефективността на използване на дисковото пространство чрез компресиране на данни при записването им на носител за съхранение (обикновено с помощта на операционна система).

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

Ако съдържанието на данните се промени по време на компресирането на данни, тогава методът на компресиране се наричанеобратим,, т.е. при възстановяване (разархивиране) на данни от архив информацията не се възстановява напълно. Такива методи често се наричат ​​методи за компресия със загуби. Ясно е, че тези методи могат да се използват само за типове данни, за които загубата на част от съдържанието не води до значително изкривяване на информацията.

  • JPEG - за графични данни;
  • MP3 - за аудио данни.

Ако компресията на данни променя само структурата на данните, тогава методът на компресия се наричаобратим.В този случай е възможно да се възстанови цялата информация от архива. Методите за обратимо компресиране могат да се прилагат към всеки тип данни, но те осигуряват по-ниско съотношение на компресия от методите за необратимо компресиране. Примери за формати за компресия без загуби:

  • GIF, TIFF - за графични данни;
  • ZIP, ARJ, RAR, CAB, LH - за произволни типове данни.

Има многоразлични практически методи за компресия без загуби, които като правило имат различна ефективност за различни типове данни и различни обеми. Тези методи обаче се основават на три теоретични алгоритъма:

  • RLE (Run Length Encoding) алгоритъм;
  • алгоритми от групата KWE (KeyWord Encoding);

RLE алгоритъм

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

1 1 1 1 2 2 3 4 4 4

В алгоритъма RLE се предлага да се замени със следната структура: 1 4 2 2 3 1 4 3, където първото число на всяка двойка числа е кодът на данните, а второто е коефициентът на повторение. Ако се разпредели 1 байт за съхраняване на всеки елемент от данни на входната последователност, тогава цялата последователност ще заема 10 байта памет, докато изходната последователност (компресирана версия) ще заема 8 байта памет. Степента на компресия, която характеризира степента на компресия, може да се изчисли по формулата:

където Vx е количеството памет, необходимо за съхраняване на изходната (резултантна) последователност от данни, Vn е входната последователност от данни.

Колкото по-малка е стойността на съотношението на компресия, толкова по-ефективен е методът на компресия. Ясно е, че алгоритъмът RLE ще даде по-добър ефект на компресия с по-голяма дължина на повтарящата се последователност от данни. В случая на горния пример, ако входната последователност изглежда така: 1 1 1 1 1 1 3 4 4 4, тогава степента на компресия ще бъде 60%. В тази връзка по-голямата ефективност на алгоритъма RLE се постига чрез компресиране на графични данни (особено за изображения с един тон).