GeoHash 에 대해서 알아보기

SnapCast 앱을 개발하면서 위도, 경도를 가지고 있는 수많은 데이터 중 내 좌표와 가장 근접한 비디오들을 가져오는 기능을 만들어야 했었습니다.

위 기능을 만든다고 하면 어떻게 만들어 볼 수 있을까요? 가장 쉽게 가져오는 방법은 모든 비디오를 탐색하여 나의 위치와 비디오의 위치를 비교하여 가장 가까운 n 개의 비디오를 가져오는 방법이 있을 것 같습니다.

하지만 위의 방법처럼 하게 된다면, 비디오가 적을 경우에는 모르겠지만 점점 많아지면 속도가 오래걸리는 문제가 발생 할 것 입니다.

그래서 우리는 좀 더 나은 방법을 모색하고자 지오해시라는 것을 알게되어 이번 앱에 사용하였고, 이를 소개해보려고 합니다

지오해시?

지오해시는 위 사진 한장으로 정리를 해볼 수 있으나, 하나하나 설명을 드리자면 "지오"는 지리(Geographic)를 의미하며, "해시"는 임의의 데이터를 고정된 크기의 값으로 변환하는 함수를 의미합니다. 위 사진 처럼 지구를 일정한 크기의 구역으로 나누고, 각 구역을 고유한 문자열로 인코딩한게 바로 지오해시 입니다. 이 지오해시는 빠르고 효율적인 검색을 가능하게 해주는 알고리즘입니다.

지오해시는 정확한 위치를 표현하기 위해 위치 정보를 일정한 길이의 이진 문자열로 변환합니다. 이때, 문자열의 길이가 짧을수록 대상 지역의 정확도는 낮아지지만, 길이가 길어질수록 대상 지역의 정확도가 높아집니다. 따라서 지오해시는 다양한 단계의 정확도를 가진 문자열을 생성할 수 있습니다.

지오해시? 그거 어떻게 만드는건데?

가장 많은 예시를 드는 서울시청(37.5666805, 126.9784147)을 기준으로 지오해시를 만들어보도록 하겠습니다. 우선 지오해시를 만들기 위해서는 2가지의 과정을 거쳐야 합니다. 같이 차근차근 만들어보도록 하겠습니다.

1. 위도 경도를 특정한 규칙으로 이진수로 변경하여야 합니다
2. 이진수를 5개씩 묶어 Geohash Base32로 변경하여야 합니다.

서울 시청의 위도 경도를 이진수로 변환하기

우선 계산을 하기전에 한가지 알으셔야 할 점은, 기존 지구 사진을 보시면 0 점을 기준으로 음수는 없고 좌 우 모두 양수로 되어 있는 이미지를 보실 수 있는데요. 위 사진에서는 음수로 표기하고 있습니다.

❓ 왜 서경과 남위를 음수로 표기하나요?

서경과 남위를 음수로 표기하는 이유는 WGS84(World Geodetic System 1984)라는 지구측량 시스템에서 사용되는 규칙 중 하나로 국제적인 합의사항에 따라 정해진 표기 규칙입니다. 음수 표기법을 사용함으로써, 서경과 남위 값이 양수와 음수로 나뉘어 표현됨으로써, 지리적 위치를 더욱 명확하게 표시할 수 있습니다.

서경과 동경 은 0 을 중심으로 동쪽과 서쪽을 구분하기 때문에, 동경은 0°부터 180°까지, 서경은 0°부터 -180°까지로 표현됩니다. 남위와 북위 는 지구의 적도를 기준으로 남쪽과 북쪽을 구분하기 때문에, 북위는 0°부터 90°까지, 남위는 0°부터 -90°까지로 표현됩니다.

우선 위도 경도를 이진수로 변환해보도록 하겠습니다. 방법은 매우 간단합니다.

• 위도는 절반을 나누었을때 왼쪽이면 0 오른쪽이면 1 로 표기합니다.
• 경도는 절반을 나누었을때 위쪽이면 1 아래쪽이면 0 로 표기합니다.
• 순서는 위도 -> 경도 순서로 번갈아 가면서 표기합니다.

그러면 우선 최소갯수인 5개만 뽑아보도록 하겠습니다.

서울 시청(37.5666805, 126.9784147)의 바이너리는 11100이 나옵니다.
하지만 해당 이진수의 범위에는 한국뿐만 아니라 중국도 포함되어 있습니다.

💡 이진수의 길이에 따라서 얼마나 정확하게 가져 올 수 있는지를 알 수 있습니다.

위 사진에서는 지오해시의 길이에 따른 오차를 보여주는 테이블 입니다. 현재는 해시값까지는 얻지 못하였으니. geohash length 에 * 5 해주시면 될 것 같습니다.

우리는 좀 더 자세한 위치를 표현하기 위해 지오해시의 레벨을 높혀야 하며 이는 2진수를 더 길게 만들어야 한다는 뜻입니다. 지오해시의 레벨은 일반적으로 1부터 12까지의 값으로 지정할 수 있습니다. 즉, 이진수길이가 최소 5에서 최대 60까지 길어질 수 있습니다. 그러면 좀 더 자세하게 위도와 경도를 이진수로 바꿔 보도록 하고, 위도와 경도를 각각 코드화 시켜 뽑아보도록 하겠습니다.

다음 코드는 12레벨의 지오해시 바이너리값을 출력하는 함수입니다.

위도

fun printBinaryLatitude(latitude: Double): String {
    val binary = Integer.toBinaryString(((latitude + 90) / 180 * (1 shl 30)).toInt())
    return binary.padStart(30, '0')
}

경도

fun printBinaryLongitude(longitude: Double): String {
    val binary = Integer.toBinaryString(((longitude + 180) / 360 * (1 shl 30)).toInt())
    return binary.padStart(30, '0')
}

❓ 왜 둘다 90, 180을 더하고 180, 360을 나누나요?

위와 같이 경도를 변환하는 이유는 지리 좌표를 2진수로 변환할 때, 일반적으로 위도와 경도를 같은 길이의 이진수로 변환하게 됩니다. 그리고 지구의 위도 범위는 -90~90 이고, 경도 범위는 -180~180입니다.

이 때문에 경도를 위도와 같은 방식으로 변환하면, 0을 기준으로 대칭인 값이 중복되게 되는 문제가 있습니다. 예를 들어, 경도가 -180일 때와 180일 때의 값은 같은 이진수가 됩니다.

• -0.123, 0.123 으로 나눠져야 하는데 0.123, 0.123 으로 같이 나오게 됩니다.

이러한 문제를 해결하기 위해, 일반적으로는 경도에 180을 더한 뒤 360으로 나누어준 뒤 2^30을 곱해 정수형으로 변환합니다. 이렇게 함으로써, 0도를 기준으로 양쪽에 대칭인 값이 중복되지 않게 되며, 각 경도 값에 대해 고유한 이진수를 생성할 수 있습니다.

이렇게 하면 다음과 같은 위도와 경도의 이진수를 얻을 수 있습니다.

위도: 10110 10101 10110 11001 11000 11010
경도: 11011 01001 00101 11011 01110 00001

이제 경도와 위도를 번갈아 가면서 하나의 이진수로 만들어주면 다음과 같이 나옵니다.

11100 11110 01100 10011 01001 10110 11110 01011 01111 01000 01010 00110

서울 시청의 이진수를 Geohash Base32 치환하기

이제 진정한 해쉬값을 뽑아보도록 하겠습니다. 그전에 Geohash Base32에 대해 간단하게 소개하자면 Geohash Base32는 기존 Base32 와는 비슷하지만 Geohash 를 위해서 생긴 인코딩 방법입니다. Base43 와 동일하게 대문자 알파벳, 소문자 알파벳 등의 문자로 이루어진 데이터를 32개의 서로 다른 문자로 구성된 알파벳으로 인코딩하는 방법입니다.

우선 5개씩 끊어서 하나씩 바꿔보면 다음과 같습니다.

11011 01101 10011 00011 10001 11001 11110 00111 10110 10100 10100 01001
wydm9qycg8b6

해당 사이트에서 검색을 해보면 실제로 서울시청의 위치가 출력이 됩니다.
https://geohash.softeng.co

❓ 어? 왜 가로와 세로의 길이가 서로 번갈아 가면서 다른가요?

홀수 레벨은 세로 방향으로 긴 셀을, 짝수 레벨은 가로 방향으로 긴 셀을 사용하는 것은 일반적인 GeoHash 구현에서 사용되는 방식 중 하나입니다. 이 방식에서는 각 레벨에서 셀의 경계를 중심으로 번갈아가며 가로 방향으로 긴 셀과 세로 방향으로 긴 셀을 번갈아 배치하여 사용합니다.

이러한 방식은 셀의 가로 세로 비율을 보다 균등하게 유지하면서도 셀의 개수를 최소화할 수 있는 장점이 있습니다. 세로만 하게되는것과 세로와 가로를 번갈아가면서 배치하게 되는것에 대한 균등도에는 차이가 있습니다.

하지만 이 방식이 반드시 사용되는 것은 아니며, 다른 구현에서는 가로와 세로를 번갈아 사용하지 않고, 랜덤하게 배치하는 경우도 있습니다. 이는 구현에 따라 다를 수 있는 것이며, 이러한 차이는 GeoHash의 해싱 알고리즘에 직접적인 영향을 미치지는 않습니다.

어떻게 사용해?

이제 해당 해쉬를 모든 좌표가 있는 비디오 객체에 넣어주고, 파이어베이스에서 제공하는 지오해시 쿼리를 사용하여 데이터를 뽑았습니다. 만약, 파이어베이스가 아니라 직접 디비를 운용하신다면 데이터 테이블에 지오해시 컬럼을 만들어서 해당 값을 같이 저장하고 조회하시면 될 것 같습니다!

https://firebase.google.com/docs/firestore/solutions/geoqueries?hl=ko

정리

생각보다 재미있는 시간이였습니다. 평소에는 잘 접근해보지 못했던 지오해시를 자세히 공부해볼 수 있는 좋은 시간이였습니다.