Sau khi đọc tất cả các câu hỏi của bạn ( ràng buộc duy nhất khiến hàm băm trở nên vô dụng? , 512 bit hash so với 4 128bit hash và nén văn bản url (không rút ngắn ) và lưu trữ trong mysql ), Tôi hiểu rằng vấn đề của bạn ít nhiều là như sau:
Có phải vậy không?
Những điểm sau đây rất quan trọng:Định dạng của URL mà bạn sẽ lưu như thế nào? Bạn sẽ cần đọc lại URL hay chỉ cập nhật thông tin về nó, nhưng không bao giờ tìm kiếm dựa trên một phần URL, v.v.?
Giả sử URL =" http://www.somesite.com.tv/images/picture01 .jpg "và bạn muốn lưu trữ mọi thứ, bao gồm tên tệp. Nếu tên tệp khác, vui lòng cung cấp thêm chi tiết hoặc sửa các giả định câu trả lời của tôi .
-
Nếu có thể tiết kiệm dung lượng bằng cách thay thế một số nhóm ký tự trong URL. Không phải tất cả các ký tự ASCII đều hợp lệ trong một URL, như bạn có thể thấy ở đây:RFC1738 , vì vậy bạn có thể sử dụng chúng để đại diện (và nén) URL. Ví dụ:sử dụng ký tự 0x81 để đại diện cho "http://" có thể khiến bạn tiết kiệm được 6 ký tự, 0x82 để đại diện cho ".jpg" có thể giúp bạn tiết kiệm được 3 byte khác, v.v.
-
Một số từ có thể rất phổ biến (như "hình ảnh", "hình ảnh", "video", "người dùng"). Nếu bạn chọn ký tự người dùng 0x90 đến 0x9f + bất kỳ ký tự nào khác (vì vậy, 0x90 0x01, 0x90 0x02, 0x90 0xfa) để mã hóa các từ như vậy, bạn có thể có 16 * 256 =4.096 "mục từ điển" để mã hóa các từ được sử dụng nhiều nhất. Bạn sẽ sử dụng 2 byte để đại diện cho 4 - 8 ký tự.
Chỉnh sửa: như bạn có thể đọc trong RFC đã đề cập ở trên, trong URL, bạn chỉ có thể có các ký tự ASCII có thể in được. Điều này có nghĩa là chỉ nên sử dụng các ký tự 0x20 đến 0x7F, với một số quan sát được thực hiện trong RFC. Vì vậy, không nên sử dụng bất kỳ ký tự nào sau 0x80 (ký hiệu thập lục phân, sẽ là ký tự 128 thập phân trong bảng ASCII). Vì vậy, nếu có thể chọn một ký tự (giả sử 0x90) là một cờ để chỉ ra "byte sau là một chỉ báo trong từ điển, chỉ mục mà tôi sẽ sử dụng". Một ký tự (0x90) * 256 ký tự (0x00 tối đa 0xFF) =256 mục nhập trong từ điển. Nhưng bạn cũng có thể chọn sử dụng các ký tự 0x90 đến 0x9f (hoặc 144 đến 159 ở dạng thập phân) để chỉ ra rằng chúng là một cờ trong từ điển, do đó cung cấp cho bạn khả năng 16 * 256 ...
Hai phương pháp này có thể giúp bạn tiết kiệm rất nhiều dung lượng trong cơ sở dữ liệu và có thể đảo ngược, không cần lo lắng về xung đột, v.v. Bạn sẽ dễ dàng tạo một từ điển trong ứng dụng của mình và mã hóa / giải mã URL bằng cách sử dụng nó, rất nhanh, làm cơ sở dữ liệu của bạn nhẹ hơn nhiều.
Vì bạn đã có hơn 50 triệu URL, bạn có thể tạo thống kê dựa trên chúng, để tạo từ điển tốt hơn.
Sử dụng hàm băm :Trong trường hợp này, hàm băm là sự cân bằng giữa kích thước và bảo mật. Nó sẽ tồi tệ như thế nào nếu bạn bị va chạm? Và trong trường hợp này, bạn có thể sử dụng nghịch lý sinh nhật để giúp bạn.
Đọc bài viết để hiểu vấn đề:nếu tất cả các đầu vào (các ký tự có thể có trong URL) là tương đương, bạn có thể kích thích xác suất xảy ra va chạm. Và có thể tính toán ngược lại:với xác suất va chạm chấp nhận được của bạn và số lượng tệp của bạn, phạm vi của bạn phải rộng như thế nào? Và vì phạm vi của bạn hoàn toàn liên quan đến số bit được tạo bởi hàm băm ...
Chỉnh sửa: nếu bạn có một hàm băm cung cấp cho bạn 128 bit, bạn sẽ có 2 ^ 128 kết quả có thể xảy ra. Vì vậy, "phạm vi" của bạn trong nghịch lý ngày sinh là 2 ^ 128:giống như năm của bạn có 2 ^ 128 ngày, thay vì 365. Vì vậy, bạn tính toán xác suất va chạm ("hai tệp được sinh ra trong cùng một ngày, với một năm có 2 ^ 128 ngày thay vì 365 ngày). Nếu bạn chọn sử dụng hàm băm cung cấp cho bạn 512 bit, phạm vi của bạn sẽ từ 0 đến 2 ^ 512 ...
Và, một lần nữa, hãy lưu ý đến RFC:không phải tất cả các byte (256 ký tự) đều hợp lệ trong thế giới Internet / URL. Vì vậy, xác suất của các vụ va chạm giảm xuống. Tốt hơn cho bạn :).
