Изменения

'''<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>offset</tex>) и длиной совпадающей подстроки (<tex>length</tex>). В таком случае, что алгоритм LZ77 относится к [[Методы сжатия с использованием контекстного моделирования|методам контекстного моделирования]]. Поэтому следует отметитьнапример, что алгоритм LZ77 принято классифицировать строка <tex>pabcdeqabcde</tex> может быть представлена как метод [[Методы сжатия с использованием словаря|словарного сжатия]] данных<tex>pabcdeq \langle 6, 5 \rangle</tex>. Выражение <tex>\langle 6, когда вместо понятия «скользящего окна» используется термин «динамического словаря»5 \rangle</tex> означает «вернись на <tex>6</tex> символов назад и выведи <tex>5</tex> символов».

Алгоритм <tex>\mathrm{LZ77}</tex> кодирует ссылки блоками из трёх элементов {{---}} <tex>\langle offset, length, next \rangle</tex>. В дополнение к двум уже описанным элементам, новый параметр <tex>next</tex> означает первый символ после найденного совпадающего фрагмента. Если <tex>\mathrm{LZ77}</tex> не удалось найти совпадение, то считается, что <tex>offset =length == Механизм кодирования совпадений ===0</tex>.

Перед тем, как перейти к рассмотрению механизма кодирования, уточним понятие ''совпадения'' (от {{lang[[Файл:LZ77-en|match}}). Рассмотрим последовательность из N элементов. Если все элементы последовательности уникальны, то такая последовательность не будет содержать ни одного повторяющегося элемента, или, иначе говоря, в последовательности не найдется хотя бы двух равных друг другу или совпадающих элементовsimple-example.jpg]]

В стандартном алгоритме Для эффективного поиска повторов в <tex>\mathrm{LZ77 }</tex> применяется метод «скользящего окна» {{---}} совпадения кодируются парой:* ищутся не на всём обработанном префиксе, а в небольшом буфере, состоящем из последних обработанных символов. Обычно длина буфера равна <tex>2</tex>, <tex>4</tex> или <tex>32 \mathrm{KB}</tex>. Таким образом, при больших объемах ввода алгоритм тратит меньше времени за счет того, что просматривается не вся исходная строка. С другой стороны, слишком маленькая длина словаря может привести к тому, что расположенные далеко друг от друга совпадения (match length)* смещение (offset) или дистанция (distanceна большем расстоянии, чем длина словаря)не будут учтены, и кодирование станет менее оптимальным.

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

Пример с командой копирования не совсем очевиден: «Вернуться на 1 символ назад в буфере и скопировать 7 символов, начиная с текущей позиции». Каким образом можно скопировать 7 символов из буфера, когда в настоящий момент Хранить результат кодирования будем в буфере находится только 1 символ? Однако следующая интерпретация кодирующей пары может прояснить ситуациюсписке структур следующего вида: каждые 7 последующих символов совпадают (эквивалентны) с 1 символом перед ними.

Это означает, что каждый символ можно однозначно определить, переместившись назад в буфере — даже если данный символ еще отсутствует в буфере на момент декодирования текущей пары <code> ''длина-смещение'struct'. Такая кодируемая пара будет представлять собой многократное (определяемое значением смещения) повторение последовательности (определяемой значением длины) символов, что представляет собой более общую форму [[RLE]].'' Node: '''int''' offset '''int''' length '''char''' next</code>

=== Недостатки ===* невозможность кодирования подстрокФункция <code>findMatching</code> ищет в буфере строку, отстоящих друг от друга на расстояниисовпадающую с префиксом суффикса строки <tex>s</tex>, большем длины словаря* длина подстрокиначинающегося с символа <tex>pos</tex> и возвращает искомую пару <tex>\langle offset, которую можно закодировать, ограничена размером буфера* малая эффективность при кодировании незначительного объёма данныхlength \rangle</tex>.

=== Пример "abracadabra" === ПозФункция <code>shiftBuffer</code> сдвигает буфер вперёд на <tex>x</tex> символов. Длина Симв. ''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 на Си ===<code> <source langfont color="c"green>// <tex>s</tex> {{---}} исходная строка /*==============================/ функция возвращает список блоков <tex>\langle offset, length, next \rangle</tex></font>Архивирование Алгоритм LZ77'''list<Node>''' encodeLZ77('''string''' s):Очень неоптимизированный вариант '''list<Node>''' ans = []Просьба обработать напильничком, pos = 0 как следует '''while''' pos < s.length: offset, length ==============================*/#define DICBITS 12 // LogfindMatching(DICSIZEbuffer, pos)#define DICSIZE (1<<DICBITS) font color=green>// 4-32kB Размер словаря#define THRESHOLD 2 ищем слово в словаре<// Порогfont>#define STRBITS 6 // Log shiftBuffer(STRMAX-THRESHOLDlength + 1)#define STRMAX ((1 <font color=green>// перемещаем скользящее окно<STRBITS)+THRESHOLD) // Мах. длина строкиfont>#define BUFSIZE 0xff00U // Полный размер буфера pos += length#define TEXTSIZE ans.push(BUFSIZE-DICSIZE-STRMAX{offset, length, s[pos]}) <font color=green>// Размер буфера текстадобавляем в ответ очередной блок</font>#define YES 1 '''return''' ans#define NO 0</code>

FILE *first_file, *second_file;long srcleng=0, fileleng;unsigned char *srcbuf, *srcstart;/*==Пример ====================================Функция записи=======================================*/int putbits(int data, int nbits){ static int bitcounter=0; static int outdata=0; int bit, error; data<<=(16-nbits); for( ; nbits > 0 ; nbits-- ) { if( bitcounter == 8 ) { bitcounter=0; error=putc(outdata,second_file); if( error == EOF ) { printf("Error writing to Second file."); return -5; } } outdata<<=1; bit=( data & 0x8000 ) ? 1:0; outdata+=bit; bitcounter++; data<<=1; }}

/*====================================Функция Архивирования===================================*/void compress_stud()Рассмотрим пример кодирования <tex>\mathrm{/LZ77}</ struct stat buf; unsigned char *position, *pointer; tex> на строке <tex>abacabacabadaca</tex> с буфером размера <tex>5</байт в файле , байт в буфере int i, dist, offset=0, last=NO, cnt, maxleng;tex>. Квадратом обведен буфер.

printf({| class="Compress started.wikitable"); ! Строка || Совпадение || Закодированная последовательность || Примечание|-| <tex>abacabacabadaca</tex> || {{---}} || <tex>\langle 0, 0, a \rangle</tex> || Буфер пуст|-| <tex>\fbox{$a$}bacabacabadaca</tex> || {{---}} || <tex>\langle 0, 0, b \rangle</tex> || В буфере нет <tex>b</tex>|-| <tex>\fbox{$ab$}acabacabadaca</tex> || <tex>a</tex> || <tex>\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> |- fstat(fileno(first_file)| <tex>abacaba\fbox{$cabad$}aca</tex> || <tex>a</tex> || <tex>\langle 2,&buf);1, c \rangle</tex> || Последовательность <tex>aca</tex> уже встречалась, но она находится за пределами окна, и <tex>\mathrm{LZ77}</tex> её не находит fileleng=buf.st_size;|- write(fileno(second_file)| <tex>abacabaca\fbox{$badac$}a</tex> || <tex>a</tex> || <tex>\langle 2, &fileleng1, sizeof(long));\varnothing \rangle</tex> || Символов в строке больше нет, поэтому в качестве <tex>next</tex> ставим символ конца строки|}

// Читаем файл в буфер по частям размера TEXTSIZE while((srcleng=fread(srcstart+offsetРезультатом кодирования является список полученных троек: <tex>\left[ \langle 0, 10, TEXTSIZEa \rangle, first_file))>\langle 0) { if(srcleng < TEXTSIZE ) // Последняя часть текста { last=YES; } position=srcstart; pointer=srcbuf; srcleng+=offset; while(srcleng>, 0) { printf(", b \rangle, \langle 2, 1, c \nrangle, \nStep - %langle 4, 7, d\n"rangle,srcleng); maxleng=0; if((last == NO) && (srcleng < STRMAX)) // Если в буфере текста осталось мало символов\langle 2, 1, c \rangle, сдвигаем словарь и оставшийся текст в начало буфера и дочитываем следующую часть из файла { memcpy(srcbuf\langle 2,pointer1,DICSIZE+(int)srcleng); offset=(int)srcleng; break; }\varnothing \rangle \right]</tex>.

for( i=DICSIZE-1; i >= 0; i-- )// Ищем самую длинную совпадающую строку в словаре= Декодирование === Для декодирования <tex>\mathrm{ for( cnt=0; cnt LZ77}< STRMAX; cnt++ ) if( *(position+cnt) != *(pointer+i+cnt) ) break;/tex> необходимо пройти по уже раскодированной строке назад, вывести необходимую последовательность, затем следующий символ.

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

if( (last == YES) && (maxleng = Модификации ===Известно много различных модификаций алгоритма <tex> srcleng) ) \mathrm{LZ77}<// Проверяемtex>. Например, чтобы не было выхода за границы файла вместо блоков можно хранить отдельно одиночные символы и отдельно {{ maxleng=(int)srcleng; //обрезаем длину по границу буфера ---}} if( maxleng  пары <tex> THRESHOLD )//Если строка достаточно длинная\langle offset, формируем pointer-код { printf("link!length \n"); putbitsrangle</tex> (1,1); length-distance pair<ref>[https://помечаем как ссылку putbits(dist,DICBITS); en.wikipedia.org/wiki/записываем позицию putbits(maxlengLZ77_and_LZ78#LZ77 Wikipedia {{--THRESHOLD-1,STRBITS}} LZ77]</ref>); . [[Алгоритм LZSS]] является улучшением <tex>\mathrm{LZ77}</tex> и хранит однобитный флаг, показывающий, какие данные за ним идут: одиночный символ или пара смещения и длины. В формате <tex>\mathrm{PalmDoc}</записываем длину position+=maxleng; srcleng-=maxleng; pointer+=maxleng; } else tex><ref>[https:// Иначе - chr-код { printf("Char!\n"); putbits(0,1); wiki.mobileread.com/wiki/помечаем как chr-код putbits(*position,8); PalmDOC Описание формата PalmDOC]</ref> на каждую пару смещения и длины выделяется по <tex>2</записываем чар код position++; srcleng--; pointer++; } } }tex> байта.

Также на <tex>\mathrm{LZ77}</tex> основаны алгоритмы <tex>\mathrm{LZH}</ Записываем оставшиеся биты putbitstex><ref>[https://msdn.microsoft.com/en-us/library/hh554076.aspx LZH]</ref> и <tex>\mathrm{DEFLATE}</tex><ref>[https://en.wikipedia.org/wiki/DEFLATE Wikipedia {{---}} DEFLATE]</ref> (0последний является широко используемым), которые совмещают <tex>\mathrm{LZ77}</tex> с [[Алгоритм Хаффмана|алгоритмом Хаффмана]],8);кодируя элементы пар и одиночные символы.

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

for( ; nbits <code> 0 ; nbits-- ) { '''struct''' Node: if( bitcounter '''int''' pos <font color== 8 )green>// номер слова в словаре</font> { '''char''' next bitcounter=0; indata=getc(first_file); } if( indata == EOF ) { printf("Error writing to First file."); return -6; }</code>

bit=( indata & 0x80 ) ? 1:0; dataВ качестве словаря будем использовать обычный <code>map<=1; data+=bit; bitcounter++; indata<<=1; } return data;}/code>:

/*===========<code> '''list<Node>''' encodeLZ78('''string''' s): '''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: '''if''' dict.hasKey(buffer + s[i]): <font color=green>// можем ли мы увеличить префикс</font> 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> buffer ="" <font color=green>// сбрасываем буфер</font> '''if''' not (buffer is empty): <font color=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''' ans==============================*</code>

printf("Decompress startedВ этот раз для примера возьмем строку <tex>abacababacabc</tex>.\n");

{| class="wikitable"! Словарь || Осталось обработать || Найденный префикс || Код || Примечание|-| <tex>\varnothing</tex> || <tex>abacababacabc</ Получаем длину исходного файла read(fileno(first_file)tex> || {{---}} || <tex>\langle 0,&filelenga \rangle</tex> || В словаре ничего не нашлось,sizeof(long)); pos=srcstart; while( fileleng вместо номера в словаре указываем <tex> 0 )</tex> {|- if( (ch=getbits(1)) == 0 ) | <tex>a</tex> || <tex>bacababacabc</ Если chrtex> || {{---код}} || <tex>\langle 0, копируем в буфер текста символ b \rangle</tex> || {|- ch=getbits| <tex>a</tex>, <tex>b</tex> || <tex>acababacabc</tex> || <tex>a</tex> || <tex>\langle 1, c \rangle</tex> || Нашелся префикс <tex>a</tex> (8слова в словаре нумеруются с <tex>1</tex>); putc(ch,second_file); добавляем <tex>ac</tex> *pos=ch; |- pos++; | <tex>a</tex>, <tex>b</tex>, <tex>ac</tex> || <tex>ababacabc</tex> || <tex>a</tex> || <tex>\langle 1, b \rangle</tex> || fileleng|--; } else | <tex>a</tex>, <tex>b</tex>, <tex>ac</tex>, <tex>ab</tex> || <tex>abacabc</tex> || <tex>ab</ Иначе - копируем maxleng символов из словаряtex> || <tex>\langle 4, начиная с позиции dista \rangle</tex> || {|- dist=getbits(DICBITS)+1; maxleng=getbits(STRBITS)+THRESHOLD+1; for( i=0; i | <tex>a</tex>, <tex>b</tex>, <tex>ac</tex>, <tex>ab</tex>, <tex>aba</tex> || <tex>cabc< maxleng; i++ ) /tex> || {{ *(pos+i)=*(pos+i-dist); putc(*(pos+i-dist)-}} || <tex>\langle 0,second_file); c \rangle </tex> || } pos+=maxleng; fileleng|-=maxleng; } if( pos | <tex>a</tex>, <tex>b</tex>, <tex> srcstart+TEXTSIZE ) ac</tex>, <tex>ab</ Если буфер заполненtex>, записываем его на диск и сдвигаем словарь в начало буфера { memcpy(srcbuf<tex>aba</tex>,pos-DICSIZE<tex>c</tex> || <tex>abc</tex> || <tex>ab</tex> || <tex>\langle 4,DICSIZE); pos=srcstart; } } printf("c\nDecompress completed.");rangle </tex> || |}

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 ''literals'' (single characters 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 [[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.* [[As of 2004]], the most popular LZ77 based compression method is called [[DEFLATE (algorithm)|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на основе декодируемой информации строим словарь и берем из него значения.-->

<code> '''string''' decodeLZ78('''list<Node>''' encoded): '''list<string>''' dict =[""] <font color=green>// словарь, слово с номером 0 {{---}} пустая строка</font> '''string''' ans = "" <font color=green>// ответ</font> '''for''' node '''in''' encoded: word = dict[node.pos] + node.next <font color=green>// составляем слово из уже известного из словаря и новой буквы</font> ans += word <font color=green>// приписываем к ответу</font> dict.push(word) <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Алгоритмы сжатия]]