Hachís rodante

Tipo de función hash

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

Algunas funciones hash permiten calcular un hash móvil muy rápidamente: el nuevo valor hash se calcula rápidamente dado solo el valor hash antiguo, el valor antiguo se elimina de la ventana y el nuevo valor se agrega a la ventana, de manera similar a la forma en que una función de promedio móvil se puede calcular mucho más rápidamente que otros filtros de paso bajo; y de manera similar a la forma en que un hash Zobrist se puede actualizar rápidamente a partir del valor hash antiguo.

Una de las principales aplicaciones es el algoritmo de búsqueda de cadenas Rabin–Karp , que utiliza el hash rotativo descrito 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 su hash rotativo. El sistema de archivos de red de bajo ancho de banda (LBFS) utiliza una huella digital de Rabin como su hash rotativo. FastCDC (Fast Content-Defined Chunking) utiliza una huella digital de Gear de computación eficiente como su hash rotativo.

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

Hash de polinomios

El algoritmo de búsqueda de cadenas de Rabin-Karp se explica a menudo utilizando una función hash continua 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 obtener 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}$

Para quitar y agregar caracteres, simplemente hay que sumar o restar el primer o el último término. Para desplazar todos los caracteres una posición hacia la izquierda, es necesario multiplicar la suma total por . Para desplazar todos los caracteres una posición hacia la derecha, es necesario dividir la suma total por . Tenga en cuenta que, en aritmética de módulo, se puede elegir que haya 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 dactilar de Rabin

La huella 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 de Rabin utilizando solo el byte de entrada y el de salida, lo que lo convierte en un hash continuo.

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 rotatorio más simple, y debido a que este hash rotatorio más simple también es un polinomio, ambos hashes rotatorios a menudo se confunden entre sí. El software de respaldo restic usa una huella digital 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 por polinomio cíclico ^[3] —a veces llamado Buzhash— también es simple y tiene el beneficio de evitar multiplicaciones, utilizando en su lugar desplazamientos de barril . Es una forma de hash de tabulación : presupone que hay alguna función hash de caracteres a números enteros en el intervalo . Esta función hash puede 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 ): rota los bits en 1 hacia la izquierda, empujando el último bit a la primera posición. Por ejemplo, . Sea el bit exclusivo 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. Gire una vez: . ​​Si es el carácter 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 de pares: simplemente se conservan los primeros bits. Es decir, se toma el resultado y se descartan los bits consecutivos. ^[1] En la práctica, esto se puede lograr mediante una división entera . ${\displaystyle L-k+1}$ ${\displaystyle H}$ ${\displaystyle k-1}$ ${\displaystyle H\rightarrow H\div 2^{k-1}}$

Segmentación basada en contenido mediante un hash continuo

Uno de los casos de uso interesantes de la función hash continua es que puede crear fragmentos dinámicos basados ​​en contenido de un flujo 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 bytes al principio del archivo normalmente haría que se actualizaran todas las ventanas de tamaño fijo, mientras que en realidad, solo se ha modificado el primer "fragmento". ^[4]

Un enfoque simple para crear fragmentos dinámicos es calcular un hash continuo y, si el valor del 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 se elige como límite del fragmento. Por lo tanto, cada fragmento tendrá un tamaño promedio de bytes. Este enfoque garantiza que los datos no modificados (a más de un tamaño de ventana 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, es necesario comparar los fragmentos mediante un valor hash criptográfico para detectar cambios. ^[5] El software de respaldo Borg utiliza el algoritmo Buzhash con un rango de tamaño de fragmento personalizable para dividir flujos de archivos. ^[6]

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

Segmentación basada en contenido mediante suma móvil

Varios programas, incluidos gzip (con la --rsyncableopción) y rsyncrypto, realizan segmentaciones basadas en contenido basándose en 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 byte del archivo, ${\displaystyle i}$
• ${\displaystyle H(n)}$es un "valor hash" que consta de los 12 bits inferiores de . ${\displaystyle S(n)}$

Desplazar 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.

En todos los casos , estos programas cortan el archivo entre y . Este enfoque garantizará que cualquier cambio en el archivo solo afecte al fragmento actual y posiblemente al siguiente, pero 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

La fragmentación es una técnica que permite 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 Content-Defined Chunking necesita calcular el valor hash de un flujo de datos byte por byte y dividir el flujo de datos en fragmentos cuando el valor hash coincide con un valor predefinido. Sin embargo, comparar una cadena byte por byte introducirá una gran sobrecarga de cálculo. FastCDC ^[8] propone un nuevo y eficiente enfoque de Content-Defined Chunking. Utiliza un algoritmo hash Gear de rápido desplazamiento, ^[9] omitiendo la longitud mínima, normalizando la distribución del tamaño de los fragmentos y, por último, pero no menos importante, desplazando dos bytes cada vez para acelerar el algoritmo CDC, que puede lograr un rendimiento aproximadamente 10 veces mayor que el enfoque CDC basado en Rabin. ^[10]

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

algoritmo FastCDC entrada: 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 Mask ← 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  // Omite los primeros bytes de MinSize y activa el hash
    mientras  i < MinSize  haga  fp ← ( fp << 1 ) + Gear [ src [ i ]] i ← i + 1     mientras  i < n  hacer  fp ← ( fp << 1 ) + Gear [ src [ i ]] si  !( fp & Mask ) entonces  devuelve  i  i ← i + 1    devuelvo  yo

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

Complejidad computacional

Todas las funciones hash rotativas 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, el cálculo del hash rotativo de Rabin-Karp de una cadena de longitud requiere operaciones aritméticas modulares, y el hash mediante polinomios cíclicos requiere operaciones OR exclusivas bit a bit y desplazamientos circulares . ^[1] ${\displaystyle k}$ ${\displaystyle O(k)}$ ${\displaystyle O(k)}$

Véase también

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

Notas al pie

1. Daniel Lemire, Owen Kaser: El hashing recursivo de n -gramas es independiente por pares, en el mejor de los casos, Computer Speech & Language 24 (4), páginas 698–710, 2010. arXiv:0705.4676.
2. "Referencias — documentación de 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. Syst. 15 (3), 1997.
4. "Fundación: Introducción a 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 — Documentación de Borg - 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. Asociación Usenix. ISBN 9781931971300. Recuperado 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 rendimiento . 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". IEEE Transactions on Parallel and Distributed Systems . 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