Немного про GPS-трек
В нашем конкретном случае под треком подразумевалась последовательность точек, задаваемых координатами, в которых находился пользователь, с привязкой ко времени и, возможно, некоторыми флагами (например, SOS, начало трека).
Время можно было определять таким способом:
long time= System.currentTimeMillis();Координаты — это долгота и широта. В объекте Location в Android используется double для longitude и latitude.
Таким образом, каждая точка трека должна была содержать в себе 64 + 2 * 64 + 2 = 194 бита информации.
Немного про SMS
Кто пользовался (пользуется) SMS помнит, что кириллицей можно набирать 70 символов в одну SMS, а транслитом — целых 160! Вот где несправедливость, а вы говорите санкции.
О том, как же устроена SMS'ка можно почитать в RFC 5724:
GSM SMS messages are alphanumeric paging messages that can be sent to
and from SMS clients. SMS messages have a maximum length of 160
characters (7-bit characters from the GSM character set [SMS-CHAR]),
or 140 octets. Other character sets (such as UCS-2 16-bit
characters, resulting in 70-character messages) MAY also be supported
[SMS-CHAR], but are defined as being optional by the SMS
specification. Consequently, applications handling SMS messages as
part of a chain of character-processing applications MUST make sure
that character sets are correctly mapped to and from the character
set used for SMS messages.
Таким образом, в качестве полезной нагрузки можно использовать 140 байт, которые превращаются в те самые 160 символов для 7-битной кодировки (латиница, цифры и ещё некоторое количество символов).
Допускается отправлять значительно большее количество текста, но тогда исходное сообщение будет разбито на части. Каждая часть будет меньше на 6 байт, так как информация о сегментах сохраняется в специальном заголовке UDH в начале каждого кусочка. В 7-битных символах остаётся 153.
В теории поддерживается разбиение до 255 сегментов, на практике же видел гарантированную поддержку только 6 сегментов.
Бинарный формат: Заголовок
Для помещения бинарных данных трека в SMS должно было быть использовано простое и совместимое с 7-битной кодировкой Base64 преобразование, которое на выходе на каждые три байта исходных данных выдаёт четыре 7-битных символа. Итого, полезных данных остаётся уже не так много — всего-то 160 * 3 / 4 = 120 байт.
Приложению пророчилось большое будущее, поэтому разрабатываемый формат не должен был ограничиваться как одним типом сообщения, так и одной версией протокола, поэтому под messageType был отведён тип short.
Поскольку данные должны были поступать по SMS, где нет привычных для классического web-а сертификатов, паролей и аутентификаций, нужно было научиться привязывать получаемое сообщение к пользователю системы: был введён authenticationToken типа long, генерируемый случайным образом.
Для контроля целостности было добавлено поле с контрольной суммой checksum типа short.
Общий размер заголовка стал равен 2 + 8 + 2 = 12 байтам.
Исключим из общего объёма полезных данных размер заголовка: 120 — 12 = 108 байт или
864 бита.
Наивная реализация
Одна точка трека занимает 194 бита. В одну SMS'ку входит 864 бита данных трека. Кхм, влезет лишь 864 / 194 = 4 точки.
А что если разбить сообщение на 6 сегментов? 1 сегмент = 153 7-битных символа; 6 сегментов = 153 * 6 = 818 7-битных символа. Полезных данных окажется 818 * 3 / 4 = 613 байт. Таким образом, под данные трека останется 613 — 12 = 601 байт или 4808 бита. Итого, в жирную SMS'ку можно будет засунуть 4808 / 194 = 24 точки и ещё 19 байт останется.
Кроме очевидного минуса — в сообщение можно поместить очень мало точек, вылезает неудобная логика работы с точкой, занимающей не кратную байту длину.
Оптимизация
Время
- В действительности нам не нужна точность в миллисекунду
- Приложение не будет отсылать данные за прошедшие десятилетия
- Приложение вряд ли просуществует в неизменном виде 50 лет
Пусть мы оставим точность до 4 секунд.
Введём свою эру:
long ERA = 1388534400000L;Относительно стандартной юниксовой (1 января 1970 года UTC). Дата выше соответствует 1 января 2014 года UTC.
С учётом последнего допущения нам достаточно хранить 4 байта для времени:
(60 / 4) * 60 * 24 * 365.25 * 50 = 394 470 000 < 2^29. Ещё 3 бита в запасе (на флаги).
long time= System.currentTimeMillis();
long newTime = (time - ERA) / (1000 * 4);
География
Земля очень близка по форме шару, сплюснутому со стороны полюсов, таким образом длина экватора (40 075 696 метров) чуть больше, чем длина удвоенного меридиана (40 008 552 метров).
Координаты в Location задаются в градусах (± в зависимости З/В и С/Ю).
Всего же в окружности у нас 360 градусов, или 21 600 минут или 1 296 000 секунд. Таким образом, в одном метре экватора или меридиана не менее 0.032 секунды (1 296 000 / 40 075 696 = 0.0323388...). На широте, скажем, 60 градусов в одном метре параллели будет примерно в 2 раза больше секунд (около 0.064 секунды). Что это значит? Ошибка позиционирования в 1 метр на экваторе и на 60-ой параллели отличается в ошибке в градусах Location.getLongitude() в два раза. При этом, чем дальше от экватора, тем ошибка в градусах при фиксированной в метрах выше. И, наоборот: при удалении от экватора при фиксированной ошибке в градусах — в метрах ошибка уменьшается, то есть вблизи экватора округление до 32/1000 секунды даст наибольшую ошибку позиционирования не более одного метра.
Допустим, нас устраивает точность позиционирования в 5 метров (в действительности, точность значений, получаемого от GPS-модуля оказывается в разы хуже). Возьмём границу пониже: пусть по широте и долготе точность позиционирования не менее 3 метров (5 > 3 * sqrt(2)).
Теперь, мы можем отказаться от координат в double и привести их к неотрицательному целочисленному значению с точностью до 96/1000 секунды:
long newLatitude = (latitude + 90) * 60 * 60 * 1000 / 96;
long newLongitude = (longitude + 180) * 60 * 60 * 1000 / 96;
Очевидно, что новые значения не превысят 360 * 60 * 60 * 1000 / 96 = 13 500 000 < 2^24, что укладывается в 3 байта, да ещё и бит остался «про запас» от преобразования latitude, так как максимально возможное значение будет меньше в 2 раза и для хранения значения будет достаточно 23 бита.
Результат
Размер точки трека сократился до 4 + 3 + 3 = 10 байт и ещё несколько битов осталось не использованных. В обычную SMS стало входить 864 / 80 = 10 точек. В жирную из 6 сегментов: 4808 / 80 = 60 точек.
Ещё оптимизации
До этого мы никак не использовали то, что точки принадлежат одному треку, следовательно можно делать предположения о расстоянии между точками и временных промежутках.
Таким образом, абсолютные координаты и время фиксировались только для первой точки, а все последующие точки хранили в себе смещение относительно предыдущей и по координатам, и по времени. Такая оптимизация позволила сократить размер последующих точек ещё на 2 байта до 8 байт, увеличив, в итоге, общее количество точек в одной SMS'ке до 13, а в жирной — до 84.
Описание формата
HEADER (96) + BODY (variable):
|| Message Type (16) | Authentication Token (64) | Checksum (16) || Data (variable) ||
FIRST TRACKPOINT INFO (80):
|| Start (1) | SOS (1) | Reserved (1) | DateTime (29) | Reserved (1) | Latitude (23) | Longitude (24) ||
NTH TRACKPOINT INFO (64):
|| Offset (16) | Start (1) | SOS (1) | North (1) | Latitude (21) | Reserved (1) | Reserved (1) | East (1) | Longitude (21) ||
В скобках указаны длины полей в битах.
Пример
HEX-запись бинарного сообщения (30 байт), состоящего из заголовка (12 байт) и двух точек (10 и 8 байт, соответственно):
00 01 00 11 AA BB CC DD EE FF 00 90 80 00 24 09 54 04 9D 89 87 A0 09 B1 40 00 00 20 92 7C
Расшифровка:
short messageType = 1; // 00 01
long authenticationToken = 4972798176784127L; // 00 11 AA BB CC DD EE FF
short checksum = 144; // 00 90
boolean start = true; // [1]000 0000 00 24 09
boolean sos = false; // 1[0]000 0000 00 24 09
int dateTime = 9225; // 100[0 0000 00 24 09] // 1 января 2014 10:15:00 UTC
int latitude = 5506205; // 0[101 0100 04 9D] // 56.83213333° с. ш. (исходные данные: 56.832139° с. ш.)
int longitude = 9013152; // 89 87 A0 // 60.35072° в. д. (исходные данные: 60.350722° в. д.)
int offset = 2481 // 09 B1 // 1 января 2014 12:45:24 UTC
boolean start2 = false; // [0]100 0000 00 00
boolean sos2 = true; // 0[1]00 0000 00 00
boolean north2 = false; // 01[0]0 0000 00 00
int latitude2 = 0; // 010[0 0000 00 00] // 56.83213333° с. ш.
boolean east2 = true; // 00[1]0 0000 92 7C
int longitude2 = 37500; // 001[0 0000 92 7C] // 61.35072° в. д.P.S. Всех с наступающим! Надеюсь, пост окажется кому-нибудь полезным/интересным.
Комментарии (27)
Renatk
30.12.2016 13:44Да, я тоже ожидал увидеть СМС в статике. А раз прмера нет, то это не хорошая статья...
gnkoshelev
30.12.2016 14:03Если вас интересует использование SMS API в Android, то здесь я вам не подскажу. Если речь про base64 от бинарных данных, то я не очень понимаю, что вы хотите в итоге увидеть?
klim76
30.12.2016 13:51А зачем пользователю без интернета GPS-трек? или у вас приложение с загружаемыми картами?
gnkoshelev
30.12.2016 14:10Даже в отсутствии загружаемых карт можно писать трек. Ведь карты нужны только для показа пользователю на экране телефона.
В простом варианте можно использовать оффлайновый «сриншот» кусочка карты, где мы знаем, например, координаты левой верхней и правой нижней точки прямоугольника. Если, конечно, речь не про северный полюс.klim76
30.12.2016 14:32пардон, спутал направление передачи :)
Вы от пользователя без интернета получаете GPS-трек, я почему то подумал что наоборот ему передаёте.gnkoshelev
30.12.2016 15:14А это, между прочим, идея! Для всяких квестов и трофи-рейдов, например.
В предыдущем комментарии конечно же имелся ввиду «скриншот».
Markscheider
30.12.2016 13:52абсолютные координаты и время фиксировались только для первой точки, а все последующие точки хранили в себе смещение относительно предыдущей и по координатам, и по времени.
Скажите честно, сами до идеи дошли или подсмотрели в MPEG-сжатии? :)
gnkoshelev
30.12.2016 14:26Сам дошёл, причём вполне естественным образом: статья, конечно, больше поток сознания из воспоминаний трёхлетней давности, но логику постепенного создания формата привёл без искажений. Поскольку я увидел очевидные предположения (пункты 1-3) по сжатию метки времени — оставалось смасштабировать время с 50 лет до максимальной теоретической продолжительности одного трека (что заведомо было меньше недели, а в своём большинстве ограничивалось одним-двумя днями). С координатами было чуть сложнее — можно было только предполагать, как далеко может пользователь сместиться от первой точки, поэтому в первой версии протокола могли отказаться от этой оптимизации.
К сожалению, я не знаю, как устроено сжатие в MPEG. Возможно, что перед тем, как начинать оптимизировать, нужно было изучить матчасть.Markscheider
30.12.2016 14:28К сожалению, я не знаю, как устроено сжатие в MPEG
Почти как у вас. Берется ключевой кадр, а информация о следующих кадрах записывается разностная (т.е. изменения относительно ключевого). Если в общих словах — то вот и вся премудрость.old_bear
31.12.2016 10:32Первая мысль, которая мне пришла в голову по прочтении: «надо туда CABAC прикрутить».
gnkoshelev
31.12.2016 11:15Почитал про контекстно-адаптивное сжатие — а не слишком ли малый объём данных для применения таких методов?
old_bear
31.12.2016 11:32Извините, я не поставил смайлик хотя это была большей частью шутка (и меньшей частью моя профессиональная деформация).
Если серьёзно, то в случае, если передаётся разница между точками трека, вполне можно поэсплуатировать большую вероятность небольшой разницы и использовать универсальный код, что-то вроде экспоненциального кода Голомба.
Zverik
30.12.2016 14:408 байт — что-то многовато для инкрементального кодирования. Байта на время и трех-четырёх на координаты (зигзаг-кодированием) должно хватить.
gnkoshelev
30.12.2016 15:10Как в один байт сохранить сдвиг на 1 час для указанной точности? С координатами сложно, т.к. за те же 2 часа можно долететь из Екатеринбурга в Санкт-Петербург, поэтому нужно понимать область применимости.
Впрочем, пока писал статью — увидел ещё несколько возможных вариантов допущений и оптимизаций, но уж как было — так и рассказал.
am-amotion-city
30.12.2016 17:54кириллицей можно набирать 70 символов в одну SMS, а транслитом — целых 160!
Вот так в XXI веке и узнаешь, что в традиционных SMS использовалось ASCII–7...
Anatol_s
30.12.2016 22:24Будет интересно посмотреть на код по работе с побитовыми операциями.
gnkoshelev
30.12.2016 23:14Примеры декодирования данных:
public static final DateTime ERA_DATE = DateTime.parse("2014-01-01T00:00:000Z"); public static final int SEC_SCALE = 4; public static final int SEC_TO_MILLIS = 1000; public DateTime decodeDateTime(byte first, byte second, byte third, byte fouth) { long time = (first & 0x1FL)<<24 | (second & 0xFFL)<<16 | (third & 0xFFL)<<8 | (fouth & 0xFFL); return ERA_DATE.plus(time * SEC_SCALE * SEC_TO_MILLIS); } public DateTime decodeOffset(DateTime date, byte first, byte second) { long offset = (first & 0xFFL)<<8 | (second & 0xFFL); offset *= SEC_SCALE;//в секундах offset *= SEC_TO_MILLIS;//в миллисекундах return date.plus(offset); }
Тут можно отметить две вещи:
1. Нужно не забывать правильно очищать входные байты, которые «шарятся» между полями сообщения (пример с первым байтом при декодировании поля dateTime).
2. Используется Big Endian порядок байтов (замечание актуально только для платформ/языков, где используется другой порядок), так как от «расшаренных» байтов под флаги откусываются старшие биты старших байтов.
private_tm
31.12.2016 11:18Всегда люблю статьи где что то не очень сложное оптимизируют))
Немного покритикую(не воспринимайте сильно близко).
Возможно я что то неправильно или не до конца понял.
1. base64 кодирует и при этом выходная строка увеличивается в объёме.
2. Время можно брать по тому когда сообщения придет, а всё остальное по сдвигам от первой точки(как бы в обратном порядке)
3.160 символов для 7-битной кодировки т. е. по факту у вас 160*7=1120 бит(140 байт). Как я понял используются только цифры и то не все + точка + разделитель(можно и не использовать) а буквы и другии символы не использующийся т.е это позволяет использовать собственную кодировку для данного формата которая будет вмешать больше данных.gnkoshelev
31.12.2016 11:54Если перефразировать 1 и 3 — можно попробовать заморочиться за собственное кодирование на основе 7-битных символов. Полезная нагрузка для текущего решения — 120 байт, а максимально возможная — 140 байт, то есть возможен прирост до 16.5%. Оптимизация же самих данных давала от 30% на каждом шаге (переход от наивной реализации вообще в разы увеличил объём переданных полезных данных). Так что такое решение бы стало следующим шагом.
Закладываться на время получения сообщения нельзя, так как имеют место действия, временные интервалы между которыми могут быть неопределённой длины: момент формирования трека, момент упаковки в бинарный формат, момент создания сообщения, момент отправки с телефона, момент получения сообщения оператором и так далее.
Одини из поинтов статьи заключался в том, что в 2014 году (да и уже завтра — в 2017 году) в эпоху 4G, без пяти минут 5G, домашнего интернета до 300 МБит могут возникать ситуации, когда нельзя бездумно разбрасываться данными. Если бы я не вмешался в разработку алгоритма (Base64 был зафиксирован), то на полном серьёзе собирались использовать формат, который позволял бы передать только четыре точки в одинарной СМСке, когда весь трек состоит из десятков (в некоторых случаях — из сотен) точек. К сожалению, мы пережили то время, когда программирование было искусством.
rotorB
31.12.2016 18:20У гугла есть polylineutility — алгоритм позволяет хранить координаты в строковом виде с отличным сжатием, например 10 точек уложились в 45 байт.
gnkoshelev
05.01.2017 14:28В моём случае для кодирования 10 точек (без учёта меток времени и флагов) потребуется 443 бита против 360 бит (на 18.7% эффективнее); с другой стороны, если считать, что все точки в пределах одной улицы (как в вашем примере), то можно добиться и лучшего результата. В любом случае, стоит ознакомиться с алгоритмом, спасибо!
Для нас важным результатом было:
1. В трети случаев точки помещались в одну маленькую СМСку.
2. В подавляющем большинстве весь трек укладывался бы в одну жирную СМС (за редким исключением, когда трек мог состоять из ~ 100-200 точек).
3. Заголовок, тело и каждая точка трека занимали целое число байт.
4. Кодирование (не сжатие) давало предсказуемый результат по длине (цель не столько в упаковке как можно большего числа точек, сколько в упаковке заранее известного достаточного количества точек).
tirinox
Дайте, пожалуйста, пример готовой СМСки.
gnkoshelev
К сожалению, примера готовой СКСки нет, так как само мобильное приложение писал не я, а только предоставил библиотеку для упаковки трека в массив массивов байтов (так как трек мог быть больше 84 точек и нужно было делать несколько жирных СМСок).
Схема работы была следующей: Сырые данные -> Преобразование в массив байтов (бинарный формат из статьи) -> Base64 -> Использование SMS API в Android.
Для других платформ предоставил описание формата (заголовок, тело, первая точка трека, последующие точки трека, правила заполнения флагов).
gnkoshelev
Добавил сводную информацию по бинарному формату + пример сообщения.