Jak wygenerować unikatowy skrót dla adresu URL?

Question

Biorąc pod uwagę te dwa obrazy ze Twittera.

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

Chcę pobrać je do lokalnego systemu plików & przechowywać je w jednym katalogu. Jak mogę pokonać konflikty nazw?

W powyższym przykładzie nie mogę zapisać ich jako lowres_profilepic.jpg. Mój pomysł na projekt traktuje adresy URL jako nieprzejrzyste ciągi z wyjątkiem ostatniego segmentu. Jakie algorytmy (zaimplementowane jako f) można użyć do zaszyfrowania prefiksów w unikatowe ciągi.

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

ten sposób mogę zapisać pliki jako: -

6tgjsdjfjdhgf_lowres_profilepic.jpg 
iuhd87ysdfhdk_lowres_profilepic.jpg 

Nie chcę algorytm kryptograficzny, ponieważ musi to być wydajnych operacji.

Answer 1

Widzę twoje pytanie, jaki jest najlepszy algorytm skrótu w tej sprawie. Możesz sprawdzić to: Best hashing algorithm in terms of hash collisions and performance for strings

Answer 2

Charakter mieszania jest taki, że może powodować kolizje. Co powiesz na jedną z tych opcji:

1. użyć drzewa katalogów. Dosłownie tworzyć podkatalogi dla każdego komponentu adresu URL.
2. Generowanie identyfikatora unikalnego. Problem polega na tym, jak zachować odwzorowanie między prawdziwą nazwą a zapisanym identyfikatorem. Można użyć bazy danych, która mapuje między adresem URL a wygenerowanym unikalnym identyfikatorem. Możesz po prostu wstawić rekord do bazy danych, która generuje unikalne identyfikatory, a następnie użyć tego identyfikatora jako nazwy pliku.

Answer 3

Jedną z kluczowych koncepcji adresu URL jest to, że jest unikalny. Dlaczego jej nie użyć?

Każdy algorytm, który skraca informacje, może powodować kolizje. Być może jest to mało prawdopodobne, ale możliwe, że jest to możliwe.

Answer 4

System zarządzania treścią git oparty jest na SHA1, ponieważ ma on bardzo małą szansę na kolizję.

Jeśli to dobrze dla gita, będzie to dla ciebie dobre.

Answer 5

bardzo proste podejście:

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

Ponieważ pozostałe części tego adresu URL są stałe, można użyć subdomenę, ostatnią część ścieżki zapytań jako unikalnej nazwy pliku.

Nie wiem, co może być problem z tym rozwiązaniem

Answer 6

Mówiłeś:

Nie chcę algorytm kryptograficzny, ponieważ musi to być wydajnych operacji.

Cóż, rozumiem twoją potrzebę szybkości, ale myślę, że musisz wziąć pod uwagę wady ze swojego podejścia. Jeśli potrzebujesz tylko utworzyć hash dla adresów URL, powinieneś trzymać się go i nie pisać nowego algorytmu, na przykład gdy będziesz musiał uporać się z kolizjami.

Dzięki temu możesz mieć Dictionary<string, string> działać jako pamięć podręczna dla adresów URL. Tak więc, gdy otrzymasz nowy adres, najpierw wykonaj odnośnik na tej liście, a jeśli nie znajdziesz pasującego, skopiuj go i przechowuj do wykorzystania w przyszłości.

Po tej linii, można dać MD5 spróbować:

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); 
} 

otrzymasz:

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

Answer 7

Wydaje się, czego naprawdę chcę to mieć nazwę pliku prawnej, które nie będą zderzaj się z innymi.

• Wszystkie kodowanie adresu URL będzie działać, nawet base64: np. filename = base64(url)
• crypto hash da ci to, czego chcą - choć twierdzą, że będzie to wąskie gardło wydajności, nie bądź pewien, dopóki nie porównywana

Answer 8

Podczas CRC32 produkuje maksymalnych wartości 2^32 niezależnie danych wejściowych, a więc nie uniknie konfliktów, nadal jest realną opcją dla tego scenariusza.

Jest szybki, więc jeśli generujesz plik, który powoduje konflikty, po prostu dodaj/zmień znak na adres URL i po prostu spróbuj ponownie skalować CRC.

4,3 miliarda możliwych sum kontrolnych oznacza, że ​​prawdopodobieństwo konfliktu nazw plików w połączeniu z oryginalną nazwą pliku będzie tak niskie, że będzie nieistotne w normalnych sytuacjach.

Użyłem tego podejścia dla czegoś podobnego i byłem zadowolony z wykonania. Zobacz Fast CRC32 in Software.

Answer 9

Niezależnie od tego, jak to zrobić (mieszania, kodowania, przeszukiwania bazy danych) to polecam nie starają się odwzorować ogromną liczbę adresów URL do plików w dużym katalogu płaskiej.

Powód jest taki, że wyszukiwanie plików w większości systemów plików wymaga skanowania liniowego przez nazwy plików w katalogu. Jeśli więc wszystkie N twoich plików znajdują się w jednym katalogu, wyszukiwanie będzie wymagało średnio 1/2 porównań; tj. O(N) (Zauważ, że ReiserFS porządkuje nazwy w katalogu jako BTree, jednak ReiserFS wydaje się raczej wyjątkiem, niż regułą.)

Zamiast jednego dużego płaskiego katalogu, lepiej byłoby zmapować identyfikatory URI do drzewo katalogów. W zależności od kształtu drzewa wyszukiwanie może być równie dobre jak O(logN). Na przykład, jeśli zorganizowałeś drzewo w taki sposób, aby miało 3 poziomy katalogu z co najwyżej 100 pozycjami w każdym katalogu, możesz umieścić 1 milion adresów URL. Jeśli zaprojektowałeś mapowanie tak, aby używało nazw plików 2-znakowych, każdy katalog powinien łatwo zmieścić się w bloku pojedynczego dysku, a wyszukiwanie nazwy ścieżki (zakładając, że wymagane katalogi są już buforowane) powinno zająć kilka mikrosekund.

Answer 10

Wygląda na to, że część liczbowa adresów URL twimg.com jest już unikatową wartością dla każdego obrazu. Moje badania wskazują, że liczba jest sekwencyjna (tj.Poniższy przykładowy adres URL dotyczy 433,484,366 obrazu profilowego, który kiedykolwiek został przesłany - co właśnie stało się moje. Tak więc ta liczba jest wyjątkowa. Moim rozwiązaniem byłoby po prostu użycie numerycznej części nazwy pliku jako "wartości mieszania", bez obawy, że kiedykolwiek znajdzie ona nieunikalną wartość.

• URL: http: //a2.twimg.com/profile_images/433484366/terrorbite-industries-256.png
• Nazwa pliku: 433484366.terrorbite-przemysłowa-256.png
• unikatowy identyfikator: 433484366

Już używam tego systemu do skryptu w języku Python, który wyświetla powiadomienia o nowych tweetach, a jako część jego działania buforuje miniatury obrazów profilu, aby zmniejszyć niepotrzebne pobrania.

P.S. Nie ma znaczenia, z której poddomeny pobierany jest obraz, wszystkie obrazy są dostępne ze wszystkich subdomen.

Answer 11

Używam thumbalizr używając zmodyfikowanej wersji ich skryptu do buforowania i mam kilka dobrych rozwiązań, które myślę. Kod znajduje się na github.com/mptre/thumbalizr, ale jego krótka wersja używa formatu md5 do budowania nazw plików i pobiera pierwsze dwa znaki z nazwy pliku i używa go do utworzenia folderu o tej samej nazwie . Oznacza to, że łatwo jest rozbić foldery i szybko znaleźć odpowiedni folder bez bazy danych. Coś mnie sprzykrzyło dzięki swojej prostocie.

To generuje nazwy plików jak to http://pappmaskin.no/opensource/delicious_snapcasa/mptre-thumbalizr/cache/fc/fcc3a328e0f4c1b51bf5e13747614e7a_1280_1024_8_90_250.png

ostatnia część, _1280_1024_8_90_250, pasuje do różnych ustawień, że skrypt wykorzystuje podczas rozmowy z api thumbalizr, ale myślę fcc3a328e0f4c1b51bf5e13747614e7a jest prosto md5 url, w to sprawa dla thumbalizr.com

Próbuję zmienić config do generowania obrazów 200px szerokości, i że obrazy idzie w tym samym folderze, ale zamiast _250.png nazywa _200.png

nie mam miał czas, aby wkopać tyle kod, ale jestem pewien, że można go było oddzielić od logiki thumbalizr i uczynić bardziej ogólnym.

Answer 12

można używać UUID klasy w Javie do generowania UUID z cokolwiek w bajtach, który jest wyjątkowy i nie będzie problem z pliku odnośnika

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