Это сообщение в блоге, в основном написанное моим аспирантом третьего курса Йиханом Гао, представляет собой общий обзор нашей статьи KDD'16 под названием Squish: почти оптимальное сжатие для архивирования реляционных наборов данных с кодом на github. И бумага на arXiv .
Из-за постоянно растущей скорости создания данных, от диалоговых ботов и Интернета вещей до крупномасштабного физического моделирования и высокопроизводительного геномного секвенирования, сжатие данных, особенно для целей архивный, остается крайне важным.
Традиционные алгоритмы сжатия предназначены для двоичных строк и определяют возможности сжатия путем поиска повторяющихся шаблонов в этих строках. Поскольку файлы по существу хранятся в виде двоичных строк, эти алгоритмы универсально применимы ко всем типам данных.
Однако, работая с обычным двоичным строковым представлением, эти алгоритмы теряют возможности детального сжатия. Одним из таких параметров является сверхважный параметр реляционных или табличных наборов данных: здесь общие алгоритмы сжатия в конечном итоге работают очень плохо. Мы представляем Squish: асимптотически оптимальный алгоритм сжатия реляционных наборов данных. По сравнению с другими алгоритмами для реляционных наборов данных, а также с более традиционными алгоритмами, наш алгоритм обеспечивает превосходную степень сжатия и настраивается для специальных наборов данных и потребностей, как мы и будем опишу позже.
Мотивация
Рассмотрим в качестве примера набор данных переписи местного населения с именем, полом, возрастом, весом и ростом в качестве атрибутов. Алгоритмы сжатия реляционных наборов данных, предложенные в предыдущей работе, могут использовать ограничения домена (например, имена представляют собой строки; пол имеет только два возможных значения; возраст, вес и рост являются числовыми полями). Но есть и другие возможности сжатия:
1. Между значениями атрибутов существуют мягкие зависимости. Например, пол обычно определяется по имени, а пол человека часто влияет на рост и вес.
2. Числовые значения могут быть коррелированы. Например, более высокие люди обычно весят больше. Дети (возраст
Используя эти возможности, мы можем использовать меньше места для хранения той же информации. Однако это нетривиальная задача, поскольку мы не знаем, с какими типами наборов данных будем иметь дело. Нам необходимо разработать алгоритм, который может фиксировать зависимости, не предполагая какой-либо конкретной структуры набора данных, и найти способ использовать эти зависимости для сжатия набора данных.
Использование байесовских сетей для сбора зависимостей
Давайте займемся первой задачей: как мы можем зафиксировать зависимости в наборе данных, не предполагая какой-либо структуры? Поскольку зависимости мягкие или «нечеткие», нам нужна вероятностная модель, чтобы зафиксировать эти зависимости. Для этого мы используем байесовскую сеть.
Короче говоря, мы используем каждую случайную переменную в байесовской сети для представления одного из значений атрибутов кортежа, так что каждый кортеж в наборе данных соответствует случайной выборке из байесовской сети.
Таким образом, первым шагом нашего алгоритма сжатия является изучение байесовской сети из реляционного набора данных. Тогда возникает вопрос: как использовать байесовскую сеть для сжатия набора данных? Прежде чем ответить на этот вопрос, давайте рассмотрим некоторые основные концепции арифметического кодирования.
Базовый обзор арифметического кодирования
Арифметическое кодирование - это адаптивная схема сжатия строк. Он требует условно-вероятностной модели для каждого символа в строке и генерирует уникально декодируемый код для всех возможных строк фиксированной длины. Мы используем пример, чтобы проиллюстрировать эту схему кодирования.
В этом примере правая часть - вероятностная модель строки. Для начала арифметическое кодирование присваивает каждой строке интервал вероятности, длина которого равна вероятности строки. Например, aaa соответствует [0, 0,048], а aba соответствует [0,12 , 0,204]. Затем, учитывая интервал вероятности [l, r], мы находим наименьшее целое число k и другое целое число M такое, что l ‹= 2 ^ {- k} M‹ 2 ^ {- k} (M + 1) ‹= r. Двоичное представление M - это код строки.
Объединение байесовских сетей с арифметическим кодированием
Несмотря на то, что она была разработана для строк, процедура арифметического кодирования действительно может использоваться в байесовских сетях с небольшими изменениями. Конструкция требует только двух вещей: упорядочивания случайных величин и условного распределения вероятностей для каждой случайной величины с учетом всех предыдущих. Интересно, что байесовские сети предоставляют нам и то, и другое. Вот пример того, как применить ту же процедуру в байесовской сети. Обратите внимание, что вычисление по существу такое же, как и раньше.
Работа со сложными атрибутами
В приведенном выше примере показано, как мы можем использовать байесовские сети и арифметическое кодирование для сжатия реляционных наборов данных только с категориальными атрибутами. А вот и последний недостающий элемент Squish: как мы можем работать со сложными атрибутами, такими как числа и строки?
Чтобы иметь возможность обрабатывать сложные атрибуты, мы разработали абстрактный интерфейс для всех типов данных, названный SquID (сокращение от «Squish Interface for Data types»). SquID используется для кодирования атрибутов таким образом, чтобы они вели себя как категориальные атрибуты, а затем мы можем использовать арифметическое кодирование для их сжатия.
SquID - это древовидная модель распределения вероятностей. По сути, это дерево решений с вероятностями, связанными с ребрами. Вот пример SquID, который описывает распределение Pr (X in (k - 1, k]) = 0,9 ^ {k - 1} * 0,1.
Чтобы закодировать атрибут с помощью SquID, мы просто создаем последовательность решений, так что в конце последнего решения мы бы точно знали, что такое значение атрибута. Например, чтобы закодировать числовой атрибут с помощью SquID, мы можем смоделировать процедуру деления пополам и определить значение атрибута в пределах [log n] шагов.
Поддержка типов данных, определяемых пользователем
Интерфейс SquID также позволяет нам поддерживать определенные пользователем атрибуты. Даже если набор данных содержит атрибуты, которые не принадлежат одному из реализованных нами примитивных типов данных (категориальные, числовые и строковые), пользователь все равно может использовать Squish для сжатия набора данных, реализуя интерфейс SquID для нового типа данных. Это относительно просто и предлагает большие возможности для включения в Squish знаний о предметной области для достижения еще лучших результатов сжатия.
Выводы
1. Мы разработали Squish, алгоритм сжатия реляционных наборов данных. Он использует комбинацию байесовских сетей и арифметического кодирования для использования мягких зависимостей и корреляций между атрибутами.
2. SquID, интерфейс типов данных Squish, позволяет нам применять арифметическое кодирование к сложным атрибутам. SquID также позволяет пользователю определять новые типы атрибутов, с помощью которых Squish может сжимать наборы данных с непримитивными типами атрибутов.
3. Squish поддерживает сжатие с потерями с заданным пользователем порогом ошибки.
4. Squish является асимптотически оптимальным для всех наборов данных, которые могут быть эффективно описаны с помощью байесовских сетей, и работает намного лучше - с сокращением объема памяти до 50% - чем современный реляционный алгоритмы сжатия наборов данных на 4 реалистичных наборах данных.
