Logo Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware
Бесплатный конструктор сайтов и Landing Page

Хостинг с DDoS защитой от 2.5$ + Бесплатный SSL и Домен

SSD VPS в Нидерландах под различные задачи от 2.6$

✅ Дешевый VPS-хостинг на AMD EPYC: 1vCore, 3GB DDR4, 15GB NVMe всего за €3,50!

🔥 Anti-DDoS защита 12 Тбит/с!

VPS в 21 локации

От 104 рублей в месяц

Безлимитный трафик. Защита от ДДоС.

🔥 VPS до 5.7 ГГц под любые задачи с AntiDDoS в 7 локациях

💸 Гифткод CITFORUM (250р на баланс) и попробуйте уже сейчас!

🛒 Скидка 15% на первый платеж (в течение 24ч)

2004 г.

2.6.1. Алгоритм Зива-Лемпеля

Семёнов Ю.А. (ГНЦ ИТЭФ), book.itep.ru

В 1977 году Абрахам Лемпель и Якоб Зив предложили алгоритм сжатия данных, названный позднее LZ77. Этот алгоритм используется в программах архивирования текстов compress , lha , pkzip и arj . Модификация алгоритма LZ78 применяется для сжатия двоичных данных. Эти модификации алгоритма защищены патентами США. Алгоритм предполагает кодирование последовательности бит путем разбивки ее на фразы с последующим кодированием этих фраз.

Суть алгоритма заключается в следующем:

Если в тексте встретится повторение строк символов, то повторные строки заменяются ссылками (указателями) на исходную строку. Ссылка имеет формат <префикс, расстояние, длина>. Префикс в этом случае равен 1. Поле расстояние идентифицирует слово в словаре строк. Если строки в словаре нет, генерируется код символ вида <префикс, символ>, где поле префикс =0, а поле символ соответствует текущему символу исходного текста. Отсюда видно, что префикс служит для разделения кодов указателя от кодов символ . Введение кодов символ, позволяет оптимизировать словарь и поднять эффективность сжатия. Главная алгоритмическая проблема здесь заключатся в оптимальном выборе строк, так как это предполагает значительный объем переборов.

Рассмотрим пример с исходной последовательностью (см. также http://geeignetra.chat.ru/lempel/lempelziv.htm )

U =0010001101 (без надежды получить реальное сжатие для столь ограниченного объема исходного материала).

Введем обозначения:

P[n] - фраза с номером n .

C - результат сжатия.

Разложение исходной последовательности бит на фразы представлено в таблице ниже.

N фразы

Значение

Формула

Исходная последовательность U

0

-

P[0]

0010001101

1

0

P[1]=P[0] . 0

0 . 010001101

2

01

P[2]=P[1] . 1

0 . 01 . 0001101

3

010

P[3]=P[1] . 0

0 . 01 . 00 . 01101

4

00

P[4]=P[2] . 1

0 . 01 . 00 . 011 . 01

5

011

P[5]=P[1] . 1

0 . 01 . 00 . 011 . 01

P[0] - пустая строка. Символом . (точка) обозначается операция объединения (конкатенации).

Формируем пары строк, каждая из которых имеет вид (A . B). Каждая пара образует новую фразу и содержит идентификатор предыдущей фразы и бит, присоединяемый к этой фразе. Объединение всех этих пар представляет окончательный результат сжатия С. P[1]=P[0] . 0 дает (00 . 0), P[2]=P[1] . 0 дает (01 . 0) и т.д. Схема преобразования отражена в таблице ниже.

Формулы

P[1]=P[0] . 0

P[2]=P[1] . 1

P[3]=P[1] . 0

P[4]=P[2] . 1

P[5]=P[1] . 1

Пары

00 . 0=000

01 . 1=011

01 . 0=010

10 . 1=101

01 . 1=011

С

000 . 011 . 010 . 101 . 011 = 000011010101011

Все формулы, содержащие P[0] вовсе не дают сжатия. Очевидно, что С длиннее U , но это получается для короткой исходной последовательности. В случае материала большего объема будет получено реальное сжатие исходной последовательности.

Назад: 2.6. Методы сжатия информации
Оглавление: Телекоммуникационные технологии
Вперёд: 2.6.2. Локально адаптивный алгоритм сжатия

Скидка до 20% на услуги дата-центра. Аренда серверной стойки. Colocation от 1U!

Миграция в облако #SotelCloud. Виртуальный сервер в облаке. Выбрать конфигурацию на сайте!

Виртуальная АТС для вашего бизнеса. Приветственные бонусы для новых клиентов!

Виртуальные VPS серверы в РФ и ЕС

Dedicated серверы в РФ и ЕС

По промокоду CITFORUM скидка 30% на заказ VPS\VDS

VPS/VDS серверы. 30 локаций на выбор

Серверы VPS/VDS с большим диском

Хорошие условия для реселлеров

4VPS.SU - VPS в 17-ти странах

2Gbit/s безлимит

Современное железо!

Новости мира IT:

Архив новостей

IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

Информация для рекламодателей PR-акции, размещение рекламы — adv@citforum.ru,
тел. +7 495 7861149
Пресс-релизы — pr@citforum.ru
Обратная связь
Информация для авторов
Rambler's Top100 TopList liveinternet.ru: показано число просмотров за 24 часа, посетителей за 24 часа и за сегодня This Web server launched on February 24, 1997
Copyright © 1997-2000 CIT, © 2001-2019 CIT Forum
Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...