비슷한 입력에 대해 유사한 해시를 만드는 방법은 무엇입니까?

Question

파일이있는 데이터베이스를 만들고 싶습니다. 그리고 이러한 파일을 쉽게 검색하기 위해 일종의 해싱 기술을 사용하고 싶습니다. 그러나 정확하게 동일한 파일을 찾고 싶을뿐만 아니라 파일의 일부가 동일한 지 (즉 파일이 유사한 지) 확인합니다. 즉, 유사한 파일은 유사한 해시를 가져야합니다.

이 해쉬의 종류는 '쇄도 효과'가 없어야하기 때문에 암호화 해시 실제로 없다는 것을 의미 (애벌란 효과는 데이터의 각 비트는 다른 데이터가 모두 다른 비트에 영향을 미치는 것을 의미한다.)를

다른 해시는 보안 목적으로 사용되지 않고 파일 비교를 위해 사용되므로 단방향 일 필요는 없습니다.

그래서 본질적으로, 나는 그 각각의 고유 한 입력을위한 고유 해시를 만들 수있는 알고리즘을 찾고 있어요 :

• 가 있음 (거의) 충돌

• 는 대한 유사한 출력을 생성합니다 유사한 입력

• 원래 파일보다 짧습니다 (그렇지 않으면 원본 파일을 단순히 비교하는 것이 더 빠릅니다).

내가 그러나 등, 다음, 함께 처음 두 문자를 추가 함께 3, 4rth을 추가하는 등 뭔가 생각

이는 "1 + 4"이후 충돌의 엄청난 금액을 가지고 "과 동일 2 + 2 "등

나는 시작하는 방법을 모른다. 누군가 제발 나를 밝혀 줄 수 있니? :)

Answer 1

이것은 일반적으로 near duplicate detection라고하며 해결하기 쉽지 않습니다. simhash 알고리즘 (코드는 here)을 권하고 싶습니다.

Answer 2

저는 현재 동일한 효과를 얻기 위해 ssdeep을 사용하고 있으며, 꽤 좋은 결과를 얻고 있습니다.

나는 또한 sdhash가 ssdeep보다 낫다고 읽었습니다.