Совет дня №33

Разберем еще один случай, когда нужен срез строк – геохэш (geohash). Это быстрый и дешевый способ кодировать положение объектов, а также искать их.

Представим себе карту мира. Точки отсчета – Лондон и экватор. Это квадрат. Разделим его пополам по вертикали. Если человек живет западней Лондона, запишем 0, если восточнее – то 1. Теперь разделим область по горизонтали. Если человек находится северней, добавим 0, если южнее – 1. Продолжаем дробить область по горизонтали и вертикали и накапливать нули и единицы. В результате мы достигнем квадрата, достаточного малого, чтобы остановиться. Скажем, если речь о здании, квадрат может быть 25x25 метров. Если стадион, деревня или город, то еще больше.

Нули и единицы образуют цепочку бит. Переводим их в байты и кодируем base53 или похожим алгоритмом. Получаем строку вида hsGHrgga3ysg6, которая указывает на квадрат определенной точности.

Прелесть вот в чем: есть взять какой-то квадрат, то хэши всех точек в нем имеют общую часть. Например, есть квадрат hsGHrgga. В нем будут точки hsGHrgga3ysg6, hsGHrgga3ysgS, hsGHrgga6sg и так далее. Это значит, для их поиска нужно выбрать строки, которые начинаются с hsGHrgga. С индексом btree, что мы рассмотрели в прошлом совете, это крайне эффективно.

Похоже устроен поиск ближних объектов. Скажем, точка hsGHrgga3ysg6 указывает на кинотеатр и нужно показать ближайшие. Отломаем у хэша последний символ и таким образом поднимемся на квадрат выше: hsGHrgga3ysg. Найдем по нему все кинотеатры и покажем. Что-то лишнее можно почистить в приложении, так дешевле. Вопрос лишь в том, насколько “отъезжать” при поиске: на один символ, два и так далее.

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

Геохэш работает не только для плоскости, но и кубов. Пространство – это куб, который делится на 8 под-кубов, те – еще на 8 и так далее. Чтобы продвинуться на шаг, нужны три бита – по числу измерений. Такая структура называется октодеревом. По аналогии можно работать с многомерным пространством.

И не только многомерным – одномерным! Представим, на отрезке множество точек. Делим отрезок пополам: слева – 0, справа – 1. Переходим на нужный под-отрезок, делим пополам и так далее, пока не достигнем нужной точности. Накопленные нули и единицы кодируем в строку. Потом, чтобы получить точки в нужном отрезке, делаем срез по префиксу.

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