Алгоритмите за компресия - класификация на методи за компресиране

техники за компресиране на данни могат да бъдат разделени на два типа:

Изкривявания (loseless) методи за компресиране (наричани още техники без загуби компресия) гарантира, че кодираните данни ще отговарят точно на оригинала;
Нарушаване методи (загуба) на компресия (наричан също големи загуби методи за компресия) може да наруши оригиналните данни, например чрез отстраняване на не-съществената част от данните, след пълното възстановяване е невъзможно.

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

В допълнение, можете да изберете:

Методи обща компресия цел (общо предназначение), които не зависят от физическото естество на входните данни и обикновено са ориентирани към текст компресия, изпълними програми, обект модули и библиотеки, и така нататък. Д. Т. Е. Данни, които основно и съхранявана в компютъра;
специфични (специални) методи за компресиране, са ориентирани за компресиране на данните на известен произход, като звук, картина, и така нататък. д. И благодарение на познаването на специфичните параметри на компресиран данни се постигат значително по-добро качество и / или степен на компресия, отколкото когато се използват техники, с общо предназначение.

По дефиниция, с общо предназначение компресионни методи - изкривяване; изкривяващи може да бъде само на специални методи за компресиране. Обикновено изкривяване допустимо само при обработката на всички видове сигнали (звук, изображения, данни от физически сензори), когато е известно, по какъв начин и до каква степен данните могат да бъдат променяни без загуба на техните потребителски качества.

Критерии за оценка на методи за компресия

Основните свойства на алгоритъм за компресиране на данни са:

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

В областта на компресиране на данни, както често се случва, законът на лоста актове: алгоритми, които използват повече ресурси (време и пространство), обикновено се достигне по-добро качество на компресия. и обратно: по-малко интензивно ресурси алгоритми за качеството на компресиране. обикновено се получи повече ресурси.

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

Ясно е, че критериите за оценка на техники за компресиране от практическа гледна точка, са силно зависими от приложението по предназначение. Например, когато се използва за компресиране на системи в реално време, трябва да се осигури висока скорост кодиране и декодиране; за вградени системи критичен параметър - размера на паметта се изисква; за дългосрочни системи за съхранение на данни - качеството на компресията и / или скоростта на декодиране, и т.н. ...

програма Надеждност и сложността на алгоритми

Надеждността на софтуерни системи и системи е много важно и се предоставя като непогрешим програмиране и дизайн и характеристики на използваните алгоритми.

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

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

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