Locality Sensitive Hash Implementation?

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

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 una función hash que devuelve hashes similares para entradas similares. Puedo aprender más de esto mediante el ejemplo después. :)

Fuente

2011-04-24 Mehrdad

Para cadenas que puede utilizar el algoritmo de coincidencia aproximado.

generar una cadena aleatoria
Para todas las cadenas calcular su distancia de esa cadena compartida al azar usando un algoritmo como http://www.dotnetperls.com/levenshtein

Si las cadenas son equidistantes de una cadena de referencia, entonces es probable que se son similares el uno al otro. Y ahí tienes una implementación de hash senitivo de localidad para cadenas.

Puede crear diferentes cubos hash para un rango de distancias.

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

Fuente

2011-04-24 11:02:37

+1 parece ser * exactamente * lo que estoy buscando, lo veré un poco más. ¡Muchas gracias! :) – Mehrdad

@Hasan: Estoy un poco confundido ... las cadenas '' abcd "' y '" xyzw "' son ambas una distancia 4 de una cadena aleatoria como '" 6pGO "', pero son completamente diferentes . ¿Cómo funciona? (Es 4 para casi cualquier * cadena * aleatoria de longitud 4 ...) – Mehrdad

@Mehrdad este algoritmo le dice cuántos cambios necesita para transformar su cadena de entrada en la cadena de referencia (aleatoria). También puede probar un algoritmo más simple en el que la distancia es no. de los caracteres comunes entre la cadena aleatoria y su cadena de entrada. –

Bueno hay un excelente en el artículo 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 por lo menos una vez biblioteca de C++ que se puede inspeccionar el código fuente de aquí: http://sourceforge.net/projects/lshkit/

Fuente

2011-04-24 10:45:41

Mismo problema que con el enlace de @Mehran, pero gracias de todos modos, +1. – Mehrdad

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

Se llama LikeLike

Actualmente Likelike sólo admite Min-Wise permutaciones independientes. Min-Wise permutaciones independientes se aplicar la recomendación de Google Noticias

Fuente

2011-04-24 13:37:01 Mehran

Gracias por el enlace, pero parece un poco complicado para mi caso ... Estoy tratando de evitar grandes bibliotecas hasta que entiendo una simple. :-) Gracias de todos modos, +1. – Mehrdad

Soy consciente de que pidió explícitamente para C/C++/C#, pero hay a Python port del nilsimsa hash que podría ser más fácil de asimilar que otras, bibliotecas más grandes.

Fuente

2011-05-27 15:57:05

+1 eso es genial, también estoy aprendiendo Python, así que mata a dos pájaros de un tiro. ¡Gracias por compartir esto! :) – Mehrdad

Locality Sensitive Hash Implementation?

Respuesta

Cuestiones relacionadas