geohash

Geohash.net

Geohash.net-это легкая, высокопроизводительная библиотека C# для кодирования и декодирования строки и целочисленных геохаш.

Установка

Тодо

Использование

Вот быстрый пример того, как использовать библиотеку Geohash.net:

 using NetGeohash ;

// Encode latitude and longitude coordinates into a geohash string
string geohash = Geohash . Encode ( 37.421999 , - 122.084057 , 9 ) ;

// Decode the geohash string into latitude and longitude coordinates
( double latitude , double longitude ) = Geohash . Decode ( geohash ) ;

// Encode the geohash string into an integer format
ulong geohashInt = Geohash . EncodeToInt64 ( 37.421999 , - 122.084057 , 9 ) ;

// Decode the integer geohash into latitude and longitude coordinates
( latitude , longitude ) = Geohash . DecodeFromInt64 ( geohashInt ) ; 

Обзор

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

Концепция геохаширования состоит в том, чтобы взять координаты широты и долготы и преобразовать их в более компактную форму. Это достигается путем рекурсивного подразделения поверхности Земли в прямоугольные клетки, которым затем назначается уникальный идентификатор. Длина геохаша определяет уровень точности, с более длинными геохашами, представляющими меньшие участки.

Клетки геохаш обладают несколькими заметными свойствами:

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

Как это работает

Например, чтобы генерировать строку Geohash для местоположения с широтой 37,7749 и долготы -122,4194 на точке уровня 12, мы можем следовать этим трем этапам:

1. Квантование

Квантовать широту и долготу до 32-битных целых чисел путем отображения с интервалом единицы [0, 1] и умножения на 2^32 ( exp2(32) ):

Широта принимает диапазон [-90, 90], поэтому 32-разрядное целочисленное представление широты

 lat32 = floor ( exp2 ( 32 ) * ( latitude + 90 ) / 180 )

Что в нашем случае равна 3048827870 ( 0b10110101101110010110101111011110 )

Аналогично для долготы [-180, 180]:

 lng32 = floor ( exp2 ( 32 ) * ( longitude + 180 ) / 360 )

Что в нашем случае равна 686963316 ( 0b101000111100100011101001110100 )

2. Бит -интеррелирование

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

Диаграмма ниже иллюстрирует операцию.

Примечание: широта и долгота занимают равномерные и нечетные биты соответственно .

В нашем запущенном примере Integer Geohash: 5589511709871930228 ( 0b0100110110010001111011110100100100011110110011010111101101110100 )

Это число должно быть принято при более низкой точности. Точность целочисленного Geohash состоит из N High Bits, поэтому нам нужно усетать избыточные биты. Мы можем сделать это с помощью операции смены битов:

 hash = interleaved >> ( sizeof ( ulong ) * BITS_PER_BYTE - log2 ( 32 ) * precision ) // 64 - 5 * precision

Это 349344481866995639 ( 0b010011011001000111101111010010010001111011001101011110110111 ) для нашего примера.

ПРИМЕЧАНИЕ. Этот шаг в конечном итоге обеспечивает критическое свойство префикса Geohash: Geohash точки при более низкой точности является префиксом Geohash при более высокой точке. Следовательно, поиск в ближайшем случае может быть сведен к соответствующим префиксам Geohash (в качестве первого прохода).

3. BASE32 Кодирование

Строка Gehohash получается из целочисленного геохаша с помощью кодирования BASE32. Это стандарт, за исключением выбора алфавита. Каждый символ Geohash представляет собой 5-битное ( log2(32) ) двоичное значение, а вся строка Geohash состоит из нескольких 5-битных значений.

 0123456789bcdefghjkmnpqrstuvwxyz

Кодирование начинается с высоких битов, потребляя 5 бит целочисленного геохаша для каждого характера точности. В результате максимальная точность составляет 12 символов или 60 бит .

Разделите бинарное значение на группы по 5 бит и преобразуйте каждую группу в соответствующий его символ базы-32:

 01001 ( 9) - 9
10110 (22) - q
01000 ( 8) - 8
11110 (30) - y
11110 (30) - y
10010 (18) - k
01000 ( 8) - 8
11110 (30) - y
11001 (25) - t
10101 (21) - p
11101 (29) - x
10111 (23) - r

Объединить все символы Base-32 вместе, чтобы сформировать конечную строку Geohash: 9q8yyk8ytpxr

Для вариантов внутреннего использования целочисленного геохаша обычно достаточно . Базовый шаг 32 был включен здесь для полноты.

Тесты

Настраивать

 BenchmarkDotNet =v0.13.5, OS =Windows 11 (10.0.22000.1696/21H2/SunValley)
AMD Ryzen 9 3900X, 1 CPU, 24 logical and 12 physical cores
.NET SDK =8.0.100-preview.1.23115.2
  [Host]     : .NET 8.0.0 (8.0.23.11008), X64 RyuJIT AVX2
  Job-KKMPKU : .NET 8.0.0 (8.0.23.11008), X64 RyuJIT AVX2

Jit =RyuJit  Platform =X64  Runtime =.NET 8.0  

Декодировать

Метод	Вход	Иметь в виду	Ошибка	Stddev	Код размер	Gen0	Выделено
Netgeohash	k	8.112 нс	0,1881 нс	0,2090 нс	1717 б	-	-
Netcoregeohash	k	145.271 нс	0,8736 нс	0,7295 нс	18 б	0,0038	32 б
Ngeohashlib	k	143.414 нс	0,8529 нс	0,7561 нс	9 б	0,0229	192 б
Netgeohash	яд	8,442 нс	0,1032 нс	0,0965 нс	1717 б	-	-
Netcoregeohash	яд	166,305 нс	0,8682 нс	0,8121 нс	18 б	0,0038	32 б
Ngeohashlib	яд	169,663 нс	1,0957 нс	1,0249 нс	9 б	0,0229	192 б
Netgeohash	6n3	9.442 нс	0,1746 нс	0,1633 нс	1717 б	-	-
Netcoregeohash	6n3	192.502 нс	2.0566 нс	1,9238 нс	18 б	0,0038	32 б
Ngeohashlib	6n3	202.150 нс	1,9676 нс	1,8405 нс	9 б	0,0229	192 б
Netgeohash	zvgk	10.183 нс	0,1023 нс	0,0907 нс	1717 б	-	-
Netcoregeohash	zvgk	218.244 нс	1,4455 нс	1,3521 нс	18 б	0,0038	32 б
Ngeohashlib	zvgk	223,580 нс	0,7643 нс	0,6776 нс	9 б	0,0229	192 б
Netgeohash	T05KH	10.726 нс	0,2016 нс	0,1886 нс	1717 б	-	-
Netcoregeohash	T05KH	310.208 нс	0,9773 нс	0,8663 нс	18 б	0,0038	32 б
Ngeohashlib	T05KH	263.364 нс	2.2418 нс	2.0970 нс	9 б	0,0229	192 б
Netgeohash	B5CV2H	11.413 нс	0,0796 нс	0,0706 нс	1717 б	-	-
Netcoregeohash	B5CV2H	328,490 нс	2.4518 нс	2.1735 нс	18 б	0,0038	32 б
Ngeohashlib	B5CV2H	283,862 нс	2.9657 нс	2.7741 нс	9 б	0,0229	192 б
Netgeohash	VveyJ80	12.114 нс	0,1749 нс	0,1636 нс	1717 б	-	-
Netcoregeohash	VveyJ80	358.143 нс	0,9470 нс	0,7908 нс	18 б	0,0038	32 б
Ngeohashlib	VveyJ80	318,725 нс	1,7533 нс	1,6400 нс	9 б	0,0229	192 б
Netgeohash	f7y53xjt	12.676 нс	0,2287 нс	0,2140 нс	1717 б	-	-
Netcoregeohash	f7y53xjt	380.157 нс	2,2520 нс	2.1065 нс	18 б	0,0038	32 б
Ngeohashlib	f7y53xjt	334.277 нс	1,0733 нс	1,0039 нс	9 б	0,0229	192 б
Netgeohash	TRM92JKBV	12,990 нс	0,1217 нс	0,1139 нс	1717 б	-	-
Netcoregeohash	TRM92JKBV	404.136 нс	1,9322 нс	1,7128 нс	18 б	0,0038	32 б
Ngeohashlib	TRM92JKBV	374,209 нс	1,0807 нс	1,0109 нс	9 б	0,0229	192 б
Netgeohash	DRMQ3GX6ZT	13.861 нс	0,1824 нс	0,1706 нс	1717 б	-	-
Netcoregeohash	DRMQ3GX6ZT	429,735 нс	1,6946 нс	1,4151 нс	18 б	0,0038	32 б
Ngeohashlib	DRMQ3GX6ZT	400.585 нс	1,9080 нс	1,7847 нс	9 б	0,0229	192 б
Netgeohash	9zefgnuj7dw	14.265 нс	0,2997 нс	0,2803 нс	1717 б	-	-
Netcoregeohash	9zefgnuj7dw	455,781 нс	3.3098 нс	2.9341 нс	18 б	0,0038	32 б
Ngeohashlib	9zefgnuj7dw	416.747 нс	2.7821 нс	2.6023 нс	9 б	0,0229	192 б
Netgeohash	K9M2H7T1N0C2	14.864 нс	0,3210 нс	0,3153 нс	1717 б	-	-
Netcoregeohash	K9M2H7T1N0C2	479,624 нс	1,5628 нс	1,3854 нс	18 б	0,0038	32 б
Ngeohashlib	K9M2H7T1N0C2	467.252 нс	1,3795 нс	1,2904 нс	9 б	0,0229	192 б

Кодировать

Метод	широта	долготу	точность	Иметь в виду	Ошибка	Stddev	Код размер	Gen0	Выделено
Netgeohash	-89.127865	-179.438962	7	20,69 нс	0,146 нс	0,129 нс	906 б	0,0048	40 б
Netcoregeohash	-89.127865	-179.438962	7	195.04 нс	0,632 нс	0,528 нс	14 б	0,0172	144 б
Ngeohashlib	-89.127865	-179.438962	7	324,45 нс	3.044 нс	2.848 нс	19 б	0,0458	384 б
Netgeohash	-41.2858	174.7868	12	24,77 нс	0,352 нс	0,329 нс	906 б	0,0057	48 б
Netcoregeohash	-41.2858	174.7868	12	318,08 нс	2.079 нс	1,944 нс	14 б	0,0181	152 б
Ngeohashlib	-41.2858	174.7868	12	493,78 нс	2.879 нс	2,552 нс	19 б	0,0687	576 б
Netgeohash	-12.347856	34.890273	3	17,95 нс	0,215 нс	0,201 нс	906 б	0,0038	32 б
Netcoregeohash	-12.347856	34.890273	3	104,91 нс	0,616 нс	0,546 нс	14 б	0,0162	136 б
Ngeohashlib	-12.347856	34.890273	3	167,74 нс	2,523 нс	2,360 нс	19 б	0,0277	232 б
Netgeohash	45.678912	92.45236	4	18,39 нс	0,313 нс	0,293 нс	906 б	0,0038	32 б
Netcoregeohash	45.678912	92.45236	4	127,05 нс	1,053 нс	0,985 нс	14 б	0,0162	136 б
Ngeohashlib	45.678912	92.45236	4	209,17 нс	1,549 нс	1,449 нс	19 б	0,0305	256 б
Netgeohash	52,5174	13.409	12	24,64 нс	0,299 нс	0,280 нс	906 б	0,0057	48 б
Netcoregeohash	52,5174	13.409	12	310,05 нс	1,637 нс	1,451 нс	14 б	0,0181	152 б
Ngeohashlib	52,5174	13.409	12	498,72 нс	5,374 нс	5,027 нс	19 б	0,0687	576 б
Netgeohash	80.294617	19.543821	5	18,82 нс	0,228 нс	0,191 нс	906 б	0,0038	32 б
Netcoregeohash	80.294617	19.543821	5	152,24 нс	0,561 нс	0,498 нс	14 б	0,0162	136 б
Ngeohashlib	80.294617	19.543821	5	242,98 нс	2.265 нс	2.008 нс	19 б	0,0391	328 б

Вклад

Я призываю вклад в Geohash.net! Если вы сталкиваетесь с ошибкой или имеете предложение для новой функции, не стесняйтесь открыть проблему или отправлять запрос на привлечение на GitHub. Я постоянно ищу способы улучшить библиотеку и обеспечить большую ценность сообществу.

Кредиты

Geohash.net основан на исследованиях и выводах Майкла Маклафлина. Его работы по геохашированию и реализацию высокопроизводительного алгоритма геохаширования в GO можно найти в этой статье Geohash в собрании Голанга.