c# - ¿Implementación localizada de hash sensible?

java locality-sensitive-hash

Question

¿Hay algún ejemplo de hash sensible a las localidades relativamente simple de entender (y simple de implementar) en C / C ++ / Java / C #?

Me gustaría obtener más información sobre el concepto y, por tanto, quiero probar una implementación en algunos archivos de texto solo para ver cómo funciona, así que no necesito nada de alto rendimiento ni nada ... solo un ejemplo de hash. función que devuelve hashes similares para entradas similares. Puedo aprender más de esto mediante el ejemplo después. :)

Answer 1

Bueno, hay un artículo excelente en los blogs de MSDN aquí: http://blogs.msdn.com/b/spt/archive/2008/06/11/locality-sensitive-hashing-lsh-and-min-hash.aspx

También hay al menos una biblioteca C ++ en la que puedes inspeccionar el código fuente de aquí: http://sourceforge.net/projects/lshkit/

Answer 2

Me doy cuenta de que pediste explícitamente C / C ++ / C #, pero hay un puerto de Python del hash nilsimsa que podría ser más fácil de asimilar que otras bibliotecas más grandes.

Answer 3

Para cadenas, puede usar un algoritmo de coincidencia aproximado.

• Genera una cadena aleatoria
• Para todas las cadenas calcule su distancia desde esa cadena aleatoria compartida utilizando un algoritmo como http://www.dotnetperls.com/levenshtein

Si las cadenas son equidistantes de una cadena de referencia, es probable que sean similares entre sí. Y ahí tienes una implementación de hash senitivo de localidad para cadenas.

Puede crear diferentes cubos hash para un rango de distancias.

EDITAR: Puedes probar otras variaciones de distancia de cuerda. Un algoritmo simple simplemente devolvería no. de caracteres comunes entre dos cadenas.

Answer 4

También hay una implementación de Java en Hadoop. hace un buen trabajo en documentos.

se llama LikeLike

Actualmente, Likelike solo admite permutaciones independientes Min-Wise. Las permutaciones independientes Min-Wise se aplican a la recomendación de Google News