Analisando algoritmos: Geohash
Olá!
Este texto faz parte de uma série em que abordarei alguns algoritmos utilizados em diversos tipos de problemas diferentes.
Problema
Imagine que você precisa desenvolver um sistema que lide com coordenadas geográficas. Isso pode ser usado para aplicativos de entrega, mapas, mecanismos de cálculo de last mile, aplicativos de transporte ou algo similar. O que você faria para processar esse tipo de dado de forma eficiente?
Possível solução
Você pode resolver esse problema através do uso de latitude e longitude (latlon). Vou conceituar brevemente o que são para facilitar o entendimento.
A latitudeé a distância angular medida em graus, norte ou sul do equador, que é uma linha imaginária que circunda a Terra horizontalmente. Ela varia de 0° no equador até 90°N (norte) e 90°S (sul) nos polos. Os pontos localizados no hemisfério norte têm latitude positiva, enquanto os pontos no hemisfério sul têm latitude negativa.
A longitude é a distância angular medida em graus, leste ou oeste do Meridiano de Greenwich, que é uma linha imaginária que vai do Polo Norte ao Polo Sul, passando pelo Observatório Real de Greenwich, em Londres. Ela varia de 0° a 180° a leste e de 0° a 180° a oeste do Meridiano de Greenwich. Portanto, o total é de 360 graus. Pontos a leste do Meridiano de Greenwich têm longitude positiva, enquanto os pontos a oeste têm longitude negativa.
Essas coordenadas são frequentemente expressas no formato de graus, minutos e segundos para maior precisão. Ao combinar latitude e longitude, é possível determinar a posição exata de qualquer ponto na Terra.
A Praça da Sé em São Paulo, por exemplo, tem os seguintes valores:
Latitude: -23° 33' 0.59" S
Longitude: -46° 38' 1.19" W
É possível criar sistemas que armazenem localizações somente com essa estrutura, o que geraria tabelas parecidas com esta, por exemplo:
| Local | Latitude | Longitude |
|--------------|------------|------------|
| City A | -23.5505 | -46.6333 |
| Beach B | -20.2758 | -40.2989 |
| Park C | -22.9068 | -43.1729 |
| Mountain D | -25.4284 | -49.2733 |
| Lake E | -15.7801 | -47.9292 |
| Plaza F | -12.9714 | -38.5014 |
| Forest G | -30.0330 | -51.2300 |
| River H | -3.7172 | -38.5433 |
| Island I | 1.3521 | 103.8198 |
| Village J | 40.7128 | -74.0060 |
|--------------|------------|------------|Agora, imagine que você tenha que calcular distâncias entre os pontos com uma precisão de poucos centímetros. Apesar de ser possível atingir isso adicionando mais casas decimais ao LatLon, há uma limitação nessa representação que é importante notar: o comprimento de grau de latitude não é constante na superfície da Terra, sendo maior nos polos e menor no equador. A longitude também varia em comprimento com a latitude, mas essa variação é menor.
Portanto, para cálculos de distância, a curvatura da terra precisa ser levada em consideração para se obter resultados precisos. Felizmente, já existe um método consolidado para fazer isso, chamado Fórmula de Harvesine. Uma explicação detalhada do motivo da fórmula funcionar está fora da minha área de expertise.
Para aplicações pequenas, na grandeza de centenas e até alguns milhões, essas técnicas funcionam. No entanto, o que acontece quando precisamos processar grandes volumes de dados?
Geohashing
Em alto volume, cada bit importa. Portanto, armazenar coordenadas no formato LatLon tem alguns problemas: a necessidade de armazenar os campos em duas colunas, além de consumir mais bits do que o necessário.
Para buscas extremamente eficientes em alto volume, o que você acha que seria mais eficiente: Fazer buscas numéricas envolvendo as duas colunas ou fazer buscas por prefixos textuais, usando uma única coluna?
A técnica que otimiza a representação de coordenadas chama-se Geohash. A ideia básica envolve converter LatLon em um hash único, trocando processamento adicional para converter os formatos por um armazenamento menor, mantendo a precisão no processo.
A comparação entre tamanho e precisão está na tabela abaixo:
É possível chegar até 12 digitos no total, que torna a precisão na grandeza de centímetros. O que é o suficiente para a grande maioria das aplicações que envolvem representação espacial.
As principais vantagens do uso dessa técnica são as seguintes: Compactação, Precisão Ajustável e Busca Espacial Eficiente (regiões próximas no espaço geográfico têm prefixos Geohash similares).
A representação visual do algoritmo é a seguinte:
Perceba a natureza recursiva do processo. Para obter localidades próximas a Florianopólis (27.5948° S, 48.5569° W) usando esse mapeamento, por exemplo, o hash resultante seria algo iniciando em j + alguns caracteres.
Implementação
Abaixo está um exemplo de como gerar o Geohash em Python:
def encode_geohash(latitude, longitude, precision=12):
"""
Converte latitude e longitude para Geohash.
Parâmetros:
- latitude: Latitude em graus decimais.
- longitude: Longitude em graus decimais.
- precision: Precisão do Geohash (número de caracteres). Padrão é 12.
Retorna:
- Uma string representando o Geohash.
"""
# Conjunto de caracteres base32 usado na codificação Geohash
base32 = '0123456789bcdefghjkmnpqrstuvwxyz'
# Faixa inicial para latitude e longitude
lat_range = (-90.0, 90.0)
lon_range = (-180.0, 180.0)
# Inicializações de variáveis
geohash = ""
bits = 0
ch = 0
even = True
# Loop principal para gerar o Geohash
while len(geohash) < precision:
# Verifica se o bit deve ser extraído da longitude ou latitude
if even:
mid = (lon_range[0] + lon_range[1]) / 2
if longitude > mid:
ch |= (1 << bits)
lon_range = (mid, lon_range[1])
else:
lon_range = (lon_range[0], mid)
else:
mid = (lat_range[0] + lat_range[1]) / 2
if latitude > mid:
ch |= (1 << bits)
lat_range = (mid, lat_range[1])
else:
lat_range = (lat_range[0], mid)
# Alterna entre longitude e latitude
even = not even
bits += 1
# Quando bits atinge 5, converte para base32 e reinicia as variáveis
if bits == 5:
geohash += base32[ch]
bits = 0
ch = 0
# Retorna a string Geohash gerada
return geohash
# Exemplo de uso:
latitude = 37.7749
longitude = -122.4194
precision = 8
geohash_result = encode_geohash(latitude, longitude, precision)
print(f"Latitude: {latitude}, Longitude: {longitude} -> Geohash: {geohash_result}")A função inversa é a seguinte:
def decode_geohash(geohash):
"""
Converte Geohash para latitude e longitude.
Parâmetros:
- geohash: String representando o Geohash.
Retorna:
- Tupla contendo a latitude e longitude.
"""
# Conjunto de caracteres base32 usado na codificação Geohash
base32 = '0123456789bcdefghjkmnpqrstuvwxyz'
# Faixa inicial para latitude e longitude
lat_range = (-90.0, 90.0)
lon_range = (-180.0, 180.0)
# Variável para controlar se o bit atual refere-se a longitude ou latitude
even = True
# Itera sobre cada caractere no Geohash
for char in geohash:
# Obtém o índice do caractere na base32
index = base32.index(char)
# Itera sobre cada bit no índice
for i in range(5):
# Obtém o bit atual do índice
bit = (index >> (4 - i)) & 1
# Atualiza a faixa de longitude ou latitude com base no bit
if even:
lon_mid = (lon_range[0] + lon_range[1]) / 2
if bit:
lon_range = (lon_mid, lon_range[1])
else:
lon_range = (lon_range[0], lon_mid)
else:
lat_mid = (lat_range[0] + lat_range[1]) / 2
if bit:
lat_range = (lat_mid, lat_range[1])
else:
lat_range = (lat_range[0], lat_mid)
# Alterna entre longitude e latitude
even = not even
# Calcula a latitude e longitude final
latitude = (lat_range[0] + lat_range[1]) / 2
longitude = (lon_range[0] + lon_range[1]) / 2
# Retorna a tupla contendo a latitude e longitude
return latitude, longitude
# Exemplo de uso:
geohash_input = "ezs42"
decoded_latitude, decoded_longitude = decode_geohash(geohash_input)
print(f"Geohash: {geohash_input} -> Latitude: {decoded_latitude}, Longitude: {decoded_longitude}")Recomendações
Apesar de estar listada aqui uma implementação, existe uma recomendação geral em engenharia de software que gostaria de replicar aqui:
Não use implementações caseiras de algoritmos específicos em produção.
Portanto, para algoritmos commodity, como criptografia, acesso a banco de dados ou geohash, não implemente manualmente, Exceto se você conhecer o domínio do problema a ser resolvido a fundo.
Se você só precisa resolver um problema, use uma biblioteca. Provavelmente ela implementou a solução de uma forma mais correta que a visão de um leigo no assunto. Só isso já reduz riscos consideráveis.
Opções alternativas
Existem vários algoritmos e métodos relacionados ao Geohash, cada um com suas próprias abordagens e características. Alguns deles incluem:
Quadkey: Similar ao Geohash, o Quadkey divide a superfície da Terra em quadrantes e atribui um código a cada quadrante. É frequentemente usado em sistemas de mapeamento e a hierarquia é representada por meio de uma sequência de códigos:
S2 Geometry: Desenvolvido pelo Google, é uma biblioteca de geometria espacial que representa a superfície da Terra em uma esfera usando uma grade hierárquica. Ele é usado para indexação espacial eficiente e é aplicável em várias áreas, incluindo mapeamento e análise espacial.
Uber H3: Desenvolvido pela Uber, é um sistema de grade hexagonal que visa equilibrar a distorção de área encontrada em sistemas de grade baseados em latitudes e longitudes. Ele é usado para indexação espacial e análise de dados de localização.
Como saber quais deles usar?
Analisando trade-offs, como sempre. Conhecendo o problema a fundo, qual algoritmo atende melhor emerge naturalmente como resultado dessa análise, na maioria das vezes.
Espero que este texto seja útil para você de alguma forma.
Até!
Você gostou do conteúdo e gostaria de fazer mentoria comigo? Clique aqui e descubra como.
