hachís rodante

Un hash rodante (también conocido como hash recursivo o suma de comprobación rodante) es una función hash en la que la entrada se procesa en una ventana que se mueve a través de la entrada.

Algunas funciones hash permiten calcular un hash continuo muy rápidamente: el nuevo valor hash se calcula rápidamente teniendo en cuenta sólo el valor hash anterior, el valor anterior eliminado de la ventana y el nuevo valor agregado a la ventana, de manera similar a la forma en que la función de media móvil se puede calcular mucho más rápidamente que otros filtros de paso bajo; y similar a la forma en que un hash de Zobrist se puede actualizar rápidamente a partir del valor de hash anterior.

Una de las principales aplicaciones es el algoritmo de búsqueda de cadenas Rabin-Karp , que utiliza el hash rodante que se describe a continuación. Otra aplicación popular es el programa rsync , que utiliza una suma de comprobación basada en adler-32 de Mark Adler como hash rodante. El sistema de archivos de red de bajo ancho de banda (LBFS) utiliza una huella digital de Rabin como hash rodante. FastCDC (Fast Content-Defined Chunking) utiliza una huella digital Gear eficiente en computación como hash rodante.

En el mejor de los casos, los valores hash rodantes son independientes por pares ^[1] o fuertemente universales . No pueden ser independientes en tres sentidos , por ejemplo.

Hash rodante polinomial

El algoritmo de búsqueda de cadenas Rabin-Karp a menudo se explica mediante una función hash rodante que solo utiliza multiplicaciones y sumas:

${\displaystyle H=c_{1}a^{k-1}+c_{2}a^{k-2}+c_{3}a^{k-3}+...+c_{k}a^{0}}$,

donde es una constante y son los caracteres de entrada (pero esta función no es una huella digital de Rabin , ver más abajo). ${\displaystyle a}$ ${\displaystyle c_{1},...,c_{k}}$

Para evitar manipular valores enormes, todos los cálculos se realizan en módulo . La elección de y es fundamental para conseguir un buen hash; en particular, el módulo suele ser un número primo. Consulte el generador congruencial lineal para obtener más información. ${\displaystyle H}$ ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle n}$ ${\displaystyle n}$

Quitar y agregar caracteres simplemente implica sumar o restar el primer o último término. Para desplazar todos los caracteres una posición hacia la izquierda es necesario multiplicar la suma completa por . Para desplazar todos los caracteres una posición hacia la derecha es necesario dividir la suma completa entre . Tenga en cuenta que en aritmética de módulo, se puede elegir tener un inverso multiplicativo por el cual se puede multiplicar para obtener el resultado de la división sin realizar realmente una división. ${\displaystyle H}$ ${\displaystyle a}$ ${\displaystyle H}$ ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle a^{-1}}$ ${\displaystyle H}$

huella digital de rabin

La huella digital de Rabin es otro hash, que también interpreta la entrada como un polinomio, pero sobre el campo de Galois GF(2) . En lugar de ver la entrada como un polinomio de bytes, se ve como un polinomio de bits, y toda la aritmética se realiza en GF(2) (de manera similar a CRC32 ). El hash es el resultado de la división de ese polinomio por un polinomio irreducible sobre GF(2). Es posible actualizar una huella digital de Rabin utilizando solo el byte de entrada y de salida, lo que la convierte efectivamente en un hash rodante.

Debido a que comparte el mismo autor que el algoritmo de búsqueda de cadenas Rabin-Karp, que a menudo se explica con otro hash rodante más simple, y debido a que este hash rodante más simple también es un polinomio, ambos hashes rodantes a menudo se confunden entre sí. El software de respaldo restic utiliza una huella digital de Rabin para dividir archivos, con un tamaño de blob que varía entre 512 KiB y 8 MiB . ^[2]

Polinomio cíclico

El hash mediante polinomio cíclico ^[3] , a veces llamado Buzhash, también es simple, pero tiene la ventaja de evitar multiplicaciones y, en su lugar, utiliza desplazamientos de barril . Es una forma de hash de tabulación : supone que hay alguna función hash desde caracteres hasta números enteros en el intervalo . Esta función hash podría ser simplemente una matriz o una tabla hash que asigna caracteres a números enteros aleatorios. Sea la función una rotación binaria cíclica (o desplazamiento circular ): gira los bits 1 hacia la izquierda, empujando el último bit a la primera posición. P.ej, . Sea el exclusivo bit a bit o . Los valores hash se definen como ${\displaystyle h}$ ${\displaystyle [0,2^{L})}$ ${\displaystyle s}$ ${\displaystyle s(101)=011}$ ${\displaystyle \oplus }$

${\displaystyle H=s^{k-1}(h(c_{1}))\oplus s^{k-2}(h(c_{2}))\oplus \ldots \oplus s(h(c_{k-1}))\oplus h(c_{k}),}$

donde las multiplicaciones por potencias de dos se pueden implementar mediante desplazamientos binarios. El resultado es un número en . ${\displaystyle [0,2^{L})}$

El cálculo de los valores hash de forma continua se realiza de la siguiente manera. Sea el valor hash anterior. Girar una vez: . Si es el personaje que se va a eliminar, gírelo varias veces: . Luego simplemente establezca ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle H\leftarrow s(H)}$ ${\displaystyle c_{1}}$ ${\displaystyle k}$ ${\displaystyle s^{k}(h(c_{1}))}$

${\displaystyle H\leftarrow s(H)\oplus s^{k}(h(c_{1}))\oplus h(c_{k+1}),}$

¿ Dónde está el nuevo personaje? ${\displaystyle c_{k+1}}$

El hash mediante polinomios cíclicos es fuertemente universal o independiente por pares: simplemente mantenga los primeros bits. Es decir, tomar el resultado y descartar los bits consecutivos. ^[1] En la práctica, esto se puede lograr mediante una división de números enteros . ${\displaystyle L-k+1}$ ${\displaystyle H}$ ${\displaystyle k-1}$ ${\displaystyle H\rightarrow H\div 2^{k-1}}$

Corte basado en contenido usando un hash rodante

Uno de los casos de uso interesantes de la función hash rodante es que puede crear fragmentos dinámicos basados ​​en contenido de una secuencia o archivo. Esto es especialmente útil cuando se requiere enviar solo los fragmentos modificados de un archivo grande a través de una red: una simple adición de un byte al frente del archivo normalmente haría que todas las ventanas de tamaño fijo se actualizaran, mientras que en realidad, solo la primera "trozo" ha sido modificado. ^[4]

Un enfoque simple para crear fragmentos dinámicos es calcular un hash rodante, y si el valor hash coincide con un patrón arbitrario (por ejemplo, todos ceros) en los N bits inferiores (con una probabilidad de , dado que el hash tiene una distribución de probabilidad uniforme), entonces es elegido para ser un límite de fragmento. Por tanto, cada fragmento tendrá un tamaño medio de bytes. Este enfoque garantiza que los datos no modificados (a más de un tamaño de ventana de distancia de los cambios) tendrán los mismos límites. ${\textstyle {1 \over 2^{n}}}$ ${\textstyle 2^{n}}$

Una vez que se conocen los límites, los fragmentos deben compararse mediante el valor hash criptográfico para detectar cambios. ^[5] El software de copia de seguridad Borg utiliza el algoritmo Buzhash con un rango de tamaño de fragmento personalizable para dividir secuencias de archivos. ^[6]

Esta fragmentación definida por contenido se utiliza a menudo para la deduplicación de datos . ^{[4] [6]}

División basada en contenido usando suma móvil

Varios programas, incluidos gzip (con la --rsyncableopción) y rsyncrypto, realizan divisiones basadas en contenido en función de esta suma móvil específica (no ponderada): ^[7]

${\displaystyle S(n)=\sum _{i=n-8195}^{n}c_{i},}$

${\displaystyle H(n)=S(n)\mod 4096,}$

dónde

• ${\displaystyle S(n)}$es la suma de 8196 bytes consecutivos que terminan en byte (requiere 21 bits de almacenamiento), ${\displaystyle n}$
• ${\displaystyle c_{i}}$es un byte del archivo, ${\displaystyle i}$
• ${\displaystyle H(n)}$es un "valor hash" que consta de los 12 bits inferiores de . ${\displaystyle S(n)}$

Cambiar la ventana un byte simplemente implica agregar el nuevo carácter a la suma y restar el carácter más antiguo (que ya no está en la ventana) de la suma.

Para todos los lugares , estos programas cortan el archivo entre y . Este enfoque garantizará que cualquier cambio en el archivo solo afecte a su fragmento actual y posiblemente al siguiente, pero no a ningún otro fragmento. ${\displaystyle n}$ ${\displaystyle H(n)==0}$ ${\displaystyle n}$ ${\displaystyle n+1}$

Huella digital de engranajes y algoritmo de fragmentación basado en contenido FastCDC

Chunking es una técnica para dividir un flujo de datos en un conjunto de bloques, también llamados fragmentos. La fragmentación definida por contenido (CDC) es una técnica de fragmentación en la que la división del flujo de datos no se basa en un tamaño de fragmento fijo, como en la fragmentación de tamaño fijo, sino en su contenido.

El algoritmo de fragmentación definido por contenido necesita calcular el valor hash de un flujo de datos byte a byte y dividir el flujo de datos en fragmentos cuando el valor hash cumple con un valor predefinido. Sin embargo, comparar una cadena byte por byte introducirá una gran sobrecarga de cálculo. FastCDC ^[8] propone un enfoque nuevo y eficiente de fragmentación definida por contenido. Utiliza un algoritmo hash Gear de avance rápido, ^[9] omitiendo la longitud mínima, normalizando la distribución del tamaño de los fragmentos y, por último, pero no menos importante, lanzando dos bytes cada vez para acelerar el algoritmo CDC, que puede lograr un rendimiento aproximadamente 10 veces mayor. que el enfoque de los CDC basado en Rabin. ^[10]

El pseudocódigo de la versión básica se proporciona de la siguiente manera:

algoritmo de entrada FastCDC : búfer de datos src , longitud de datos n , salida: punto de corte i  MinSize ← 2 KB // el tamaño mínimo del fragmento dividido es 2 KB MaxSize ← 64 KB // el tamaño máximo del fragmento dividido es 64 KB Máscara ← 0x0000d93003530000LL  fp ← 0  i ← 0  // el tamaño del buffer es menor que el tamaño mínimo del fragmento si  n ≤ MinSize  entonces  devuelve  n  si  n ≥ MaxSize  entonces  n ← MaxSize  // Omita los primeros bytes de MinSize e inicie el hash
    mientras  i < MinSize  hace  fp ← ( fp << 1 ) + Gear [ src [ i ]] i ← i + 1     mientras que  i < n  haz  fp ← ( fp << 1 ) + Gear [ src [ i ]] si  !( fp & Mask ) entonces  regresa  i  i ← i + 1    volver  yo

Donde Gear array es una matriz hash precalculada. Aquí, FastCDC utiliza el algoritmo de hash Gear que puede calcular los resultados del hash continuo rápidamente y mantener la distribución uniforme de los resultados del hash como Rabin. En comparación con el algoritmo hash tradicional de Rabin, logra una velocidad mucho más rápida. Los experimentos sugieren que puede generar casi la misma distribución de tamaño de fragmentos en un tiempo mucho más corto (aproximadamente 1/10 de los fragmentos basados ​​en rabin ^[10] ) al segmentar el flujo de datos.

Complejidad computacional

Todas las funciones hash rodantes se pueden calcular en tiempo lineal en el número de caracteres y actualizarse en tiempo constante cuando los caracteres se desplazan una posición. En particular, calcular el hash rodante de Rabin-Karp de una cadena de longitud requiere operaciones aritméticas modulares, y el hash mediante polinomios cíclicos requiere or exclusivos bit a bit y desplazamientos circulares . ^[1] ${\displaystyle k}$ ${\displaystyle O(k)}$ ${\displaystyle O(k)}$

Ver también

• MinHash  – Técnica de minería de datos
• w-tejas

Notas a pie de página

1. Daniel Lemire, Owen Kaser: El hash recursivo de n -gramas es, en el mejor de los casos, independiente por pares, Computer Speech & Language 24 (4), páginas 698–710, 2010. arXiv:0705.4676.
2. "Referencias: documentación restic 0.9.0". restic.readthedocs.io . Consultado el 24 de mayo de 2018 .
3. Jonathan D. Cohen, Funciones hash recursivas para n -Gramos, ACM Trans. inf. Sistema. 15 (3), 1997.
4. "Fundación: Presentación de la fragmentación definida por contenido (CDC)". 2015.
5. Horvath, Adam (24 de octubre de 2012). "Rabin Karp Rolling Hash: fragmentos de tamaño dinámico basados ​​en contenido hash".
6. "Estructuras de datos y formatos de archivo - Borg - Documentación de Deduplicating Archiver 1.1.5". borgbackup.readthedocs.io . Consultado el 24 de mayo de 2018 .
7. "Algoritmo Rsyncrypto".
8. Xia, Wen; Zhou, Yukun; Jiang, Hong; Feng, Dan; Hua, Yu; Hu, Yuchong; Liu, Qing; Zhang, Yucheng (2005). FastCDC: un enfoque de fragmentación definido por contenido rápido y eficiente para la deduplicación de datos. ISBN 9781931971300. Consultado el 24 de julio de 2020 . {{cite book}}: |website=ignorado ( ayuda )
9. Xia, Wen; Jiang, Hong; Feng, Dan; Tian, ​​Lei; Fu, Min; Zhou, Yukun (2014). "Ddelta: un enfoque de compresión delta rápida inspirado en la deduplicación". Evaluación del desempeño . 79 : 258–272. doi :10.1016/j.peva.2014.07.016. ISSN  0166-5316.
10. Xia, Wen; Zou, Xiangyu; Jiang, Hong; Zhou, Yukun; Liu, Chuanyi; Feng, Dan; Hua, Yu; Hu, Yuchong; Zhang, Yucheng (16 de junio de 2020). "El diseño de fragmentación rápida definida por contenido para sistemas de almacenamiento basados ​​en deduplicación de datos". Transacciones IEEE en sistemas paralelos y distribuidos . 31 (9): 2017-2031. doi :10.1109/TPDS.2020.2984632. S2CID  215817722 . Consultado el 22 de julio de 2020 .

enlaces externos

• MIT 6.006: Introducción a los algoritmos 2011 - Recitación 9 - Rolling Hash