Изменения

'''<tex>\mathrm{LZ77''' }</tex> и '''<tex>\mathrm{LZ78''' — }</tex> {{---}} алгоритмы сжатие сжатия без потерь, опубликованные в статьях Абрахама Лемпеля Абрахамом Лемпелем<ref>[https://en.wikipedia.org/wiki/Abraham_Lempel Wikipedia {{---}} Abraham Lempel]</ref> и Якоба Зива Якобом Зивом<ref>[https://en.wikipedia.org/wiki/Yaakov_Ziv Wikipedia {{---}} Yaakov Ziv]</ref> в <tex>1977 </tex> и <tex>1978 </tex> годахсоответственно. Эти алгоритмы наиболее известные варианты в семействе стали основой других алгоритмов семьи <tex>\mathrm{LZ*, которое включает в себя также }</tex>: [[Алгоритм LZWАлгоритм_LZW|LZW]], [[Алгоритм_LZSS|LZSS]], [[Алгоритм_LZMA|LZMA ]] и другие алгоритмы.Оба приведенных алгоритма относятся к словарным методам. LZ77 является алгоритмом со «скользящим окном», что эквивалентно неявному использованию словарного подхода, впервые предложенного в LZ78используют словарный подход.

=== Принцип скользящего окна Идея алгоритма ===В кодируемых строках часто содержатся совпадающие длинные подстроки. Идея, лежащая в основе <tex>\mathrm{LZ77}</tex>, заключается в замене повторений на ссылки на позиции в тексте, где такие подстроки уже встречались.

Метод кодирования согласно принципу скользящего окна учитывает уже ранее встречавшуюся информациюИнформацию о повторении можно закодировать парой чисел {{---}} смещением назад от текущей позиции (<tex>offset</tex>) и длиной совпадающей подстроки (<tex>length</tex>). В таком случае, например, строка <tex>pabcdeqabcde</tex> может быть представлена как <tex>pabcdeq \langle 6, то есть информацию5 \rangle</tex>. Выражение <tex>\langle 6, которая уже известна для кодировщика и декодировщика (второе 5 \rangle</tex> означает «вернись на <tex>6</tex> символов назад и последующие вхождения некоторой строки символов в сообщении заменяются ссылками на ее первое вхождение)выведи <tex>5</tex> символов».

Благодаря этому принципу алгоритмы LZ* иногда называются методами сжатия с использованием скользящего окна. Скользящее окно можно представить в виде буфера (или более сложной динамической структуры данных)Алгоритм <tex>\mathrm{LZ77}</tex> кодирует ссылки блоками из трёх элементов {{---}} <tex>\langle offset, который организован такlength, чтобы запоминать «сказанную» ранее информацию и предоставлять к ней доступnext \rangle</tex>. Таким образом, сам процесс сжимающего кодирования согласно LZ77 напоминает написание программы, команды которой позволяют обращаться В дополнение к двум уже описанным элементам «скользящего окна», и вместо значений сжимаемой последовательности вставлять ссылки на эти значения в «скользящем окне»новый параметр <tex>next</tex> означает первый символ после найденного совпадающего фрагмента. Размер скользящего окна может динамически изменяться и составлять 2Если <tex>\mathrm{LZ77}</tex> не удалось найти совпадение, 4 или 32 килобайта. Следует также отметитьто считается, что размер окна кодировщика может быть менее или равен размеру окна декодировщика, но не наоборот<tex>offset = length = 0</tex>.

Приведенное выше сравнение процесса кодирования с «программированием» может натолкнуть на преждевременный вывод о том, что алгоритм LZ77 относится к [[Методы сжатия с использованием контекстного моделирования|методам контекстного моделирования]]Файл:LZ77-simple-example. Поэтому следует отметить, что алгоритм LZ77 принято классифицировать как метод [[Методы сжатия с использованием словаря|словарного сжатияjpg]] данных, когда вместо понятия «скользящего окна» используется термин «динамического словаря».

Перед темТакже нетривиальным может оказаться то, как перейти к рассмотрению механизма кодированиячто при кодировании <tex>\mathrm{LZ77}</tex> значение <tex>offset</tex> может быть меньше, уточним понятие ''совпадения'' чем <tex>length</tex> (от {{lang-en|match}}например, «вернись на <tex>2</tex> символа назад и выведи <tex>10</tex> символов»). Рассмотрим последовательность из N элементов. Если все элементы последовательности уникальныЭто означает, то такая последовательность не что подстрока будет содержать ни одного повторяющегося элементаповторяться несколько раз так, чтобы каждый символ совпадал с символом, стоящим на <tex>2</tex> позиции раньше, илии всего добавилось <tex>10</tex> символов. Например: <tex>hello\langle 2, иначе говоря10 \rangle \Leftrightarrow hello\boldsymbol{lololololo}</tex>. Символ всегда можно определить однозначно, даже если он отсутствует в последовательности не найдется хотя бы двух равных друг другу или совпадающих элементовбуфере.

В продолжение уже приведенной аналогии с программированием отметим, что Хранить результат кодирования будем в большинстве статей, посвященных алгоритму LZ77, кодируемая пара трактуется именно как команда копирования символов из скользящего окна с определенной позиции, или дословно каксписке структур следующего вида: «Вернуться в буфере символов на ''значение смещения'' и скопировать ''значение длины'' символов, начиная с текущей позиции».

Хотя для приверженцев [[Императивное программирование| императивного программирования]] такая интерпретация может показаться интуитивно понятной, она, к сожалению, мало говорит о сущности алгоритма LZ77 как метода сжатия. Особенность данного алгоритма сжатия заключается в том, что использование кодируемой пары <code> ''длина-смещение'struct' является не только приемлемым, но и эффективным в тех случаях, когда значение длины превышает значение смещения.'' Node: '''int''' offset '''int''' length '''char''' next</code>

Пример с командой копирования не совсем очевиден: «Вернуться на 1 символ назад Функция <code>findMatching</code> ищет в буфере и скопировать 7 символовстроку, начиная совпадающую с текущей позиции». Каким образом можно скопировать 7 символов из буферапрефиксом суффикса строки <tex>s</tex>, когда в настоящий момент в буфере находится только 1 символ? Однако следующая интерпретация кодирующей пары может прояснить ситуацию: каждые 7 последующих символов совпадают (эквивалентны) начинающегося с 1 символом перед нимисимвола <tex>pos</tex> и возвращает искомую пару <tex>\langle offset, length \rangle</tex>.

Это означает, что каждый символ можно однозначно определить, переместившись назад в буфере — даже если данный символ еще отсутствует в буфере Функция <code>shiftBuffer</code> сдвигает буфер вперёд на момент декодирования текущей пары ''длина-смещение''. Такая кодируемая пара будет представлять собой многократное (определяемое значением смещения) повторение последовательности (определяемой значением длины) <tex>x</tex> символов, что представляет собой более общую форму [[RLE]].

<code> <font color=green>// <tex>s</tex> {{---}} исходная строка // функция возвращает список блоков <tex>\langle offset, length, next \rangle</tex></font> '''list<Node>''' encodeLZ77('''string''' s): '''list<Node>''' ans =[] pos = Недостатки 0 '''while''' pos < s.length: offset, length = findMatching(buffer, pos) <font color=green>// ищем слово в словаре</font> shiftBuffer(length + 1) <font color=green>// перемещаем скользящее окно</font> pos +=length* невозможность кодирования подстрок ans.push({offset, отстоящих друг от друга на расстоянииlength, большем длины словаряs[pos]}) <font color=green>// добавляем в ответ очередной блок</font>* длина подстроки, которую можно закодировать, ограничена размером буфера '''return''' ans* малая эффективность при кодировании незначительного объёма данных</code>

=== Пример "abracadabra" === Поз. Длина Симв. ''abracadabra'' 0 0 a a ''bracadabra'' 0 0 b ab ''racadabra'' 0 0 r '''a'''br ''acadabra'' 3 1 c abr'''a'''c ''adabra'' 2 1 d '''abra'''cad ''abra'' 7 4 abra

=== Реализация LZ77 на Си ===Рассмотрим пример кодирования <source lang="c"tex>/*==============================Архивирование Алгоритм \mathrm{LZ77Очень неоптимизированный вариантПросьба обработать напильничком, как следует.==============================*}</#define DICBITS 12 // Log(DICSIZE)#define DICSIZE (1tex> на строке <tex>abacabacabadaca<DICBITS) // 4-32kB Размер словаря#define THRESHOLD 2 // Порог#define STRBITS 6 // Log(STRMAX-THRESHOLD)#define STRMAX ((1tex> с буфером размера <tex>5<STRBITS)+THRESHOLD) // Махtex>. Квадратом обведен буфер. длина строки#define BUFSIZE 0xff00U // Полный размер буфера#define TEXTSIZE (BUFSIZE-DICSIZE-STRMAX) // Размер буфера текста#define YES 1#define NO 0

FILE *first_file, *second_file;{| class="wikitable"! Строка || Совпадение || Закодированная последовательность || Примечание|-long srcleng=| <tex>abacabacabadaca</tex> || {{---}} || <tex>\langle 0, fileleng;unsigned char *srcbuf0, *srcstart;a \rangle</*==============================tex> || Буфер пуст========Функция записи=========|-==============================*| <tex>\fbox{$a$}bacabacabadaca</int putbits(int data, int nbits)tex> || {{ static int bitcounter=---}} || <tex>\langle 0; static int outdata=, 0; int bit, error; datab \rangle</tex> || В буфере нет <tex>b<=(16/tex>|-nbits); for( ; nbits | <tex>\fbox{$ab$}acabacabadaca</tex> || <tex>a</tex> || <tex> 0 ; nbits\langle 2, 1, c \rangle</tex> || |-- ) | <tex>\fbox{$abac$}abacabadaca</tex> || <tex>abacaba</tex> || <tex>\langle 4, 7, d \rangle</tex> || Здесь выгодно сделать так, что <tex>offset > length</tex> if( bitcounter == 8 )|- | <tex>abacaba\fbox{ bitcounter=0; error=putc(outdata$cabad$}aca</tex> || <tex>a</tex> || <tex>\langle 2, 1, c \rangle</tex> || Последовательность <tex>aca</tex> уже встречалась, но она находится за пределами окна,second_file); if( error == EOF ) и <tex>\mathrm{ LZ77}</tex> её не находит printf("Error writing to Second file."); return |-5; | <tex>abacabaca\fbox{$badac$} } outdataa</tex> || <tex>a<=/tex> || <tex>\langle 2, 1; bit=( data & 0x8000 ) ? 1:0; outdata+=bit; bitcounter++; data, \varnothing \rangle</tex> || Символов в строке больше нет, поэтому в качестве <tex>next<=1; }/tex> ставим символ конца строки|}

/*====================================Функция Архивирования===================================*/void compress_stud(){// struct stat buf; unsigned char *positionРезультатом кодирования является список полученных троек: <tex>\left[ \langle 0, *pointer; //байт в файле 0, байт в буфере int ia \rangle, dist\langle 0, offset=0, last=NOb \rangle, \langle 2, 1, c \rangle, \langle 4, 7, d \rangle, \langle 2, cnt1, maxleng;c \rangle, \langle 2, 1, \varnothing \rangle \right]</tex>.

printf("Compress started."); === Декодирование === Для декодирования <tex>\mathrm{LZ77}<// Записываем размер исходного файла fstat(fileno(first_file)tex> необходимо пройти по уже раскодированной строке назад, вывести необходимую последовательность,&buf); fileleng=bufзатем следующий символ.st_size; write(fileno(second_file), &fileleng, sizeof(long));

for( i<code> <font color=DICSIZEgreen>// <tex>encoded</tex> {{-1; i --}} список блоков <tex>\langle offset, length, next \rangle</tex> // функция возвращает декодированную строку</font> '''string''' decodeLZ77('''list<Node>''' encoded): ans = "" '''for''' node '''in''' encoded: '''if''' node.length > 0; i: <font color=green>// если необходим повтор</font> start = ans.length -- )node.offset <font color=green>// возвращаемся на <tex>offset</tex> символов назад</ Ищем самую длинную совпадающую строку в словаре {font> '''for( cnt''' i =0; cnt .. node.length - 1: <font color=green>// добавляем < STRMAX; cnt++ )tex>length</tex> символов</font> if( *(position ans +cnt) != *(pointerans[start +i] ans +cnt) ) = node.next <font color=green>// добавляем следующий символ</font> '''return''' ans break;</code>

if=== Модификации ===Известно много различных модификаций алгоритма <tex>\mathrm{LZ77}</tex>. Например, вместо блоков можно хранить отдельно одиночные символы и отдельно {{---}} пары <tex>\langle offset, length \rangle</tex> ( cnt length-distance pair<ref>[https://en.wikipedia.org/wiki/LZ77_and_LZ78#LZ77 Wikipedia {{---}} LZ77]<= THRESHOLD /ref>). [[Алгоритм LZSS]] является улучшением <tex>\mathrm{LZ77}</tex> и хранит однобитный флаг, показывающий, какие данные за ним идут: одиночный символ или пара смещения и длины. В формате <tex>\mathrm{PalmDoc}</tex><ref>[https://wiki.mobileread.com/wiki/PalmDOC Описание формата PalmDOC]</ref> на каждую пару смещения и длины выделяется по <tex>2</ Если длина меньше порога, отбрасываем continue;tex> байта.

if( cnt == STRMAX )Также на <tex>\mathrm{LZ77}</tex> основаны алгоритмы <tex>\mathrm{LZH}</ Если максимальная строка, дальше не ищем { dist=DICSIZE-1-i; tex><ref>[https://позиция maxleng=STRMAX; msdn.microsoft.com/en-us/длина break; } if( cnt > maxleng ) library/hh554076.aspx LZH]</ Если очередная строка длиннее уже найденных, сохраняеМ ее длину ref> и позицию <tex>\mathrm{ dist=DICSIZE-1-i; DEFLATE}</tex><ref>[https:// позиция maxleng=cnt; en.wikipedia.org/wiki/длина DEFLATE Wikipedia {{---} }DEFLATE]</ref> (последний является широко используемым), которые совмещают <tex>\mathrm{LZ77}</tex> с [[Алгоритм Хаффмана|алгоритмом Хаффмана]], кодируя элементы пар и одиночные символы.

== LZ78 == === Идея алгоритма ===Алгоритм <tex>\mathrm{LZ78}<// Записываем оставшиеся биты tex> имеет немного другую идею: этот алгоритм в явном виде использует словарный подход, генерируя временный словарь во время кодирования и декодирования.  putbitsИзначально словарь пуст, а алгоритм пытается закодировать первый символ. На каждой итерации мы пытаемся увеличить кодируемый префикс, пока такой префикс есть в словаре. Кодовые слова такого алгоритма будут состоять из двух частей {{---}} номера в словаре самого длинного найденного префикса (0<tex>pos</tex>) и символа,8который идет за этим префиксом (<tex>next</tex>);. При этом после кодирования такой пары префикс с приписанным символом добавляется в словарь, а алгоритм продолжает кодирование со следующего символа.

/*==============================<code>======Функция считывания======== '''struct''' Node: '''int''' pos <font color==============================*green>// номер слова в словаре</font>int getbits(int nbits){ '''char''' next static int bitcounter=8; static int indata=0; int bit, data=0;</code>

for( ; nbits В качестве словаря будем использовать обычный <code> 0 ; nbits-- ) { if( bitcounter == 8 ) { bitcounter=0; indata=getc(first_file); } if( indata == EOF ) { printf("Error writing to First file."); return -6; }map</code>:

bit=<code> '''list<Node>''' encodeLZ78( indata & 0x80 '''string''' s) ? 1:0; data '''string''' buffer = "" <font color=green>// текущий префикс</font> '''map<string, int>''' dict = {} <font color=green>// словарь</font> '''list<Node>''' ans = [] <font color=green>// ответ</font> '''for''' i =0 .. s.length - 1; : data '''if''' dict.hasKey(buffer +s[i]): <font color=bit; green>// можем ли мы увеличить префикс</font> bitcounter buffer += s[i] '''else''': ans.push({dict[buffer], s[i]}) <font color=green>// добавляем пару в ответ</font> dict[buffer +; s[i]] = dict.length + 1 <font color=green>// добавляем слово в словарь</font> indata buffer = "" <font color=green>// сбрасываем буфер</font> '''if''' not (buffer is empty): <font color=1;green>// если буффер не пуст - этот код уже был, нужно его добавить в конец словаря</font> last_ch = buffer.peek() <font color=green>// берем последний символ буффера, как "новый" символ</font> buffer.pop() <font color=green>// удаляем последний символ из буфера</font> ans.push({dict[buffer], last_ch}) <font color=green>// добавляем пару в ответ</font> '''return data;''' ans}</code>

/*===Пример ==================================Функция Извлечения=====================================*/

printf({| class="wikitable"Decompress started.! Словарь || Осталось обработать || Найденный префикс || Код || Примечание|-| <tex>\n"varnothing</tex> || <tex>abacababacabc</tex> || {{---}} || <tex>\langle 0, a \rangle</tex> || В словаре ничего не нашлось, вместо номера в словаре указываем <tex>0</tex>|-| <tex>a</tex> || <tex>bacababacabc</tex> || {{---}} || <tex>\langle 0, b \rangle</tex> || |-| <tex>a</tex>, <tex>b</tex> || <tex>acababacabc</tex> || <tex>a</tex> || <tex>\langle 1, c \rangle</tex> || Нашелся префикс <tex>a</tex> (слова в словаре нумеруются с <tex>1</tex>);, добавляем <tex>ac</tex>|-| <tex>a</tex>, <tex>b</tex>, <tex>ac</tex> || <tex>ababacabc</tex> || <tex>a</tex> || <tex>\langle 1, b \rangle</tex> || |-| <tex>a</tex>, <tex>b</tex>, <tex>ac</tex>, <tex>ab</tex> || <tex>abacabc</tex> || <tex>ab</tex> || <tex>\langle 4, a \rangle</tex> || |-| <tex>a</tex>, <tex>b</tex>, <tex>ac</tex>, <tex>ab</tex>, <tex>aba</tex> || <tex>cabc</tex> || {{---}} || <tex>\langle 0, c \rangle </tex> || |-| <tex>a</tex>, <tex>b</tex>, <tex>ac</tex>, <tex>ab</tex>, <tex>aba</tex>, <tex>c</tex> || <tex>abc</tex> || <tex>ab</tex> || <tex>\langle 4, c\rangle </tex> || |}

// Получаем длину исходного файла read(fileno(first_file)Результатом кодирования является список пар: <tex>\left[ \langle 0,&filelenga \rangle,sizeof(long)); pos=srcstart; while( fileleng > \langle 0 ) { if( (ch=getbits(, b \rangle, \langle 1, c \rangle, \langle 1)) == 0 ) // Если chr-код, копируем в буфер текста символ { ch=getbits(8); putc(chb \rangle, \langle 4,second_file); *pos=ch; pos++; fileleng--; } else // Иначе - копируем maxleng символов из словаряa \rangle, начиная с позиции dist { dist=getbits(DICBITS)+1; maxleng=getbits(STRBITS)+THRESHOLD+1; for( i=\langle 0; i < maxleng; i++ ) { *(pos+i)=*(pos+i-dist); putc(*(pos+i-dist),second_file); } pos+=maxleng; fileleng-=maxleng; } if( pos > srcstart+TEXTSIZE ) // Если буфер заполненc \rangle, записываем его на диск и сдвигаем словарь в начало буфера { memcpy(srcbuf\langle 4,pos-DICSIZE,DICSIZE); pos=srcstart; } } printf("c \rangle \nDecompress completed.");}right]</tex>

</source>{{скрытый текст}}<!--Статья еще не содержит этой Декодирование происходит аналогично кодированию, на основе декодируемой информации:строим словарь и берем из него значения.

Even though all LZ77 algorithms work by definition on the same basic principle, they can vary widely in how they output their encoded data — what values are possible for lengths and distances, for example, and how length-distance pairs are distinguished from <code> '''string'literals'' decodeLZ78(single characters '''list<Node>''' encoded as themselves, rather than as part of a length-distance pair.) A few examples:* The algorithm illustrated in Lempel and Ziv’s original 1977 paper output all its data three values at a time: the length and distance of the longest match found in the buffer, and the literal which followed that match. If two successive characters in the input stream could only be encoded as literals, the length would be 0.* In the '''list<string>''' dict = [[PalmDoc]""] format <font color=green>// словарь, a lengthслово с номером 0 {{-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.}} пустая строка</font> '''string''' ans = "" <font color=green>// ответ</font> '''for''' node '''in''' encoded:* word = dict[[As of 2004node.pos]], the most popular LZ77 based compression method is called [[DEFLATE + node.next <font color=green>// составляем слово из уже известного из словаря и новой буквы</font> ans += word <font color=green>// приписываем к ответу</font> dict.push(algorithmword)|DEFLATE]]; it combines LZ77 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; since a distance only occurs just after a length, it cannot be mistaken for another kind of symbol or vice-versa. <font color=green>// добавляем в словарь</font> '''return''' ans--</code>

== LZ78 = Модификации ===Одна из главных проблем <tex>\mathrm{LZ78}</tex> {{---}} размер словаря. Он ничем не ограничен и может достигать огромных размеров на больших объемах входных данных. В различных модификациях установлены лимиты на размер словаря: при достижении определенного лимита словарь может «замораживаться» (в него перестают добавляться новые слова), из словаря могут удалять менее используемые или самые старые слова и так далее.

Самой известной модификацией <tex>\mathrm{LZ78}</tex> является [[Алгоритм LZW|LZW]]. В отличие от LZ77нём есть две важных особенности. Первая {{---}} словарь изначально инициализирован всеми символами алфавита. Вторая {{---}} после нахождения максимального префикса поиск следующего префикса начинается не с символа после неподходящего, работающего а с уже полученными данными, LZ78 ориентируется на данные, которые только будут получены (LZ78 самого неподходящего символа. Это позволяет не использует «скользящее» окновыводить неподходящий символ, он хранит словарь а выяснять его прямо из уже просмотренных фраз)словаря. Алгоритм считывает символы сообщения до тех пор, пока накапливаемая подстрока входит целиком Эта модификация используется в том числе в одну из фраз словаря. Как только эта строка перестанет соответствовать хотя бы одной фразе словаря, алгоритм генерирует код, состоящий из индекса строки изображениях в словаре, которая до последнего введенного символа содержала входную строку, и символа, нарушившего совпадениеформате <tex>\mathrm{GIF}</tex><ref>[https://en. Затем в словарь добавляется введенная подстрокаwikipedia. Если словарь уже заполнен, то из него предварительно удаляют менее всех используемую в сравнениях фразуorg/wiki/GIF Wikipedia {{---}} GIF]</ref>.

== Ссылки См. также ==* Jacob Ziv, Abraham Lempel. [http://www.cs.duke.edu/courses/spring03/cps296.5/papers/ziv_lempel_1977_universal_algorithm.pdf A Universal Algorithm for Sequential Data Compression[Алгоритм RLE]] IEEE Transactions on Information Theory, 23(3), pp.337-343, May 1977.* [http://www.binaryessence.com/dct/en000138.htm Пример работы алгоритма LZ77 (см. example "abracadabra")[Алгоритм LZW]]* [http://www.intuit.ru/department/calculate/infotheory/class/free/6/ Описание алгоритма LZ77 в курсе лекций по теории кодирования информации[Алгоритм LZSS]]* [http://www.intuit.ru/department/calculate/infotheory/class/free/6/2.html Описание алгоритма LZ78 в курсе лекций по теории кодирования информации[Алгоритм LZMA]]

== Источники информации ==* [https://en.wikipedia.org/wiki/LZ77_and_LZ78 Wikipedia {{---}} LZ77 and LZ78]* [Категорияhttp:Сжатие данных//ru.wikipedia.org/wiki/LZ77 Википедия {{---}} LZ77]* [https://fenix.tecnico.ulisboa.pt/downloadFile/1407993358859638/Lempel_Ziv_by_Zeeh.pdf The Lempel Ziv Algorithm]* [http://rain.ifmo.ru/cat/view.php/vis/data-compression/lz-2000 Визуализатор алгоритма LZ78]* [Категорияhttp:Алгоритмы сжатия без потерь//compression.ru/download/articles/rev_univ/semenyuk_2001_econom_encoding.pdf Семенюк В.В. {{---}} Экономное кодирование дискретной информации]* [http://mf.grsu.by/UchProc/livak/en/po/comprsite/theory_lz77.html Алгоритм LZ77]* [[Категорияhttp:Алгоритмы сжатия с использованием словаря]//www.binaryessence.com/dct/en000140.htm Lempel-Ziv-78]

[[csКатегория:LZ77Дискретная математика и алгоритмы]][[deКатегория:LZ77]][[en:LZ77 and LZ78]][[et:LZ77]][[fr:LZ77 et LZ78]][[hu:LZ77]][[it:LZ77 e LZ78]][[ja:LZ77]][[pl:LZ77]][[pt:LZ77]][[zh:LZ77与LZ78Алгоритмы сжатия]]