ジオハッシュ

ジオハッシュは、2008年にグスタボ・ニーマイヤー^{[1]によって発明された}パブリックドメインの ジオコードシステムであり、地理的位置を短い文字と数字の文字列にエンコードします。同様のアイデアは、1966年にGMモートンによって導入されました。^{[2]これは、空間を}グリッド形状のバケットに分割する階層的な空間データ構造であり、 Zオーダー曲線、および一般的には空間充填曲線と呼ばれるものの多くの応用例の1つです。

ジオハッシュは、任意の精度や、コードの末尾から文字を徐々に削除してサイズを縮小する (そして精度を徐々に下げる) 可能性などの特性を備えています。ジオハッシュでは、2 つのジオハッシュ間の共有プレフィックスが長いほど、空間的に近くなることが保証されます。その逆は保証されません。2 つのポイントが非常に近くても、共有プレフィックスが短いかまったくない場合があります。

ジオハッシュアルゴリズムの中核部分と、同様のソリューションへの最初の取り組みは、1966年のGMモートンのレポート「コンピュータ指向の測地データベースとファイルシーケンスの新技術」に文書化されました。^[2]モートンの研究は、この最新（2014年）のジオハッシュ整数バージョン（ 64ビット整数を直接インターリーブする）のようなZオーダー曲線の効率的な実装に使用されましたが、彼のジオコード提案は人間が読めるものではなく、人気がありませんでした。

どうやら、2000年代後半、G.ニーマイヤーはまだモートンの研究について知らず、base32表現の使用を追加してそれを再発明しました。2008年2月、システムの発表と同時に^[1] 、彼はウェブサイトを立ち上げました。このウェブサイトでは、ユーザーが地理座標を地球上の位置を一意に識別する短いURLhttp://geohash.orgに変換できるため、電子メール、フォーラム、ウェブサイトでの参照がより便利になります。

2009年のOpenStreetMapの 短縮リンク^[3]（base32ではなくbase64を使用）、2014年の64ビットGeohash ^[4]、2016年の珍しいHilbert-Geohash ^[5]など、多くのバリエーションが開発されてきました。

ジオハッシュを取得するには、ユーザーはジオコーディングする住所、または緯度と経度の座標を 1 つの入力ボックスに入力し (緯度と経度のペアの最も一般的な形式が受け入れられます)、リクエストを実行します。

指定されたジオハッシュに対応する緯度と経度を表示するほかに、geohash.org でジオハッシュに移動するユーザーには埋め込みマップも表示され、GPXファイルをダウンロードしたり、特定のGPS受信機にウェイポイントを直接転送したりすることもできます。また、指定された場所の周辺に関する詳細情報を提供する外部サイトへのリンクも提供されます。

たとえば、座標ペア(デンマークのユトランド半島の57.64911,10.40744先端付近) では、わずかに短いハッシュ が生成されます。 u4pruydqqvj

ジオハッシュの主な用途は次のとおりです。

• 一意の識別子として。
• たとえばデータベース内のポイント データを表します。

ジオハッシュはジオタグにも使用されることが提案されています。

データベースで使用する場合、ジオハッシュ データの構造には 2 つの利点があります。まず、ジオハッシュによってインデックス付けされたデータには、連続したスライス内の特定の長方形領域のすべてのポイントが含まれます (スライスの数は、必要な精度とジオハッシュの「断層線」の存在によって異なります)。これは、単一のインデックスに対するクエリが複数のインデックスに対するクエリよりもはるかに簡単または高速であるデータベース システムで特に役立ちます。次に、このインデックス構造は、手っ取り早い近接検索に使用できます。最も近いポイントは、多くの場合、最も近いジオハッシュ内にあります。

計算および数学的ビューの正式な説明。

正確な緯度と経度の変換の場合、ジオハッシュは4 進数の空間インデックスです。これは、空間の 4 分割を繰り返して、連続した緯度と経度の空間座標を階層的な離散グリッドに変換するためです。コンパクトなコードにするために、32 進数を使用し、その値を次のアルファベット、つまり「標準テキスト表現」で表します。

「ジオハッシュ アルファベット」(32ghs) では、0 から 9 までのすべての数字と、「a」、「i」、「l」、「o」を除くすべての小文字が使用されます。

たとえば、上記の表と定数を使用すると、Geohash は通常の位置表記法によって 10 進表現に変換できます。 ${\displaystyle B=32}$ezs42

[ ezs42] _32ghs =${\displaystyle [(e\times B^{4})+(z\times B^{3})+(s\times B^{2})+(4\times B^{1})+(2\times B^{0})]_{32ghs}}$

=${\displaystyle [e]_{32ghs}\times B^{4}+[z]_{32ghs}\times B^{3}+[s]_{32ghs}\times B^{2}+[4]_{32ghs}\times B^{1}+[2]_{32ghs}\times B^{0}}$

=${\displaystyle [13]_{10}\times B^{4}+[31]_{10}\times B^{3}+[24]_{10}\times B^{2}+[4]_{10}\times B^{1}+[2]_{10}\times B^{0}}$

= =${\displaystyle 13\times 1048576+31\times 32768+24\times 1024+4\times 32+2\times 1}$${\displaystyle 13631488+1015808+24576+128+2=14672002}$

Geohash のジオメトリには混合空間表現があります。

• 2、4、6、... e桁 (偶数桁)のジオハッシュは、「通常のグリッド」内のZ オーダー曲線で表され、デコードされたペア (緯度、経度) は均一な不確実性を持ち、 Geo URIとして有効です。
• 1、3、5、... d桁 (奇数桁) のジオハッシュは、「И 次曲線」で表されます。デコードされたペアの緯度と経度には異なる不確実性があります (経度は切り捨てられます)。

隣接するセルを結合し、結果として得られる長方形グリッドを関数でインデックス付けすることで、Z オーダー曲線から「И オーダー曲線」を構築することができます。図は、64 個の正方形セルのグリッドから 32 個の長方形セルのグリッドを取得する方法を示しています。 ${\displaystyle j=\left\lfloor {\frac {i}{2}}\right\rfloor }$

人間にとってジオハッシュの最も重要な特性は、コード プレフィックスの空間階層が保持されることです。
たとえば、上記の 32 個の長方形の「1 ジオハッシュ 桁グリッド」の図では、コードの空間領域(位置 4,3 にある灰色がかった青色の円の長方形) が、 1024 個の長方形の「2 桁グリッド」のeプレフィックスとともに保持されています(スケールが表示され、グリッドに灰色がかった緑色から青色の円があります)。 eem

ハッシュをezs42例にとると、これが 10 進数の緯度と経度にデコードされる方法が次のようになります。最初のステップは、上記のようにテキストの「base 32ghs」からデコードして、バイナリ表現を取得することです。

${\displaystyle [e]_{32ghs}=[13]_{10}=[01101]_{2}}$

${\displaystyle [z]_{32ghs}=[31]_{10}=[11111]_{2}}$

${\displaystyle [s]_{32ghs}=[24]_{10}=[11000]_{2}}$

${\displaystyle [4]_{32ghs}=[4]_{10}=[00100]_{2}}$

${\displaystyle [2]_{32ghs}=[2]_{10}=[00010]_{2}}$。

この演算の結果、ビット 01101 11111 11000 00100 00010が生成されます。最初の位置の数字 0 から左側から数えて、偶数位置の数字が経度コード ( 0111110000000) を形成し、奇数位置の数字が緯度コード ( 101111001001) を形成します。

次に、各バイナリ コードは、左から右へ 1 ビットずつ考慮しながら、一連の分割に使用されます。緯度値の場合、間隔 -90 ～ +90 が 2 で割られ、-90 ～ 0 と 0 ～ +90 の 2 つの間隔が生成されます。最初のビットが 1 であるため、大きい方の間隔が選択され、現在の間隔になります。この手順は、コード内のすべてのビットに対して繰り返されます。最後に、緯度値は結果の間隔の中心になります。経度は、最初の間隔が -180 ～ +180 であることを念頭に置いて、同様に処理されます。

たとえば、緯度コードでは101111001001、最初のビットは 1 なので、緯度は 0 から 90 の間であることがわかります。これ以上ビットがなければ、緯度は 45 であると推測され、誤差は ±45 になります。さらにビットが利用できるので、次のビットに進むことができ、後続の各ビットはこの誤差を半分にします。この表は、各ビットの効果を示しています。各段階で、関連する範囲の半分が緑色で強調表示されています。低いビットは低い範囲を選択し、高いビットは高い範囲を選択します。

「平均値」の列には緯度が表示され、範囲の平均値だけが示されます。後続の各ビットによって、この値はより正確になります。

（上記の表の数字は、わかりやすくするために小数点第3位に丸められています）

最終的な丸めは慎重に行う必要があります。

${\displaystyle \min \leq \mathrm {round} (値)\leq \max }$

したがって、42.605 を 42.61 または 42.6 に丸めるのは正しいですが、43 に丸めるのは正しくありません。

ジオハッシュは、共通のプレフィックスに基づいて互いに近接するポイントを見つけるために使用できます。ただし、エッジ ケースでは、互いに近接しているものの 180 度の子午線の反対側にある場所では、共通のプレフィックスのないジオハッシュ コードが生成されます (物理的な場所が近いのに経度が異なります)。北極と南極に近いポイントでは、ジオハッシュが大きく異なります (物理的な場所が近いのに経度が異なります)。

赤道 (またはグリニッジ子午線) の両側にある 2 つの近い場所は、世界の異なる「半分」に属しているため、長い共通のプレフィックスを持ちません。簡単に言えば、一方の場所のバイナリ緯度 (または経度) は 011111... で、もう一方の場所は 100000.... になるため、共通のプレフィックスは持たず、ほとんどのビットが反転します。これは、ポイントの順序付けにZ オーダー曲線(この場合は N オーダー訪問と呼ぶ方が適切かもしれません) に依存した結果とも言えます。近い 2 つのポイントは、まったく異なる時間に訪問される可能性があるからです。ただし、長い共通のプレフィックスを持つ 2 つのポイントは近くにあります。

近接検索を行うには、境界ボックスの南西コーナー (低い緯度と経度でジオハッシュが低い) と北東コーナー (高い緯度と経度でジオハッシュが高い) を計算し、その 2 つのコーナー間のジオハッシュを検索します。この検索で​​は、2 つのコーナー間の Z オーダー曲線にあるすべてのポイントが取得されますが、ポイントが多すぎる可能性があります。この方法は、180 度の子午線と極でも機能しません。Solr は、ジオハッシュに最も近い正方形のプレフィックスを計算することにより、プレフィックスのフィルター リストを使用します [1]。

ジオハッシュ (この実装では) は経度と緯度の座標に基づいているため、2 つのジオハッシュ間の距離は 2 点間の緯度/経度座標の距離を反映しますが、実際の距離に変換されるわけではありません。Haversineの公式を参照してください。

緯度経度システムの非線形性の例:

• 赤道（0度）では、経度1度の長さは111.320 km、緯度1度の長さは110.574 kmで、誤差は0.67%です。
• 30度（中緯度）では誤差は110.852/96.486 = 14.89%
• 60 度 (高緯度北極) では誤差は 111.412/55.800 = 99.67% となり、極では無限大に達します。

これらの制限は、ジオハッシュや緯度経度座標によるものではなく、球面上の座標 (非線形で、モジュロ演算と同様に値が折り返される) を 2 次元座標にマッピングすることの難しさ、および 2 次元空間を均一に探索することの難しさによるものであることに注意してください。1 つ目は地理座標系と地図投影に関連し、もう 1 つはヒルベルト曲線とZ オーダー曲線に関連します。ポイントを距離に対して線形に表し、端で折り返され、均一に探索できる座標系が見つかると、それらの座標にジオハッシュを適用しても上記の制限は発生しません。

デカルト座標系を持つエリアにジオハッシュを適用することは可能ですが、その場合、ジオハッシュは座標系が適用されるエリアにのみ適用されます。

^{これらの問題にもかかわらず、回避策は存在し、このアルゴリズムはElasticsearch、 [6]、} MongoDB、^[7] 、 HBase、Redis、^[8]、Accumulo ^[9]で近接検索を実装するために効果的に使用されています。

ジオハッシュを文字列としてデータベースに保存する代わりに、ロケーションコードを使用する方法があります。ロケーションコードは空間キーとも呼ばれ、QuadTilesに似ています。^{[10] [11]}

一部の 地理情報システムやビッグデータ空間データベースでは、S2ジオメトリライブラリのように、ヒルベルト曲線に基づくインデックスをZオーダー曲線の代替として使用することができます。^[12]

^{2019年にQA Locate [13]によって、GeohashPhrase [14]}と呼ばれるフロントエンドが設計され、フレーズを使用してジオハッシュをコード化し、英語の音声によるコミュニケーションを容易にしました。GeohashPhraseをオープンソースにする計画がありました。^[15]

ジオハッシュアルゴリズムは、2008年2月26日の発表で発明者によってパブリックドメインにされました。 ^[16]

類似のアルゴリズムは特許取得に成功し^[17]、著作権を主張されてきましたが^{[18] [19]、} GeoHashは全く異なるアルゴリズムとアプローチに基づいています。

GeohashはCTA-5009として標準化されています。^[20]  この標準は2023年版のWikipediaの記事に準拠していますが、正式な（規範的な）リファレンスで追加の詳細を提供しています。Geohashの作成以来公式仕様が存在しなかったため、CTA WAVE組織は、業界の実装者間でのより広範な採用と互換性を支援するためにCTA-5009を公開しました。

• 測地線ジオコーディングシステムの一覧
• Geohash-36 (Geohash の亜種ではありません)
• グリッド（空間インデックス）
• メイデンヘッド ロケーター システム
• 軍事グリッド参照システム
• モートン数（数論）
• ナチュラルエリアコード
• 番号体系
• オープンロケーションコード（プラスコード）
• 空間充填曲線
• 3ワード
• Zオーダー曲線

• 公式サイト
• JTS ジオメトリのジオハッシュ近似
• ジオハッシュプレイグラウンド