ジオハッシュ

パブリックドメインジオコーディングは2008年に発明されました

6g ^[1]セルとそのサブグリッド。

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

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

歴史

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

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

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

典型的な主な用途

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

geohash.org でジオハッシュにアクセスすると、指定されたジオハッシュに対応する緯度と経度が表示されるだけでなく、埋め込まれた地図も表示されます。また、GPXファイルをダウンロードしたり、特定のGPS受信機にウェイポイントを直接転送したりすることもできます。さらに、指定された場所の周辺情報を提供する外部サイトへのリンクも提供されます。

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

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

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

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

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

技術的な説明

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

テキスト表現

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

小数点	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
基数32	0	1	2	3	4	5	6	7	8	9	b	c	d	e	f	グラム
小数点	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
基数32	h	j	け	メートル	n	p	q	r	s	t	あなた	v	わ	×	y	z

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

たとえば、上の表と定数を使用すると、ジオハッシュは通常の位置表記法によって 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}$

幾何学的表現

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

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

32 セルのグリッドの曲線は、「次のレベル」の 2 x 2 セル (ここで示されている 64 セルのグリッド) を結合して取得され、「奇数桁ジオハッシュ」の幾何学的表現が得られました。

隣接するセルを結合し、結果として得られる長方形グリッドに関数 でインデックスを付けることで、Zオーダー曲線から「Iオーダー曲線」を構築することができます。図は、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度になります。さらにビットが利用できるので、次のビットに進むことができ、後続の各ビットはこの誤差を半分に減らします。この表は、各ビットの効果を示しています。各段階で、関連する範囲の半分が緑色で強調表示されています。下位ビットは下限範囲を選択し、上位ビットは上限範囲を選択します。

「平均値」列は緯度を示しており、これは単に範囲の平均値です。後続の各ビットによって、この値はより正確になります。

緯度コード 101111001001
ビット位置	ビット値	分	ミッド	最大	平均値	最大誤差
0	1	−90.000	0.000	9万	45,000	45,000
1	0	0.000	45,000	9万	22,500	22,500
2	1	0.000	22,500	45,000	33.750	11.250
3	1	22,500	33.750	45,000	39.375	5.625
4	1	33.750	39.375	45,000	42.188	2.813
5	1	39.375	42.188	45,000	43.594	1.406
6	0	42.188	43.594	45,000	42.891	0.703
7	0	42.188	42.891	43.594	42.539	0.352
8	1	42.188	42.539	42.891	42.715	0.176
9	0	42.539	42.715	42.891	42.627	0.088
10	0	42.539	42.627	42.715	42.583	0.044
11	1	42.539	42.583	42.627	42.605	0.022

経度コード 0111110000000
ビット位置	ビット値	分	ミッド	最大	平均値	最大誤差
0	0	−180,000	0.000	18万	−90.000	9万
1	1	−180,000	−90.000	0.000	−45,000	45,000
2	1	−90.000	−45,000	0.000	−22.500	22,500
3	1	−45,000	−22.500	0.000	−11.250	11.250
4	1	−22.500	−11.250	0.000	−5.625	5.625
5	1	−11.250	−5.625	0.000	−2.813	2.813
6	0	−5.625	−2.813	0.000	−4.219	1.406
7	0	−5.625	−4.219	−2.813	−4.922	0.703
8	0	−5.625	−4.922	−4.219	−5.273	0.352
9	0	−5.625	−5.273	−4.922	−5.449	0.176
10	0	−5.625	−5.449	−5.273	−5.537	0.088
11	0	−5.625	−5.537	−5.449	−5.581	0.044
12	0	−5.625	−5.581	−5.537	−5.603	0.022

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

最終的な丸めは、

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

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

桁数と精度（km）

ジオハッシュの長さ	latビット	長いビット	緯度エラー	lngエラー	kmエラー
1	2	3	±23	±23	±2,500 km (1,600 マイル)
2	5	5	±2.8	±5.6	±630 km (390 マイル)
3	7	8	±0.70	±0.70	±78 km (48 マイル)
4	10	10	±0.087	±0.18	±20 km（12マイル）
5	12	13	±0.022	±0.022	±2.4 km (1.5 マイル; 2,400 m)
6	15	15	±0.0027	±0.0055	±0.61 km (0.38 マイル; 610 メートル)
7	17	18	±0.00068	±0.00068	±0.076 km (0.047 マイル; 76 メートル)
8	20	20	±0.000085	±0.00017	±0.019 km (0.012 マイル; 19 m)

近接性を判断する際に使用する際の制限

エッジケース

ジオハッシュは、共通の接頭辞に基づいて互いに近接する地点を見つけるために使用できます。ただし、 180度子午線の反対側に位置しながらも互いに近接しているような特殊なケースでは、共通の接頭辞を持たないジオハッシュコードが生成されます（物理的な位置が近いのに経度が異なる）。北極と南極に近い地点では、ジオハッシュは大きく異なります（物理的な位置が近いのに経度が異なる）。

赤道（またはグリニッジ子午線）の両側にある2つの近接した地点は、世界の異なる「半分」に属するため、長い共通の接頭辞を持ちません。簡単に言えば、一方の地点のバイナリ緯度（または経度）は011111…で、もう一方の地点は100000…となるため、共通の接頭辞は持たず、ほとんどのビットが反転します。これは、点の順序付けにZオーダー曲線（この場合はNオーダー訪問と呼ぶ方が適切かもしれません）に依存していることの帰結とも言えます。近接した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次元空間を均一に探索することの難しさによるものであることに注意してください。前者は地理座標系と地図投影に関連し、後者はヒルベルト曲線とZオーダー曲線に関連します。点を距離に対して線形に表し、端で折り返され、均一に探索できる座標系が見つかれば、それらの座標にジオハッシュを適用しても上記の制限は発生しません。

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

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

類似のインデックスシステム

同じbase32-Geohashコードを異なるインデックス曲線で使用できます。四辺形タイルの場合、S2ジオメトリなどで使用されているモートン曲線の代わりにヒルベルト曲線が最適です。偶数桁のコード（2、4、…）は規則的なグリッドにマッピングされますが、奇数桁のコード（1、3、…）は不規則な中間グリッドにマッピングする必要があり、セルは縮退した曲線でインデックスされます。

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

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

^{2019年、QA Locate [14]}は、ジオハッシュをフレーズでコード化し、英語でのコミュニケーションを容易にするためのフロントエンドを設計しました。GeohashPhrase ^[15]は、英語圏のコミュニティで広く利用されています。GeohashPhrase をオープンソース化する計画もありました。^[16]

• Cスクエア（2002）
• フィックスフレーズ
• GeoKey（2018年、独自仕様）
• ガーナポストGPS（2017）
• 立方メートルを使用した国際郵便番号システム (CubicPostcode.com)
• メイデンヘッド ロケーター システム(1980)
• マカニー・コード（2011）
• マップコード（2008）
• 軍事グリッド参照システム
• ナチュラルエリアコード
• オープンロケーションコード（2014、別名「プラスコード」、Googleマップ）
• QRAロケーター（1959）
• ユニバーサル横メルカトル座標系
• 言語的イド
• what3words（2013年、独自仕様）
• WhatFreeWords
• wherewords.id
• wolo.codes
• GEOREF（同様の2桁の階層コード）
• Xアドレス
• 3Geonames（2018年、オープンソース）

ライセンス

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

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

正式な標準

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

参照

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

参考文献

1. "6g". GeoHashエクスプローラー.
2. • Niemeyer, G. (2008-02-26). 「geohash.org が公開されました！」Labix Blog . 2008年3月5日時点のオリジナルよりアーカイブ。
   • Whelan, Phil (2011年12月15日). 「Geohash Intro」. Big Fast Blog . 2012年1月12日時点のオリジナルよりアーカイブ。
   • niemeyer (2008年2月26日). 「geohash.org」.ジオキャッシングフォーラム. 2018年3月9日時点のオリジナルよりアーカイブ。
3. Morton, GM (1966). 「コンピュータ指向の測地データベースとファイルシーケンスの新技術」(PDF) . IBM Research . IBM Canada. 2019年1月25日時点のオリジナルよりアーカイブ。
4. OpenStreetMapの短縮リンクは wiki.openstreetmap.org に文書化されており、2009年にリリースされましたが、10年後の現在でもほぼ同じソースコードを使用しています。これは、Morton のインターレースアルゴリズムを強く基盤としています。
5. 「Geohash バイナリ 64 ビット」には、yinqiwen/geohash-int のような従来のソリューションと、mmcloughlin/geohash-assembly のような最適化されたソリューションがあります。
6. Vukovic, Tibor (2016). Hilbert-Geohash - ヒルベルト空間充填曲線を用いた地理的ポイントデータのハッシュ化. 70 (論文). hdl : 11250/2404058 .
7. Elasticsearch の geo_shape データ型
8. MongoDB における地理空間インデックス
9. Redisコマンドガイド
10. 非リレーショナル分散データベースにおける時空間インデックス
11. 空間キー
12. クアッドタイル
13. 「S2ジオメトリライブラリ」最適化された空間インデックス作成用、https://s2geometry.io 2023年12月11日アーカイブ、Wayback Machine
14. 「QA Locate | 高精度位置情報インテリジェンスの威力」QA Locate . 2020年6月10日閲覧。
15. 「GeohashPhrase」. QA Locate . 2019年9月17日. 2020年6月10日閲覧。
16. thelittlenag (2019年11月11日). 「QA Locateでは、GeohashPhraseというソリューションに取り組んできました | Hacker News」news.ycombinator.com . 2020年6月10日閲覧。
17. geohash.orgのgroundspeak.comフォーラムでの発表記事。2018年のWaybackも参照してください。https://web.archive.org/web/20180309054335/https://forums.geocaching.com/GC/index.php?/topic/186412-geohashorg/ web.archive.org/web/20180309054335
18. 緯度/経度座標のコンパクトなテキストエンコーディング - 特許 20050023524
19. マイクロソフトは自然地域符号化システムを侵害しているのか？ 2010年12月28日アーカイブ - Wayback Machine
20. 「ナチュラルエリアコーディングシステム - 法的およびライセンス」。2019年5月23日時点のオリジナルよりアーカイブ。2008年2月26日閲覧。
21. 「高速で読み取り可能な地理ハッシュ（CTA-5009）」。コンシューマーテクノロジー協会® 。 2024年3月4日閲覧。

外部リンク

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

「https://en.wikipedia.org/w/index.php?title=Geohash&oldid=1318248359」から取得