Кіріспе
Түпнұсқа деректерді қатесіз қалпына келтіруге мүмкіндік беретін деректерді сығыстыру тәсілі.
Ақпаратты жоғалтпайтын сығыстыру – бұл бастапқы деректерді ешқандай ақпарат жоғалтпай, сығылған деректерден толыққанды қалпына келтіруге мүмкіндік беретін деректерді сығыстыру класы. Ақпаратты жоғалтпайтын сығыстыру мүмкін, себебі нақты әлемдегі деректердің көп бөлігі статистикалық артықшылықты көрсетеді. Керісінше, ақпаратты жоғалтатын сығыстыру бастапқы деректердің жуық шамасын ғана қалпына келтіруге мүмкіндік береді, бірақ әдетте сығылу деңгейі жоғары болады (соның салдарынан медиа көлемі кішірейеді). Күгіртке ішегі қағидасына сәйкес, ешқандай ақпаратты жоғалтпайтын сығыстыру алгоритмі барлық мүмкін деректердің көлемін қысқарта алмайды: кейбір деректер кем дегенде бір символ немесе байтқа ұзарады. Сығыстыру алгоритмдері көбінесе адам және машина оқи алатын құжаттар үшін тиімді, ал артықшылықтары жоқ кездейсоқ деректердің көлемін қысқарта алмайды. Әртүрлі алгоритмдер бар, олар нақты кіріс деректерінің типін ескере отырып немесе сығылмаған деректерде қандай артықшылықтар болуы мүмкін деген болжамдармен жасалған. Ақпаратты жоғалтпайтын деректерді сығыстыру көптеген қолданыстарда қолданылады. Мысалы, ол ZIP файл форматында және GNU құралы gzip-де қолданылады. Сонымен қатар, ол жиі ақпаратты жоғалтатын деректерді сығыстыру технологияларының бір бөлігі ретінде қолданылады (мысалы, MP3 кодектері мен басқа ақпаратты жоғалтатын аудио кодектерінің ақпаратты жоғалтпайтын орта/жақын стерео алдын ала өңдеуі). Ақпаратты жоғалтпайтын сығыстыру осындай жағдайларда қолданылады, онда бастапқы және сығылмаған деректер толықтай сәйкес болуы керек немесе бастапқы деректерден кез келген ауытқулар жағымсыз болар еді. Көбінесе қолданылатын мысалдар – орындалатын бағдарламалар, мәтіндік құжаттар және бастапқы кодтар. Кейбір кескіндер файл форматтары, мысалы PNG немесе GIF, тек ақпаратты жоғалтпайтын сығыстыруды қолданады, ал TIFF және MNG сияқты басқалары ақпаратты жоғалтпайтын немесе ақпаратты жоғалтатын әдістерді қолдануы мүмкін. Ақпаратты жоғалтпайтын аудио форматтары көбінесе деректерді сақтау немесе өндіріс мақсаттары үшін қолданылады, ал кішкентай ақпаратты жоғалтатын аудио файлдары әдетте портативті плеерлерде және жад орынның шектеулі болған немесе аудионың нақты көшірмесі қажет емес басқа жағдайларда қолданылады.
Техникалар
Жоғалмайтын сығылу бағдарламаларының көпшілігі екі қадамды бірінен соң бірі орындайды: бірінші қадам кіріс деректері үшін статистикалық модельді құрайды, ал екінші қадам осы модельді пайдаланып кіріс деректерін биттік тізбектерге түрлендіреді, сонда "көп кездесетін" (яғни, жиі ұшырасатын) деректер "сирек кездесетін" деректерге қарағанда қысқарақ шығыс тудырады. Биттік тізбектерді жасау үшін қолданылатын негізгі кодтау алгоритмдері – Хаффман кодтау (дефляция алгоритмінде де қолданылады) және арифметикалық кодтау. Арифметикалық кодтау белгілі бір статистикалық модель үшін қол жеткізілетін ең жақсы қысылу деңгейіне жақымдасады, бұл ақпараттық энтропиямен анықталады, ал Хаффман қысылуы қарапайым және жылдам, бірақ символдардың ықтималдығы 1-ге жақын модельдер үшін нашар нәтижелер береді. Статистикалық модельдерді құрудың екі негізгі тәсілі бар: статикалық модельде деректер талданып, модель құрылады, содан кейін бұл модель сығылған деректермен бірге сақталады. Бұл тәсіл қарапайым және модулдік, бірақ модельдің өзі сақтау үшін қымбатқа түсуі мүмкін, сонымен қатар ол барлық деректер үшін бір модельді қолдануға мәжбүр етеді, сондықтан әртүрлі деректерден тұратын файлдарда тиімсіз жұмыс істейді. Адаптивтік модельдер деректер сығылғанда модельді динамикалық түрде жаңартады. Кодтаушы және декодер бастапқы деректерді нашар қысуға әкелетін қарапайым модельден бастайды, бірақ деректер туралы көбірек білген сайын, өнімділік жақсарады. Қазіргі кезде қолданылатын көптеген қысылу түрлері адаптивтік кодтаушыларды пайдаланады. Жоғалмайтын қысылу әдістерін олар қысуға арналған деректер түріне қарай жіктеуге болады. Теориялық тұрғыдан алғанда, кез келген жалпы мақсаттағы жоғалмайтын қысылу алгоритмі (жалпы мақсатты – яғни, кез келген биттік тізбекті қабылдай алатын) кез келген дерек түрінде қолданылуы мүмкін, бірақ көптеген алгоритмдер оларға арналған форматта емес деректерді тиімді қысуға қабілетсіз. Мәтінді қысу үшін қолданылатын көптеген жоғалмайтын әдістер индекстелген кескіндер үшін де жақсы жұмыс істейді.
Мультимедиялық
Бұл әдістер суреттердің ерекше қасиеттерін пайдаланады, мысалы, ұқсас түстердің тікелей орналасқан 2D аймақтарының кең таралған құбылысы. Бірінші пикселден басқа әрбір пиксел сол жақтанғы көршісімен салыстырылған айырмасымен алмастырылады. Бұл кіші мәндердің үлкен мәндерге қарағанда әлдеқайда жоғары ықтималдыққа ие болуына әкеледі. Бұл әдіс көбінесе дыбыс файлдарына да қолданылады және негізінен төмен жиіліктері мен төмен деңгейдегі дыбыстары бар файлдарды қысуға мүмкіндік береді. Суреттер үшін бұл қадамды жоғарғы пикселге қатысты айырманы есептеп қайталауға болады, ал бейнелерде келесі кадрдағы пикселге қатысты айырманы есептеуге болады. Бұл техниканың иерархиялық түрі көршілес дерек нүктелерін алып, олардың айырмасын және қосындысын сақтайды, содан кейін төмен ажыратымдылықтағы жоғары деңгейде қосындылармен жұмысты жалғастырады. Бұл дискретті толқындық түрлендіру деп аталады. JPEG2000 басқа жұптардан алынған деректерді және көбейту коэффициенттерін пайдаланып, оларды айырмаға қосу үшін қолданады. Бұл коэффициенттер бүтін сандар болуы керек, нәтижесінде мән әрқашан бүтін сан болады. Осылайша, мәндер артып, файлдың көлемі ұлғаяды, бірақ мәндердің таралуы біркелкі болуы мүмкін деген үміт бар. Адаптивті кодтау дыбыс кодтау кезінде алдыңғы үлгіден, сурет кодтау кезінде сол және жоғарғы пикселден, ал бейне кодтау кезінде алдыңғы кадрдан алынған ықтималдықтарды пайдаланады. Толқындық түрлендіруде ықтималдықтар иерархия бойынша да беріледі.
Тарихи құқықтық мәселелер
Бұл әдістердің көпшілігі ашық кодты және коммерциялық құралдарда іске асырылған, әсіресе LZW және оның түрлері. Кейбір алгоритмдер АҚШ және басқа елдерде патенттелген, оларды заңды түрде пайдалану үшін патент иесінен лицензия алу қажет. LZW сығылымының белгілі бір түрлеріне патенттер болғандықтан және көптеген дамытушылардың пікірінше, Unisys патент иесінің лицензиялау саясаты тиімсіз болғандықтан, ашық кодты жақтаушылар кейбір адамдарды кескін файлдарын сығымдау үшін Graphics Interchange Format (GIF) форматын пайдаланудан аулақ болуға және LZ77 негізіндегі deflate алгоритмін және доменге қатысты болжам сүзгілерін біріктіретін Portable Network Graphics (PNG) форматын пайдалануға шақырды. Дегенмен, LZW патенттері 2003 жылдың 20 маусымында аяқталды. Мәтін үшін қолданылатын көптеген жоғалтусыз сығымдау техникалары индекстелген кескіндер үшін де жақсы жұмыс істейді, бірақ кейбір кескіндер үшін пайдалы, ал әдеттегі мәтін үшін жұмыс істемейтін басқа да техникалар бар (әсіресе қарапайым растрлік кескіндер үшін), сондай-ақ кескіндердің ерекше ерекшеліктерін пайдаланатын техникалар да бар (мысалы, ұқсас түстердің жалғасқан 2D аймақтарының кең таралған құбылысы және түсті кескіндердегі түстер кеңістігінде бейнеленетін түстердің шектеулі диапазонынан түстердің көп болуы). Бұрын айтқандай, жоғалтусыз дыбыс сығымдау - бұл мамандық саласы. Жоғалтусыз дыбыс сығымдау алгоритмдері толқын тәрізді сипаттаманың қайталама үлгілерін пайдалана алады, негізінен «келесі» мәнді болжау үшін авторегрессиялық модельдерді қолдана отырып, күтілетін мән мен нақты дерек арасындағы (көбінесе шағын) айырмашылықты кодтайды. Егер болжалған және нақты дерек арасындағы айырмашылық (қате деп аталады) кішкентай болса, онда белгілі бір айырмашылық мәндері (мысалы, 0, +1, -1 және т.б. үлгілік мәндерде) өте жиі болады, оларды аз шығыс биттерінде кодтау арқылы пайдалануға болады. Кейде файлдың екі нұсқасының (немесе бейне сығымдау кезінде, тізбектегі екі кезекті кескіннің) арасындағы айырмашылықты ғана сығымдау тиімді. Бұл дельта кодтау деп аталады (грек әрпі Δ-дан, математикада айырмашылықты білдіреді), бірақ бұл термин әдетте екі нұсқа да сығымдау мен ашып көрсетуден тыс мәнді болғанда ғана қолданылады. Мысалы, жоғарыда аталған жоғалтусыз дыбыс сығымдау схемасындағы қателікті сығымдау процесін шамамен алынған дыбыс толқынынан бастапқы дыбыс толқынына дельта кодтау ретінде сипаттауға болады, бірақ дыбыс толқынының шамамен алынған нұсқасы басқа контексте мағыналы емес.
Әдістер
Жоқ жоғалтусыз сығылу алгоритмі барлық мүмкін деректерді тиімді қысып шығара алмайды. Сондықтан, әртүрлі алгоритмдер бар, олар нақты дерек түріне немесе қысылмаған деректерде қандай артық ақпарат болуы мүмкін деген болжамдарға сүйене отырып жасалған. Ең көп қолданылатын жоғалтусыз сығылу алгоритмдерінің бірнешесі төменде тізілген.
Криптография
Криптожүйелер көбінесе қосымша қауіпсіздік үшін шифрлау алдында деректерді ("таза мәтін") сығып алады. Дұрыс іске асырылған жағдайда, сығымдау криптоталдауды жеңілдететін үлгілерді жою арқылы бірегейлік қашықтығын едәуір арттырады. Дегенмен, көптеген қарапайым жоғалтусыз сығымдау алгоритмдері ішекті, қаптама, кестелер немесе басқа да болжамды нәтижелерді тудырады, бұл криптоталдауды оңайлатуы мүмкін. Сондықтан криптожүйелер осындай болжамды үлгілерді өндірмейтін сығымдау алгоритмдерін қолдануы керек.
Генетика және геномика
Генетикалық қысылу алгоритмдері (генетикалық алгоритмдермен шатастырмау керек) – деректерді (әдетте нуклеотидтер тізбектерін) стандартты қысылу алгоритмдерімен және генетикалық деректерге бейімделген арнайы алгоритмдерді пайдаланып қысылатын жоғалтусыз алгоритмдердің ең соңғы буыны. 2012 жылы Джонс Хопкинс университетінің ғалымдары сыртқы генетикалық деректер базасына тәуелді емес алғашқы генетикалық қысымдау алгоритмін жариялады. HAPZIPPER HapMap деректері үшін жасалған және 20 еседен астам қысылуға (файл көлемін 95% азайтуға) қол жеткізеді, бұл жетекші жалпы мақсаттағы қысымдау құралдарынан 2-4 есе жақсы және жылдамырақ қысымдауды қамтамасыз етеді. Геномдық тізбектерді қысымдау алгоритмдері, сондай-ақ ДНК тізбегін қысу құралдары деп те аталады, ДНК тізбектерінің кері қайталану сияқты ерекше қасиеттерін пайдаланады. Ең табысты қысу құралдары – XM және GeCo. Эукариоттар үшін XM қысу көрсеткішімен сәл артық, бірақ 100 МБ-тан асатын тізбектер үшін оның есептеу талаптары қолдануға қолайсыз.
Орындалатын файлдар
Өзін-өзі шығаратын орындалатын файлдар қысылған қосымшаны және оны ашушы бағдарламаны қамтиды. Іске қосылғанда, ашушы бағдарлама бастапқы қосымшаны көрінбейтін түрде ашып, іске қосады. Бұл әсіресе демо-кодтауда жиі қолданылады, онда 1 килобайт сияқты қатаң өлшем шектері бар демо-байқаулар өткізіледі. Мұндай сығылу тек бинарлық орындалатын файлдармен ғана шектелмейді, сонымен қатар JavaScript сияқты сценарийлерге де қолданылуы мүмкін.
Шектеулер
Жоғалмайтын деректерді сығыстыру алгоритмдері барлық кіріс деректер жиынтықтары үшін сығылуды кепілдемейді. Басқаша айтқанда, кез келген жоғалмайтын деректерді сығымдау алгоритмі үшін, алгоритм өңдегенде кішіреймейтін деректер жиынтығы болады, ал кем дегенде бір файлды кішірейтетін кез келген жоғалмайтын деректерді сығымдау алгоритмі үшін, кем дегенде бір файлды үлкейтетін файл болады. Бұл элементар математика және «көгершін ұясы» принципі деп аталатын санау аргументі арқылы оңай дәлелденеді:
Assume that each file is represented as a string of bits of some arbitrary length. Suppose that there is a compression algorithm that transforms every file into an output file that is no longer than the original file, and that at least one file will be compressed into an output file that is shorter than the original file. Let M be the least number such that there is a file F with length M bits that compresses to something shorter. Let N be the length (in bits) of the compressed version of F.
Because N<M, every file of length N keeps its size during compression. There are 2N such files possible. Together with F, this makes 2N+1 files that all compress into one of the 2N files of length N.
But 2N is smaller than 2N+1, so by the pigeonhole principle there must be some file of length N that is simultaneously the output of the compression function on two different inputs. That file cannot be decompressed reliably (which of the two originals should that yield? ), which contradicts the assumption that the algorithm was lossless. We must therefore conclude that our original hypothesis (that the compression function makes no file longer) is necessarily untrue. Most practical compression algorithms provide an "escape" facility that can turn off the normal coding for files that would become longer by being encoded. In theory, only a single additional bit is required to tell the decoder that the normal coding has been turned off for the entire input; however, most encoding algorithms use at least one full byte (and typically more than one) for this purpose. For example, deflate compressed files never need to grow by more than 5 bytes per 65,535 bytes of input. In fact, if we consider files of length N, if all files were equally probable, then for any lossless compression that reduces the size of some file, the expected length of a compressed file (averaged over all possible files of length N) must necessarily be greater than N. So if we know nothing about the properties of the data we are compressing, we might as well not compress it at all. A lossless compression algorithm is useful only when we are more likely to compress certain types of files than others; then the algorithm could be designed to compress those types of data better. Thus, the main lesson from the argument is not that one risks big losses, but merely that one cannot always win. To choose an algorithm always means implicitly to select a subset of all files that will become usefully shorter. This is the theoretical reason why we need to have different compression algorithms for different kinds of files: there cannot be any algorithm that is good for all kinds of data. The "trick" that allows lossless compression algorithms, used on the type of data they were designed for, to consistently compress such files to a shorter form is that the files the algorithms are designed to act on all have some form of easily modeled redundancy that the algorithm is designed to remove, and thus belong to the subset of files that that algorithm can make shorter, whereas other files would not get compressed or even get bigger. Algorithms are generally quite specifically tuned to a particular type of file: for example, lossless audio compression programs do not work well on text files, and vice versa. In particular, files of random data cannot be consistently compressed by any conceivable lossless data compression algorithm; indeed, this result is used to define the concept of randomness in Kolmogorov complexity. It is provably impossible to create an algorithm that can losslessly compress any data. While there have been many claims through the years of companies achieving "perfect compression" where an arbitrary number N of random bits can always be compressed to N − 1 bits, these kinds of claims can be safely discarded without even looking at any further details regarding the purported compression scheme. Such an algorithm contradicts fundamental laws of mathematics because, if it existed, it could be applied repeatedly to losslessly reduce any file to length 1. that there is no algorithm to determine whether a file is incompressible in the sense of Kolmogorov complexity. Hence it is possible that any particular file, even if it appears random, may be significantly compressed, even including the size of the decompressor. An example is the digits of the mathematical constant pi, which appear random but can be generated by a very small program. However, even though it cannot be determined whether a particular file is incompressible, a simple theorem about incompressible strings shows that over 99% of files of any given length cannot be compressed by more than one byte (including the size of the decompressor).
Файлдардың әрқайсысы белгілі бір кездейсоқ ұзындықтағы биттер тізбегі ретінде ұсынылсын. Сығымдау алгоритмі барлық файлды бастапқы файлдан ұзын емес шығыс файлына түрлендіреді дейлік, және кем дегенде бір файл бастапқы файлдан қысқа шығыс файлына сығылады. M – ұзындығы M бит болатын F файлы қысқарақ нәрсеге сығылатын ең кіші сан болсын. N – F-тің сығылған нұсқасының ұзындығы (биттермен) болсын.
Assume that each file is represented as a string of bits of some arbitrary length. Suppose that there is a compression algorithm that transforms every file into an output file that is no longer than the original file, and that at least one file will be compressed into an output file that is shorter than the original file. Let M be the least number such that there is a file F with length M bits that compresses to something shorter. Let N be the length (in bits) of the compressed version of F.
Because N<M, every file of length N keeps its size during compression. There are 2N such files possible. Together with F, this makes 2N+1 files that all compress into one of the 2N files of length N.
But 2N is smaller than 2N+1, so by the pigeonhole principle there must be some file of length N that is simultaneously the output of the compression function on two different inputs. That file cannot be decompressed reliably (which of the two originals should that yield? ), which contradicts the assumption that the algorithm was lossless. We must therefore conclude that our original hypothesis (that the compression function makes no file longer) is necessarily untrue. Most practical compression algorithms provide an "escape" facility that can turn off the normal coding for files that would become longer by being encoded. In theory, only a single additional bit is required to tell the decoder that the normal coding has been turned off for the entire input; however, most encoding algorithms use at least one full byte (and typically more than one) for this purpose. For example, deflate compressed files never need to grow by more than 5 bytes per 65,535 bytes of input. In fact, if we consider files of length N, if all files were equally probable, then for any lossless compression that reduces the size of some file, the expected length of a compressed file (averaged over all possible files of length N) must necessarily be greater than N. So if we know nothing about the properties of the data we are compressing, we might as well not compress it at all. A lossless compression algorithm is useful only when we are more likely to compress certain types of files than others; then the algorithm could be designed to compress those types of data better. Thus, the main lesson from the argument is not that one risks big losses, but merely that one cannot always win. To choose an algorithm always means implicitly to select a subset of all files that will become usefully shorter. This is the theoretical reason why we need to have different compression algorithms for different kinds of files: there cannot be any algorithm that is good for all kinds of data. The "trick" that allows lossless compression algorithms, used on the type of data they were designed for, to consistently compress such files to a shorter form is that the files the algorithms are designed to act on all have some form of easily modeled redundancy that the algorithm is designed to remove, and thus belong to the subset of files that that algorithm can make shorter, whereas other files would not get compressed or even get bigger. Algorithms are generally quite specifically tuned to a particular type of file: for example, lossless audio compression programs do not work well on text files, and vice versa. In particular, files of random data cannot be consistently compressed by any conceivable lossless data compression algorithm; indeed, this result is used to define the concept of randomness in Kolmogorov complexity. It is provably impossible to create an algorithm that can losslessly compress any data. While there have been many claims through the years of companies achieving "perfect compression" where an arbitrary number N of random bits can always be compressed to N − 1 bits, these kinds of claims can be safely discarded without even looking at any further details regarding the purported compression scheme. Such an algorithm contradicts fundamental laws of mathematics because, if it existed, it could be applied repeatedly to losslessly reduce any file to length 1. that there is no algorithm to determine whether a file is incompressible in the sense of Kolmogorov complexity. Hence it is possible that any particular file, even if it appears random, may be significantly compressed, even including the size of the decompressor. An example is the digits of the mathematical constant pi, which appear random but can be generated by a very small program. However, even though it cannot be determined whether a particular file is incompressible, a simple theorem about incompressible strings shows that over 99% of files of any given length cannot be compressed by more than one byte (including the size of the decompressor).
N < M болғандықтан, ұзындығы N болатын әрбір файл сығылу кезінде өз өлшемін сақтайды. Мұндай 2N файл болуы мүмкін. F файлымен бірге, бұл 2N+1 файлды құрайды, олардың барлығы ұзындығы N болатын 2N файлдың біріне сығылады.
Assume that each file is represented as a string of bits of some arbitrary length. Suppose that there is a compression algorithm that transforms every file into an output file that is no longer than the original file, and that at least one file will be compressed into an output file that is shorter than the original file. Let M be the least number such that there is a file F with length M bits that compresses to something shorter. Let N be the length (in bits) of the compressed version of F.
Because N<M, every file of length N keeps its size during compression. There are 2N such files possible. Together with F, this makes 2N+1 files that all compress into one of the 2N files of length N.
But 2N is smaller than 2N+1, so by the pigeonhole principle there must be some file of length N that is simultaneously the output of the compression function on two different inputs. That file cannot be decompressed reliably (which of the two originals should that yield? ), which contradicts the assumption that the algorithm was lossless. We must therefore conclude that our original hypothesis (that the compression function makes no file longer) is necessarily untrue. Most practical compression algorithms provide an "escape" facility that can turn off the normal coding for files that would become longer by being encoded. In theory, only a single additional bit is required to tell the decoder that the normal coding has been turned off for the entire input; however, most encoding algorithms use at least one full byte (and typically more than one) for this purpose. For example, deflate compressed files never need to grow by more than 5 bytes per 65,535 bytes of input. In fact, if we consider files of length N, if all files were equally probable, then for any lossless compression that reduces the size of some file, the expected length of a compressed file (averaged over all possible files of length N) must necessarily be greater than N. So if we know nothing about the properties of the data we are compressing, we might as well not compress it at all. A lossless compression algorithm is useful only when we are more likely to compress certain types of files than others; then the algorithm could be designed to compress those types of data better. Thus, the main lesson from the argument is not that one risks big losses, but merely that one cannot always win. To choose an algorithm always means implicitly to select a subset of all files that will become usefully shorter. This is the theoretical reason why we need to have different compression algorithms for different kinds of files: there cannot be any algorithm that is good for all kinds of data. The "trick" that allows lossless compression algorithms, used on the type of data they were designed for, to consistently compress such files to a shorter form is that the files the algorithms are designed to act on all have some form of easily modeled redundancy that the algorithm is designed to remove, and thus belong to the subset of files that that algorithm can make shorter, whereas other files would not get compressed or even get bigger. Algorithms are generally quite specifically tuned to a particular type of file: for example, lossless audio compression programs do not work well on text files, and vice versa. In particular, files of random data cannot be consistently compressed by any conceivable lossless data compression algorithm; indeed, this result is used to define the concept of randomness in Kolmogorov complexity. It is provably impossible to create an algorithm that can losslessly compress any data. While there have been many claims through the years of companies achieving "perfect compression" where an arbitrary number N of random bits can always be compressed to N − 1 bits, these kinds of claims can be safely discarded without even looking at any further details regarding the purported compression scheme. Such an algorithm contradicts fundamental laws of mathematics because, if it existed, it could be applied repeatedly to losslessly reduce any file to length 1. that there is no algorithm to determine whether a file is incompressible in the sense of Kolmogorov complexity. Hence it is possible that any particular file, even if it appears random, may be significantly compressed, even including the size of the decompressor. An example is the digits of the mathematical constant pi, which appear random but can be generated by a very small program. However, even though it cannot be determined whether a particular file is incompressible, a simple theorem about incompressible strings shows that over 99% of files of any given length cannot be compressed by more than one byte (including the size of the decompressor).
Бірақ 2N, 2N+1-ден кіші болғандықтан, «көгершін ұясы» принципі бойынша ұзындығы N болатын кейбір файл екі түрлі кіріс бойынша сығылу функциясының бір мезгілде шығысы болуы керек. Мұндай файлды сенімді түрде декомпрессиялау мүмкін емес (екі түпнұсқаның қайсысын алу керек?), бұл алгоритм жоғалмайтын болды деген болжамға қайшы келеді. Сондықтан, бастапқы гипотезамыз (сығылу функциясы ешқандай файлды үлкейтіп жібермейді) міндетті түрде дұрыс емес деп қорытындылауымыз керек. Көптеген практикалық сығылу алгоритмдері файлдарды кодтағанда олардың көлемін үлкейтетін жағдайда қалыпты кодтауды өшіретін «эскейп» мүмкіндігін ұсынады. Теориялық тұрғыдан алғанда, декодерге кіріс бойынша қалыпты кодтау өшірілгенін хабарлау үшін тек бір қосымша бит қажет; алайда, көптеген кодтау алгоритмдері осы мақсат үшін кем дегенде бір толық байтты (көбінесе бірнешеуін) пайдаланады. Мысалы, deflate сығылған файлдар 65 535 байт кіріс үшін 5 байттан артық өспеуі керек. Шын мәнінде, егер біз ұзындығы N болатын файлдарды қарастырсақ, егер барлық файлдар бірдей ықтимал болса, онда кейбір файлдың көлемін азайтатын кез келген жоғалмайтын сығылу үшін, сығылған файлдың күтілетін ұзындығы (ұзындығы N болатын барлық файлдардың орташасы) міндетті түрде N-ден үлкен болуы керек. Сондықтан, егер біз сығылатын деректердің қасиеттері туралы ештеңе білмейтін болсақ, оны мүлдем сығымауымыз керек. Жоғалмайтын сығылу алгоритмі тек кейбір файл түрлерін басқаларына қарағанда сығыуға ықтимал болған кезде ғана пайдалы; содан кейін алгоритм осы типтегі деректерді жақсы сығыу үшін жасалуы мүмкін. Осылайша, аргументтен алынған негізгі сабақ – үлкен шығынға ұшырау емес, тек әрқашан жеңіске жете алмайтынымыз. Алгоритмді таңдау – барлық файлдардың пайдалы түрде қысқа болатын кіші жиынтығын таңдауды білдіреді. Бұл әртүрлі файлдар үшін әртүрлі сығылу алгоритмдерінің қажеттілігінің теориялық себебі: барлық деректер үшін жақсы алгоритм болуы мүмкін емес. Жоғалмайтын сығылу алгоритмдері, олар үшін жасалған деректердің түрінде, осындай файлдарды үнемі қысқа формаға сығып алуға мүмкіндік беретін «хикмет» – алгоритмдер әрекет етуге арналған файлдардың барлығы алгоритм алып тастауға арналған оңай модельденген артықшылыққа ие, сондықтан ол алгоритм қысқара алатын файлдардың кіші жиынтығына жатады, ал басқа файлдар сығылмайды немесе тіпті үлкейеді. Алгоритмдер әдетте файлдың белгілі бір түріне арнайы бапталады: мысалы, жоғалмайтын аудио сығылу бағдарламалары мәтіндік файлдарда жақсы жұмыс істемейді және керісінше. Әсіресе, кездейсоқ деректер файлдарын кез келген жоғалмайтын деректерді сығымдау алгоритмімен тұрақты түрде сығыстыру мүмкін емес; шын мәнінде, бұл нәтиже Колмогоров күрделілігіндегі кездейсоқтық ұғымын анықтау үшін қолданылады. Кез келген деректерді жоғалмайтын сығылатын алгоритмді жасау мүмкін емес. Компаниялардың «мүлтіксіз сығылуға» жеткендігі туралы көптеген мәлімдемелер болған, онда кездейсоқ биттердің кез келген саны әрқашан N-1 битке дейін сығылуы мүмкін, мұндай мәлімдемелерді тіпті болжамды сығылу схемасына қатысты қосымша мәліметтерге назар аудармай-ақ қауіпсіз түрде жобауға болады. Мұндай алгоритм математиканың негізгі заңдарына қайшы келеді, өйткені егер ол бар болса, кез келген файлды ұзындығы 1-ге дейін жоғалмайтын түрде азайту үшін қайта-қайта қолданылуы мүмкін. Сондай-ақ, файлдың Колмогоров күрделілігінің мағынасында сығылмайтынын анықтайтын алгоритм жоқ. Сондықтан, кез келген нақты файл, тіпті ол кездейсоқ көрінгенмен, оның декомпрессорының мөлшеріне дейін айтарлықтай сығылуы мүмкін. Мысалы, математикалық тұрақты пи сандары кездейсоқ көрінеді, бірақ өте кішкентай бағдарламамен жасалуы мүмкін. Алайда, нақты файлдың сығылмайтынын анықтау мүмкін болмаса да, сығылмаған тізбектер туралы қарапайым теорема кез келген ұзындықтағы файлдардың 99%-дан астамын бір байттан артық (декомпрессордың мөлшеріне қоса) сығылмауға болатынын көрсетеді.
Assume that each file is represented as a string of bits of some arbitrary length. Suppose that there is a compression algorithm that transforms every file into an output file that is no longer than the original file, and that at least one file will be compressed into an output file that is shorter than the original file. Let M be the least number such that there is a file F with length M bits that compresses to something shorter. Let N be the length (in bits) of the compressed version of F.
Because N<M, every file of length N keeps its size during compression. There are 2N such files possible. Together with F, this makes 2N+1 files that all compress into one of the 2N files of length N.
But 2N is smaller than 2N+1, so by the pigeonhole principle there must be some file of length N that is simultaneously the output of the compression function on two different inputs. That file cannot be decompressed reliably (which of the two originals should that yield? ), which contradicts the assumption that the algorithm was lossless. We must therefore conclude that our original hypothesis (that the compression function makes no file longer) is necessarily untrue. Most practical compression algorithms provide an "escape" facility that can turn off the normal coding for files that would become longer by being encoded. In theory, only a single additional bit is required to tell the decoder that the normal coding has been turned off for the entire input; however, most encoding algorithms use at least one full byte (and typically more than one) for this purpose. For example, deflate compressed files never need to grow by more than 5 bytes per 65,535 bytes of input. In fact, if we consider files of length N, if all files were equally probable, then for any lossless compression that reduces the size of some file, the expected length of a compressed file (averaged over all possible files of length N) must necessarily be greater than N. So if we know nothing about the properties of the data we are compressing, we might as well not compress it at all. A lossless compression algorithm is useful only when we are more likely to compress certain types of files than others; then the algorithm could be designed to compress those types of data better. Thus, the main lesson from the argument is not that one risks big losses, but merely that one cannot always win. To choose an algorithm always means implicitly to select a subset of all files that will become usefully shorter. This is the theoretical reason why we need to have different compression algorithms for different kinds of files: there cannot be any algorithm that is good for all kinds of data. The "trick" that allows lossless compression algorithms, used on the type of data they were designed for, to consistently compress such files to a shorter form is that the files the algorithms are designed to act on all have some form of easily modeled redundancy that the algorithm is designed to remove, and thus belong to the subset of files that that algorithm can make shorter, whereas other files would not get compressed or even get bigger. Algorithms are generally quite specifically tuned to a particular type of file: for example, lossless audio compression programs do not work well on text files, and vice versa. In particular, files of random data cannot be consistently compressed by any conceivable lossless data compression algorithm; indeed, this result is used to define the concept of randomness in Kolmogorov complexity. It is provably impossible to create an algorithm that can losslessly compress any data. While there have been many claims through the years of companies achieving "perfect compression" where an arbitrary number N of random bits can always be compressed to N − 1 bits, these kinds of claims can be safely discarded without even looking at any further details regarding the purported compression scheme. Such an algorithm contradicts fundamental laws of mathematics because, if it existed, it could be applied repeatedly to losslessly reduce any file to length 1. that there is no algorithm to determine whether a file is incompressible in the sense of Kolmogorov complexity. Hence it is possible that any particular file, even if it appears random, may be significantly compressed, even including the size of the decompressor. An example is the digits of the mathematical constant pi, which appear random but can be generated by a very small program. However, even though it cannot be determined whether a particular file is incompressible, a simple theorem about incompressible strings shows that over 99% of files of any given length cannot be compressed by more than one byte (including the size of the decompressor).
Математикалық білімі
Абстрактты түрде, компрессиялық алгоритмді реттіліктерге (әдетте октеттерге) әсер ететін функция ретінде қарастыруға болады. Компрессия табысты болады, егер нәтижедегі реттілік бастапқы реттіліктен қысқа болса (және декомпрессиялау нұсқаулары да ескерілсе). Компрессиялық алгоритм жоғалтусыз болуы үшін, компрессиялық функция "нақты" биттік реттіліктерді "қысқалған" биттік реттіліктерге инъекциялық түрде бейнелеуі керек. Клубшаңдық принцип ұзындығы N реттіліктер жиыны мен ұзындығы N-1 реттіліктер жиынының кез келген ішкі жиыны арасындағы бір-бірге сәйкестіктің болуын қанағаттандырмайды. Сондықтан, кез келген мүмкін кіріс реттілігінің көлемін қысқартатын жоғалтусыз алгоритм жасау мүмкін емес.
Нақты сығылу теориясындағы қолдану нүктелері
Нақты сығылу алгоритмдерін жобалаушылар жоғары ақпараттық энтропияға ие ағындарды сығымдау мүмкін емес екенін мойындайды және осыған сәйкес, осы жағдайды анықтау және өңдеуге арналған мүмкіндіктерді қосады. Анықтаудың қарапайым жолы – бастапқы сығымдау алгоритмін қолданып, оның нәтижесі кірістен кішірек екенін тексеру. Кейде анықтау эвристикалық әдістермен жасалады; мысалы, сығымдау қолданбасы ".zip", ".arj" немесе ".lha" сопасымен аяқталатын файлдарды ешқандай күрделі анықтаусыз сығымдалмайтын деп есептеуі мүмкін. Осы жағдайды басқарудың кең таралған тәсілі – кіріс немесе кірістің сығымдалмайтын бөліктерін шығыста көрсету, сығымдау шығындарын азайту. Мысалы, zip дерек форматы мұрағатқа өзгеріссіз көшірілген кіріс файлдары үшін 'Stored' сығымдау әдісін анықтайды.
Миллиондық кездейсоқ сандық сынақ
Марк Нельсон, comp.compression тобында пайда болған "керемет" сығылу алгоритмдері туралы айтылған сөздерге жауап ретінде, 415,241 байт көлемінде, жоғары энтропиялы мазмұнға ие бинарлық файл құрастырып, оны қайта құруға қатесіз мүмкіндік беретін, оның кірісімен бірге одан кіші болатын бағдарлама жазған әркімге 100 доллар сыйлық беруге публично шақыру жасады. Майк Голдман да осыған ұқсас сынақ ұйымдастырып, 5000 доллар сыйақы белгіледі.