Лучший алгоритм сжатия для векторных данных?

Question

Мне нужно сжать некоторые пространственно коррелированные записи данных. В настоящее время я получаю сжатие 1.2x-1.5x с zlib, но я полагаю, что возможно получить больше как 2x. Записи данных имеют различные поля, но, например, zlib, похоже, не может сжать списки точек.

Точки представляют дорожную сеть. Они представляют собой пары 4-байтовых целых чисел с фиксированной точкой вида XXXXYYYY. Как правило, если один блок данных имеет 100 точек, будет только несколько комбинаций двух верхних байтов X и Y (пространственная корреляция). Но нижние байты всегда меняются и должны выглядеть как случайные данные для zlib.

Аналогично, записи имеют 4-байтовые идентификаторы, которые обычно имеют постоянные старшие байты и переменные младшие байты.

Есть ли другой алгоритм, который мог бы лучше сжимать данные такого типа? Я использую C ++.

Редактировать : Пожалуйста, больше никаких предложений по изменению самих данных. Мой вопрос об алгоритмах автоматического сжатия. Если у кого-то есть ссылка на обзор всех популярных алгоритмов сжатия, я просто приму это как ответ.

Answer 1

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

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

Но дублирующиеся данные не исчезают.Дублированная последовательность становится короче, но она все еще дублируется так же часто, как и раньше.

Насколько я понимаю, у вас есть большое количество точек данных вида

XXxxYYyy, гдезаглавные буквы очень однородны.Поэтому исключите их.

Перепишите список примерно так:

XXYY // a header describing the common first and third byte for all the subsequent entries
xxyy // the remaining bytes, which vary
xxyy
xxyy
xxyy
...
XXYY // next unique combination of 1st and 3rd byte)
xxyy
xxyy
...

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

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

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

Answer 2

Не относится к вашим данным, но я бы порекомендовал проверить 7zip вместо zlib, если вы можете. Я видел смехотворно хорошие коэффициенты сжатия, используя это.

http://www.7 -zip.org /

Answer 3

Возможно, вы захотите записать два списка в сжатый файл: a NodeList и a LinkList. Каждый узел будет иметь идентификатор, х, у. Каждая ссылка будет иметь FromNode и ToNode, а также список промежуточных значений xy. Вы можете иметь запись заголовка с ложным происхождением и иметь значения узла xy относительно этого.

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

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

Опять же, если ваши дороги не находятся в городской сетке, это, вероятно, не купит вам много.

Answer 4

Похоже, преобразование Берроуза-Уилера может быть полезно для этой проблемы.У него есть особая тенденция соединять серии повторяющихся байтов, что может улучшить сжатие zlib. В этой статье предлагается, чтобы я сочетал другие алгоритмы, кроме zlib, с BWT.

Интуитивно это звучит дорого, но взгляд на некоторый исходный код показывает, что обратный BWT - это O (N) с 3передает данные и занимает немного места, вероятно, делая это достаточно быстро на моей целевой платформе (WinCE).Прямое преобразование примерно равно O (N log N) или немного больше, если принять обычный алгоритм сортировки.

Answer 5

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

0-1 Количество байтов идентификатора, которые должны быть заимствованы из предыдущей записи. 2-4 Формат записи позиции 6-7 Количество последовательных записей, которые используют один и тот же байт режима

Каждая позициязапись может храниться одним из восьми способов;все типы, кроме 000, используют подписанные смещения.Число после битового кода соответствует размеру записи позиции.

000 - 8 - две полных четырехбайтовых позиции 001 - 3 - двенадцать битов для X и Y 010 - 2 - десятиразрядная X и шестьбита Y 011 - 2 - шестибитовые X и десятиразрядные Y 100 - 4 - два смещения шестнадцатиразрядных со знаком 101 - 3 - шестнадцатибитные X и 8-битные смещения Y со знаком 110 - 3 - восьмибитные смещения со знакомдля X;16 бит для Y 111 - 2 - два восьмибитных смещения со знаком

Нулевой байт режима будет хранить всю информацию, относящуюся к точке, без ссылки на какую-либо предыдущую точку, используя для хранения всего 13 байтов12 байт полезной информации.Байты другого режима позволят сжать записи на основе сходства с предыдущими записями.Если четыре последовательные записи отличаются только последним битом идентификатора, и либо имеют X и Y в пределах +/- 127 от предыдущей записи, либо X в пределах +/- 31 и Y в пределах +/- 511, либо X в пределах+/- 511 и Y в пределах +/- 31, тогда все четыре записи могут храниться в 13 байтах (в среднем по 3,25 байта каждая (сокращение на 73%).

«жадный» алгоритм можетиспользоваться для сжатия: проверьте запись, чтобы увидеть, какой идентификатор размера и XY он будет использовать в выходных данных, а затем захватите до трех дополнительных записей, пока не будет найдена одна, которая не может «соответствовать» предыдущим записям, используявыбранные размеры или могут быть записаны меньшими размерами (обратите внимание, что, если, например, первая запись имеет смещения X и Y, равные 12, XY будет записан двумя байтами, но до тех пор, пока одна из них не прочитает следующие записи, никто не будет знать, какая из трехиспользование двухбайтовых форматов).

Прежде чем устанавливать формат в камне, я рекомендую пропустить ваши данные через него. Возможно, это небольшая настройка (например, использование 7 + 9 или 5 + 11 битформаты вместо 6 + 10) позволят упаковывать многие данные лучше.Однако единственный реальный способ узнать это - посмотреть, что происходит с вашими реальными данными.

Answer 6

Сортировка точек по некоторому критерию близости, так что среднее расстояние между соседними точками невелико. Затем сохраните разницу между соседними точками.

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

В качестве альтернативы zlib, семейство методов сжатия, которые хорошо работают, когда распределение вероятностей перекошено в сторону небольших чисел, это универсальные коды . Их нужно настроить для чисел со знаком (кодировать abs(x)<<1 + (x < 0 ? 1 : 0)).