Как бы вы наиболее эффективно хранили данные о широте и долготе?

Question

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

DD MM SS.S

ДД ММММ

DD.DDDDD

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

Мое решение основано на первом формате. Я использовал 3 байта для широты: 8 бит для DD (от -90 до 90), 6 бит для MM (0-59) и 10 бит для SS.S (0-59.9). Затем я использовал 25 бит для долготы: 9 бит для DDD (от -180 до 180), 6 бит для MM и 10 для SS.S. Это решение не очень хорошо вписывается в байтовую границу, но я полагал, что следующее чтение может быть сохранено сразу после предыдущего, и в 8 чтениях будет использоваться только 49 байтов.

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

Answer 1

Ваш предложенный метод не является оптимальным. Вы используете 10 бит (1024 возможных значения) для хранения значения в диапазоне (0..599). Это пустая трата пространства.

Если вы будете использовать 3 байта для широты, вы должны отобразить диапазон [0, 2 ^ 24-1] на диапазон [-90, 90]. Следовательно, каждое из 2 ^ 24 значений представляет 180/2 ^ 24 градуса, что составляет 0,086 секунды.

Если вам нужна точность только 0,1 секунды, вам потребуется 23 бита для широты и 24 бита для долготы (вы получите точность 0,077 секунды). Это всего 47 бит вместо ваших 49 бит с большей точностью.

Можем ли мы сделать еще лучше?

Точное число бит, необходимое для точности 0,1 секунды, равно log2 (180 * 60 * 60 * 10 * 360 * 60 * 60 * 10) <46,256. Это означает, что вы можете использовать 46256 бит (5782 байта) для хранения 1000 (широта, долгота) пар, но математика требует использования очень больших целых чисел. </p>

Можем ли мы сделать еще лучше?

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

Answer 2

Придерживаясь существующих технологий:

Если вы использовали половинную точность чисел с плавающей запятой для хранения только данных DD.DDDDD, вы можете быть намного более компактными, но вам придется принять смещение показателя из 15, что означает: сохраненные координаты могут быть не точными, но со смещением от исходного значения.

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

Следующий наиболее часто используемый механизм чисел с плавающей запятой использует 32 бита (тип «float» во многих языках программирования) - все еще эффективен, но больше, чем ваш пользовательский формат.

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

Answer 3

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