жиною | s | ВЈ smax. smax зазвичай вибирається з діапазону 16 ... 256 байт; в якості словника використовуються | V | байт стискуваного тексту, що передують поточному кодованого символу у позиції pos (звідси і назва ковзний -словник як би ковзає уздовж по тексту від його початку до кінця, підтримуючи найсвіжішу інформацію про його зміст). Оскільки, перед початком процесу компресії перед першим символом нічого немає, спочатку словник порожній (або заповнений якимось певним символом).
Словами в словнику виступають будь рядки довжини не більше smax, що починаються в будь-якій позиції словника. Таким чином, в словнику завжди присутній | V | Г— smax слів. Якщо ж рядка s в словнику не виявилося, генерується код chr виду chr = , де prefix = 0, а symbol-поточний символ вихідного тексту (у позиції pos). Префікс, як видно, потрібен для того, щоб відрізнити код ptr від коду chr. Саме префікс вносить в алгоритм кодування LZ77 деяку додаткову інформацію, через яку можливе зростання надмірності.
В
Вид словника і вихідного тексту для алгоритму LZ77 перед початком роботи а) і на 23-му кроці б).
На малюнку б) показаний вигляд словника і кодованого тексту на 23-му символі, коли алгоритм виявив збіг слова де з таким же словом у словнику довжини length = 4 байти, на відстані distance = 23 байта від pos. Буде згенеровано код ptr = <1,23,4>. Довжина ptr-коду
| ptr | = 1 + Г©log (| V |) Г№ + Г©log (| smax |) Г№ (біт), коду
| chr | = 1 + Г©log (| symbol |) Г№ (біт).
Звідси випливає висновок, що, якщо довжина ptr-коду в байтах перевищує length, то таке кодування лише збільшить надмірність, тому в алгоритм вводять поріг (threshold), рівний зазвичай 2-3 байтам і, якщо збігається рядок коротше цього порога, вона кодується (вірніше, кодується явно, посимвольний, за допомогою chr-кодів).
Непоганий альтернативою послідовному пошуку може служити використання множинних двозв'язних списків - нескладної структури даних, яка дозволяє прискорити пошук не в 10 разів. Вона, звичайно, істотно поступається в швидкості бінарним деревах, але значно простіше в реалізації. Ідея методу полягає в тому, що створюється 256 (або більше) двозв'язних списків, у кожний з яких включаються слова, що починаються на однакову букву (або 1.5-2 літери). Пошук чергового слова здійснюється, очевидно, тільки в тому списку, слова якого починаються на ту ж букву, що і перша буква поточного слова symbol. p> Зворотне відновлення тексту здійснюється значно швидше і простіше. Оскільки до моменту декодування чергового символу весь попередній текст вже відомий, декодувальнику не потрібно передавати словник разом з упакованими даними. Словник будується декомпресора за тим же алгоритмом, що...
