Po przeczytaniu wszystkich pytań ( unikalne ograniczenie sprawia, że haszy są bezużyteczne? , hasz 512-bitowy vs. hasz 128-bitowy i kompresja tekstu URL (nie skracanie ) i przechowywanie w mysql ), zrozumiałem, że Twój problem jest mniej więcej taki:
Czy to o to chodzi?
Ważne są następujące punkty:Jaki jest format adresu URL, który zapiszesz? Czy będziesz musiał odczytać adres URL z powrotem, czy po prostu zaktualizować informacje na jego temat, ale nigdy nie wyszukiwać w oparciu o częściowe adresy URL itp.
Zakładając URL ="http://www.somesite.com.tv/images/picture01 .jpg ” i chcesz przechowywać wszystko, łącznie z nazwą pliku. Jeśli jest inna, podaj więcej szczegółów lub popraw moje założenia dotyczące odpowiedzi .
-
Jeśli można zaoszczędzić miejsce, zastępując pewną grupę znaków w adresie URL. Nie wszystkie znaki ASCII są prawidłowe w adresie URL, jak widać tutaj:RFC1738 , dzięki czemu można ich używać do reprezentowania (i kompresowania) adresu URL. Na przykład:użycie znaku 0x81 do reprezentowania „http://” może spowodować zapisanie 6 znaków, 0x82 do przedstawienia „.jpg” może zaoszczędzić kolejne 3 bajty, itd.
-
Niektóre słowa mogą być bardzo powszechne (np. „obraz”, „zdjęcie”, „wideo”, „użytkownik”). Jeśli zdecydujesz się na użycie znaków od 0x90 do 0x9f + dowolny inny znak (czyli 0x90 0x01, 0x90 0x02, 0x90 0xfa) do zakodowania takich słów, możesz mieć 16 * 256 =4096 "wpisów słownikowych" do zakodowania najczęściej używanych słów. Użyjesz 2 bajtów do przedstawienia 4-8 znaków.
Edytuj: jak możesz przeczytać we wspomnianym wyżej RFC, w adresie URL możesz mieć tylko drukowane znaki ASCII. Oznacza to, że należy używać tylko znaków od 0x20 do 0x7F, z pewnymi obserwacjami poczynionymi w RFC. Tak więc żaden znak po 0x80 (zapis szesnastkowy byłby znakiem 128 dziesiętnym w tabeli ASCII) nie powinien być używany. Tak więc, jeśli możesz wybrać jeden znak (powiedzmy 0x90) jako jedną flagę, aby wskazać "następny bajt jest wskazaniem w słowniku, indeksem, którego użyję". Jeden znak (0x90) * 256 znaków (0x00 do 0xFF) =256 wpisów w słowniku. Ale możesz także użyć znaków od 0x90 do 0x9f (lub od 144 do 159 dziesiętnie), aby wskazać, że są one flagą słownika, co daje 16 *256 możliwości...
Te dwie metody mogą zaoszczędzić dużo miejsca w Twojej bazie danych i są odwracalne, bez konieczności martwienia się o kolizje itp. Po prostu utworzysz słownik w swojej aplikacji i zaczniesz kodować/dekodować adresy URL za jego pomocą, bardzo szybko, czyniąc Twoja baza danych jest znacznie lżejsza.
Ponieważ masz już +50 mln adresów URL, możesz na ich podstawie generować statystyki, aby wygenerować lepszy słownik.
Korzystanie z hashów :Hasze są w tym przypadku kompromisem między rozmiarem a bezpieczeństwem. Jak źle będzie, jeśli dojdzie do kolizji? W tym przypadku możesz użyć paradoksu urodzinowego by ci pomóc.
Przeczytaj artykuł, aby zrozumieć problem:gdyby wszystkie dane wejściowe (możliwe znaki w adresie URL) były równoważne, można by oszacować prawdopodobieństwo kolizji. I można obliczyć odwrotnie:biorąc pod uwagę twoje dopuszczalne prawdopodobieństwo kolizji i liczbę plików, jak szeroki powinien być twój zakres? A ponieważ twój zakres jest dokładnie powiązany z liczbą bitów wygenerowanych przez funkcję skrótu...
Edytuj: jeśli masz funkcję mieszającą, która daje 128 bitów, będziesz miał 2^128 możliwych wyników. Zatem Twój „zakres” w paradoksie urodzin to 2^128:to tak, jakby Twój rok miał 2^128 dni zamiast 365. Obliczasz więc prawdopodobieństwo kolizji („dwa pliki być narodzonym tego samego dnia, z roku które mają 2^128 dni zamiast 365 dni). Jeśli zdecydujesz się użyć skrótu, który daje 512 bitów, twój zakres zmieni się od 0 do 2^512...
I znowu, pamiętaj o RFC:nie wszystkie bajty (256 znaków) są prawidłowe w świecie Internetu / URL. Tak więc prawdopodobieństwo kolizji maleje. Lepiej dla Ciebie :).
