Tôi muốn tạo cơ sở dữ liệu với các tệp. Và, để dễ dàng tìm kiếm các tệp này, tôi muốn sử dụng một số loại kỹ thuật băm. Tuy nhiên, tôi không chỉ muốn tìm các tệp CHÍNH XÁC, mà còn kiểm tra xem các phần của tệp có giống nhau hay không (nghĩa là các tệp tương tự). nói cách khác, các tệp tương tự sẽ có các hash tương tự.Cách tạo hàm băm tương tự cho đầu vào tương tự?
Điều này có nghĩa rằng loại băm là không thực sự là một băm mật mã vì có không phải là một 'hiệu ứng tuyết lở' (hiệu ứng tuyết lở có nghĩa là mỗi bit dữ liệu ảnh hưởng đến tất cả các bit khác của dữ liệu khác.)
Một điều này là băm không cần phải là một chiều, vì nó không được sử dụng cho mục đích bảo mật nhưng để so sánh các tệp.
Vì vậy, trong bản chất, tôi đang tìm kiếm một thuật toán có thể tạo ra một băm duy nhất cho mỗi đầu vào duy nhất:
Có (hầu như) không có va chạm
Tạo một đầu ra tương tự cho các đầu vào tương tự
Nhỏ hơn tệp gốc (nếu không sẽ nhanh hơn so với việc so sánh các tệp ban đầu nhanh hơn).
Tôi đã nghĩ về điều gì đó giống như thêm hai ký tự đầu tiên vào nhau, sau đó thêm thứ 3 và thứ 4 cùng nhau, v.v. Tuy nhiên, điều này có số lượng va chạm rất lớn vì "1 + 4" giống như " 2 + 2 ", v.v.
Tôi thực sự không biết cách bắt đầu. Ai đó có thể khai sáng cho tôi được không? :)
Điều này có lẽ rất khó. Hãy xem http://en.wikipedia.org/wiki/Agrep –
nếu công việc là tìm các tệp có byte phổ biến, [ssdeep] (http://ssdeep.sourceforge.net/), là điều tuyệt vời ở đó. –
Bạn sẽ xem xét việc tạo thuật toán nén, theo sau là sắp xếp. Bạn sẽ sử dụng cùng một bảng tần số cho tất cả các đầu vào nén để làm cho mọi thứ xác định. – sehe