 |
|
 |
| Главное меню | ||
· Главная · Права на контект · Скачать NOD32 |
||
| Сетевые технологии | ||
· Учебные пособия и обзоры · Беспроводные технологии · Локальные сети · Сетевое оборудование · Сети хранения данных · TCP/IP · xDSL · ATM · Netware |
||
| Счетчики | ||
|
|
||
| Друзья | ||
 |
 |
|
Семёнов Ю.А. (ГНЦ ИТЭФ), 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 , но это получается для короткой исходной последовательности. В случае материала большего объема будет получено реальное сжатие исходной последовательности. |