Come generare un hash univoco per un URL?

Question

Dato queste due immagini da Twitter.

http://a3.twimg.com/profile_images/130500759/lowres_profilepic.jpg 
http://a1.twimg.com/profile_images/58079916/lowres_profilepic.jpg 

Vorrei scaricare loro di filesystem locale & memorizzarli in una singola directory. Come posso superare i conflitti di nome?

Nell'esempio precedente, non posso memorizzarli come lowres_profilepic.jpg. La mia idea di design è considerare gli URL come stringhe opache tranne per l'ultimo segmento. Quali algoritmi (implementati come f) posso utilizzare per hash i prefissi in stringhe univoche.

f("http://a3.twimg.com/profile_images/130500759/") = 6tgjsdjfjdhgf 
f("http://a1.twimg.com/profile_images/58079916/") = iuhd87ysdfhdk 

In questo modo, posso salvare i file come: -

6tgjsdjfjdhgf_lowres_profilepic.jpg 
iuhd87ysdfhdk_lowres_profilepic.jpg 

Non voglio un algoritmo di crittografia in quanto questo deve essere un'operazione performante.

Answer 1

Vedo che la tua domanda è qual è il miglior algoritmo di hash per questa materia. Potresti voler controllare questo Best hashing algorithm in terms of hash collisions and performance for strings

Answer 2

La natura di un hash è che potrebbe causare collisioni. Che ne dici di una di queste alternative:

1. utilizzare un albero di directory. Crea letteralmente sottodirectory per ogni componente dell'URL.
2. Genera un ID univoco. Il problema qui è come mantenere la mappatura tra nome reale e ID salvato. Potresti usare un database che mappa tra un URL e un ID univoco generato. È sufficiente inserire un record in un database che genera ID univoci e quindi utilizzare tale id come nome file.

Answer 3

Uno dei concetti chiave di un URL è che è unico. Perché non usarlo?

Ogni algoritmo che accorcia le informazioni, può produrre collisioni. Forse improbabile, ma comunque possibile

Answer 4

Il sistema di gestione del contenuto git è basato su SHA1 perché ha una probabilità molto piccola di collisione.

Se è buono per git, sarà buono per te.

Answer 5

Un approccio molto semplice:

f("http://a3.twimg.com/profile_images/130500759/") = a3_130500759.jpg 
f("http://a1.twimg.com/profile_images/58079916/") = a1_58079916.jpg 

Come le altre parti di questo URL sono costanti, è possibile utilizzare il sottodominio, l'ultima parte del percorso di query come un nome di file unico.

Non so che cosa potrebbe essere un problema con questa soluzione

Answer 6

Lei ha detto:

Non voglio un algoritmo di crittografia in quanto questo deve essere un'operazione performante.

Bene, capisco il tuo bisogno di velocità, ma penso che tu debba considerare gli inconvenienti del tuo approccio. Se hai solo bisogno di creare l'hash per gli URL, dovresti attenervisi e non scrivere un nuovo algoritmo, per esempio per gestire le collisioni.

Quindi potresti avere un Dictionary<string, string> per funzionare come cache per gli URL. Quindi, quando si ottiene un nuovo indirizzo, si esegue prima una ricerca in tale elenco e, se non trova una corrispondenza, l'hash e lo spazio di archiviazione per l'utilizzo futuro.

Seguendo questa linea, si potrebbe dare una prova MD5:

public static void Main(string[] args) 
{ 
    foreach (string url in new string[]{ 
     "http://a3.twimg.com/profile_images/130500759/lowres_profilepic.jpg", 
     "http://a1.twimg.com/profile_images/58079916/lowres_profilepic.jpg" }) 
    { 
     Console.WriteLine(HashIt(url)); 
    } 
} 

private static string HashIt(string url) 
{ 
    Uri path = new Uri(new Uri(url), "."); 
    MD5CryptoServiceProvider md5 = new MD5CryptoServiceProvider(); 
    byte[] data = md5.ComputeHash(
     Encoding.ASCII.GetBytes(path.OriginalString)); 
    return Convert.ToBase64String(data); 
} 

Otterrete:

rEoztCAXVyy0AP/6H7w3TQ== 
0idVyXLs6sCP/XLBXwtCXA== 

Answer 7

Sembra cosa si vuole veramente è quello di avere un nome di file legale che non lo farà Scontrarsi con gli altri.

• Qualsiasi codifica dell'URL funzionerà, anche base64: ad es. filename = base64(url)
• Un hash crittografico ti darà quello che vuoi - anche se si sostiene che questo sarà un collo di bottiglia, non essere sicuri fino a quando hai benchmark

Answer 8

Mentre CRC32 produce un massimo di 2^32 valori a prescindere del tuo input e quindi non eviterà conflitti, è ancora un'opzione percorribile per questo scenario.

È veloce, quindi se si genera un nome file in conflitto, basta aggiungere/modificare un carattere al proprio URL e semplicemente ricalcolare il CRC.

4.3 miliardi di possibili checksum significano che la probabilità di un conflitto di nome file, se combinata con il nome file originale, sarà così bassa da non essere importante nelle normali situazioni.

Ho usato questo approccio io stesso per qualcosa di simile e sono rimasto soddisfatto della prestazione. Vedere Fast CRC32 in Software.

Answer 9

A prescindere dal come si fa (hashing, la codifica, la ricerca nel database) vi consiglio di non non tenta di connettere un numero enorme di URL di file in una directory grande piatto.

Il motivo è che la ricerca di file per la maggior parte dei file system comporta una scansione lineare attraverso i nomi di file in una directory. Quindi se tutti i N dei tuoi file sono in una directory, una ricerca comporterà in media 1/2 N di confronti; ie O(N) (nota che ReiserFS organizza i nomi in una directory come un BTree.Tuttavia, ReiserFS sembra essere l'eccezione piuttosto che la regola.)

Invece di una grande directory flat, sarebbe meglio mappare gli URI a un albero di directory. A seconda della forma dell'albero, la ricerca può essere pari a O(logN). Ad esempio, se hai organizzato l'albero in modo che avesse 3 livelli di directory con un massimo di 100 voci in ciascuna directory, potresti ospitare 1 milione di URL. Se hai progettato la mappatura per utilizzare nomi di file a 2 caratteri, ciascuna directory dovrebbe essere facilmente inserita in un singolo blocco di disco e una ricerca di percorso (supponendo che le directory richieste siano già memorizzate nella cache) dovrebbe richiedere alcuni microsecondi.

Answer 10

Sembra che la parte numerica degli URL di twimg.com sia già un valore univoco per ciascuna immagine. La mia ricerca indica che il numero è sequenziale (ad es.l'url di esempio qui sotto è per l'immagine del profilo 433.484.366th mai caricata - che capita di essere la mia). Quindi, questo numero è unico. La mia soluzione sarebbe semplicemente usare la parte numerica del nome del file come "valore hash", senza timore di trovare mai un valore non univoco.

• URL: http: //a2.twimg.com/profile_images/433484366/terrorbite-industries-256.png
• Nome file: 433484366.terrorbite-industries-256.png
• ID univoco: 433484366

Ho già utilizzato questo sistema per uno script Python che visualizza notifiche per nuovi tweet e, come parte del suo funzionamento, memorizza nella cache le anteprime dei profili per ridurre i download non necessari.

P.S. Non importa quale sottodominio viene scaricato l'immagine, tutte le immagini sono disponibili da tutti i sottodomini.

Answer 11

Sto giocando con thumbalizr utilizzando una versione modificata del loro script di memorizzazione nella cache, e ho alcune buone soluzioni che penso. Il codice è su github.com/mptre/thumbalizr ma la versione breve è che usa md5 per creare i nomi dei file, e prende i primi due caratteri dal nome del file e lo usa per creare una cartella che ha lo stesso nome . Ciò significa che è facile rompere le cartelle, e veloce per trovare la cartella corrispondente senza un database. Mi ha fatto impazzire la mente con la sua semplicità.

genera i nomi di file come questo http://pappmaskin.no/opensource/delicious_snapcasa/mptre-thumbalizr/cache/fc/fcc3a328e0f4c1b51bf5e13747614e7a_1280_1024_8_90_250.png

l'ultima parte, _1280_1024_8_90_250, corrisponde alle diverse impostazioni che lo script utilizza quando si parla al api Thumbalizr, ma immagino fcc3a328e0f4c1b51bf5e13747614e7a è un md5 rettilineo del URL, in questo caso per thumbalizr.com

ho provato a cambiare la configurazione per generare immagini 200px di larghezza, e che le immagini va nella stessa cartella, ma invece di _250.png si chiama _200.png

non ho avuto il tempo di scavare così tanto dentro il codice, ma sono sicuro che potrebbe essere separato dalla logica thumbalizr e reso più generico.

Answer 12

È possibile utilizzare UUID classe in Java per generare qualsiasi cosa in UUID dal byte che è unico e non sarà avendo un problema con file di ricerca

String url = http://www.google.com; 
String shortUrl = UUID.nameUUIDFromBytes("http://www.google.com".getBytes()).toString();