Geohash

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

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

История [ править ]

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

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

Многие варианты были разработаны, в том числе OpenStreetMap «с короткой ссылкой ^[3] ( с помощью base64 вместо base32) в 2009 году, 64-битный Geohash ^[4] в 2014 году, экзотический Гильберт-Geohash ^{[5] [6]} в 2016 году, и другие.

Типичное и основное использование [ править ]

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

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

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

Основное использование геохешей:

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

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

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

Техническое описание [ править ]

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

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

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

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

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

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

знак равно ${\displaystyle [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}}$

знак равно ${\displaystyle [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}}$

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

Геометрическое изображение [ править ]

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

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

Можно построить «кривую И-порядка» из Z-порядка путем объединения соседних ячеек и индексации полученной прямоугольной сетки функцией j = floor ( i ÷ 2). На боковой иллюстрации показано, как получить сетку из 32 прямоугольных ячеек из сетки из 64 квадратных ячеек.

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

Алгоритм и пример [ править ]

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

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

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

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

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

${\displaystyle [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. Поскольку доступно больше битов, мы можем продолжить со следующим битом, и каждый последующий бит уменьшает эту ошибку вдвое. В этой таблице показано влияние каждого бита. На каждом этапе соответствующая половина диапазона выделяется зеленым цветом; младший бит выбирает нижний диапазон, старший бит выбирает верхний диапазон.

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

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

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

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

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

Цифры и точность в км [ править ]

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

Крайние случаи [ править ]

Геохеши можно использовать для поиска близких друг к другу точек на основе общего префикса. Однако местоположения крайних вариантов близко друг к другу, но на противоположных сторонах меридиана 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%, достигая бесконечности на полюсах.

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

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

Несмотря на эти проблемы, существуют возможные обходные пути, и алгоритм успешно использовался в Elasticsearch, ^[7] MongoDB, ^[8] HBase, Redis, ^[9] и Accumulo ^[10] для реализации поиска по близости.

Подобные системы индексации [ править ]

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

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

В 2019 году QA Locate ^{[14] разработал} интерфейс в том, что они назвали GeohashPhrase ^[15], чтобы использовать фразы для кодирования геохешей для облегчения общения через разговорный английский язык. Были планы сделать GeohashPhrase открытым. ^[16]

Лицензирование [ править ]

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

Хотя сопоставимые алгоритмы были успешно запатентованы ^[18] и заявлены авторские права, ^{[19] [20]} GeoHash основан на совершенно другом алгоритме и подходе.

См. Также [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]

• Официальный веб-сайт
• elasticsearch: полное руководство - Geo
• Аппроксимации Geohash для геометрий JTS
• Игровая площадка Geohash