Алгоритмы сжатия только для чисел

Question

Я сжимаю данные о местоположении (широта, долгота, дата, время). Все числа в фиксированном формате. 2 из них (широта, долгота) имеют десятичный формат. Другие 2 являются целыми числами.

Теперь эти числа находятся в фиксированной строке формата.

Каковы алгоритмы сжатия чисел в фиксированном формате? Сжатие только чисел (если есть) лучше сжатия строк? Должен ли я напрямую сжимать строку без преобразования ее в числа, а затем сжимать?

Заранее спасибо.

Answer 1

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

• Каково разрешение ваших измерений: 0,1 ° или 0,001 °? 1 секунда или одна микросекунда?
• Связаны ли измерения и в каком-то порядке, или случайно объединены?

Допустим, например, что разрешение составляет 0,01 °. Их вы знаете, что ваши значения колеблются от -180 ° до + 180 °, или 35900 различных значений. Lg (35900) & asymp; 16, поэтому вам нужно 16 бит; 14 бит для -90 ° - + 90 °. Ясно, что если вы храните значение такого типа в виде числа с плавающей запятой, вы можете сразу сжать данные наполовину.

Аналогично дате и времени, каков диапазон; сколько битов у вас должно быть?

Теперь, если данные в некотором порядке (например, выборки, взятые последовательно на одном корабле), тогда все, что вам нужно, это начальное значение и дельта; это может иметь большое значение. С кораблем, движущимся со скоростью 30 узлов, положение не может измениться больше, чем на 0,03 градуса в час или на 0,0000083 градуса в секунду. Эти дельты будут очень маленькими значениями, поэтому вы можете хранить их в несколько бит.

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

---

Обновление: Ой, подождите, фиксированная точка строк ?!

Хорошо, это (относительно) просто. Просто для начала, да, вы хотите преобразовать ваши строки в некоторое двоичное представление. Просто составив элемент данных, вы можете получить

040.00105.0020090518212100Z

который вы можете конвертировать в

|  4000            | short int, 16 bits |  
| 10500            | short int, 16 bits |  
| 20090518212100Z  | 64 bits            |

Так что это 96 бит, 12 байтов против 26 байтов.

Answer 2

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

Как правило, данные, о которых вы говорите, будут просто храниться в виде двоичных чисел (не текстовых), и это, как правило, эффективно при использовании пространства и извлечения.

Я рекомендую вам взглянуть на Книга сжатия данных

Answer 3

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

Сжатие данных плохо работает на «случайных» данных. Если ваши данные находятся в меньшем диапазоне, вы вполне можете использовать это.

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

В качестве примера можно сказать, что ваши данные - это не только латы и лонги, но предполагается, что они «близки» друг к другу. Тогда вы, вероятно, могли бы хранить «происхождение» Lat и Long, а остальные могут быть дифференциальными. Возможно, эти различия достаточно малы, чтобы соответствовать одному подписанному байту.

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

Answer 4

Это зависит от того, что вы собираетесь делать с данными, и насколько вам нужна точность.

Широта / долгота традиционно задается в градусах, минутах и ​​секундах, с 60 секундами в минуту, 60 минутами в градусах и 1 градусом широты, номинально равными 60 морским милям (nmi). 1 минута - 1 нми, а 1 секунда - чуть более 100 футов.

Широта идет от -90 до +90 градусов. Представление широты в виде целых секунд дает диапазон -324000 .. + 324000, или около 20 бит. Долгота изменяется от -180 до +180, поэтому для представления долготы таким же образом требуется еще 1 бит.

Таким образом, вы можете представить полную широту / длинную позицию до +/- 50 футов в 41 бите.

Очевидно, что если вам не нужна такая большая точность, вы можете уменьшить количество бит.

Обратите внимание, что традиционный 32-битный плавающий с одинарной точностью использует около 24 бит мантиссы, так что вы упадете до +/- 6 футов, если вы просто конвертируете свой широту / долготу в секундах, чтобы плавать. Для такого рода вещей трудно победить два поплавка одинарной точности.