Случвало ли ви се е след дълго пътуване да си спомняте само някои моменти от него? А всичките отпуски от изтеглите няколко години да се слеят в едно цяло? А от ученическите си години да помните имената на само няколко души? Това съвсем не е загуба на паметта, както би могло да ви се стори. Точно обратното, това е признак и цялостна функция на един добре развит човешки интелект, който се е научил и умее много ефективно да компресира данните.
Всъщност спомените от човешката памет могат да бъдат измъкнати (декомпресирани) с помощта на обикновена регресивна хипноза. Просто в един определен момент тези спомени не са необходими и затова са записани и съхранени в компресиран вид в лентов стример в далечните ъгълчета на нашата памет.
Всички познаваме и използваме компютърните архиватори: включително ZIP, RAR, Brotli и т.н. Но малцина ги възприемат като модел за интелигентност. Това дори изглежда странно на пръв поглед. Въпреки че, ако се замислите, перфектната компресия е синоним на разбирането.
Ако погледнем исторически теорията за компресиране на информацията и нарастващата сложност на алгоритмите, които вече преминават към използването на невронни мрежи, то сякаш пред очите ни се е появило и развило някакво живо същество. Може дори да си фантазираме, че неговата сложност ще нарасне толкова много над нашето ниво на разбиране, че това нещо ще може да компресира всичко на света до числото „42“.
Вече без шега, всички алгоритми за компресиране се разделят на две големи категории: компресиране със загуба и компресиране без загуба. Първата категория често се използва за компресия на снимки, видеа и аудио – тоест, може да се каже за аналогови нервни сигнали (зрение, слух), а втората – за цифрови. Компресията без загуби се използва при компресията и архивирането на данни. В този случай до голяма степен се разчита на намирането на дубликати в някакъв масив от цифрова информация.
За първия в света архиватор може да се счита Морзовата азбука (1838 година), която използва по-кратки кодове за кодиране на по-често срещаните букви в английския език – буквите e и t.
Историята на компютърните алгоритми за компресия без загуби датира от 1949 година, когато Клод Шанън и Робърт Фано изобретяват алгоритъма Шанън-Фано, при който кодовете на символите в блока се основават на вероятността за появата на даден символ. Вероятността за появата на даден символ е обратно пропорционална на дължината на кода, което води до по-кратък начин на представяне на данните.
Две години по-късно идва ред на студента Дейвид Хъфман, който е в курса на Робърт Фано в Масачузетския технологичен институт (MIT) и подготвя курсова работа, в която описва най-ефикасния по онова време метод за двоично кодиране, сега известен като кода на Хъфман, който е подобен на кода на неговия учител.
Ерата LZ77
В края на 1970-те години компютрите стават по-популярни и се появява първият софтуер за компресиране и създаване на на резервни копия. Първоначално се използват кодовете на Хъфман, а през 1977 година е изобретен революционният алгоритъм Lempel-Ziv-Welch (LZ77) – първият алгоритъм, използващ речници. По-специално, първоначално се използва динамичен речник (известен също като плъзгащ се прозорец), който е идеален за намиране на повтарящи се последователности от битове.
LZ77 определя развитието на архиваторите в продължение на десетилетия, с по-нататъшни технически подобрения и много разклонения, показани на диаграмата по-горе. Използването на LZ78 (със статичен речник) бе възпрепятствано от появата през 1984 година на производния алгоритъм LZW, който бе успешно патентован с изискване за плащане на лицензна такса. След това собственикът на патента започна да съди другите разработчици и дори крайните потребители за използване на GIF формата без лиценз.
С разпространението на интернет през 80-90-те години на миналия век производните алгоритми на LZ77 станаха основата на нови формати за компресиране на файловете: ZIP (1989 г.), GIF (1987 г.), PNG (1994 г.), RAR (комбинация от PPM и LZSS, 1993 г.) и др. Първият масов архиватор е ARC с отворен код през 1985 г. и PKARC (ZIP) през 1989 г. След това производните на LZ77 започнаха да се използват буквално навсякъде, включително в HTTP и SSL.
Новите алгоритми. Невронните мрежи. Компресията с помощта на GPU
От една страна, повечето от съвременните архиватори използват базовите техники, но се въвеждат и някои принципно нови подходи. В началото на 2000-те години алгоритъмът PAQ, базиран на смесване на контекста (context mixing, CM), разгледан по-долу, става много популярен, а през 2019 г. известният програмист Фабрис Белар представи уникалния архиватор NNCP, разработен на базата на архитектура на невронна мрежа с трансформиращ механизъм (през 2021 г. излиза втората версия). Основните принципи са описани в научни статии от 2019 г. и 2021 г. Последната версия е 3.1 и вече е постигнала най-високото в света съотношение на компресия в стандартния критерий за компресиране на голям текст – тестът Large Text Compression Benchmark (109 байта на английската версия на Wikipedia). Това постави началото на използването на невронните мрежи за компресиране на данни.
Лидерската петорка включва nncp, cmix, tensorflow-compress, cmix-hp и starlit. Повечето от включените в топ-20 рейтинга архиватори използват алгоритъма за смесване на съдържанието (context mixing, CM), въпреки че има някои уникални алгоритми за компресия от рода на NNCP. Започват масовите експерименти с използването на изкуствен интелект и невронни мрежи.
CMIX и много други архиватори от 2002-2019 години използват смесване на контекста с предварителна обработка на речника – революционна някога техника, при която множество статистически модели се комбинират интелигентно по такъв начин, че предвиждат следващия символ по-добре, отколкото който и да е от моделите сам по себе си.
PAQ (2002 г.) е един от най-обещаващите CM алгоритми и от създаването му досега са създадени десетки варианти, като някои от тях достигат рекордни коефициенти на компресия.
Архиваторът CMIX се считаше за световен лидер в компресията преди появата на NNCP. Той се базира на кодовете paq8hp12any и paq8l (съвременни модели от фамилията PAQ).
Сред другите нововъведения от последните години можем да споменем алгоритъма Brotli-G, базиран на обичайния Brotli (класически LZ77 + код на Huffman), но оптимизиран за GPU. Това означава, че получаваме компресия с хардуерно ускорение. Като се има предвид потенциалната употреба на невронните мрежи, подобно хардуерно ускорение е много подходящо. Brotli е аутсайдер по отношение на ефективността, но е първият в света архиватор, базиран на GPU. Да, и първоначално е създаден за криптиране на интернет трафика и е фокусиран основно върху скоростта в реално време, а не върху компресията. Всички съвременни браузъри поддържат тази функция.
Компресията на информацията като еквивалент на интелекта
Ясно е защо Фабрис Белар е решил да използва невронните мрежи именно за компресиране на данни. Това е напълно логично, като се има предвид фактът, че някои учени свързват компресирането на данни с общата интелигентност.
Работата е в това, че ефективната компресия изисква разбиране на данните. Колкото по-добро е разбирането, толкова повече са моделите, по които се подреждат и групират данните. И толкова по-ефективна става компресията. Така например в милиардите числа на екрана изведнъж виждаме координатите на точките на една окръжност, а след това можем да компресираме цели терабайти информация само в три числа (координатите на центъра и радиуса). Почти като във вица за ученика с архиватора, който криптира всичко в 1 байт, но не може да го декриптира.
Следователно компресирането на информацията изисква нейното разбиране. Оттук и аналогията с интелигентността, която също намира смисъл в околните явления. В милиардите хаотични събития в заобикалящия ни свят ние виждаме физически обекти и дори абстрактни понятия и ги „компресираме“ до една-единствена дума, схема или изображение.
Като пример можем да посочим диаграмите на Файнман, които „компресират“ описанието на сложни физични процеси до една простичка картина.
Това всъщност е работата на интелекта. Ричард Файнман получи Нобелова награда предимно за най-ефективното компресиране на информацията.
Грубо казано, един човек може да компресира и разбира само прости обекти (минимална компресия, среден коефициент на интелигентност), а друг – по-сложни (максимална компресия на информацията, висок коефициент на интелигентност), които са извън разбирането на първия „архивиращ“. Колкото по-висок е коефициентът на компресия на информацията, толкова по-добър и по-ефективен е моделът на данните за заобикалящия го свят.
Между другото, тази теза е в основата на компресионизма – теорията на мисленето на базата на компресирането на данни. Всъщност, ако разгледаме човешкия ум и интелект в този им вид, компресирането на данни е основната концепция в живота ни.
Авторите на тази наскоро публикувана научна работа дават примери за компресиране на данни, които се основават на разбирането на определени концепции от високо ниво. Например, безкрайната последователност от числа
4, 6, 8, 12, 14, 18, 20, 24…
…се свежда до една фраза „нечетни прости числа +1“.
Тук се вижда и връзката между компресирането на данните и прогнозирането на бъдещето. Това е като в живота: ако имате по-добър модел на компресия (разбиране) на света, вие сте по-добри в прогнозирането на това, което другите хора ще направят. Теоремата на Леонид Левин (1974 г.) за кодиране на информацията показва, че с голяма вероятност най-компактният модел е най-правилният (бръсначът на Окам).
В научна статия от 2009 г. Шмидхубер предлага компресирането на данни да е прост принцип, който обяснява основните аспекти на субективната красота, новостта, изненадата, интереса, вниманието, любопитството, творчеството, изкуството, науката, музиката и шегите. Той твърди, че данните стават временно интересни, веднага щом наблюдателят се научи да ги предсказва (т.е. да ги компресира) по по-добър начин, правейки ги субективно по-прости и по-красиви.
От тази гледна точка любопитството може да се разглежда като желание да се създават и откриват модели, които позволяват напредък в компресията, като нивото на любопитство е свързано с необходимите усилия за постигането на това.
По подобен начин теорията за субективната вероятност на Макгуйър (2013), както и теорията за простотата на Десалес (2011) разглеждат компресирането на данни като ключов обяснителен конструкт във феномена на изненадата. Когато хората се сблъскат със стимул, който се очаква да бъде случаен, но се оказва компресируем, той предизвиква реакция на изненада (или смях).
Според Магуайър хората често разчитат на компресирането на данни, а не на теорията на вероятностите, за да вземат решения в много от сценариите на реалния свят. Ако се замислите, компресията е именно разбиране. Главната концепция в живота ни.
Може би силният изкуствен интелект би могъл да се формира някъде в симбиозата между чатботове (речта) и архиваторите (разбирането на значенията).