Жоғалмалы деректерді қысу алгоритмдері (LZ77 және LZ78)

Кіріспе

Жоғалмайтын деректерді сығымдау алгоритмдері

LZ77 және LZ78 – Авраам Лемпель мен Джейкоб Зивтің 1977 және 1978 жылдары жариялаған мақалаларында келтірілген екі жоғалмайтын деректерді сығымдау алгоритмі. Олар сәйкесінше LZ1 және LZ2 деп те аталады. Бұл екі алгоритм LZW, LZSS, LZMA және басқалары сияқты көптеген түрленулердің негізін құрайды. Академиялық әсерінен бөлек, бұл алгоритмдер GIF және PNG мен ZIP форматында қолданылатын DEFLATE алгоритмі сияқты кең таралған сығымдау схемаларының негізі болды. Олардың екеуі де теориялық тұрғыдан сөздік кодтағыштары болып табылады. LZ77 сығымдау кезінде жылжымалы терезені қолданады. Кейіннен бұл LZ78 құрастырған сөздікке тең екені көрсетілді, бірақ олар тек барлық деректерді декомпрессиялау үшін ғана тең болады. LZ77 бұрын көрген символдардың жылжымалы терезесі арқылы кодтайды және декодтайды, сондықтан декомпрессия әрқашан кірістің басынан басталуы тиіс. Теориялық тұрғыдан алғанда, егер бүкіл сөздік алдын ала белгілі болса, LZ78 декомпрессиясы кіріске кездейсоқ қол жеткізуге мүмкіндік береді. Бірақ практикада сөздік кодтау және декодтау кезінде жаңа тіркес шығарылған сайын жасалады. Алгоритмдер 2004 жылы IEEE Milestone мәртебесіне ие болды. 2021 жылы Джейкоб Зив олардың әзірленуіне қосқан үлесі үшін IEEE Құрмет медалімен марапатталды.

Теориялық тиімділік

Бұл алгоритмдерді таныстырған екі мақаланың екіншісінде олар шекті күйдегі автоматтарымен анықталатын кодтаушылар ретінде талданады. Жеке тізбектер үшін (ықтималдық жиындарға қарағанда) ақпараттық энтропияға ұқсас өлшем жасалады. Бұл өлшем қол жетімді деректерді қысу қатынасының шегін көрсетеді. Содан кейін, әрбір тізбек үшін тізбектің ұзындығы шексіздікке ұлғайғанда осы шекке жететін шекті жоғалтусыз кодтаушылардың бар екендігі көрсетіледі. Осылайша, осы схемаға негізделген алгоритм асимптотикалық жақын кодтауларды құрайды. Бұл нәтиже, мысалы, Питер Шордың жазбаларында көрсетілгендей, тікелей дәлелдеуге болады. Формальды түрде (Теорема 13.5.3). Ұқсас теоремалар LZ алгоритмінің басқа да нұсқаларына қолданылады.

LZ77

LZ77 алгоритмдері деректердің қайталанған кездесуін компрессияланбаған дерек ағынында бұрын болған осы деректердің бір көшірмесіне сілтемелермен алмастыру арқылы сығылуды жүзеге асырады. Сәйкестік ұзындық-арақашықтық жұбымен кодталады, бұл «келесі ұзындық символдарының әрқайсысы сығылмаған ағындағы дәл сол арақашықтықтағы символдарға тең» дегенді білдіреді. (Арақашықтық кейде офсет деп аталады.) Сәйкестікті табу үшін кодер соңғы 2 КБ, 4 КБ немесе 32 КБ сияқты соңғы деректерді есте сақтауы керек. Бұл деректерді сақтайтын құрылым жылжымалы терезе деп аталады, сондықтан LZ77 кейде жылжымалы терезе сығылуы деп аталады. Кодер бұл деректерді сәйкестіктерді іздеу үшін сақтауы керек, ал декодер осы деректерді кодер сілтеме жасайтын сәйкестіктерді түсіндіру үшін сақтауы керек. Жылжымалы терезе неғұрлым үлкен болса, кодер сілтеме жасау үшін соғұрлым алыс іздеуі мүмкін. Ұзындық-арақашықтық жұптарына арақашықтықтың өзінен асып түсетін ұзындықты көрсетуге рұқсат беру ғана емес, сонымен қатар көбінесе пайдалы. Көшіру командасы ретінде бұл оғаш: «Төрт символға кері оралып, сол орыннан он символды қазіргі орынға көшіріңіз». Егер тек төртеуі ғана буферде болса, он символ қалай көшіріледі? Бір уақытта бір байттан өңдеу, бұл сұранысты орындауда ешқандай қиындық жоқ, өйткені байт көшірілгенде, оны көшіру командасына кіріс ретінде қайтадан беруге болады. Көшіру басталатын орын бастапқы мақсатты орынға жеткенде, ол осылайша көшіру басталатын орыннан алынған мәліметтерді желімдейді. Бұл операция «сізге берілген деректерді көшіріп, сәйкес келгенше қайталап жабыстырыңыз» дегенге тең. Бұл жұп деректердің бір көшірмесін бірнеше рет қайталайтындықтан, оны орындау ұзындығы кодтамасының икемді және оңай түрін қосу үшін пайдалануға болады. Мәселені тағы бір жағынан қарастырайық: кодтау кезінде іздеу көрсеткіші іздеу терезесінің соңынан өткен кезде сәйкес жұптарды табуды жалғастыру үшін, D офсетіндегі алғашқы сәйкестіктен бастап және іздеу терезесінің соңына дейінгі барлық символдар сәйкес келуі керек, және бұл (бұрын көрінген) символдар LR ұзындығындағы бір рет орындалатын бірлік құрайды, ол D-ге тең болуы керек. Содан кейін іздеу көрсеткіші іздеу терезесінен өтіп, алға жылжығанда, егер іздеу үлгісі қайталанса, іздеу және кіріс көрсеткіштері синхронды болады және жүгіру үлгісі бұзылғанша символдар сәйкес келеді. Содан кейін L символ жалпы сәйкестікке ие болады, L > D, және код [D, L, c] болады. [D, L, c] декодталғанда, қайтадан, D = LR. Алғашқы LR символдары шығысқа оқылғанда, бұл шығыс буферіне қосылған бір рет орындалатын бірлікке сәйкес келеді. Бұл кезде оқу көрсеткіші тек int((L/LR) + (1 егер L mod LR ≠ 0)) рет бастапқы буферленген жүгіру бірлігіне оралып, LR символдарды (немесе соңғы оралуда азырақ) оқып, L символ оқылғанша қайталауы керек деп ойлауға болады. Бірақ кодтау процесін еске ала отырып, үлгі қайталанатындықтан, оқу көрсеткіші тек жазу көрсеткішінен LR ұзындығына тең қашықтықта қалып, L символдары шығысқа көшірілгенше ғана жүруі керек. Жоғарыда айтылғандарды ескере отырып, әсіресе деректердің қайталануының сығылуы күтілсе, терезе іздеуі терезенің соңынан басталып, кері қарай жалғастырылуы керек, өйткені қайталану үлгілері, егер олар болса, бірінші болып табылады және іздеуді аяқтауға мүмкіндік береді, егер ағымдағы максималды сәйкестік тізбегінің ұзындығы орындалса немесе жеткілікті ұзындығы орындалса, және соңында деректер жақында болса және келесі кіріспен жақсы сәйкес келуі мүмкін болса.

LZ77 algorithms achieve compression by replacing repeated occurrences of data with references to a single copy of that data existing earlier in the uncompressed data stream. A match is encoded by a pair of numbers called a length distance pair, which is equivalent to the statement "each of the next length characters is equal to the characters exactly distance characters behind it in the uncompressed stream". (The distance is sometimes called the offset instead.) To spot matches, the encoder must keep track of some amount of the most recent data, such as the last 2 KB, 4 KB, or 32 KB. The structure in which this data is held is called a sliding window, which is why LZ77 is sometimes called sliding window compression. The encoder needs to keep this data to look for matches, and the decoder needs to keep this data to interpret the matches the encoder refers to. The larger the sliding window is, the longer back the encoder may search for creating references. It is not only acceptable but frequently useful to allow length distance pairs to specify a length that actually exceeds the distance. As a copy command, this is puzzling: "Go back four characters and copy ten characters from that position into the current position". How can ten characters be copied over when only four of them are actually in the buffer? Tackling one byte at a time, there is no problem serving this request, because as a byte is copied over, it may be fed again as input to the copy command. When the copy from position makes it to the initial destination position, it is consequently fed data that was pasted from the beginning of the copy from position. The operation is thus equivalent to the statement "copy the data you were given and repetitively paste it until it fits". As this type of pair repeats a single copy of data multiple times, it can be used to incorporate a flexible and easy form of run length encoding. Another way to see things is as follows: While encoding, for the search pointer to continue finding matched pairs past the end of the search window, all characters from the first match at offset D and forward to the end of the search window must have matched input, and these are the (previously seen) characters that comprise a single run unit of length LR, which must equal D. Then as the search pointer proceeds past the search window and forward, as far as the run pattern repeats in the input, the search and input pointers will be in sync and match characters until the run pattern is interrupted. Then L characters have been matched in total, L > D, and the code is [D, L, c]. Upon decoding [D, L, c], again, D = LR. When the first LR characters are read to the output, this corresponds to a single run unit appended to the output buffer. At this point, the read pointer could be thought of as only needing to return int(L/LR) + (1 if L mod LR ≠ 0) times to the start of that single buffered run unit, read LR characters (or maybe fewer on the last return), and repeat until a total of L characters are read. But mirroring the encoding process, since the pattern is repetitive, the read pointer need only trail in sync with the write pointer by a fixed distance equal to the run length LR until L characters have been copied to output in total. Considering the above, especially if the compression of data runs is expected to predominate, the window search should begin at the end of the window and proceed backwards, since run patterns, if they exist, will be found first and allow the search to terminate, absolutely if the current maximal matching sequence length is met, or judiciously, if a sufficient length is met, and finally for the simple possibility that the data is more recent and may correlate better with the next input.

Қолданылу

LZ77 алгоритмдерінің барлығы бірдей негізгі принцип бойынша жұмыс істесе де, олар ұзындығы-қашықтығы жұптарының сандық диапазондарын өзгертуге, ұзындығы-қашықтығы жұптары үшін жұмсалатын биттердің санын өзгертуге және олардың ұзындығы-қашықтығы жұптарын тура мәндерден (ұзындығы-қашықтығы жұптарының бөлігі ретінде емес, өздігінен кодталған шикі деректер) ажыратуға байланысты әртүрлі болуы мүмкін. Бірнеше мысал: Лемпель мен Зивтің 1977 жылғы мақаласында көрсетілген алгоритм барлық деректерді бір мезгілде үш мәнге шығарады: буферде табылған ең ұзақ сәйкестіктің ұзындығы мен қашықтығы және осы сәйкестіктен кейінгі тура мән. Егер кіріс ағынындағы екі қатарлы символ тек тура мән ретінде кодталуы мүмкін болса, онда ұзындығы-қашықтығы жұптың ұзындығы 0 болады. LZSS, LZ77-ге қарағанда жақсырақ, келесі деректер бөлігі тура мән немесе ұзындығы-қашықтығы жұп екенін көрсету үшін 1 биттік флагты пайдаланады және ұзындығы-қашықтығы жұп ұзағырақ болса, тура мәндерді қолданады. PalmDoc форматында ұзындығы-қашықтығы жұбы әрқашан екі байттық тізбек ретінде кодталады. Осы екі байтты құрайтын 16 биттің 11-і қашықтықты кодтауға, 3-і ұзындықты кодтауға жұмсалады, ал қалған екеуі декодердің бірінші байтты осындай екі байттық тізбектің басталуы ретінде анықтай алатынына көз жеткізу үшін қолданылады. Electronic Arts көптеген ойындарда қолданатын нұсқасында ұзындығы-қашықтығы жұптың байт мөлшері ұзындығы-қашықтығы жұптың бірінші байтының ішінде көрсетілуі мүмкін; егер бірінші байт 0, 10, 110 немесе 111 (үлкен эндиандық бит бағытында оқылғанда) басталатын болса, ұзындығы-қашықтығы жұптың ұзындығы 1-ден 4 байтқа дейін болуы мүмкін. 2008 жылдан бастап LZ77 негізіндегі ең танымал сығу әдісі DEFLATE болып табылады; ол LZSS-ті Хэффман кодтамасымен біріктіреді. Тұра мәндер, ұзындықтар және ағымдағы дерек блогының соңына қатысты символдар бір алфавитке біріктіріледі. Қашықтықтарды бөлек алфавитке орналастыруға болады, себебі қашықтық тек ұзындықтан кейін ғана пайда болады, сондықтан оны басқа символмен немесе керісінше шатастыру мүмкін емес.

Even though all LZ77 algorithms work by definition on the same basic principle, they can vary widely in how they encode their compressed data to vary the numerical ranges of a length–distance pair, alter the number of bits consumed for a length–distance pair, and distinguish their length–distance pairs from literals (raw data encoded as itself, rather than as part of a length–distance pair). A few examples:
The algorithm illustrated in Lempel and Ziv's original 1977 article outputs all its data three values at a time: the length and distance of the longest match found in the buffer, and the literal that followed that match. If two successive characters in the input stream could be encoded only as literals, the length of the length–distance pair would be 0. LZSS improves on LZ77 by using a 1 bit flag to indicate whether the next chunk of data is a literal or a length–distance pair, and using literals if a length–distance pair would be longer. In the PalmDoc format, a length–distance pair is always encoded by a two byte sequence. Of the 16 bits that make up these two bytes, 11 bits go to encoding the distance, 3 go to encoding the length, and the remaining two are used to make sure the decoder can identify the first byte as the beginning of such a two byte sequence. In the implementation used for many games by Electronic Arts, the size in bytes of a length–distance pair can be specified inside the first byte of the length–distance pair itself; depending on whether the first byte begins with a 0, 10, 110, or 111 (when read in big endian bit orientation), the length of the entire length–distance pair can be 1 to 4 bytes. as of 2008, the most popular LZ77 based compression method is DEFLATE; it combines LZSS with Huffman coding. Literals, lengths, and a symbol to indicate the end of the current block of data are all placed together into one alphabet. Distances can be safely placed into a separate alphabet; because a distance only occurs just after a length, it cannot be mistaken for another kind of symbol or vice versa.

LZ78

LZ78 алгоритмдері кіріс деректерінен токендік тізбектердің сөздігін құрастырып, дерек ағынында тізбектің екінші және келесі кездесуін сөздіктегі жазбаға сілтемемен алмастырады. Байқағанымыздай, қайталанатын тізбектердің саны тізбектің кездейсоқтық емес сипатын бағалаудың жақсы тәсілі болып табылады. Алгоритмдер сөздікті n-арлық ағаш ретінде ұсынады, мұнда n – токендік тізбектерді құру үшін қолданылатын токендер саны. Әрбір сөздік жазбасы , түрінде болады, мұнда индекс – бұрын кездескен тізбекті көрсететін сөздіктегі жазбаның индексі, ал токен – осы жазбаны сөздікте бірегей ететін кірістен келесі токен. Алгоритмнің ашкөз екенін ескеріңіз, сондықтан бірегей токен табылғанша кестеге ештеңе қосылмайды. Алгоритм соңғы сәйкес келетін индекс = 0 және келесі бос индекс = 1 деп бастамалайды, содан кейін кіріс ағынының әрбір токені үшін сөздікте сәйкестік іздейді: Егер сәйкестік табылса, соңғы сәйкес келетін индекс сәйкес келетін жазбаның индексіне теңестіріледі, ештеңе шығарылмайды және соңғы сәйкес келетін индекс осы уақытқа дейінгі кірісті көрсетеді. Кіріс сәйкестік табылмайынша өңделеді. Содан кейін жаңа сөздік жазбасы құрылады, , және алгоритм соңғы сәйкес келетін индексті, содан кейін токенді шығарады, содан кейін соңғы сәйкес келетін индексті 0-ге қайта орнатып, келесі бос индексті арттырады. Мысалы, сөздікті құрайтын токендер тізбесін қарастырайық; және сығылған деректердің шығыс тізбесі мынадай болады: Соңғы А әлі көрсетілмеген, өйткені алгоритм келесі не болатынын білмейді. Іс жүзінде, мысалы, кіріске EOF маркері қосылады. Сондай-ақ, бұл жағдайда шығыс бастапқы кірістен ұзын, бірақ сөздік өскен сайын сығылу коэффициенті айтарлықтай жақсарады және бинарлық форматта индекстерді ең аз бит санымен көрсету жеткілікті. Декомпрессия сығылған тізбектен сөздікті қайта құрудан тұрады. Тізбектегі бірінші жазба әрқашан терминатор болып табылады, ал тізбектен біріншісі шығысқа қосылады. Кірістің екінші жұбы сөздікте 2-ші жазбаны құрайды. "B" токені шығарылады, оған сөздіктегі 1-ші жазбаға сілтеме қосады. 1-ші жазба – "A" (одан кейін "0" жазбасы, ештеңе жоқ) сондықтан шығысқа қосылады. Келесі жазба сөздікке қосылады, ал B (алдынан ештеңе жоқ) шығысқа қосылады. Соңында жазба құрылады және шығыс болады, нәтижесінде бос орындар мен EOF маркері алынады немесе алынады.

The LZ78 algorithms compress sequential data by building a dictionary of token sequences from the input, and then replacing the second and subsequent occurrence of the sequence in the data stream with a reference to the dictionary entry. The observation is that the number of repeated sequences is a good measure of the non random nature of a sequence. The algorithms represent the dictionary as an n ary tree where n is the number of tokens used to form token sequences. Each dictionary entry is of the form , where index is the index to a dictionary entry representing a previously seen sequence, and token is the next token from the input that makes this entry unique in the dictionary. Note how the algorithm is greedy, and so nothing is added to the table until a unique making token is found. The algorithm is to initialize last matching index = 0 and next available index = 1 and then, for each token of the input stream, the dictionary searched for a match: If a match is found, then last matching index is set to the index of the matching entry, nothing is output, and last matching index is left representing the input so far. Input is processed until a match is not found. Then a new dictionary entry is created, , and the algorithm outputs last matching index, followed by token, then resets last matching index = 0 and increments next available index. As an example consider the sequence of tokens which would assemble the dictionary;

and the output sequence of the compressed data would be Note that the last A is not represented yet as the algorithm cannot know what comes next. In practice an EOF marker is added to the input for example. Note also that in this case the output is longer than the original input but compression ratio improves considerably as the dictionary grows, and in binary the indexes need not be represented by any more than the minimum number of bits. Decompression consists of rebuilding the dictionary from the compressed sequence. From the sequence the first entry is always the terminator , and the first from the sequence would be The is added to the output. The second pair from the input is and results in entry number 2 in the dictionary, The token "B" is output, preceded by the sequence represented by dictionary entry 1. Entry 1 is an 'A' (followed by "entry 0" nothing) so is added to the output. Next is added to the dictionary as the next entry, , and B (preceded by nothing) is added to the output. Finally a dictionary entry for is created and is output resulting in or removing the spaces and EOF marker.

ЖЖЖ

LZW – LZ78 негізінде құрылған алгоритм, ол барлық мүмкін таңбалармен (символдармен) алдын ала инициализацияланған сөздікті немесе алдын ала инициализацияланған сөздіктің имитациясын пайдаланады. LZW-нің негізгі артықшылығы – сәйкестік табылмайтын жағдайда, ағымдағы кіріс ағынының таңбасы сөздіктегі бар тізбектің бірінші таңбасы деп есептеледі (өйткені сөздік барлық мүмкін таңбалармен инициализацияланған), сондықтан тек соңғы сәйкес келетін индекс шығарылады (бұл алдыңғы (немесе бастапқы) кіріс таңбасына сәйкес сөздік индексі болуы мүмкін). Толық ақпарат алу үшін LZW мақаласына жүгініңіз. BTLZ – LZ78 негізінде құрылған алгоритм, ол нақты уақыт байланыс жүйелерінде (алғашқыда модемдерде) қолдану үшін әзірленді және CCITT/ITU тарапынан V.42bis стандарты ретінде бекітілді. Түйіндік құрылымды сөздік толғанда, сөздіктің өзгеріп жатқан деректерге бейімделуін қамтамасыз ету үшін қарапайым қайта пайдалану/қалпына келтіру алгоритмі қолданылады. Сандық сөздік бойынша жүреді. Жаңа жазба қажет болғанда, сандық сөздікте жапырақ түйіні (бағынышты түйіні жоқ түйін) табылғанша іздейді. Ол жойылады және жаңа жазба үшін орын босатылады. Бұл LRU немесе LFU-дан қарапайымрақ және олармен теңдей өнімділікке қол жеткізеді.