В този план, има и други приложения, вижте. Компресия.
компресия на данните (Engl компресиране на данни.) - алгоритмична реализация. произведени с цел намаляване на обема, която заемат. Използва се за по-ефективно използване на съхранение на данни и прехвърляне на средства. Синоними - пакетни данни. компресия. компресия кодиране. източник кодиране. Свържи се с процедура, наречена възстановяване на данни (декомпресиране, декомпресия).
Компресията се основава на премахването на съкращения. съдържаща се в оригиналните данни. Най-простият пример на излишък е повторение на фрагменти текстови (например, думи на физическо или машина език). Такова съкращения обикновено се елиминира чрез заместване на повторно последователност на вече кодиран позоваване фрагмент, което показва неговата дължина. Друг вид излишък се дължи на факта, че някои от стойностите в компресираната информация се появи по-често от другите. Намаляване на размера на данните се постига чрез замяна на често срещаната данни кратки кодови думи, и рядко - дълго (ентропия кодиране). компресиране на данните, че не е собственост на съкращения (например случаен сигнал или бял шум. криптирани съобщения) е невъзможно по принцип, без загуба.
Lossless компресия ви позволява напълно да възстанови първоначалното съобщение, тъй като тя не се намали количеството на информация в него, въпреки намаляването на дължина. Тази възможност се появява само ако вероятностите на снимачната площадка на съобщенията не е равномерно разпределение, например на теоретично е възможно в предишните съобщения за кодиране на практика не се случи.
Принципи за компресиране на данни
В основата на всеки метод за компресиране е модел източник на данни, или по-точно, модела на съкращения. С други думи, за компресиране на данни използва някои предварително познаване на това, което е компресиран вид данни. Липсата на такава информация за източника, не можете да правите каквито и да било предположения за преобразуването, което би довело до намаляване на обема на съобщения. Redundancy модел може да бъде статичен, неизменен за всички сгъстен съобщение или изграждане или параметризиран в етап компресия (и възстановяване). Методи за въвеждане на данни, въз основа на промяна модел на съкращение, наречени адаптивна. Nonadaptive обикновено са високо специализирани алгоритми се използват за данни, които имат добре дефинирани и постоянни характеристики. По-голямата част от алгоритми са достатъчно универсален до една или друга степен адаптивна.
Всички техники за компресия на данни са разделени в две основни категории:
Характеристики на алгоритми за компресия и тяхната приложимост
компресия
Съотношение - основната характеристика на алгоритъм за компресия. Тя се определя като съотношение на обема на компресираните данни на първоначалния обем на некомпресирано данни, който е: к = S в S о >>>>. където к - степен на сгъстяване, така че - обем на първоначалните данни, както и Sc - сгъстен обем. По този начин, по-високо съотношение на компресия, алгоритъмът ефективно. Трябва да се отбележи:
- ако к = 1, алгоритъмът не произвежда компресия, който е изходен съобщение е равен на обема на входа;
- Ако к> 1, алгоритъмът генерира съобщение по-голям от некомпресиран, т.е. изпълнява "вредни" на работни места.
Ситуацията с к <1 вполне возможна при сжатии. Принципиально невозможно получить алгоритм сжатия без потерь, который при любых данных образовывал бы на выходе данные меньшей или равной длины. Обоснование этого факта заключается в том, что поскольку число различных сообщений длиной n бит составляет ровно 2 n. число различных сообщений с длиной меньшей или равной n (при наличии хотя бы одного сообщения меньшей длины) будет не больше 2 n. Это значит, что невозможно однозначно сопоставить все исходные сообщения сжатым: либо некоторые исходные сообщения не будут иметь сжатого представления, либо нескольким исходным сообщениям будет соответствовать одно и то же сжатое, а значит их нельзя отличить. Однако даже когда алгоритм сжатия увеличивает размер исходных данных, легко добиться того, чтобы их объём гарантировано не мог увеличиться более, чем на 1 бит. Тогда даже в самом худшем случае будет иметь место неравенство:
к ⩾ S о S о + 1> 1 >>>
Това се извършва, както следва: ако количеството сгъстен данни е по-малко от първоначалния обем, върне компресирани данни, добавянето им в "1", в противен случай се върне оригиналните данни чрез прибавяне към него "0").
Степента на сгъстяване може да бъде или постоянно (някои аудио алгоритми, изображения и така нататък. е. Например, една практика. μ практика. ADPCM. Съкратени блок кодиране) и променливи. Във втория случай, тя може да бъде определена или даден съобщение или otsenon на определени критерии:
- среда (обикновено от няколко теста набор от данни);
- максимална стойност (най-добрия случай компресия);
- минимум (най-лошия случай на компресия);
или който и да е друг. Със загуби компресия така силно зависи от качеството или компресия допустимата грешка. които обикновено действа като параметър на алгоритъма. Като цяло, постоянна компресия може да предостави само техники за компресиране на данни със загуби.
По допустимостта на загуби
Основният критерий за разликите между компресия алгоритми е описано по-горе в присъствието или отсъствието на загуби. В общи линии, без загуби алгоритми за компресия са универсални в смисъл, че прилагането им със сигурност е възможно за всеки тип данни, а възможността за прилагане на компресия със загуби следва да бъде обоснован. За някои видове данни за корупция не е приемливо по принцип. Сред тях
Системни изисквания алгоритми
Различни алгоритми могат да изискват различно количество ресурси на компютърната система, на която те се прилагат:
- RAM (под междинните данни);
- енергонезависима памет (за програмен код и константи);
- CPU време.
Като цяло, тези изисквания зависят от сложността и "умни" алгоритъм. Общата тенденция е: на ефективността и гъвкавостта на алгоритъма, на високите изисквания на изчислителни ресурси го прави. Въпреки това, в определени случаи, прости и компактни алгоритми могат да работят по-добре от сложен и многостранен. Системни изисквания определят техните потребителски качества: по-малко взискателни алгоритъм, толкова по-лесно и по този начин компактен, надежден и евтин система, тя може да бъде изпълнена.
Тъй като алгоритмите за компресия и декомпресия работят по двойки, има стойност на съотношението на системните изисквания към тях. Често това може да бъде сложно алгоритъм да се опрости значително по-различно. По този начин, има три възможности:
Алгоритмите за компресия на данни неизвестен формат
Има два основни подхода за компресиране на данни неизвестен формат:
- На всяка стъпка, алгоритъм на компресия или друг свиваем символ е поставен в изхода буфер енкодер компресия като е (със специален флаг, флаг, не се пресова), или група с няколко знака се заменя свиваем позоваване съвпада с група на вече кодираните символи. Тъй като възстановяването на компресираната информация по този начин е много бърз, този подход често се използва за създаване на саморазархивиращи се програма.
- За всеки сгъстим характер последователност веднъж или всеки път, когато на статистическите данни за наличие Събирани са в кодирани данни. Въз основа на тези статистически данни за изчисляване на вероятността стойността на следващия знак, за да бъдат кодирани (или последователност от символи). След това се прилага един или друг вид кодиране с ентропия. например, аритметично кодиране или Huffman кодиране. да представлява общите къси последователности от кодови думи, и рядко - по-дълго.
Свързани статии