2012-08-24 46 views
6

Supongamos que tengo un gran número de cadenas (digamos 10 mil millones de cadenas de ~ 50 caracteres cada una). Quiero distribuir las cadenas en exactamente 10 cubos. Cada cubo debe contener alrededor del 10% de las cuerdas. Con una función hash h() que puedo hacer:Mejorar la distribución de los valores de la función hash

int bucket_for_s = h(s) % 10 

Sin embargo, esto no proporciona ninguna garantía sobre la uniformidad de la distribución. Supongamos que hago lo anterior para todas las cadenas y encuentro que el 30% va al cubo 1, el 5% va al cubo 2 y así sucesivamente. Mi pregunta es:

Dada la distribución h(), ¿hay alguna forma de generar una nueva función hash h2() que distribuya las cadenas de forma más pareja?

Alternativamente, hay un proceso que puede generar una serie de funciones hash h2(), h3() ... de modo que 1: cada función hash es mejor que la anterior y 2: solo tengo que generar un cantidad razonable de funciones hash?

También debo mencionar que, desafortunadamente, no puedo simplemente dividir la entrada en 10 partes porque mi entrada está repartida entre varias máquinas. Estoy buscando una solución determinista que pueda aplicar a cada máquina por separado y obtener los mismos resultados (por lo que eventualmente "hola" iría al cubo x, sin importar en qué máquinas se almacenara).

+0

¿Es esta una pregunta teórica? ¿O tienes datos empíricos sobre esto? Además, ¿estás usando un sistema artesanal o algo así como Hadoop? – cyroxx

+0

Esta es una pregunta teórica que cruzó mi mente mientras pensaba en diseñar un sistema artesanal. Hasta el momento no he encontrado una respuesta para eso. – user1424934

Respuesta

5

Las funciones hash criptográficamente sólidas ya deberían tener una distribución muy uniforme en todos los bits de la salida hash.

Si está utilizando algo como Java de hashCode() que creo que se ve como

s [0] * 31^(n-1) + s 1 * 31^(n-2) + ... + s [n-1]

es posible que vea una distribución de hash menos que ideal.

Intente usar un hash criptográfico como SHA-256 como base.

Google City Hash está menos distribuido que SHA-256, pero es mucho más rápido. Eso puede proporcionar una distribución suficiente a un menor gasto computacional.

+0

También se debe tener en cuenta que depende en gran medida de los datos. Si tiene 50 mil millones de artículos, con 5 mil millones de duplicados, entonces ese es el 10% allí que probablemente unirá otros datos en un cubo. Si los datos realmente no importan más que la función de hash, entonces será más fácil simplemente tomar el 10% y ponerlo en un cubo, y luego continuar. Después de todo, usar un cubo para almacenar 5 mil millones de artículos vence el objetivo en comparación con el uso de una colección tradicional (por ejemplo, una lista). – pickypg

+0

@Eric J. - Solo tengo 10 cubos, por lo que incluso SHA-256 podría no distribuir mis artículos de manera uniforme para todos los conjuntos de artículos. – user1424934

+0

@pickypg: supongo que las cadenas no se duplicarán más de un millón de veces, que es el 0,01% de la entrada. Lamentablemente, no puedo dividir la entrada fácilmente en 10 partes porque no tengo todo en un solo lugar. – user1424934

0

Una orientación sobre cómo resolverlo simplifica a 2 cubos en lugar de 10 o N.

Supongamos que se obtiene una distribución h() con asignaciones p de cubo 1 y 2 q de balde, claro p + q = 1.

Ahora, el objetivo es encontrar dicha distribución h2() con parámetros p1, q1, p2, q2 que: dado cubeta 1 que utiliza las posibilidades p1, q1 (p1+q1=1) y dado cubeta 2 que utiliza Chances p2, q2 (p2+q2=1):

  h()   h2() 

       /bucket1 p*p1 
     bucket1 p - 
    /   \ bucket2 p*q1 
x - 
    \   /bucket1 q*p2 
     bucket2 q - 
       \ bucket2 q*q2 

donde nuestro objetivo es incluso Chances para todos los cubos 2:

p*q1 + q*p2 = 1/2 (total chances for bucket 1 after h2()) 
p*q2 + q*q2 = 1/2 (total chances for bucket 2 after h2()) 

y como antes:

p1 + q1 = 1 
p2 + q2 = 1 

Este es un sistema lineal de 4 ecuaciones con 4 variables (parámetros p1,q1,p2,q2 de la distribución h2()).

Nota: Con 10 cubos tendríamos h() con p1, p2, ..., p10 donde p1 + p2 + ... + p10 = 1. En caso de que cuando el número de cubetas> 2 haya menos ecuaciones que incógnitas, para cada asignación como p1 obtendrá un componente de h2() con p11+p12+...+p1_10=1). Por lo tanto, para 10 cubos hay 100 parámetros desconocidos de h2() y solo 20 ecuaciones. Esto significa que se podrían dar algunos valores arbitrarios (pero factibles) a 80 parámetros de h2() antes de resolver ecuaciones para los parámetros restantes. No es bonita, pero sigue siendo una solución.

6

Encadenar funciones hash o generar una serie de funciones hash sería innecesariamente costoso desde el punto de vista informático. Debería usar una función hash que ya tiene las propiedades requeridas out-of-the-box.

candidatos posibles

De lo que se ha descrito, la función hash debe ser determinista (su "hola" ejemplo) - esto es cierto para todas las funciones de hash - y debe generar una distribución uniforme.

Un hash criptográfico como SHA-256 debe cumplir con sus requisitos, ya que genera hashes completamente diferentes incluso para entradas ligeramente diferentes como "hola" y "hola". Al usar la operación de módulo (%) en el hash, puede tener tantos buckets como desee (no más que el número de hashes, por supuesto).

Sin embargo, las funciones hash criptográficas están diseñadas para la seguridad y las sumas de comprobación e implican algunos cálculos complejos. En su caso, es muy probable que no necesite las fuertes propiedades relacionadas con la seguridad que proporcionan.

Quizás prefiera buscar las denominadas "funciones hash no criptográficas" que tienen propiedades relajadas y están más diseñadas para búsquedas, por lo que están optimizadas para la velocidad. Java hashCode(), MurmurHash y el ya mencionado CityHash (Google announcement) podría ser un buen comienzo.

naturaleza determinista de funciones hash frente a una distribución uniforme de los hashes

Dicho esto, como funciones hash son deterministas en cuanto a la entrada, el hash para una determinada entrada como "hola" siempre será el mismo, incluso si llama a la función hash varias veces. Si su conjunto de datos contiene algunos elementos con muchos duplicados exactos (por ejemplo, "a" y "el" son sospechosos habituales de textos tokenizados), esto puede conducir fácilmente a intervalos de tamaño no uniforme, sin importar qué función hash use.

Suponiendo que desea utilizar la distribución uniforme de hashes para una distribución uniforme de la carga de trabajo, esto se puede superar con la siguiente estrategia. Piense en cada cubo como un paquete de trabajo o trabajo que puede ser procesado por cualquiera de las máquinas disponibles. Si tiene más paquetes de trabajo que máquinas (digamos 20 o 30 paquetes para 10 máquinas), puede distribuir uniformemente la carga de trabajo siempre que permita una programación flexible. Cuando la máquina A obtiene uno de los paquetes sobredimensionados y tarda un tiempo en procesarlo, la máquina B podría procesar dos paquetes pequeños o medianos al mismo tiempo, por lo que se reduce el impacto general en el rendimiento del paquete sobredimensionado.

0

Las funciones hash están diseñadas para producir una distribución uniforme. Si este no es el caso con sus datos, entonces sus datos son de alguna manera "parcialmente" inversos de esa función hash en particular, y el problema debería desaparecer cuando elija otra información.

Dado que esto es una cuestión teórica, un enfoque sería:

Blanqueamiento ruido coloreado

Se puede jugar con el int bucket_for_s

int bucket_for_s = put_in_bucket(s) 

put_in_bucket: 
    x = h(s) % 10 + 10*((h(s)/10)%10) 
    if(0<=x<=2) return 0 
    if(3<=x<=5) return 1 
    if(6<=x<=9) return 2 
    #The previous bucket_1 (30%) is now split into 3 buckets 
    if(10<=x<=27) return 0 
    #The previous bucket_2 (5%) is now enlarged 
    #to incorporate more of the small old buckets (or parts of buckets) 
    #This bucket is now bucket_4 
    #... more of the same 
    if(83<=x<=99) return 9 

Puede ampliar esta idea por otro dígito hasta que se están contentos con su "resolución"

Puede sacar la lógica de put_in_bucket y ponerla en h2(s) usando h1(s).

Este enfoque se utiliza para colorear el ruido blanco (o el ruido de color de blanqueamiento, como en este caso), de ahí el nombre.

Cuestiones relacionadas