Fungsi Hashing untuk data GIS

8

Saya ingin mengambil geometri dari dataset vektor dan menguranginya menjadi hash. Hash ini kemudian akan digunakan untuk memverifikasi integritas data itu dan juga mengidentifikasi geometri yang identik.

Apakah ada algoritma yang sesuai yang dapat digunakan? Perangkap apa yang bisa saya temui?

vector algorithm Matthew Snape
sumber
4
Anda mungkin tertarik pada artikel saya tentang steganografi vektor (di Majalah Direction) untuk ikhtisar dari hanya beberapa masalah yang terlibat dalam aplikasi terkait erat, yaitu menyembunyikan pesan dalam data vektor.
Whuber
Apa yang perlu dipenuhi oleh semua geometri agar dianggap setara? Jika tidak ada rotasi yang terlibat, Anda bisa mulai dengan melihat WKB dan memperluasnya sehingga Anda dapat membandingkan geometri yang diterjemahkan.
lynxlynxlynx
"hal paling sederhana yang mungkin bisa berfungsi" adalah menggunakan hash standar (misalnya CRC32 atau MD4 jika Anda tidak memerlukan properti keamanan apa pun, atau SHA256 jika Anda memerlukan satu atau lebih properti keamanan). Seperti yang ditunjukkan oleh lynxlynxlynx, geometri adalah data titik mengambang, jadi Anda harus berhati-hati tentang perbandingan untuk "kesetaraan".
BradHards

Jawaban:

4

dan juga mengidentifikasi geometri yang identik.

Anda tidak dapat mengandalkan kode hash untuk identifikasi. Dalam kasus tabrakan hash, Anda bisa mendapatkan kode hash yang sama untuk objek yang berbeda, sehingga Anda akan selalu memerlukan metode perbandingan yang lebih mahal seperti pasca pemrosesan. Tapi tentu saja, Anda bisa menyetel metode hashing Anda untuk mengurangi tabrakan hash.

Jika Anda ingin membuatnya sederhana cukup gunakan MD5 atau apa pun hash, tetapi Anda bisa mengurangi kemungkinan tabrakan hash lebih. Jika Anda belum menerjemahkan atau memutar geometri dan Anda menginginkan kode hash integer, metode Anda akan terlihat seperti:

int hash = numberOfPoints * 37;
hash += geometryType * 37;
...
for(point : points) {
     hash = hash XOR geohash(point.lat, point.lon)
}

Untuk metode geohash juga melihat kunci spasial ('binary geohash') yang lebih hemat memori dan lebih tepat jika batas wilayah lebih kecil daripada batas dunia. Anda juga dapat melihat implementasi Java saya .

Anda bahkan dapat mengurangi kemungkinan tabrakan hash lebih lanjut jika Anda menggunakan perbedaan poin dan menghitung beberapa titik pusat :

int hash = numberOfPoints;
hash += 37 * geometryType;
...
hash = hash XOR geohash(someCenterPoint.lat, someCenterPoint.lon);
for(point : points) {
   hash += 37 * latToInteger(previousPoint.lat - point.lat);
   hash += 37 * lonToInteger(previousPoint.lon - point.lon);
}

Untuk mengonversi mis lintang menjadi integer yang dapat Anda lakukan:

latAsInt = latitudeFloatValue * (Integer.MAX / 90)

Atau untuk garis bujur:

lonAsInt = longitudeFloatValue * (Integer.MAX / 180)
Karussell
sumber
Saya akui saya bukan ahli hash, tetapi dalam praktiknya, orang biasanya mengandalkan hash untuk identifikasi - sebagian karena kemungkinan mendapatkan tabrakan sangat rendah. Metode identifikasi yang lebih mahal akan memberikan hasil yang lebih baik, tetapi saya pikir Anda juga bisa menggunakan algoritma hashing dengan ruang hasil yang lebih besar (SHA1, SHA256) untuk membantu itu juga. Apakah perbandingan yang lebih kompleks menjadi cukup cepat vs hashing pada saat itu, saya tidak tahu.
nicksan
Saya sendiri bukan ahli hash :)! dan Anda memang benar bahwa tabrakan untuk SHA-1 (dan bahkan MD5) jarang terjadi. Tetapi satu keuntungan dari perhitungan hash spesifik saya bisa (tidak diuji meskipun!) Bahwa mereka lebih cepat untuk menghitung. BTW: nilai hash int dapat ditingkatkan ke array byte yang panjang atau bahkan
Karussell