Научная работа
Е.А. Кудревцова. Алгоритм сжатия HTML трафика. Физико-математический факультет, 2003

Скачать презентацию

Число удаленных локальных сетей подразделений, связанных по различным телекоммуникационным каналам с информационно-вычислительными сетями центральных офисов своих корпораций, растет быстрыми темпами.

В то же время по мере увеличения потребности в удаленном доступе к компьютерным сетям пользователи все чаще сталкиваются с проблемами, связанными с недостаточной пропускной способностью линий связи LAN-WAN.

Поскольку аренда высокоскоростных каналов для передачи данных на большие расстояния доступна лишь за высокую арендную плату, фирмы разработчики аппаратных средств и программного обеспечения постоянно ищут решения, направленные на повышение эффективности использования обычных телефонных линий. Сегодня эта проблема решается по двум основным направлениям.

Первое из них связано с развитием технологии клиент-серверов в сетевых приложениях. Реализация такого подхода позволяет существенно уменьшить интенсивность сетевого трафика за счет того, что обработка запросов и операции с базами данных, массивами и др. производятся непосредственно на сервере, а по сети на рабочую станцию передаются лишь результаты обработки запроса.

Второй способ - сжатие (компрессия) данных при их передаче по низкоскоростным каналам. Именно компрессия позволяет значительно увеличить пропускную способность линий при относительно небольших затратах на приобретение специального оборудования и ПО. При этом "прозрачная" работа удаленного пользователя в сети корпорации может быть обеспечена даже при передаче данных по обычным аналоговым телефонным линиям. Помимо несомненного выигрыша в скорости передачи больших объемов данных на большие расстояния, компрессия также является дополнительной мерой обеспечения защиты конфиденциальной информации при попытке ее несанкционированного перехвата во время передачи по каналам WAN.

Разнообразные продукты для сжатия данных в системах коммуникаций LAN-WAN можно подразделить на два больших класса: программное обеспечение и аппаратные средства.

Аппаратные устройства сжатия данных обычно обеспечивают менее высокую степень компрессии, и их стоимость зачастую значительно выше стоимости программных продуктов.

На сегодняшний день существует множество различных алгоритмов сжатия данных, подразделяющихся на несколько основных групп:

    • алгоритмы кодирования повторов;
    • вероятностные методы;
    • арифметические методы;
    • "метод словарей" (dictionary).

Алгоритм "метод словарей" был впервые описан в работах А. Лемпеля и Дж. Зива в 1977-78 гг., поэтому этот метод часто называется Lempel-Ziv или сокращенно LZ. На сегодняшний день LZ-алгоритм и его модификации получили наиболее широкое распространение по сравнению с другими методами компрессии. В его основе лежит идея замены наиболее часто встречающихся последовательностей символов (строк) в файле ссылками на "образцы", хранящиеся в специально создаваемой таблице (словаре). Так, например, создан словарь, содержащий 65536 наиболее употребительных слов, можно представить текстовые файлы в виде последовательности 16-битовых ссылок на "место" данного слова в словаре.

На практике, конечно, мы имеем дело не с фиксированными словарями, а с таблицами, заполняемыми по мере сканирования файла. При этом уже просмотренная часть файла используется как словарь. Алгоритм основывается на движении по потоку данных, состоящего из двух частей: большей по объему, в которой содержатся уже обработанные данные, и меньшей, в которую по мере просмотра помещается вновь считанная информация. Во время считывания каждой новой порции информации происходит проверка, и если оказывается, что такая строка уже помещена в словарь ранее, то она заменяется ссылкой на нее. Множество модификаций метода LZ, активно используется в различных приложениях, модемах, а также во многих системах аппаратного сжатия данных.

Предварительное построение словаря

  1. Исходное сообщение не некоторому алгоритму разбивается на последовательности символов, называемых словами. (слово может быть одно или несколько вхождений в исходный текст сообщения)
  2. Полученное множество слов считается буквами нового алфавита. Для этого алфавита строится разделимая схема алфавитного кодирования. Полученная схема называется словарем, так как она сопоставляет слову код.
  3. Далее код сообщения строится как пара - код словаря и последовательность кодов слов из данного словаря.
  4. При декодировании исходное сообщение восстанавливается путем замены кодов слов на слова из словаря.

Математическое обоснование

Пусть заданы алфавиты А={a1,:,an} и B={b1,:,bn}, тогда функция F:S® B*, где S -некоторое множество слов в алфавите А, SÌ A.

Тогда функцию F - будем называть кодированием, элементы множества S -сообщениями, а b =F(a ), a Î S, b Î B* - кодами.

Множество P={p1,:,pn} - множество вероятностей появления букв aiÎ A в сообщении S, причем (согласно третьему свойству эмпирической вероятности) и p1³ p2³ :.³ pn>0 (доказано Фано в его работе про оптимальное кодирование)

Показателем эффективности сжатия служит величина -

, где li=|b i| - длинна закодированного символа,

- правило кодирования.

Общий объем архива можно описать формулой:

, (2)

где hdr =const, которая определяет заголовок архива. По сути дела выражение - и есть словарь. Пример кодирование сообщений по алгоритму Хаффмана

В случае архивирования произвольных данных мы не знаем какие сообщения могут быть в множестве А. При кодировании HTML файла можно заранее сказать какие из сообщений будут (или могут быть) в исходном сообщении. Ведь практически в любом HTML файле, помимо неизвестного нам набора сообщений присутствуют известные тэги <HTML>,<BODY>,<FONT>,<P ALIGN=:> <A HREF=":"> и т.д., а также закрывающие тэги.

Рассмотрим идею архивирования HTML файла.

Разобьем множество исходного алфавита А={a1,:,an} на два множества A1={a1,..,am} и A2={am+1,:,an}, причем A=A1È A2.

Тогда и множество кодов разобьется на два подмножества

B1={b1,..,bm} и B2={bm+1,:,bn}, причем B1 и B2 будем рассматривать как самостоятельные множества т.е. B¹ B1È B2

Множество P1={p1,:,pm} - множество вероятностей появления букв aiÎ A1, P2={pm+1,:,pn} - множество вероятностей появления букв aiÎ A2,

Пусть А1 - множество слов исходного алфавита, которые нам неизвестны, а A2 - множество тэгов HTML. Каждое из этих множеств будем кодировать отдельно, тогда

Показателем эффективности сжатия для A1 служит величина -

, где l1i=|b 1i| - длинна закодированного символа,

- правило кодирования.

Показателем эффективности сжатия для A2 служит величина -

, где l2i=|b 2i| - длинна закодированного символа,

- правило кодирования.

Таким образом объем заархивированного файла можно посчитать по формуле:

(2)

где hdr =const - заголовок архива.

Учитывая, что в каждом HTML документе как правило присутствуют одни и те же теги, то словарь тегов не необязательно передавать вместе с архивом, а можно хранить встроенным в программу-архиватор, тогда выражение (2) можно преобразовать так:

(3)

Из (1), (2) и (3) очевидно видно, что length=length*, а length*>length**. Следовательно, length**<length.

Во встроенном словаре можно хранить не только теги, но и наиболее распространенные слова, тогда размер архива будет еще меньше.