Logo Host-telecom.com — профессиональный хостинг в Европе! Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

💰 Самые низкие цены на домены

🔒 Отличный хостинг на SSD c бесплатными SSL

💻 Огромнейший выбор dedicated выделенных серверов

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

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

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

VDS хостинг Облачный сервер в Нидерландах и Украине

Аренда виртуального сервера от $7.91

Партнёрская программа
$20 за клиента

Wildcard сертификаты от $74,97 в год.

Дешевые ssl сертификаты для домена

Sectigo сертификаты от $7,67 в год.

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. Локально адаптивный алгоритм сжатия

хостинг Украина Виртуальный хостинг для сайта от $4,87

Регистрация домена от $2 в год

Партнерская программа – $20 за клиента

VPS с гибкой конфигурацией: за 1€

Мощные выделенные сервера: от 25€

Собственный Дата-Центр
Поддержка 24/7

Бесплатный конструктор сайтов и Landing Page

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

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

ATLEX Выделенные серверы: в Европе / в России.

Виртуальные серверы: в Европе / в России.

Партнерская программа

Ваш сайт в 8 раз быстрее конкурентов. Хостинг от $2.95

VPS: SSD, KVM, бесплатные бэкапы и администрирование

Все необходимое для вашего сайта и лучшая техподдержка 24/7

хостинг сайтов ГиперХост — хостинг сайтов который Вы искали.

Виртуальный хостинг, Аренда VPS серверов, рация доменных имен, SSL сертификаты

Новости мира 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
Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...