algoritmo para determinar la identidad de un archivo (Optimización)

Question

En relación con esta pregunta: Algorithm for determining a file’s identity

Crónica: Estoy buscando un algoritmo barato para determinar una identidad de archivos que trabaja la gran mayoría de las veces.

Seguí adelante e implementé un algoritmo que me da un "bastante único" hash por archivo.

La forma en que funciona mi algoritmo es:

• Para archivos más pequeños que un cierto umbral uso el contenido de archivos completo para el hash identidad.

• Para archivos mayores que el umbral, tomo N muestras aleatorias de tamaño X.

• Incluyo el tamaño del archivo en los datos hash. (Es decir, todos los archivos con diferentes tamaños resultan en un hash diferente)

Preguntas:

• ¿Qué valores debería elegir para N y X (el número de muestras al azar debo tomar de qué tamaño?) Fui con 4 muestras de 8K cada una y no puedo copiar el algoritmo. Descubrí que aumentar la cantidad de muestras disminuye rápidamente la velocidad del algoritmo (porque las búsquedas son bastante caras)

• El matemático: cómo mis archivos deben ser diferentes para que este algoritmo explote. (2 archivos diferentes con la misma longitud terminan teniendo el mismo hash)

• Optimización: ¿Hay alguna manera en que pueda optimizar mi implementación concreta para mejorar el rendimiento (creo que puedo hacer unos 100 archivos por segundo en mi sistema).

• ¿Esta implementación parece sensata? ¿Puedes pensar en algún ejemplo del mundo real donde esto fracase? (Mi atención se centra en los archivos de medios)

Información relevante:

The algorithm I implemented

Gracias por su ayuda!

Answer 1

• Siempre incluya el primer y último bloque de archivos en hash.

Esto se debe a que es más probable que sean diferentes de un archivo a otro. Si considera BMP, puede tener un encabezado bastante estándar (como 800x600 de imagen, 24 bits, nulo de descanso), por lo que es posible que desee sobrepasar el encabezado un poco para llegar a los datos de diferenciación. El problema es que los encabezados varían mucho en tamaño.

El último bloque es para formatos de archivo que anexan datos al original.

• Leer en bloques de tamaño que es nativa al sistema de archivos que utiliza, o al menos divisible por 512.
• Lea siempre bloques en el desplazamiento que es divisible por tamaño de bloque.
• Si obtiene lo mismo que para el mismo archivo de tamaño, haga un escaneo profundo del mismo (compruebe todos los datos) y memorice el archivo para no volver a escanearlo.

Incluso entonces, a menos que estés suerte podrá identificar erróneamente algunos archivos como lo mismo (por ejemplo, archivos de base de datos SQL Server y es 1: 1 copia de seguridad copia después de sólo unas pocas inserciones, excepto que SS hace escribir una marca de tiempo ..)

Answer 2

Evitaría una solución como esta. Practico que podría ser casi imposible que dos archivos de medios tengan el mismo tamaño y los mismos datos en las posiciones correspondientes para formatos comprimidos. Pero si tiene que lidiar con imágenes sin comprimir o archivos de onda, aumentan las posibilidades de que no se detecten pequeños cambios locales.

Así que creo que realmente debería hash todo el archivo. Si bien esto parece caro, podría no serlo si tiene acceso a todos los archivos, por ejemplo, si crea un servidor de archivos o algo así. Podrías construir el hash de manera incremental.

Si ve un archivo nuevo con una longitud de archivo única, simplemente almacene la longitud del archivo. Si se agrega otro archivo con la misma longitud, calcule los valores hash de ambos archivos bloque por bloque hasta que difieran.Almacene la longitud del archivo, el hash y cuántos bloques del archivo se incluyen en el hash. Siempre que detecte longitudes y hashes de archivos coincidentes y aún no haya procesado todo el archivo, extienda el hash agregando más bloques.

Algunas reflexiones sobre el rendimiento. Para archivos pequeños, las posibilidades de una longitud de archivo igual son bastante altas: no hay tantas longitudes de archivo pequeñas diferentes. Pero no es costoso cortar archivos pequeños.

Para archivos más grandes, las posibilidades de colisiones de longitud de archivo disminuyen ya que hay más y más longitudes de archivo posibles. En el caso de los archivos de medios diferentes, hay muchas posibilidades de que difieran directamente del encabezado, por lo que solo deberá ajustar una parte breve del inicio del archivo.

Por último, se asegurará de que usted detecte los diferentes archivos (excepto colisiones hash) ya que de lo contrario se obtendrá todo el archivo si es necesario.

ACTUALIZACIÓN

Para las películas que consideraría la longitud del fichero práctica única, pero los archivos recodificados para caber en un medio dado, probablemente, render esta idea de vacío - (S) películas VCD estar todos en una pequeña gama de longitud de archivos de aproximadamente la capacidad del CD-ROM.

Pero para los archivos de películas en general, me gustaría simplemente hash un bloque (tal vez 512 Byte) desde el medio del archivo. ¿Dos películas diferentes con la misma imagen y sonido en la misma posición? Prácticamente imposible además de manipular archivos para fallar esta prueba. Pero podría generar fácilmente archivos para fallar en todas las estrategias de muestreo deterministas, por lo que esto realmente no debería importar.

Answer 3

1. No busque hacia atrás y abra el archivo con FILE_FLAG_SEQUENTIAL_SCAN (en Windows).
   (Seleccione X números aleatorios y luego ordénelos).
2. Para buscar lejos, usualmente hay algunos datos en el caché de lectura anticipada.
3. Si tiene archivos grandes, formatee su partición para que tenga un tamaño de sector grande.
4. Usted devuelve un Guid para el ID, algoritmos de hash must necesitan más de 128 bits.