Geohash: Biến tọa độ GPS thành một chuỗi ký tự ngắn gọn

Nếu bạn từng làm việc với dữ liệu vị trí - tìm quán cà phê gần nhất, gom cụm các điểm giao hàng, hay xây dựng tính năng "tìm bạn quanh đây" - thì sớm muộn cũng sẽ đụng tới Geohash. Đây là một thuật toán đơn giản nhưng cực kỳ hữu dụng, được Gustavo Niemeyer phát minh năm 2008, dùng để mã hóa một cặp tọa độ (vĩ độ, kinh độ) thành một chuỗi ký tự ngắn.

Geohash là gì?

Nói ngắn gọn: Geohash lấy một điểm trên bản đồ (latitude, longitude) và biến nó thành một chuỗi ký tự, ví dụ:

Hồ Gươm, Hà Nội (21.0285, 105.8542) → w7evzk4d

Điều thú vị là chuỗi này không chỉ mã hóa một điểm, mà thực chất mã hóa một vùng hình chữ nhật trên bản đồ. Chuỗi càng dài, vùng đó càng nhỏ, độ chính xác càng cao.

Ý tưởng cốt lõi: chia đôi liên tục

Thuật toán hoạt động dựa trên nguyên lý chia đôi không gian (giống tìm kiếm nhị phân):

1. Bắt đầu với toàn bộ phạm vi kinh độ [-180, 180] và vĩ độ [-90, 90].
2. Chia đôi phạm vi kinh độ. Nếu điểm cần mã hóa nằm ở nửa bên phải, ghi bit 1; nếu ở nửa trái, ghi bit 0. Sau đó thu hẹp phạm vi lại còn đúng nửa chứa điểm đó.
3. Làm tương tự với vĩ độ.
4. Luân phiên giữa kinh độ và vĩ độ (kinh độ trước, rồi đến vĩ độ, rồi lại kinh độ...) cho đến khi đủ số bit mong muốn.
5. Gom các bit thành từng nhóm 5 bit, rồi mã hóa mỗi nhóm bằng bảng ký tự Base32 (loại bỏ các chữ dễ nhầm lẫn như a, i, l, o).

Ví dụ đơn giản hóa với vĩ độ 21.0285:

Cứ tiếp tục như vậy, càng nhiều bit thì khoảng càng thu hẹp, càng bám sát tọa độ thật.

Bảng độ chính xác theo độ dài chuỗi

Đây là phần nhiều người quan tâm nhất - độ dài chuỗi Geohash quyết định kích thước vùng phủ:

Với hầu hết ứng dụng "tìm địa điểm gần đây", độ dài 6–8 ký tự là đủ dùng.

Tính chất "hàng xóm gần thì tiền tố giống nhau"

Đây chính là lý do Geohash hữu ích trong thực tế: hai điểm gần nhau về mặt địa lý thường có chung một đoạn tiền tố (prefix) trong chuỗi Geohash của chúng.

Ví dụ, các Geohash sau đều thuộc khu vực trung tâm Hà Nội và chia sẻ tiền tố w7ev:

w7evzk4d
w7evzk4e
w7evzk7s

Nhờ vậy, để tìm "các điểm gần đây", bạn không cần tính khoảng cách phức tạp - chỉ cần tìm các bản ghi có Geohash cùng tiền tố. Đây là lý do các cơ sở dữ liệu như Redis, MongoDB, Elasticsearch đều hỗ trợ Geohash để lập chỉ mục không gian (spatial indexing).

Nhược điểm cần lưu ý: vấn đề "biên"

Geohash không hoàn hảo. Vấn đề nổi tiếng nhất là hiệu ứng biên (edge case): hai điểm rất gần nhau về khoảng cách thực tế nhưng lại nằm ở hai ô lưới liền kề có thể có Geohash hoàn toàn khác nhau (không chung tiền tố), đặc biệt khi chúng nằm ngay sát đường phân chia ô.

Ví dụ, một điểm ở rìa phía đông của ô w7ev và một điểm cách đó vài mét nhưng thuộc ô w7ex bên cạnh sẽ có chuỗi Geohash nhìn hoàn toàn khác nhau dù khoảng cách vật lý rất nhỏ.

Cách khắc phục phổ biến: khi tìm kiếm lân cận, người ta thường không chỉ tra ô hiện tại mà tra luôn 8 ô lân cận (bao quanh) để đảm bảo không bỏ sót điểm nào ở gần biên.

Ứng dụng thực tế

• Tìm kiếm địa điểm gần đây: Uber, Grab, các app giao đồ ăn dùng Geohash để nhanh chóng tìm tài xế/shipper trong bán kính gần.
• Lập chỉ mục không gian trong database: Redis (lệnh GEOADD, GEOSEARCH), MongoDB, Elasticsearch đều dùng biến thể của Geohash.
• Chia sẻ vị trí ngắn gọn: một chuỗi 8-9 ký tự dễ nhớ, dễ gửi hơn nhiều so với "21.028511, 105.854133".
• Gom cụm (clustering) trên bản đồ: nhóm các điểm có cùng tiền tố Geohash để hiển thị cụm trên bản đồ khi zoom out.

Ví dụ code Python đơn giản

import geohash2

# Mã hóa tọa độ thành geohash
code = geohash2.encode(21.0285, 105.8542, precision=8)
print(code)  # w7evzk4d

# Giải mã ngược lại
lat, lon = geohash2.decode(code)
print(lat, lon)  # 21.0285, 105.8542

Chỉ vài dòng, nhưng đằng sau đó là cả một cơ chế chia đôi không gian khá tinh tế.

Tổng kết

Geohash là một ví dụ đẹp về cách một ý tưởng đơn giản - chia đôi không gian liên tục và mã hóa bit - có thể giải quyết một bài toán thực tế rất lớn: tìm kiếm và lập chỉ mục dữ liệu vị trí một cách hiệu quả. Nó không phải công cụ hoàn hảo cho mọi bài toán không gian (nếu cần độ chính xác cao ở biên ô hoặc tìm kiếm bán kính chính xác tuyệt đối, có thể cần kết hợp thêm kỹ thuật khác như R-tree hoặc quadtree), nhưng với sự đơn giản, tốc độ và khả năng tích hợp dễ dàng vào database dạng chuỗi/key-value, Geohash vẫn là lựa chọn phổ biến hàng đầu cho các ứng dụng vị trí hiện nay.