Fonctions de hachage pour les données SIG

8

Je voudrais prendre des géométries à partir d'un jeu de données vectorielles et les réduire à un hachage. Ce hachage serait ensuite utilisé pour vérifier l'intégrité de ces données et également identifier des géométries identiques.

Existe-t-il des algorithmes appropriés qui pourraient être utilisés? Quels pièges pourrais-je rencontrer?

vector algorithm Matthew Snape
la source
4
Vous pourriez être intéressé par mon article sur la stéganographie vectorielle (dans Directions Magazine) pour un aperçu de quelques-uns des problèmes liés à une application étroitement liée, celui de la dissimulation des messages dans les données vectorielles.
whuber
Qu'est-ce que les géométries doivent satisfaire pour être considérées comme égales? Si aucune rotation n'est impliquée, vous pouvez commencer par regarder WKB et l'étendre pour comparer les géométries traduites.
lynxlynxlynx
"la chose la plus simple qui pourrait éventuellement fonctionner" serait d'utiliser un hachage standard (par exemple CRC32 ou MD4 si vous n'avez pas besoin de propriétés de sécurité, ou un SHA256 si vous avez besoin d'une ou plusieurs propriétés de sécurité). Comme lynxlynxlynx l'a souligné, les géométries sont des données à virgule flottante, vous devez donc faire attention à la comparaison pour «l'égalité».
BradHards

Réponses:

4

et également identifier des géométries identiques.

Vous ne pouvez pas vous fier aux codes de hachage pour l'identification. Dans le cas d'une collision de hachage, vous pouvez obtenir le même code de hachage pour différents objets, vous aurez donc toujours besoin d'une méthode de comparaison plus coûteuse que le post-traitement. Mais bien sûr, vous pouvez ajuster votre méthode de hachage afin de réduire les collisions de hachage.

Si vous voulez simplifier, utilisez simplement MD5 ou tout autre hachage, mais vous pouvez réduire davantage la probabilité d'une collision de hachage. Si vous n'avez pas de géométries traduites ou pivotées et que vous voulez un code de hachage entier, votre méthode pourrait ressembler à ceci:

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

Pour la méthode geohash , jetez également un œil à une clé spatiale («binaire geohash») qui est plus efficace en mémoire et plus précise si les limites de la zone sont plus petites que les limites du monde. Vous pouvez également jeter un œil à mon implémentation Java .

Vous pouvez même réduire davantage la probabilité d'une collision de hachage si vous utilisez les différences des points et calculez un point central :

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);
}

Pour convertir par exemple la latitude en un entier, vous pouvez faire:

latAsInt = latitudeFloatValue * (Integer.MAX / 90)

Ou pour la longitude:

lonAsInt = longitudeFloatValue * (Integer.MAX / 180)
Karussell
la source
J'admets que je ne suis pas un expert des hachages, mais dans la pratique, les gens s'appuient généralement sur les hachages pour l'identification - en partie parce que la probabilité d'obtenir une collision est si faible. Une méthode d'identification plus coûteuse donnerait de meilleurs résultats, mais je pense que vous pouvez également utiliser un algorithme de hachage avec un espace de résultats plus grand (SHA1, SHA256) pour aider cela également. Je ne sais pas si la comparaison plus complexe devient assez rapide par rapport au hachage.
nicksan
Je ne suis pas moi-même un expert du hash :)! et vous avez en effet raison que les collisions pour SHA-1 (et même MD5) sont plutôt rares. Mais un avantage de mes calculs de hachage spécifiques pourrait être (pas testé cependant!) Qu'ils sont plus rapides à calculer. BTW: la valeur de hachage int peut être augmentée jusqu'à un tableau long ou même d'octets
Karussell