جيوهاش

للحصول على ترجمة دقيقة لخطوط الطول والعرض، يُعدّ Geohash فهرسًا مكانيًا أساسه 4 ، لأنه يحوّل إحداثيات خطوط الطول والعرض المتصلة إلى شبكة منفصلة هرمية، باستخدام تقسيم رباعي متكرر للفضاء. ولجعله رمزًا مضغوطًا، يستخدم أساس 32 ويمثل قيمه بالأبجدية التالية، أي "التمثيل النصي القياسي".

تستخدم "أبجدية Geohash" (32ghs) جميع الأرقام من 0 إلى 9 وجميع الأحرف الصغيرة باستثناء "a" و "i" و "l" و "o".

على سبيل المثال، باستخدام الجدول أعلاه والثابت${\displaystyle B=32}$ezs42، يمكن تحويل رمز Geohash إلى تمثيل عشري باستخدام الترميز الموضعي العادي :

[ 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 بتمثيل مكاني مختلط:

• يتم تمثيل Geohashes المكونة من 2، 4، 6، ... أرقام ( الأرقام الزوجية ) بواسطة منحنى من الدرجة Z في "شبكة منتظمة" حيث يكون للزوج الذي تم فك تشفيره (خط العرض، خط الطول) عدم يقين موحد، وهو صالح كمعرف URI جغرافي .
• يتم تمثيل رموز Geohashes المكونة من 1، 3، 5، ... d أرقام (أرقام فردية) بواسطة "منحنى من الدرجة الأولى". يختلف عدم اليقين في خط العرض وخط الطول للزوج الذي تم فك تشفيره (يتم اقتطاع خط الطول).

من الممكن إنشاء "منحنى الترتيب И" من منحنى الترتيب Z عن طريق دمج الخلايا المتجاورة وفهرسة الشبكة المستطيلة الناتجة بواسطة الدالة${\displaystyle j=\left\lfloor {\frac {i}{2}}\right\rfloor }$يوضح الرسم التوضيحي كيفية الحصول على شبكة من 32 خلية مستطيلة من شبكة من 64 خلية مربعة.

أهم ما يميز نظام Geohash بالنسبة للبشر هو أنه يحافظ على التسلسل الهرمي المكاني في بادئات الرموز . على سبيل المثال، في الرسم التوضيحي "شبكة رقم Geohash واحدة" المكونة من 32 مستطيلاً، أعلاه، يتم الحفاظ على المنطقة المكانية للرمز e(مستطيل الدائرة الرمادية المائلة للزرقة في الموضع 4،3) مع البادئة eفي "شبكة رقمين" المكونة من 1024 مستطيلاً (يظهر المقياس emوالدوائر الرمادية المائلة للخضرة إلى الزرقاء في الشبكة).

باستخدام رمز التجزئة ezs42كمثال، إليك كيفية فك تشفيره إلى خط عرض وخط طول عشريين. الخطوة الأولى هي فك تشفيره من النص " الأساس 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}}$.

ينتج عن هذه العملية البتات0110111111110000010000010 . بدءًا من العد من الجانب الأيسر مع وجود الرقم 0 في الموضع الأول، تشكل الأرقام في المواضع الزوجية رمز خط الطول ( 0111110000000)، بينما تشكل الأرقام في المواضع الفردية رمز خط العرض ( 101111001001).

يُستخدم كل رمز ثنائي في سلسلة من عمليات القسمة، مع مراعاة بت واحد في كل مرة، من اليسار إلى اليمين. بالنسبة لقيمة خط العرض، تُقسم الفترة من -90 إلى +90 على 2، مما ينتج عنه فترتان: من -90 إلى 0، ومن 0 إلى +90. بما أن البت الأول هو 1، تُختار الفترة الأعلى، وتصبح هي الفترة الحالية. تُكرر هذه العملية لجميع البتات في الرمز. في النهاية، تكون قيمة خط العرض هي مركز الفترة الناتجة. تُعالج خطوط الطول بطريقة مماثلة، مع الأخذ في الاعتبار أن الفترة الأولية هي من -180 إلى +180.

على سبيل المثال، في رمز خط العرض 101111001001، تكون البتة الأولى 1، لذا نعلم أن خط العرض يقع بين 0 و90. بدون بتات إضافية، سنفترض أن خط العرض هو 45، مما يعطينا خطأً قدره ±45. بما أن هناك بتات إضافية متاحة، يمكننا المتابعة مع البتة التالية، وكل بتة لاحقة تقلل هذا الخطأ إلى النصف. يوضح هذا الجدول تأثير كل بتة. في كل مرحلة، يتم تمييز النصف ذي الصلة من النطاق باللون الأخضر؛ البتة المنخفضة تحدد النطاق الأدنى، والبتة العالية تحدد النطاق الأعلى.

يُظهر عمود "القيمة المتوسطة" خط العرض، وهو ببساطة متوسط ​​قيمة النطاق. كل بت لاحق يجعل هذه القيمة أكثر دقة.

(تم تقريب الأرقام في الجدول أعلاه إلى 3 منازل عشرية للتوضيح)

ينبغي إجراء التقريب النهائي بعناية بطريقة تضمن

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

لذا، في حين أن تقريب العدد 42.605 إلى 42.61 أو 42.6 صحيح، فإن تقريبه إلى 43 ليس كذلك.

يمكن استخدام رموز Geohash لتحديد النقاط المتقاربة بناءً على بادئة مشتركة. مع ذلك، فإن المواقع القريبة من بعضها ولكن على جانبي خط الزوال 180 درجة ستؤدي إلى رموز Geohash بدون بادئة مشتركة (خطوط طول مختلفة لمواقع جغرافية متقاربة). كما أن النقاط القريبة من القطبين الشمالي والجنوبي ستكون لها رموز Geohash مختلفة تمامًا (خطوط طول مختلفة لمواقع جغرافية متقاربة).

لن يشترك موقعان متجاوران على جانبي خط الاستواء (أو خط غرينتش) في بادئة طويلة، لأنهما ينتميان إلى نصفين مختلفين من الكرة الأرضية. ببساطة، سيكون خط العرض (أو خط الطول) الثنائي لأحد الموقعين 011111... والآخر 100000....، لذا لن يشتركا في بادئة، وستكون معظم البتات معكوسة. يمكن اعتبار هذا أيضًا نتيجةً للاعتماد على منحنى الترتيب Z (والذي يُمكن تسميته بشكل أدق بزيارة الترتيب N في هذه الحالة) لترتيب النقاط، حيث قد تتم زيارة نقطتين متجاورتين في أوقات مختلفة تمامًا. مع ذلك، ستكون نقطتان لهما بادئة طويلة متجاورتين.

لإجراء بحث تقريبي، يمكن حساب الزاوية الجنوبية الغربية (رمز جغرافي منخفض مع خطوط طول وعرض منخفضة) والزاوية الشمالية الشرقية (رمز جغرافي مرتفع مع خطوط طول وعرض مرتفعة) لمربع محيط، ثم البحث عن الرموز الجغرافية بين هاتين النقطتين. سيسترجع هذا البحث جميع النقاط على منحنى الترتيب z بين الزاويتين، وهو ما قد ينتج عنه عدد كبير جدًا من النقاط. كما أن هذه الطريقة غير فعالة عند خط الطول 180 درجة والقطبين. يستخدم Solr قائمة تصفية من البادئات، وذلك بحساب بادئات أقرب المربعات إلى الرمز الجغرافي..

بما أن رمز التجزئة الجغرافية (في هذا التطبيق) يعتمد على إحداثيات خط الطول وخط العرض، فإن المسافة بين رمزي تجزئة جغرافية تعكس المسافة في إحداثيات خط العرض/خط الطول بين نقطتين، وهو ما لا يترجم إلى مسافة فعلية، انظر صيغة هافرسين .

مثال على اللاخطية في نظام خطوط الطول والعرض:

• عند خط الاستواء (0 درجة) يبلغ طول درجة خط الطول 111.320  كم، بينما يبلغ طول درجة خط العرض 110.574  كم، وهو خطأ بنسبة 0.67٪.
• عند خط عرض 30 درجة (خطوط العرض المتوسطة)، يكون الخطأ 110.852/96.486 = 14.89%
• عند 60 درجة (القطب الشمالي العالي) يكون الخطأ 111.412/55.800 = 99.67%، ويصل إلى اللانهاية عند القطبين.

تجدر الإشارة إلى أن هذه القيود لا تعود إلى التجزئة الجغرافية، ولا إلى إحداثيات خطوط الطول والعرض، بل إلى صعوبة تحويل الإحداثيات على سطح كروي (غير خطي، مع التفاف القيم، على غرار حساب المقياس) إلى إحداثيات ثنائية الأبعاد، وصعوبة استكشاف فضاء ثنائي الأبعاد بشكل منتظم. يرتبط الأول بنظام الإحداثيات الجغرافية وإسقاط الخرائط ، بينما يرتبط الثاني بمنحنى هيلبرت ومنحنى الترتيب z . بمجرد إيجاد نظام إحداثيات يُمثل النقاط خطيًا في المسافة، وينتهي عند الحواف، ويمكن استكشافه بشكل منتظم، فإن تطبيق التجزئة الجغرافية على هذه الإحداثيات لن يُعاني من القيود المذكورة أعلاه.

على الرغم من أنه من الممكن تطبيق التجزئة الجغرافية على منطقة ذات نظام إحداثيات ديكارتية ، إلا أنها ستنطبق فقط على المنطقة التي ينطبق عليها نظام الإحداثيات.

على الرغم من هذه المشكلات، هناك حلول بديلة ممكنة، وقد تم استخدام الخوارزمية بنجاح في Elasticsearch، ^{[ 7 ] و} MongoDB، ^{[ 8 ]} وHBase، وRedis، ^{[ 9 ]} و Accumulo ^{[ 10 ]} لتنفيذ عمليات البحث عن التقارب.