Funciones hash para datos SIG

8

Me gustaría tomar geometrías de un conjunto de datos vectoriales y reducirlas a un hash. Este hash se usaría para verificar la integridad de esos datos y también para identificar geometrías idénticas.

¿Existe algún algoritmo apropiado que pueda usarse? ¿Qué dificultades puedo encontrar?

vector algorithm Matthew Snape
fuente
44
Puede que le interese mi artículo sobre esteganografía vectorial (en la revista Directions) para obtener una descripción general de algunos de los problemas relacionados con una aplicación estrechamente relacionada, la de ocultar mensajes en datos vectoriales.
whuber
¿Qué deben satisfacer todas las geometrías para ser considerados iguales? Si no hay rotación involucrada, puede comenzar mirando WKB y extendiéndolo para poder comparar geometrías traducidas.
lynxlynxlynx
"Lo más simple que podría funcionar" sería usar un hash estándar (por ejemplo, CRC32 o MD4 si no necesita ninguna propiedad de seguridad, o un SHA256 si necesita una o más propiedades de seguridad). Sin embargo, como señaló Lynxlynxlynx, las geometrías son datos de coma flotante, por lo que debe tener cuidado con la comparación para la "igualdad".
BradHards

Respuestas:

4

y también identificar geometrías idénticas.

No puede confiar en los códigos hash para su identificación. En el caso de una colisión hash , podría obtener el mismo código hash para diferentes objetos, por lo que siempre necesitará un método de comparación más costoso como el procesamiento posterior. Pero, por supuesto, podría ajustar su método de hash para reducir las colisiones de hash.

Si desea simplificarlo, simplemente use MD5 o cualquier hash, pero podría reducir más la probabilidad de una colisión de hash. Si no tiene geometrías traducidas o rotadas y desea un código hash entero, su método podría verse así:

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

Para el método geohash también eche un vistazo a una clave espacial ('geohash binario') que es más eficiente en memoria y más precisa si los límites del área son más pequeños que los límites mundiales. También puedes echar un vistazo a mi implementación de Java .

Incluso podría reducir aún más la probabilidad de una colisión de hash si usa las diferencias de los puntos y calcula algún punto 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);
}

Para convertir, por ejemplo, la latitud en un entero, puede hacer:

latAsInt = latitudeFloatValue * (Integer.MAX / 90)

O por la longitud:

lonAsInt = longitudeFloatValue * (Integer.MAX / 180)
Karussell
fuente
Admito que no soy un experto en hashes, pero en la práctica, la gente suele confiar en los hashes para su identificación, en parte porque la probabilidad de obtener una colisión es muy baja. Un método de identificación más costoso daría mejores resultados, pero creo que también podría usar un algoritmo de hash con un espacio de resultados más grande (SHA1, SHA256) para ayudarlo también. Si la comparación más compleja se vuelve lo suficientemente rápida o no frente al hashing en ese momento, no lo sé.
nicksan
¡Yo tampoco soy un experto en hash :)! y tiene razón en que las colisiones para SHA-1 (e incluso MD5) son raramente raras. Pero una ventaja de mis cálculos específicos de hash podría ser (¡aunque no lo probé!) Que son más rápidos de calcular. Por cierto: el valor de hash int se puede aumentar a una matriz de bytes larga o incluso
Karussell