롤링 해시

이 기사를 내용 정의 청킹이라는 제목의 새로운 기사로 분할해야 한다는 의견이 제기되었다.(토론) (2020년 8월)

롤링 해시(Rolling hash, recursive hashing 또는 롤링 체크섬이라고도 함)는 입력을 통해 이동하는 창에서 입력이 해시되는 해시함수다.

몇 개의 해시함수는 롤링 해시를 매우 빠르게 계산할 수 있게 한다. 즉, 이전 해시 값, 창에서 제거된 이전 값, 그리고 창에 추가된 새로운 값만 볼 때, 이동 평균 함수를 다른 로우패스 필터보다 훨씬 빠르게 계산할 수 있는 방법과 유사하다.

주요 응용 프로그램 중 하나는 아래에 설명된 롤링 해시를 사용하는 Rabin-Karp 문자열 검색 알고리즘이다.또 다른 인기 있는 어플리케이션은 Rsync 프로그램으로 마크 애들러의 애들러-32를 바탕으로 한 체크섬을 롤링 해시로 사용한다.LBFS(Low Bandwidth Network Filesystem)는 Rabin 지문을 롤링 해시로 사용한다.FastCDC(Fast Content-Defined Chunking)는 컴퓨팅 효율이 높은 기어 지문을 롤링 해시로 사용한다.

기껏해야 롤링 해시 값은 쌍으로 독립적이거나^[1] 강하게 보편적이다.예를 들어, 그들은 3가지 지혜로 독립적일 수 없다.

다항식 롤링 해시

Rabin-Karp 문자열 검색 알고리즘은 종종 다음과 같은 곱과 추가만을 사용하는 롤링 해시 함수를 사용하여 설명된다.

${\$$+c_{k}a^{0$

여기서 ${\displaystyle a}$은(는) 상수이고, ${\displaystyle {c\mathrm{}}_{}}$ 1${\displaystyle {}_{}}$,${\displaystyle }$. ${\displaystyle .,}$ ${\displaystyle c_{}}$k {\$displaystyle c_${1}, $...,c_{k$}는 입력 문자(그러나$$ 이 기능은 라빈 지문이 아니다$,$ 아래 참조).

거대한 $H{\displaystyle }$ ${\displaystyle H}$ 값을$$ 조작하지 않기 위해 모든 수학은 modulo $n{\displaystyle }$ ${\displaystyle$ n}을(를$)$ 수행한다$.$$양호$한 해시를 위해서는 ${\displaystyle a}$ 및 $n$ ${\displaystyle$ n$}$의 선택이 매우 중요하다. 자세한 내용은 선형 결합$$ 생성기를 참조하십시오.

문자를 제거하고 추가하는 것은 단순히 첫 번째 또는 마지막 용어를 추가하거나 빼는 것을 포함한다.모든 문자를 왼쪽으로 한 위치로 이동하려면 전체 $합{\displaystyle }$ H ${\displaystyle H}$에 ${\displaystyle a}$을(를) 곱해야 한다$.$ 모든 문자를 오른쪽으로 한 위치로 이동하려면 전체 합 $H{\displaystyle }$ ${\displaystyle h}$을(를) ${\displaystyty a$}로 나누어야 한다$.$ 모듈로 $산술$에서는$${\$displaystystytyledata$.$a}$은(는) ${\displaystyle {\mathrm{실제}}^{}}$ 분할을 수행하지 않고 분할 결과를 얻기 위해 $H{\displaystyle }$ ${\displaystyle H}$을(를) 곱할 수 있는$$ 곱셈 역 $a{\displaystyle {}^{}}$- 1 ${\$을(를) 갖도록 선택할$$ 수 있다$$.

라빈 지문

라빈 지문은 또 다른 해시인데, 입력도 다항식(다항식)으로 해석하지만 갈루아 필드 GF(2)를 넘는다.입력을 바이트의 다항식으로 보는 대신 비트의 다항식으로 보고 모든 산술은 GF(2) (CRC32와 유사하게)로 한다.해시는 해당 다항식을 GF(2)에 대해 수정할 수 없는 다항식으로 나눈 결과다.입력과 이탈 바이트만 사용하여 라빈 지문을 업데이트할 수 있어 사실상 롤링 해시가 된다.

흔히 다른 간단한 롤링 해시와 설명되는 라빈-카프 문자열 검색 알고리즘과 같은 저자를 공유하기 때문에, 이 단순한 롤링 해시도 다항식이기 때문에 두 롤링 해시는 서로 오인되는 경우가 많다.백업 소프트웨어 restic은 파일을 분할하기 위해 Rabin 지문을 사용하며 512KiB와 8MiB 사이에서 blob 크기가 다양하다.^[2]

순환 다항식

주기적인 다항식^[3](Buzhash라고도 함)에 의한 해싱도 간단하지만, 배럴 시프트를 대신 사용하여 곱셈을 피하는 장점이 있다.그것은 표 해싱의 한 형태인데$,{\displaystyle }$ 그것은${\displaystyle }$[${\displaystyle {\mathrm{}}^{}}$,${\displaystyle {}^{}{2}^{}}$ L$$){\$displaystyle [0,2$^{L$}}$의 간격에 문자에서$$ 정수까지의 해시함수 $h{\displaystyle }$ ${\displaysty h}$이 있다고 가정한다$.$이 해시함수는 단순히 배열이나 해시 테이블이 문자를 무작위 정수에 매핑하는 것일 수 있다.함수 $s{\displaystyle }$ ${\displaystyle s}$을(를) 주기적 이진 회전(또는 원형 이동)으로$$ 두십시오. 이 기능은 비트를 왼쪽으로 1 회전시켜 첫 번째 위치에서 최신 비트를 밀어낸다.예: $s{\displaystyle }$(${\displaystyle 101}$)${\displaystyle }$= ${\displaystyle 011}$ ${\displaystyle s(101)=011$$\$ {\$displaystyle$ \$oplus }$을(를) 비트 배타적으로 지정하거나$$ 또는해시 값은 다음과 같이 정의된다.

${\displaystyle H=s^{k-1}(h(c_{1})\oplus s^{k-2}(h_{2})\oplus \oplus s(c_{k-1})\oplus h(c_{k}),}$

2의 힘에 의한 승수는 이항 교대조에 의해 구현될 수 있다.결과는${\displaystyle }$[ ${\displaystyle 0,}$ ${\displaystyle 2^{}}$ ${\displaystyle {}^{}}$) ${\displaystyle [0,2^{L}}$의 숫자 입니다$.$

해시 값을 롤링 방식으로 계산하는 작업은 다음과 같다.$H{\displaystyle }$ ${\displaystyle H}$을(를) 이전 해시 값으로 설정하십시오$$.$H{\displaystyle }$ ${\displaystyle H}$을(를) 한 번$$ 회전:${\displaystyle H}$ ${\displaystyle \leftarrow }$ ${\displaystyle s}$( H${\displaystyle }$) ${\displaystyle H\leftarrow s(H$ ${\displaystyle {c\mathrm{}}_{}}$ 1 ${\$을(를) 제거할 문자인$$ $경우{\displaystyle }$ ${\displaystyle k^{}}$$${\$displaystyle$ $k$$}$번$$ 회전하십시오$.$ s$h$그런 다음 간단히 설정

${\displaystyle H\leftarrow s(H)\oplus s^{k}(h(c_{1})\oplus h(c_{k+1}),}$

${\displaystyle {여기}_{}}$서 c${\displaystyle {}_{}}$+ ${\displaystyle 1_{}}$ ${\$}은$($는) 새로운 문자다$$.

주기적 다항식에 의한 해싱은 첫 $번째{\displaystyle }$ L${\displaystyle }$- ${\displaystyle k}$+ ${\displaystyle 1}$ ${\displaystyle L-k+1}$비트를$$ 유지하기만 하면 된다.즉, 결과 $H{\displaystyle }$ ${\displaystyle H}$을(를) 취하고$$ $k{\displaystyle }$- ${\displaystyle 1}$ ${\displaystyle k-1}$ 연속$$ 비트를 해제하십시오.^[1]실제로 이것은 $정수분할{\displaystyle }$H → ${\displaystyle H{\mathrm{}}^{}}$ 2${\displaystyle k^{}}$ - ${\displaystyle 1^{}}$ $(\$ 2$^{k-1})$에 의해 달성될 수 있다$.$

롤링 해시를 이용한 컨텐츠 기반 슬라이싱

롤링 해시함수의 흥미로운 사용 사례 중 하나는 스트림이나 파일의 동적 컨텐츠 기반 청크를 만들 수 있다는 것이다.이는 네트워크를 통해 대용량 파일의 변경된 청크만 전송해야 하고 파일 전면에 간단한 바이트 추가만 하면 모든 고정 크기 창이 업데이트되는 반면 실제로는 첫 번째 "청크"만 수정되었을 때 특히 유용하다.

동적 청크를 계산하는 가장 간단한 방법은 롤링 해시를 계산하는 것이며, 그것이 패턴과 일치한다면(하위 N 비트가 모두 0인^{[further explanation needed]} 것처럼) 청크 경계일 것이다.이 접근방식은 파일의 모든 변경사항이 현재 및 다음 청크에만 영향을 미치도록 보장할 것이며, 다른 것은 없다.

경계가 알려졌을 때, 어떤 것이 수정되었고 네트워크를 통해 전송이 필요한지 감지하기 위해 청크를 해시 값으로 비교할 필요가 있다.^[4]백업 소프트웨어 Attic은 파일 스트림을 분할하기 위해 사용자 정의 가능한 청크 크기 범위의 Buzhash 알고리즘을 사용한다.^[5]

이동 합을 이용한 내용 기반 슬라이싱

gzip(gzip 포함)을 포함한 여러 프로그램--rsyncable옵션) 및 rsyncrypto, 이 특정(비중량) 이동 합계를 기준으로 컨텐츠 기반 슬라이싱을 수행하십시오.^[6]

${\displaystyle S(n)=\sum _{i=n-8195}^{n}c_{i}}}$

${\displaystyle H(n)=S(n)\mod 4096,}$

어디에

• ${\displaystyle S}$( ${\displaystyle n}$) ${\displaystyle S(n)}$은(는) 바이트 $n{\displaystyle }$ ${\displaystyle n}($스토리지 21비트 필요)으로 끝나는 8196 연속 바이트의 합계입니다.
• ${\displaystyle c_{}}$ ${\displaystyle i_{}}$ ${\$는 파일의 $바이트$ i ${\displaystyle i}$이다.
• ${\displaystyle H}$( ${\displaystyle n}$) ${\displaystyle H(n)}$은(는) $S{\displaystyle }$( n${\displaystyle }$) ${\displaystyle S(n)}$의 하단 12비트로 구성된 "해시 값"이다$.$

창을 1바이트로 이동하면 단순히 새 문자를 합에 더하고, 가장 오래된 문자(창에 더 이상 없는 문자)를 합에서 빼는 것이다.

$H{\displaystyle (n}$) ${\displaystyle ==}$ ${\displaystyle 0}$ ${\displaystyle H(n)=0}$인 모든 $n{\displaystyle }$ ${\displaystyle$ $n$$}$에 대해$,$ 이러한 프로그램들은 $파일$을$$n {\$displaystyle$ n$$${\displaystyle \}}$과 n + 1$(\displaystyle$ n$+1$이 접근방식은 파일의 모든 변경사항이 현재 청크 및 다음 청크에만 영향을 미치지만 다른 청크에는 영향을 미치지 않음을 보장할 것이다.

기어 지문 및 컨텐츠 기반 청킹 알고리즘 FastCDC

CDC(Content-Defined Chunking) 알고리즘은 데이터 스트림 바이트의 해시 값을 바이트 단위로 계산하고 해시 값이 미리 정의된 값을 충족하면 데이터 스트림을 청크로 분할해야 한다.그러나, 끈을 바이트 단위로 비교하는 것은 무거운 계산 오버헤드를 도입하게 될 것이다.FastCDC는 새롭고 효율적인 콘텐츠 정의 청킹 방식을 제안한다.빠른 롤링 기어 해시 알고리즘을 사용하여 최소 길이를 건너뛰고 ^[8]청크 크기 분포를 정상화하며 마지막은 아니지만 매번 2바이트를 롤링하여 CDC 알고리즘의 속도를 높인다. CDC 알고리즘은 라빈 기반 CDC 접근법보다 약 10배 높은 처리량을 달성할 수 있다.^[9]

기본 버전 유사코드는 다음과 같이 제공된다.

algorithm FastCDC     input: data buffer src,             data length n,      output: cut point i MinSize ← 2KB     // split minimum chunk size is 2 KB     MaxSize ← 64KB    // split maximum chunk size is 64 KB     fp ← 0 i ← MinSize Mask ← 0x0000d93003530000LL          // buffer size is less than minimum chunk size     if n ≤ MinSize then return ni < n do fp fp << 1> + Gear[src[i] i do!(fp & Mask)인 경우 i를 반환한다.

여기서 기어 배열은 미리 계산된 해싱 배열이다.여기서 FastCDC는 롤링 해싱 결과를 신속하게 계산하고 해싱 결과의 균일한 분포를 라빈으로 유지할 수 있는 기어 해싱 알고리즘을 사용한다.기존의 라빈 해싱 알고리즘과 비교하면 훨씬 빠른 속도를 달성한다.실험 결과, 데이터 스트림을 분할할 때 훨씬 짧은 시간(라빈 기반 청킹의 약 1/10 )에 거의 동일한 청크 크기 분포를 생성할 수 있다는 것을 알 수 있다.

계산 복잡성

모든 롤링 해시 함수는 문자 수로 선형이지만 창 길이(${\displaystyle }$ ${\displaystyle k$에 대한 복잡성은 다양하다.Rabin-Karp 롤링 해시는 $2{\displaystyle }$ k ${\displaystyle k}$ -bit$$ 번호의 곱셈이 필요하며 $정수{\displaystyle }$ 곱셈은 O${\displaystyle {}^{}{k^{}}^{}}$ ${\displaystyle \log }$log ${\displaystyle {\mathrm{}}^{{}^{}}}$에 있다$(\$displaystyle $O(k\log k2^{*}k)}).$ 주기적인 다항식 해싱 N그램은 선형적으로 할 수 있다$.$^[10][1]

소프트웨어

• rollinghashcpp는 여러 롤링 해시 함수의 무료 소프트웨어 C++ 구현이다.
• rollinghashjava는 rolling hashi 함수의 Apache 라이센스 Java 구현이다.

참고 항목

• 민해시
• w-슬링

외부 링크

• MIT 6.006: 2011년 알고리즘 소개 - 암송 9 - 롤링 해시

각주