След като гледах драмата на HBO "Силициевата долина", винаги съм се интересувал от алгоритми за компресия. Ричард Хендрикс и неговият алгоритъм за компресия в средата навън в него, разбира се, са фалшиви, но след като търсих в Google, открих, че в реалния живот има истински гений на алгоритъма за компресия.
Ян Колет изобретява алгоритъма за компресия LZ4 през 2011 г. Разбира се, алгоритъмът LZ4 не е толкова впечатляващ като middle out, но е известен с непобедима скорост на компресия и по-бързата скорост на декомпресия, когато определена степен на компресия може да се гарантира.
Тук няма да навлизам в подробности относно оценката на скоростта на компресия, ако се интересувате, можете да прочетете тази сравнителна статия:Входът към хиперлинк е видим.
Също така е приложен github адресът на LZ4:Входът към хиперлинк е видим.
Тази статия се фокусира върху обяснението на принципа на алгоритъма за компресия LZ4. Велик бог е написал обяснение на алгоритъма LZ4 преди:Входът към хиперлинк е видим.Но когато учех преди, усетих, че тази статия не е много приятелска към начинаещи, затова започнах нова статия за начинаещи като мен.
Ако го обобщиш в едно изречение, LZ4 е LZ77, който съхранява речник с хеш таблица с размер 16k и опростява извличането.
LZ4 е алгоритъм за компресия без загуби, който предлага скорост на компресия > 500 MB/s на ядро, което може да се мащабира с многоядрени процесори. Разполага с изключително бързи декодери със скорости от няколко GB/s на ядро, често достигащи лимити на RAM при многоядрени системи.
Скоростта може да се регулира динамично, като се избира "фактор на ускорение", който заменя компресионното съотношение за по-висока скорост. От друга страна, е предоставен и производен LZ4_HC с висока компресия, който увеличава компресията за сметка на времето на процесора. Всички версии имат еднаква скорост на декомпресия.
Какво е LZ77?
Компресия и принцип на LZ77
LZ77 е алгоритъм, който прилага речник за компресия. С прости думи, това е да позволим на програмата да наблюдава (погледнете речника) дали данните, които се виждат в момента, са дублирани с предишните, и ако е така, запазваме разстоянието (офсет) и дължината на дублиращите полета, за да заменим дублиращите се полета и да компресираме данните.
препраткаВходът към хиперлинк е видим.
За низ от букви A A B C B B A B C, когато се прочете второто A, програмата запазва (1,1) (1 цифра от предишната, дължина 1), и по същия начин, когато се прочете второто B, програмата запазва (2,1) (разстояние 2, дължина 1).
Но ако низът е по-дълъг и програмата постоянно записва данните в речника, търсенето на дублиращи се полета става изключително времеемко, защото в най-лошия случай програмата преминава през целия речник с всяка нова прочетена буква. LZ77 използва метод с плъзгащ се прозорец за решаване на този проблем.
Подобно на началната точка при TCP чрез плъзгащ се прозорец, плъзгащият се прозорец може да свие кеш площта, за да избегне обработка на твърде много кеширани данни едновременно. В LZ77 речникът не се увеличава постоянно, а изхвърля първите символи, добавени в речника, когато той надвиши максималния размер, определен от речника, за да се гарантира, че размерът на речника винаги остава на определения максимален размер.
Да предположим, че дължината на речника е 3
| Речник |
| A | A B C B B A B C
Изход (0,0,A)
| A A | Б В В Б Б А Б В
Изход(1,1)
| А А Б | Ц Б Б А Б В В
Изход (0,0,B)
A | А Б В | Б Б А Б В
Изход (0,0,C)
A A | B C B | Б А Б В
Изход(2,1)
Другата част от плъзгащия прозорец е кешът, който трябва да се търси (буферът за гледане няма официален превод). Кешът, който трябва да се търси, е некомпресираната част от дължината, най-близо до речника. Алгоритъмът LZ77 ще съвпадне с най-дългия низ в тази част на знака, който е същият като речника. Предишният пример може да се разглежда като буфер за поглед напред на 1.
Да предположим, че дължината на речника е 5, а размерът на кеша, който трябва да се търси, е 3
| Речник | Буфер за гледане напред |
A | A B C B B | А Б В |
Изход(5,3)
Най-дългият низ, който съвпада, е ABC
Пълен процес на компресия:
Да предположим, че дължината на речника е 5, а размерът на кеша, който трябва да се търси, е 3
| Речник | Буфер за гледане напред |
| А А Б | Ц Б Б А Б В В
Изход (0,0,A)
| A | А Б В | Б Б А Б В
Изход(1,1)
| A A | B C B | Б А Б В
Изход (0,0,B)
| А А Б | C B B | А Б В
Изход (0,0,C)
| A A B C | B B A | Б В
Изход(2,1)
| A A B C B | Б А Б | C
Изход(1,1)
A | A B C B B | А Б В |
Изход(5,3)
A A B C | B B A B C | 。。。 |
Няма нужда да се съхранява речникът в изходния файл на компресора, защото програмата за декомпресия възстановява речника чрез съвпадение на изходните единици.
Процес на декомпресия
Едно от големите предимства на алгоритъма LZ77 е, че се декомпресира много бързо.
Ако първата съвпадяща единица е (0,0,A), тогава A е изход.
Втората съвпадяща единица е (1,1), която копира предишния бит в изходния низ и извежда A, ако дължината на копието е 1.
。。。
Ако последната съвпадяща единица е (5,3), тогава погледнете назад 5 бита в изходния низ, а ако дължината на копието е 3, тогава изхвърлете A, B, C.
Най-времеемката част от компресията на алгоритъма LZ77 е намирането на най-дългия съвпадащ символ в кеша, който да бъде търсен в речника. Ако речникът и кешът за търсене са твърде кратки, шансовете за намиране на съвпадение са малки. Затова LZ4 промени алгоритъма за съвпадение за LZ77.
Първо, речникът на алгоритъма LZ4 е хеш таблица. Ключът в речника е 4-байтов низ, всеки клавиш съответства само на един слот, а стойността в слота е позицията на този низ.
Вместо да търси кеша, LZ4 чете по четири байта наведнъж от входния файл и след това търси слота, съответстващ на низа в хеш таблицата, който по-нататък се нарича настоящият низ.
Ако сте достигнали последните 12 знака, поставете ги директно в изходния файл.
Ако няма присвоена стойност в слота, това означава, че четирите байта се появяват за първи път, добавят тези четири байта и позиции към хеш таблицата и продължават търсенето.
Ако има присвояване в слота, това означава, че сме намерили съвпадаща стойност.
Ако стойността в слота плюс размерът на прозореца на плъзгача < позицията на текущия символ, тогава позицията на съвпадение надвишава размера на блока и програмата актуализира стойността в хеш слота до позицията на текущия низ.
LZ4 ще провери дали е имало хеш конфликт. Ако 4-те байта в слота не са същите като текущия низ, трябва да има хеш конфликт. Собственият xxhash на автора е известен и с ефективността си, но конфликтите са неизбежни. В случай на конфликт програмата също актуализира стойността в хеш слота до текущата позиция на низа
Накрая можем да потвърдим, че съвпадението е валидно и програмата ще продължи да проверява дали следващите знаци в съвпадащия низ са еднакви. Накрая копирайте всички символи от края на предишното валидно съвпадение в началото на това валидно съвпадение към компресирания файл и добавете последователността на съвпадение на това валидно съвпадение.
Collet нарича съответстващите единици, изходени от LZ4 последователности, и те образуват компресирания LZ4 файл. Подробностите са следните:
Токенът е с дължина 1 байт, като първите 4 думи са буквалната дължина, а последните 4 думи са дължината на съвпадението. Както беше споменато по-рано, всички символи от края на предишното валидно съвпадение до началото на това валидно съвпадение ще бъдат копирани в компресиран файл, тези некомпресирани файлове са буквални, а дължината им е буквална дължина.
Буквално последвано от отклонение. Както в LZ77, отклонението и дължината на съвпадение се отнасят до дължината на текущия низ от съвпадението, а дължината на съвпадение се отнася до дължината на съвпадение на настоящия низ със същия низ в речника. При декомпресията е да се премине през нея, за да се намери струната, която да се копира, и дължината за копиране. Големината на отклонението е фиксирана.
На фигурата, литералната дължина+ и съвпадение дължина+ са, ако литералните или съвпадения 4 думи в токена не са достатъчни, те ще продължат да се увеличават в съответните позиции. 4 думи могат да представляват 0-15, а ако има още, добавете един байт, тоест добавете 255 към размера, докато байтът стане по-малък от 255. В съвпадащата дължина 0 представлява 4 байта.
Последните 12 байта свършват буквално, защото са копирани директно.
Нека разгледаме кода (python е по-абстрактен)
Резюме Въпреки всичко това, все още не съм обобщил защо LZ4 е толкова бърз. Нека първо сравним търсенето в речника между LZ77 и LZ4. Родният LZ77 търси речници, като търси най-голямото съвпадение в кеша за търсене и в речника. Това е проблем при намирането на най-големия идентичен низ в две струни. Ако не използваме динамично програмиране, в най-лошия случай трябва да разгледаме всички поднизове на един низ и след това да ги съпоставим в друг низ. Ако ×използваме динамично програмиране, ще използваме таблица, която да държи най-дългото съвпадение в динамиката, което ще ни позволи да завършим съвпадението само в случая на O(m*n). И това е само за чифт кешове за търсене и речници. В най-лошия случай, ако няма съвпадения, LZ77 ще трябва да брои (дължината на целия файл – дължината на кеша, който трябва да се търси) колкото много такива проблеми с съвпадението. LZ4 всъщност използва по-голямо ниво на динамично програмиране: съхранява 4 байта и техните позиции в хеш таблица, а след това съпоставя нови 4 байта данни всеки път, само за да провери дали стойностите в хеш таблицата са валидни. След като намерите валидна съвпадяща стойност, ако разгледате последващите данни на двата набора съвпадения, можете да намерите и най-дългото съвпадение. Тъй като всеки ключ от хеш таблицата LZ4 съответства само на 1 слот, работата по намиране, добавяне и модифициране на хеш таблицата изисква само O(1). Ако се намерят повече съвпадения след съвпадение, са нужни повече групови сравнения, но в общото време тези сравнения ще заместят повече време за търсене на хеш таблицата, така че общото време на алгоритъма LZ4 е само O(n). Трябва да се възхищавам на красотата на алгоритъма на Коле! За да направи алгоритъма още по-бърз, Collet задава стандартния размер на хеш таблицата на 16k, което се препоръчва да не надвишава 32k, за да може да се постави в L1 кеша на почти всички процесори (Intel). Всички знаят, че скоростта и съотношението памет на кеша на процесора L1 са много различни, така че не е изненадващо, че LZ4 лети бързо, да не говорим, че хеш уравнението, използвано в hash таблицата на LZ4, все още е най-бързото xxhash. Разбира се, такъв дизайн има своите недостатъци. Колкото по-малка е хеш таблицата, толкова по-малко ключове има. Това означава, че ще възникнат повече хеш конфликти, което е неизбежно. А повече хеш колизии означават по-малко съвпадения. А по-малката хеш таблица означава и по-малък плъзгащ се прозорец, което означава, че повече съвпадения ще бъдат изхвърлени, защото са твърде далеч. По-малко съвпадения означават по-малко компресионно съотношение, поради което LZ4 има по-малко изразено компресионно съотношение. Гледайки напред, LZ4 предлага широк спектър от сценарии за приложение. Точно както middleout се използваше във VR в Силициевата долина, LZ4 може да увеличи използването на пропускателната способност, като донесе по-малко входове, но за сметка на много ниска латентност поради много бързата си компресия. Има и малка предположение, ако има процесор с по-голям кеш на ниво 1, може ли LZ4 да увеличи компресионното съотношение без да компрометира скоростта?
Оригинален:Входът към хиперлинк е видим. |
Публикувано в 3.01.2022 г. 13:54:23 ч.
|
|
|
|
