компресиране на данни и несвиваеми файлове

компресиране на данни и несвиваеми файлове

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

Естествено възниква въпросът: защо сега трябва да компресирате файлове, ако всички основни технически характеристики на всяка година или две удвояване на персонални компютри? Памет на съвременните персонални компютри 128 до 512 мегабайта дисково пространство като цяло десетки гигабайта. Тя ще изглежда, че не може особено тревожи за размера на файла.

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

Архиватори намалят някои от файловете в 5-10 пъти. Благодарение на това, което е възможно толкова много да се намали размера на файла? Някои файлове са построени не са оптимални по отношение на обема им. Например, една обща архиватор компресирате голям Microsoft Word файлове пет до шест пъти, а малката почти десет. За да прочетете сгъстен текстов файл, че е необходимо да се разхлабят и съща програма.

Много потребители първоначално дойде с брилянтна идея - да се опита да компресирате отново вече компресирани файлове. Първият опит разочароващо - сгъстен файлове не са компресирани по-нататък, с всички архиви. Защо се случва това?

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

Когато програмните файлове се обработват по подходящ начин, намери модели, извадени малко значима информация, след това втори път тя имаше тази операция няма да бъде в състояние да издържи. Ето защо, когато файлът повторна компресия не се намалява. Може да изглежда странно, но няма излишна информация и случайни данни, като например радиочестотен шум върху записите, където няма предаване станции или в резултат на програмата - генератора на случайни числа. Факт е, че в набор от истински случайни числа архиватор не можете да намерите закономерности. Оказва се, че в кратък енциклопедия и в резултат се изпълнява Sportloto машина не може да намери излишна информация в Енциклопедия - знания се концентрира и циркулацията на спортен тотализатор - дълга поредица от случайни числа.

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

Интернет - много комфортна среда за комуникация професионалисти. Отдалечени едно от други специалисти от различни страни да обсъдят въпроси от своята област. Мрежата е добре позната мрежа йерархия на Usenet. Тя обединява хиляди дискусионни групи по различни теми. Той е там и група, наречена COMP.COMPRESS. В нея експерти обсъждат компресия, т.е. компресиране на информацията. Участва в групови дискусии изисква значителни обучение. Ето защо, случайни посетители в COMP.COMPRESS не остана дълго. Въпреки това, от време на време някой от новодошлите се предполага, в качеството на експерти в компресия около същите като в физиката вечни проекти за движение, както и историци - Фоменко работи. Условно, проблемът може да се нарече "чудо компресор".

Ако говорим за компресия без загуби, а след това вече не е пионерска работа. Последна фундаментално нов алгоритъм за компресиране bezpoternogo е изобретен през 80-те години, и има малко употребяван заради голямата сложност. Освен това, както вече бе споменато, има доказателства, че по принцип не може да се компресира без загуба. Това е, на първо място - случайни данни, и второ - компресирани по-рано. Ако приемем, че компресорът компресира Lossless всички файлове, можете да вземете файл и да го намали веднъж, а след това отново минава през компресора и да се намали отново. Ако операцията да се повтаря отново и отново, в края на краищата, файлът се свива до едно малко, като запазва всички полезната информация, която, разбира се - това е абсурдно.

Аз съм готов да плати пет хиляди долара за всеки, който отговаря на следните условия. Ти ми кажи какъв размер може да компресира файла и да докаже сериозността си да ми изпратите $ 100. Аз генериране на файл и аз ви изпращам. Научите ли го, както искате, и след това да компресирате и да ми изпратите заедно с програмата за освобождаване. Си отворя файл и да провери - дали информацията не е била изгубена. Ако не е имало, и компресиран файл, заедно с декомпресор макар и малко по-малък от оригиналния файл, ще ти 5000, плюс платите $ 100.

Четох вашето предложение. Това звучи много съблазнително, че все още е в сила? Ако е така, бих искал да знам подробностите на декомпресора - трябва да се движат по някои или достатъчно на която и да е платформа, като Linux?

Да, офертата е валидна. Linux-а е достатъчно. Искаш ли да поеме риска?

Аз все още мисля за него. Трябва само компресиран файл?

Ти казваш какъв размер е необходимо даден файл, и да ми изпратите $ 100. Аз генериране на файл и аз ви изпращам. Можете да ми го изпратите заедно с компресиран декомпресора. Ако компресиран файл с декомпресора по-малък от оригинала - Аз ви изпращам на 5000. Ако можеше да не - пак можете да ми изпратите $ 100 и опитайте отново.

Мога ли да изпратя сгъстен информация не е един единствен файл, както и няколко части, както и декомпресия, което ще възстанови оригинала?

Приемам предизвикателството. Как можете да изпратите пари?

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

Аз все още мисля за оптималния размер, но мисля, че ще бъде по-малко от гигабайт. Имате ли навсякъде достъп до FTP-сървър анонимен?

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

Това, което ги прави Патрик Kreyg? Неговата версия на събитията, той се поставя в Интернет:

Ето какво измислих Патрик. Да предположим, че имаме дълъг произволен файл с данни. Ние намираме в този файл, например буквата "А". Сега на буквата "А", ние нарязани файла на две части, и буквата на емисиите. Ние получаваме два файла, които заедно ще бъдат един байт по-малко от оригинала. За да възстановите оригиналната, просто трябва да се залепят двете части, които вмъква между буквата "А".

Разбира се, на оригиналния файл не може да се реже на две, и три и повече, в зависимост от "А" Избрахме писмото се намира в много пъти. Ако ние се занимаваме с случаен данни, а след това всеки символ ще се срещне с приблизително на всеки 255 знака. По този начин, рязане на един дълъг файл в тези места, където е буквата "А" и да го хвърлят, ние правим един голям файл в верига от малки, спестявайки с четири байта на килобайт. Човек може само да напиша една проста програма, която може да се слепват от различни кубчета един голям файл, оригинала.

Патрик, тази програма, която може да се нарече с декомпресора, е толкова малка, колкото 156 байта. Файлът източник в 3 мегабайта, може да бъде разделена на около 3000 бройки, но Патрик реши да спре след втората стотица, тъй като алгоритъмът беше ясно, и резултатът е очевиден.

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

Това Патрик Kreyg каза:

Ако операционната система за дълго файл изисква по-малко пространство, отколкото двамата кратко, това е неин проблем, не мой.

В чест на Patrika Kreyga, той не настоява за присъждане и призна по-късно, че не се е очаквало да се печелят пет хиляди долара. Нейната основна цел е да се "надхитри хитър" - за да се покаже, че самоуверен Goldman може да бъде спечелена, с неговите условия, ако вземем предвид проблема като пъзел, с помощта на размита формулиране на проблема.