Регистрация / Вход
Прислать материал

Разработка и реализация метода сжатия табличных данных на основе оптимального квантования величин

Сведения об участнике
ФИО
Комиссаров Александр Владимирович
Вуз
Федеральное государственное автономное образовательное учреждение высшего образования «Новосибирский национальный исследовательский государственный университет»
Тезисы (информация о проекте)
Область наук
Информационные технологии и вычислительные системы
Раздел области наук
Информатика
Тема
Разработка и реализация метода сжатия табличных данных на основе оптимального квантования величин
Резюме
Проект направлен на создание нового метода сжатия табличных данных. Используя технику оптимального квантования, разработанный метод позволяет достичь значительного увеличения уровня сжатия по сравнению с обычными методами сжатия, такими как Deflate (ZIP), с некоторой потерей точности данных, определяемой пользователем.
Ключевые слова
сжатие данных, потеря точности, табличные данные, оптимальное квантование, восстановление плотности вероятности, программный комплекс
Цели и задачи
Цель работы – разработать эффективный метод сжатия табличных данных с допустимой (определяемой конкретной задачей) потерей точности, учитывающий специфику обрабатываемых данных, и реализовать программный комплекс сжатия данных, основанный на разработанном методе.

Задачи:
1) сформулировать требования к методу сжатия табличных данных;
2) сформулировать требования к программному комплексу сжатия табличных данных, реализующему разрабатываемый метод;
3) разработать метод сжатия табличных данных;
4) разработать архитектуру программного комплекса сжатия табличных данных;
5) реализовать программный комплекс сжатия табличных данных;
6) протестировать эффективность программного комплекса.
Введение

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

В настоящей работе рассматриваются данные, представленные в виде таблиц объекты-признаки с численными значениями. Элементы одного столбца являются реализацией случайной величины, подчиняющейся некоторому распределению.

Методы и материалы

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

Качество квантования оценивается по двум параметрам: ошибка, вносимая квантованием (не должна превышать заданную), и энтропия столбца после квантования (должна быть минимальной).

В качестве алгоритма квантования был выбран алгоритм Ллойда-Макса, который строит оптимальное квантование для заданного количества интервалов с точки зрения ошибки квантования. Для оптимизации по энтропии был разработан алгоритм нахождения количества интервалов, при котором энтропия будет минимальна.

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

Для сжатия таблицы после квантования было предложено три различных метода: сжатие с помощью оптимального кода Хаффмана по столбцам; разработаны модификации словарного метода LZ77 и арифметического кода для сжатия таблицы целиком.

Описание и обсуждение результатов

Разработанный метод был реализован в программном комплексе сжатия табличных данных. Его работа была протестирована на трех наборах тестовых данных. Первые тестовые данные являются автоматически сгенерированной таблицей, на которой проводилось тестирование квантования в предыдущем пункте. Вторые тестовые данные содержат информацию об уровне холестерина и различных белков в крови пациентов, перенесших инфаркт. Третье тестовые данные представляют собой замеры силы тока и напряжения с электростанций города Питтсбург, США. Для сравнения был выбран популярный формат сжатия ZIP, использующий метод сжатия Deflate.

По уровню сжатия программный комплекс существенно опережает популярный формат ZIP. В худшем случае разработанный метод сжатия оказался эффективнее Deflate в 1.6-3 раза, в лучшем – в 2-5 раз. Уровень сжатия по сравнению с оригинальным размером таблицы составил 5-12 раз.

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

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

Используемые источники
1. Крянев А.В., Лукин Г.В. Математические методы обработки неопределенных данных. М.: ФИЗМАТЛИТ, 2003. 216 с.
2. Потапов, В. Н. Введение в теорию информации: учеб. пособие для студентов и аспирантов математических факультетов университетов. Москва; Ижевск: Регулярная и хаотическая динамика, 2014. 151 с.
3. Цифровая обработка изображений в информационных системах: учеб. пособие /И.С. Грузман, В.С. Киричук, В.П. Косых, Г.И. Перетягин, А.А. Спектор. Новосибирск: Изд-во НГТУ, 2002. 351 с.
4. Huffman D.A. A Method for the Construction of Minimum-Redundancy Codes // Proceedings of the IRE. Sept. 1952. Vol. 40(9): P.1098–1101.
5. Ziv J., Lempel A. A Universal Algorithm for Sequential Data Compression // IEEE Transactions on information theory. May 1977. Vol. 23(3): P. 337-343.
Information about the project
Surname Name
Komissarov Alexander
Project title
Design and implementation of tabular data compression method based on optimal quantization
Summary of the project
The aim of the project is to create a new method of tabular data compression. Using optimal quantization technique to reduce redundant data precision, it manages to achieve significant compression rate increase in comparison to conventional compression methods such as Deflate (ZIP), with user-defined precision loss.
Keywords
data compression, loss of precision, tabular data, optimal quantization, density estimation, software package