Mezcla de hash asociativa

14

Considere la lista humildemente vinculada en un entorno puramente funcional. Sus alabanzas se han cantado desde las cimas de las montañas y se seguirán cantando. Aquí abordaré uno de sus muchos puntos fuertes y la cuestión de cómo se puede extender a la clase más amplia de secuencias puramente funcionales basadas en árboles.

El problema es el siguiente: desea probar la igualdad estructural casi segura en el tiempo O (1) mediante un hashing fuerte. Si la función hash es estructuralmente recursiva, es decir, hash (x: xs) = mix x (hash xs), puede almacenar en caché de forma transparente los valores hash en las listas y actualizarlos en el momento O (1) cuando un elemento se integra en una lista existente . La mayoría de los algoritmos para las listas de hash son estructuralmente recursivos, por lo que este enfoque es eminentemente utilizable en la práctica.

Pero suponga que, en lugar de listas enlazadas individualmente, tiene secuencias basadas en árboles que admiten la concatenación de dos secuencias de longitud O (n) en el tiempo O (log n). Para que el almacenamiento en caché de hash funcione aquí, la función de mezcla de hash debe ser asociativa para respetar los grados de libertad que tiene un árbol para representar la misma secuencia lineal. El mezclador debe tomar los valores hash de los subárboles y calcular el valor hash de todo el árbol.

Aquí es donde estaba hace seis meses cuando pasé un día reflexionando e investigando este problema. Parece no haber recibido atención en la literatura sobre estructuras de datos. Me encontré con el algoritmo de hash Tillich-Zemor de la criptografía. Se basa en la multiplicación de matriz 2x2 (que es asociativa) donde los bits 0 y 1 corresponden a los dos generadores de un subálgebra con entradas en un campo de Galois.

Mi pregunta es, ¿qué me he perdido? Debe haber documentos relevantes tanto en la literatura sobre criptografía como en las estructuras de datos que no pude encontrar en mi búsqueda. Cualquier comentario sobre este problema y posibles lugares para explorar sería muy apreciado.

Editar: Estoy interesado en esta pregunta tanto en los extremos suaves y criptográficamente fuertes del espectro. En el lado más suave, se puede usar para tablas hash donde se deben evitar colisiones pero no son catastróficas. En el lado más fuerte, puede usarse para pruebas de igualdad.

Por Vognsen
fuente

Respuestas:

2

Agregado : después de leer los comentarios de Per, creo que esta respuesta es solo una variación (pobre) del algoritmo de hash Tillich-Zemor que ya se menciona en la pregunta. Retiro esta respuesta, pero la dejo con la esperanza de que (y los comentarios) puedan ser informativos para algunos lectores.


Editar : una revisión anterior de esta respuesta sugirió usar una operación monoide en [ m ], pero como señaló Per en un comentario, es deseable usar una operación grupal.

Esta respuesta se trata de crear una función hash para tablas hash que sea fácil de implementar. No se espera una garantía demostrable de la calidad.

Suponiendo que ya tiene una función hash para cada elemento de una secuencia en un conjunto finito [ m ] = {1, ..., m }, ¿qué tal interpretar cada elemento de [ m ] como un elemento en un grupo finito G y usar el operación grupal en G ? Puede usar cualquier mapeo desde [ m ] a G , pero es deseable que el mapeo sea inyectivo para que no perdamos la información en el valor hash de cada elemento. También es deseable que el grupo no sea conmutativo para que la función hash pueda detectar la diferencia en el orden de los elementos en una secuencia.

No sé mucho acerca de los grupos finitos que permiten operaciones rápidas, pero supongo que tales grupos son conocidos en la teoría de la codificación. Usar el grupo simétrico de orden al menos m puede no ser tan malo.

Tsuyoshi Ito
fuente
1
Sí, el hash de Tillich-Zemor también usa la multiplicación de matrices. Lo que sugiere no puede funcionar sin más modificaciones a la Tillich-Zemor. Por ejemplo, debe evitar matrices singulares o obtendrá acumulación en 0, arruinando las estadísticas hash. Tillich-Zemor trabaja sobre un campo de Galois; una versión anterior de su algoritmo tenía problemas porque usaban un polinomio generador que tenía estadísticas subóptimas, por lo que el campo particular de Galois puede ser muy importante.
Según Vognsen el
@Per: Ya veo. Gracias por la explicación. Entonces, ¿qué pasa con el uso de cualquier grupo finito? Modifiqué la respuesta a esto.
Tsuyoshi Ito
Estoy de acuerdo. La mejor manera de generar familias infinitas de grupos es con grupos matriciales sobre campos finitos (véase el teorema de clasificación para grupos simples finitos), por lo que parece que los algoritmos de esta forma serán del tipo Tillich-Zemor.
Por Vognsen
@Per: no estoy familiarizado con la teoría de grupos, y no puedo ver por qué los grupos de matrices sobre campos finitos son mejores que los grupos simétricos en este contexto. ¿Puedes explicarlo?
Tsuyoshi Ito
1
Hay un par de razones. Por un lado, no puede calcular de manera eficiente en grandes grupos simétricos, y necesita que los grupos estén en el orden de 2 ^ 128 para resistencia a la colisión. Por el contrario, puede calcular con matrices sobre campos finitos característicos 2 de manera muy eficiente, especialmente si elige un polinomio generador disperso; es solo un montón de pequeñas manipulaciones.
Según Vognsen el
1

La familia casi universal de funciones hash

{ha(x)=aiximodp:aZp}

ha(x)+a|x|ha(y)=ha(xy)a|x|O(1)Zp

xyO(min(|x|,|y|)/p)

jbapple
fuente
1

nn,ny,yny=H(y,y)HO(1)O(lgn)

H(x1,,xm)x1,,xmm

DW
fuente