Rabin-Karp 알고리즘과 중복 제거 간의 관계

Question

많은 중복 제거 라이브러리 또는 응용 프로그램은 빠른 해시를 위해 Rabin Karp 롤링 해시 알고리즘을 적용하여 파일 바이너리에서 청크를 자릅니다.
내 질문은 왜 Rabin Karp 알고리즘이 청크 절단에 자주 사용되는 것입니까?
저는 이것이 빠른 롤링 해시 알고리즘이라는 것을 알고 있지만 제 질문은 더 근본적입니다.
여러 가지 방법으로 청크를자를 수 있습니다.
예를 들어, 1 바이트 (mod 연산 없음)를 값과 비교하여 청크를 자르면 평균 256 바이트 청크가됩니다.
9 비트를 비교하면 평균적으로 512 바이트 청크가됩니다.
라빈 카프 (Rabin Karp)와 같은 해시 알고리즘과 유사한 해싱 결과를 사용하지 않고 마지막 몇 비트를 비교하는 것뿐입니다.

라빈 카프 롤 해시는 다른 크기의 조각으로 파일을 잘라 청크 알고리즘

인덱싱 청킹

1. :

Answer 1

는 변수가 DEDUP 청크으로 크기를 들어, 우리는 두 가지 단계가 있습니다. 그런 다음 중복 제거 이후 데이터 청크를 색인/질의해야합니다. 일반적인 방법은 청크의 해시 값을 계산하고 해시가있는 청크를 키로 저장하는 것입니다. Rabin Karp 알고리즘을 사용하면 해시와 데이터 청크를 동시에 얻을 수 있기 때문에 모두 간단합니다.

마지막 몇 비트를 비교하는 방법이 파일을 조각으로 잘라내는 데 도움이 될 수 있다고 언급했지만 이러한 조각을 인덱싱하려면 어떻게해야합니까? 따라서 해시를 계산해야합니다.

희망이 도움이 될 것입니다.