Esiste un algoritmo "anti-hash" o "similarity hash" / similarity measure?

The idea of hashes is they get drastically different results for even the smallest change of data.

No, non lo è.

L'idea degli hash è che mappano uno spazio di input più ampio, potenzialmente infinito, in uno spazio di output più piccolo, finito e solitamente fisso. Per esempio. SHA-3 mappa infinitamente molte stringhe di ottetti in 2 ⁵¹² bitstrings.

Ciò di cui stai parlando è una delle proprietà di un digest del messaggio crittograficamente sicuro , che è un caso speciale (molto piccolo) di una funzione hash.

Ad esempio, le funzioni di hash (ovvero le impronte digitali) utilizzate per rilevare le violazioni del copyright sulle piattaforme di video online sarebbero inutili se avessero questa proprietà.

Una delle funzioni di hash più conosciute che ha la proprietà opposta, ovvero che input simili generano output simili, è soundex: un algoritmo che produce valori hash simili per parole che sembrano simili.

What I am asking for is the opposite of that. An algorithm that will produce proximity hash values for data that is approximately the same. Regardless of where the difference is, to only measure the extent of the difference, and the resulting hash value is closer or further from the original hash value depending on whether the second data set is more or less similar to the original.

Questo suona più come una misura di somiglianza che una funzione di hash. In particolare, nella tua descrizione non c'è nulla che implichi uno spazio di output limitato, di dimensioni fisse.

Ciò di cui stai parlando è Analisi cluster .

Cluster analysis or clustering is the task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more similar (in some sense or another) to each other than to those in other groups (clusters).

Ci sono numerosi approcci a questo, come k-means clustering .

Si chiama Hashing percettivo

link

pHash: una libreria hash percettiva open source link

Blockhash.io: uno standard aperto per gli hash percettivi link

Insight: un tutorial di hash percettivo link

Probabilmente non è quello che vuoi, ma dal momento che è interessante, ho pensato di farlo apparire. In realtà circa un decennio fa è stato prodotto qualcosa chiamato Metrica di similarità (vedi anche Clustering per compressione ). L'idea è data x e y vogliamo calcolare la lunghezza del programma più breve che produce x dato y e y dati x (modulo alcuni fattori fondali). Se normalizziamo questo in modo appropriato, otteniamo una buona nozione di somiglianza relativa. Tuttavia, questa nozione è definita in termini di complessità di Kolmogorov che non è calcolabile, quindi questo in realtà non produce un algoritmo utilizzabile. Dobbiamo invece approssimarlo. Questo porta alla distanza di compressione normalizzata che è semplicemente:

NCD(x,y) = (C(x++y) - min(C(x),C(y))/max(C(x),C(y))

dove x++y rappresenta la concatenazione di x e y visualizzati come sequenze di bit. E, soprattutto, C(x) rappresenta la lunghezza in bit della rappresentazione compressa di x per un algoritmo di compressione (che si comporta appropriatamente) C . Fondamentalmente, se si prende un algoritmo di compressione, come gzip , si può semplicemente comprimere ogni input e la loro concatenazione e usare la formula sopra per ottenere un numero razionale tra 0 e 1 che indica come "simili" sono. (È quindi possibile arrotondare quel numero razionale al numero di punto fisso più vicino per un dato numero di bit per ottenere un output a dimensione fissa.) Ciò presuppone che ogni bit sia significativo. Potrebbe avere senso "normalizzare" l'input (ad esempio rimuovendo spazi bianchi estranei o filtri passa-basso) per evitare differenze spurie. Concettualmente, questo può essere piegato nell'algoritmo di compressione. Ciò fa notare che questa nozione di somiglianza varia con l'algoritmo di compressione, sebbene gli algoritmi di compressione generici siano spesso adeguati. Alcuni strumenti per farlo sono qui , anche se sarebbe facile eseguire il rollover.

Sospetto che un vero compressore sarà "troppo buono" per trovare somiglianze con i tuoi scopi. Cioè, troverà la somiglianza tra le cose che non vuoi considerare simili. Potrebbe essere tecnicamente risolvibile con una scelta adeguata di compressore, ma l'uso di qualche altra metrica potrebbe avere più senso di ciò.

Come altri hanno detto che una metrica di similarità è ciò che probabilmente vuoi. Tu dici di avere array di byte. Assumerò che gli array possono essere di lunghezze disuguali ma anche se sono sempre di uguale lunghezza non è molto diverso. Vorrei iniziare con una metrica semplice come la somiglianza del coseno. Tu dici che l'ordine non è importante, solo il numero di volte in cui un valore appare nell'array è.

Quindi assumiamo un byte compreso tra -128 e 127. Trasformerei i due array in un vettore all'interno di uno spazio euclideo di 256 dimensioni. Qui il valore del nuovo vettore [i] è il conteggio del numero di volte -128 + appare nell'array originale. Per semplicità assumeremo rappresentazioni vettoriali sparse.

Ora entrambi gli array si trovano nello stesso spazio dimensionale. Ora puoi calcolare la similarità del coseno nelle nuove rappresentazioni. Poiché la somiglianza del coseno è legata naturalmente [-1,1], allora sappiamo che due matrici di una similarità di 1 sono uguali e due matrici di similarità di -1 sono perfettamente dissimili.

Questo ti darebbe una similitudine di 1 per ogni due dei 3 seguenti array [1,2,3] [2,3,1] e [3,1,2] per esempio.

Potresti prendere in considerazione una funzione di correlazione . Un semplice esempio è la cross correlation .

Questi metodi forniscono una misura di somiglianza e sono generalmente invariabili alla traduzione (il che significa che le compensazioni di dati - come hai descritto nel tuo commento - sarebbero irrilevanti)