Geohash

Hello các bạn, hôm nay mình xin tiếp tục bài toán tìm các điểm gần nhất trong phạm vi cho trước. Lần trước mình đã giới thiệu thuật toán QuadTree, một thuật toán tree-based để tìm. Lần này mình giới thiệu 1 thuật toán hoàn toàn khác mà anh em có thể áp dụng ngay, đó chính là Geohash, thuật toán hashed-based.

Khái Niệm

Thuật toán Geohash là một phương pháp mã hóa tọa độ địa lý (vĩ độ và kinh độ) thành một chuỗi ký tự dạng chữ và số. Nó chia khu vực địa lý thành các ô nhỏ hơn và nhỏ hơn thông qua việc chia đôi dãy giá trị của vĩ độ và kinh độ. Chuỗi ký tự kết quả biểu diễn một vùng chữ nhật trên bề mặt Trái Đất, với độ chính xác tăng dần khi chiều dài của chuỗi ký tự tăng lên. Ví dụ:

Cách hoạt động của Geohash

1. Chia đôi phạm vi tọa độ: Bắt đầu với phạm vi toàn cầu: vĩ độ từ -90 đến 90 và kinh độ từ -180 đến 180.
   Chia phạm vi này thành hai phần. Ví dụ, vĩ độ từ -90 đến 0 và từ 0 đến 90.
   Với mỗi phần, nếu tọa độ nằm ở phần dưới, ta thêm '0', nếu ở phần trên, ta thêm '1'.

   

2. Lặp lại quy trình:Tiếp tục chia nhỏ các phạm vi và xây dựng chuỗi nhị phân cho đến khi đạt được độ chính xác mong muốn.

3. Mã hóa nhị phân thành chuỗi ký tự:Sau khi có chuỗi nhị phân, nó được mã hóa thành chuỗi ký tự bằng cách chuyển đổi từng nhóm 5 bit nhị phân thành một ký tự trong bảng Base32.

   

Thuật toán giúp ích cho việc tìm kiếm thế nào

• Bằng việc chia nhỏ, khi tìm kiếm ta chỉ cần tìm các điểm nằm ở các khu vực chứa điểm gốc và khác khu vực xung quanh, điều này giúp việc tìm kiếm trở nên vô cùng nhanh chóng.

• Bản đồ được chia nhỏ theo các cấp độ từ 1 đến 12, level càng lớn, diện tích của cell càng nhỏ. Khi tìm kiếm ta chọn cấp độ sao cho hợp lý nhất, ví dụ cần tìm bán kính 2km thì chọn cấp 5 là hợp lí.

Áp dụng

• Ví dụ: sắp tới nghỉ 2/9, anh em đang lên kế hoạch tìm khách sạn hay nhà nghỉ quanh bán kính dưới 1km chỗ anh em ở để dễ tâm sự với người yêu. Vậy cần giải quyết như thế nào, biết rằng ta có sẵn danh sách khách sạn ở Hà Nội và tọa độ của chúng.

• Bước 1: khai báo class GeospatialIndex gồm mapping địa điểm và giá trị GeoHash

• Bước 2: liệt kê danh sách khách sạn kèm theo geohash của nó

• Bước 3: xét tọa độ và tính Geohash của tâm bán kính (tức điểm gốc)

• Bước 4: liệt kê khu vực tìm kiếm thông qua geohash: bao gồm chính geohash gốc và các khu vực xung quanh

• Bước 5: tìm các địa điểm, tính khoảng cách và trả về kết quả.

Note

Bạn có thể dùng link https://geohash.softeng.co/ để tra cứu trực tiếp geohash, vô cùng tiện lợi khi lập trình.

Nếu bạn cảm thấy hay, hãy like và comment cho mình có động lực lên tiếp các bài tiếp theo nhé.