Геохеш

Эта статья о системе кодирования географических координат. Информацию об игре см. в разделе Геохеширование .

Ячейка 6g и ее подсетка.

Geohash — это общедоступная система геокодирования, изобретенная в 2008 году Густаво Нимейером. который кодирует географическое местоположение в короткую строку букв и цифр. Подобные идеи были выдвинуты Дж. М. Мортоном в 1966 году. Это иерархическая пространственная структура данных, которая подразделяет пространство на сегменты в форме сетки , что является одним из многих применений так называемой кривой Z-порядка и, как правило, кривых, заполняющих пространство .

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

История

Основная часть алгоритма Geohash и первая инициатива по созданию аналогичного решения были задокументированы в отчете Г. М. Мортона в 1966 году «Компьютерно-ориентированная база геодезических данных и новый метод упорядочения файлов». Работа Мортона использовалась для эффективных реализаций кривой Z-порядка , как в этой современной (2014 г.) версии Geohash-integer (основанной на прямом чередовании 64-битных целых чисел ), но его геокодирования предложение не было удобочитаемым для человека и не пользовалось популярностью.

Судя по всему, в конце 2000-х годов Г. Нимейер еще не знал о работе Мортона и изобрел ее заново, добавив использование представления base32 . В феврале 2008 года, одновременно с анонсом системы, он запустил сайт http://geohash.org, который позволяет пользователям преобразовывать географические координаты в короткие URL-адреса , которые однозначно идентифицируют местоположение на Земле , чтобы сделать ссылку на них в электронной почте , на форумах и веб-сайтах более удобной.

Было разработано множество вариантов, включая OpenStreetMap . короткую ссылку (с использованием base64 вместо base32) в 2009 году 64-битный Geohash в 2014 году экзотический Гильберт-Геохаш в 2016 году и другие.

Типичные и основные варианты использования

Чтобы получить Geohash, пользователь предоставляет адрес для геокодирования или координаты широты и долготы в одном поле ввода (принимаются наиболее часто используемые форматы для пар широты и долготы) и выполняет запрос.

Помимо отображения широты и долготы, соответствующих данному Geohash, пользователям, которые переходят к Geohash на сайте geohash.org, также предоставляется встроенная карта, и они могут загрузить файл GPX или передать путевую точку непосредственно на определенные GPS- приемники. Также предоставляются ссылки на внешние сайты, которые могут предоставить дополнительную информацию по указанным вопросам.расположение.

Например, пара координат 57.64911,10.40744 (около оконечности полуострова Ютландия , Дания ) производит немного более короткий хэш u4pruydqqvj.

Основные области применения геохэшей:

• В качестве уникального идентификатора.
• Для представления точечных данных, например, в базах данных.

Также было предложено использовать геохеши для геотегирования .

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

Техническое описание

Формальное описание вычислительных и математических представлений.

Текстовое представление

Для точных переводов широты и долготы Geohash представляет собой пространственный индекс с основанием 4 , поскольку он преобразует непрерывные координаты пространства широты и долготы в иерархическую дискретную сетку, используя повторяющиеся четыре раздела пространства. Чтобы быть компактным кодом, он использует базу 32 и представляет свои значения в следующем алфавите, который является «стандартным текстовым представлением».

Десятичный	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
База 32	0	1	2	3	4	5	6	7	8	9	б	с	д	и	ж	г
Десятичный	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
База 32	час	дж	к	м	н	п	д	р	с	т	в	v	В	х	и	С

«Алфавит Геохэша» (32ghs) использует все цифры 0–9 и все строчные буквы, кроме «a», «i», «l» и «o».

Например, используя приведенную выше таблицу и константу $B=32$, Геохэш ezs42 может быть преобразовано в десятичное представление с помощью обычной позиционной записи :

[ ezs42] _32 гс = $[(e\times B^{4})+(z\times B^{3})+(s\times B^{2})+(4\times B^{1})+(2\times B^{0})]_{32ghs}$

= $[e]_{32ghs}\times B^{4}+[z]_{32ghs}\times B^{3}+[s]_{32ghs}\times B^{2}+[4]_{32ghs}\times B^{1}+[2]_{32ghs}\times B^{0}$

= $[13]_{10}\times B^{4}+[31]_{10}\times B^{3}+[24]_{10}\times B^{2}+[4]_{10}\times B^{1}+[2]_{10}\times B^{0}$

= $13\times 1048576+31\times 32768+24\times 1024+4\times 32+2\times 1$ = $13631488+1015808+24576+128+2=14672002$

Геометрическое представление

Геометрия Geohash имеет смешанное пространственное представление:

• Геохэши с 2, 4, 6, ... e цифрами ( четными цифрами) представлены кривой Z-порядка в «регулярной сетке», где декодированная пара (широта, долгота) имеет равномерную неопределенность, действительную как Geo URI .
• Геохеши с 1, 3, 5, ... d цифрами (нечетными цифрами) представлены «кривой И-порядка». Широта и долгота декодированной пары имеют разную неопределенность (долгота усекается).

Кривая сетки из 32 ячеек была получена путем объединения 2 на 2 ячеек «следующего уровня» (сетка из 64 ячеек показана здесь) для получения геометрического представления «геохеша с нечетными цифрами».

Построить «кривую И-порядка» можно из кривой Z-порядка, объединив соседние ячейки и проиндексировав полученную прямоугольную сетку функцией $j=\left\lfloor {\frac {i}{2}}\right\rfloor$. На иллюстрации показано, как получить сетку из 32 прямоугольных ячеек из сетки из 64 квадратных ячеек.

Самым важным свойством Geohash для человека является то, что он сохраняет пространственную иерархию в префиксах кода .
Например, на иллюстрации «Сетка из 1 цифры Geohash» из 32 прямоугольников выше пространственная область кода e (прямоугольник серовато-синего круга в позиции 4,3) сохраняется с префиксом e в «двухзначной сетке» из 1024 прямоугольников (масштаб показывает em и серовато-зеленые или синие круги на сетке).

Алгоритм и пример

Использование хеша ezs42 в качестве примера, вот как оно расшифровывается в десятичные широту и долготу. Первым шагом является декодирование его из текстовой « базы 32ghs », как показано выше, для получения двоичного представления:

$[e]_{32ghs}=[13]_{10}=[01101]_{2}$

$[z]_{32ghs}=[31]_{10}=[11111]_{2}$

$[s]_{32ghs}=[24]_{10}=[11000]_{2}$

$[4]_{32ghs}=[4]_{10}=[00100]_{2}$

$[2]_{32ghs}=[2]_{10}=[00010]_{2}$.

В результате этой операции биты 01101 11111 11000 00100 00010. Начиная отсчет слева с цифры 0 на первой позиции, цифры на четных позициях образуют код долготы ( 0111110000000), а цифры на нечетных позициях образуют код широты ( 101111001001).

Каждый двоичный код затем используется в серии делений, рассматривая по одному биту, снова слева направо. Для значения широты интервал от -90 до +90 делится на 2, образуя два интервала: от -90 до 0 и от 0 до +90. Поскольку первый бит равен 1, выбирается более высокий интервал, который становится текущим интервалом. Процедура повторяется для всех битов кода. Наконец, значение широты является центром полученного интервала. Долготы обрабатываются аналогичным образом, учитывая, что начальный интервал составляет от -180 до +180.

Например, в коде широты 101111001001, первый бит равен 1, поэтому мы знаем, что наша широта находится где-то между 0 и 90. Без дополнительных битов мы бы предположили, что широта равна 45, что дает нам ошибку ±45. Поскольку доступно больше битов, мы можем продолжить со следующего бита, и каждый последующий бит уменьшает эту ошибку вдвое. В этой таблице показано влияние каждого бита. На каждом этапе соответствующая половина диапазона выделяется зеленым цветом; младший бит выбирает нижний диапазон, высокий бит выбирает верхний диапазон.

В столбце «Среднее значение» указана широта, просто среднее значение диапазона. Каждый последующий бит делает это значение более точным.

Код широты 101111001001
позиция бита	битовое значение	мин	середина	Макс	среднее значение	максимальная ошибка
0	1	-90.000	0.000	90.000	45.000	45.000
1	0	0.000	45.000	90.000	22.500	22.500
2	1	0.000	22.500	45.000	33.750	11.250
3	1	22.500	33.750	45.000	39.375	5.625
4	1	33.750	39.375	45.000	42.188	2.813
5	1	39.375	42.188	45.000	43.594	1.406
6	0	42.188	43.594	45.000	42.891	0.703
7	0	42.188	42.891	43.594	42.539	0.352
8	1	42.188	42.539	42.891	42.715	0.176
9	0	42.539	42.715	42.891	42.627	0.088
10	0	42.539	42.627	42.715	42.583	0.044
11	1	42.539	42.583	42.627	42.605	0.022

Код долготы 0111110000000
позиция бита	битовое значение	мин	середина	Макс	среднее значение	максимальная ошибка
0	0	-180.000	0.000	180.000	-90.000	90.000
1	1	-180.000	-90.000	0.000	-45.000	45.000
2	1	-90.000	-45.000	0.000	-22.500	22.500
3	1	-45.000	-22.500	0.000	-11.250	11.250
4	1	-22.500	-11.250	0.000	-5.625	5.625
5	1	-11.250	-5.625	0.000	-2.813	2.813
6	0	-5.625	-2.813	0.000	-4.219	1.406
7	0	-5.625	-4.219	-2.813	-4.922	0.703
8	0	-5.625	-4.922	-4.219	-5.273	0.352
9	0	-5.625	-5.273	-4.922	-5.449	0.176
10	0	-5.625	-5.449	-5.273	-5.537	0.088
11	0	-5.625	-5.537	-5.449	-5.581	0.044
12	0	-5.625	-5.581	-5.537	-5.603	0.022

(Числа в таблице выше для ясности округлены до 3 знаков после запятой)

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

$\min \leq \mathrm {round} (value)\leq \max$

Таким образом, хотя округление 42,605 до 42,61 или 42,6 является правильным, округление до 43 — нет.

Цифры и точность в км

длина геохеша	широтные биты	СПГ биты	лат ошибка	ошибка сжиженного газа	ошибка км
1	2	3	±23	±23	±2500 км (1600 миль)
2	5	5	±2.8	±5.6	±630 км (390 миль)
3	7	8	±0.70	±0.70	±78 км (48 миль)
4	10	10	±0.087	±0.18	±20 км (12 миль)
5	12	13	±0.022	±0.022	±2,4 км (1,5 мили; 2400 м)
6	15	15	±0.0027	±0.0055	±0,61 км (0,38 миль; 610 м)
7	17	18	±0.00068	±0.00068	±0,076 км (0,047 миль; 76 м)
8	20	20	±0.000085	±0.00017	±0,019 км (0,012 миль; 19 м)

Ограничения при использовании для определения близости

Краевые случаи

Геохеши можно использовать для поиска точек, находящихся рядом друг с другом, на основе общего префикса. Однако местоположения в крайнем случае , расположенные близко друг к другу, но на противоположных сторонах меридиана 180 градусов, приведут к появлению кодов Geohash без общего префикса (разные долготы для близких физических местоположений). Точки, расположенные вблизи Северного и Южного полюсов, будут иметь очень разные геохеши (разные долготы для близких физических местоположений).

Два близких места по обе стороны экватора (или Гринвичского меридиана) не будут иметь длинного общего префикса, поскольку принадлежат разным «половинам» мира. Проще говоря, двоичная широта (или долгота) одного местоположения будет 011111..., а другого - 100000...., поэтому у них не будет общего префикса, и большинство битов будут перевернуты. Это также можно рассматривать как следствие использования кривой Z-порядка (которую в данном случае правильнее было бы назвать посещением N-порядка) для упорядочивания точек, поскольку две близлежащие точки могут быть посещены в очень разное время. Однако две точки с длинным общим префиксом окажутся рядом.

Чтобы выполнить поиск близости, можно вычислить юго-западный угол (низкий геохэш с низкой широтой и долготой) и северо-восточный угол (высокий геохеш с высокой широтой и долготой) ограничивающего прямоугольника и найти геохеши между этими двумя. Этот поиск найдет все точки кривой z-порядка между двумя углами, которых может быть слишком много. Этот метод также не работает на 180 меридианах и полюсах. Solr использует список фильтров префиксов, вычисляя префиксы ближайших квадратов, близких к геохешу [1] .

Нелинейность

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

Пример нелинейности для системы широта-долгота:

• На экваторе (0 градусов) длина градуса долготы составляет 111,320 км, а градуса широты — 110,574 км, ошибка 0,67%.
• На 30 градусах (средние широты) ошибка составляет 110,852/96,486 = 14,89%.
• При 60 градусах (Высокая Арктика) ошибка составляет 111,412/55,800 = 99,67%, достигая бесконечности на полюсах.

Обратите внимание, что эти ограничения связаны не с геохешированием и не с координатами широты и долготы, а с трудностью сопоставления координат на сфере (нелинейного и с переносом значений, аналогично арифметике по модулю) в двумерные координаты и сложность равномерного исследования двумерного пространства. Первый связан с географической системой координат и картографической проекцией , а другой — с кривой Гильберта и кривой z-порядка . Как только будет найдена система координат, которая представляет точки линейно по расстоянию и охватывает края и может быть исследована равномерно, применение геохеширования к этим координатам не будет страдать от вышеперечисленных ограничений.

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

Несмотря на эти проблемы, существуют возможные обходные пути, и алгоритм успешно используется в Elasticsearch. МонгоДБ, HBase, Редис, и накопление для реализации поиска по близости.

Похожие системы индексации

Основная статья: Геокоды

Можно использовать одни и те же коды Base32-Geohash в разных кривых индексации. Для четырехугольного замощения кривая Гильберта является лучшей альтернативой кривой Мортона , используемой, например, в S2-геометрии.
Коды с четным числом цифр (2, 4, ...) отображаются в регулярные сетки, а коды с нечетным числом (1, 3, ...) должны отображаться в нерегулярную промежуточную сетку с ячейками, индексированными вырожденными кривыми. .

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

В некоторых географических информационных системах и данных больших данных пространственных базах индексация на основе кривой Гильберта может использоваться в качестве альтернативы кривой Z-порядка , как в библиотеке S2 Geometry .

В 2019 году интерфейс разработала компания QA Locate. в том, что они назвали GeohashPhrase использовать фразы для кодирования геохэшей для облегчения общения на разговорном английском языке. Были планы сделать GeohashPhrase открытым исходным кодом.

• C-квадраты (2002)
• GeoKey (2018, собственная разработка)
• Почта Ганы GPS (2017)
• Локаторная система Мейденхеда (1980)
• Код Макани (2011)
• Код карты (2008)
• Справочная система военной сети
• Код природной территории
• Открытый код местоположения (2014 г., он же «плюс-коды», Google Maps )
• QRA-локатор (1959 г.)
• Универсальная поперечная система координат Меркатора
• What3words (2013, собственность)
• WhatFreeWords
• Международная система почтовых индексов с использованием кубических метров (CubicPostcode.com)
• GEOREF (аналогичный двухзначный иерархический код)
• Xадрес
• 3Geonames (2018, с открытым исходным кодом)

Лицензирование

Алгоритм Geohash был выложен в общественное достояние его изобретателем в публичном объявлении 26 февраля 2008 года.

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

Формальный стандарт

Geohash стандартизирован как CTA-5009. Этот стандарт соответствует статье Википедии версии 2023 года, но содержит дополнительную информацию в формальной (нормативной) ссылке. В отсутствие официальной спецификации с момента создания Geohash организация CTA WAVE опубликовала CTA-5009, чтобы способствовать более широкому внедрению и совместимости среди разработчиков в отрасли.

См. также

• Список систем геодезического геокодирования
• Geohash-36 (не является вариантом Geohash)
• Сетка (пространственный индекс)
• Локаторная система Мейденхеда
• Справочная система военной сети
• Число Мортона (теория чисел)
• Код природной территории
• Схема нумерации
• Открыть код местоположения (плюс код)
• кривые, заполняющие пространство
• какие3 слова
• Кривая Z-порядка

Внешние ссылки

• Официальный сайт
• Аппроксимации Geohash для геометрии JTS
• Игровая площадка Геохэш