Конференции ИВТ СО РАН

Тезисы докладов

Информационные технологии

Быстрый рост объемов памяти и производительности компьютеров в последние 10 лет отодвинул на второй план проблему скорости алгоритмов сжатия текстовой информации и сделал практически не актуальным вопрос потребления ресурсов при кодировании текстов на IBM-совместимых компьютерах. В то же время пропускная способность каналов передачи данных в сети Интернет по-прежнему остается узким местом, и требует максимального повышения степени сжатия транслируемых данных при минимальных затратах на передачу словарей и прочих служебных составляющих кода. Сложившиеся условия спровоцировали рост популярности адаптивных статистических алгоритмов сжатия.

Тем не менее, в настоящее время по-прежнему широко распространены аппаратные (модемные) методы сжатия, основанные на словарной стратегии, из которых наиболее популярен модифицированный метод Зива-Лемпела LZW [4], нашедший свое отражение в протоколе аппаратного сжатия данных V.44 [2], который был включен в стандартную спецификацию HTTP. Программные же методы сжатия применяются в основном для мультимедийного контента, игнорируя текстовую составляющую данных, в частности коды HTML-страниц.

LZW достаточно хорошо справляется со сжатием синтаксически и семантически связанных естественноязыковых текстов и гипертекста [1]. В то же время значительную часть содержимого HTML-страниц составляют короткие естественноязыковые фрагменты текста (в среднем 8 %), такие как: текстовые ссылки, заголовки, пункты меню, служебные надписи, краткие рекламные и новостные сообщения и т. п. Статистика показывает, что словарные методы демонстрируют низкую эффективность сжатия такого типа информации, в отличие от статистических. Таким образом, представляется актуальным применение статистических алгоритмов для сжатия коротких естественноязыковых фрагментов.

В настоящее время, в программных решениях наиболее высокую степень сжатия демонстрируют статистические алгоритмы, основанные на методе предсказания по частичному совпадению (PPM) [5]. Вместе с тем скорости кодирования/декодирования этим методом экспоненциально возрастает с увеличением объема памяти и, в силу своей адаптивности, PPM не требует генерации словарей.

Предлагается использовать программную реализацию алгоритма PPM в совокупности с предварительной обработкой (предобработкой) данных для кодирования коротких естественноязыковых фрагментов, с целью повышения эффективности сжатия HTML-страниц.

На стадии предобработки из коротких естественноязыковых фрагментов HTML-страницы формируется непрерывный текст путем их последовательной конкатенации. Каждому фрагменту ставится в соответствие индекс, хранящий информацию о длине фрагмента. Индексация необходима для корректного восстановления структуры документа после распаковки сжатых фрагментов. Индексы включаются в состав архива и кодируются вместе с текстом, а в качестве маркеров, указывающих расположение фрагментов в HTML-коде для алгоритма распаковки, будут служить пустые HTML-теги форматирования текста.

Для повышения однообразия данных предлагается представлять индексы в кодах литер естественноязыкового алфавита, идентифицируемого номером кодовой станицы в заголовке обрабатываемого HTML-файла. Например, для русскоязычной страницы индекс 1 соответствует «а», 2 – «б» …, 31 – «я», 32 – «А» …, 62 – «Я».

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

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

Предложенный метод эффективен, если сумма СВПД по методу PPM для ресурсного файла естественноязыковых фрагментов и СВПД по методу LZW для страницы без фрагментов меньше СВПД по методу LZW для исходного (полного) экземпляра страницы.

Для получения значений коэффициентов сжатия и скоростей декодирования было проведено тестирование архиваторов реализующих алгоритмы PPM (в модификации PPMD [3]) и ZLW. Тестовый набор данных был сформирован из коротких естественноязыковых фрагментов произвольных русскоязычных HTML-страниц различной тематики.

Вычисления показали, что предложенный метод можно эффективно применять в сетях с пропускной способностью канала менее 2026,72 Кбит/сек. В настоящее время к этой категории можно отнести Интернет-соединения на основе сетей сотовой связи, модемный доступ по проводным телефонным линиям и большинство индивидуальных каналов в домашних сетях (VPN, ADSL и т.п.). При этом тестирования метода показали выигрыш по степени сжатия 5-13%.

Литература
1. Гилчрист Д. Тестирование компрессоров (http://www.compression.ru/arctest/act/act-text.htm). Май 2002.
2. ITU-T Study Group. ITU-T Rec.V.44 (11/2000) Data compression procedures // Series V: Data communication over the telephone network. 2001. Geneva.
3. Howard P.G. The design and analysis of efficient lossless data compression systems // PhD thesis, Brown University, Providence. 1993. Rhode Island.
4. Miller V.S., Wegman M.N. Variations on a theme by Ziv and Lempel. // Combinatorial algorithms on words. 1985. New York. P. 131-140.
5. Cleary J.G., Witten I.H. Data compression using adaptive coding and partial string matching // IEEE Transactions on Communications, Vol. 32(4). April 1984. P. 396-402.

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 1996-2000, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2000, Сибирское отделение Российской академии наук, Новосибирск