무작위 소수 및 Rabin Karp 하위 문자열 검색
Sedgewick에서 Rabin-Karb 알고리즘을 읽고 있습니다. 책은 말한다 :
오버플로를 피하면서 가능한 한 큰 값을 취하는 랜덤 프라임 Q를 사용합니다.
처음 읽었을 때 나는 무작위 의 중요성을 알아 차리지 못했고 코드에서 a long가 사용되는 것을 보았을 때 첫 번째 생각은 다음
과 같았습니다. a) 에라 토 스테 네 체를 사용하여 a long
또는
b에 맞는 큰 소수를 찾습니다. 보다 큰 소수를 소수 int로 설정하고 상수로 사용합니다.
그러나 나머지 설명은 다음과 같이 말합니다.
충돌이 발생할 확률
long보다 더 큰 값 을 사용합니다.10^2010^-20
이 부분은 그것보다 큰 값은 말할 것도 long없고 맞을 수 없기 때문에 나를 혼란스럽게 10^20했다. 그런 다음 소수에 대한 계산을 확인했을 때 책은 다음 힌트가있는 연습으로 연기됩니다.
임의의 n 자리 숫자는 1 / n에 비례하는 확률로 소수입니다.
그게 무슨 뜻입니까?
그래서 기본적으로 내가 이해하지 못하는 것은 :
a) 무작위 소수 를 사용하는 의미는 무엇 입니까? 왜 미리 계산하여 상수로 사용할 수 없습니까?
b) 10^20범위를 벗어 났기 때문에 왜 언급 long되었습니까?
c) 그 힌트가 어떻게 도움이됩니까? 정확히 무엇을 의미합니까?
답변
다시 한 번 , Sedgewick은 알고리즘을 단순화하려고 시도했지만 세부 사항이 약간 잘못되었습니다. 첫째로, 10 20 은 64 비트로 표현할 수 없습니다. 그러나 2 63 − 1에 가까운 소수를 취하더라도 후속 모듈로가 정확하도록 오버플로없이 정상적인 방식으로 곱할 약간의 공간이 필요할 것입니다. 대답은 31 비트 소수를 사용하므로 쉽게 만들 수 있지만 10-9 범위 의 충돌 확률 만 제공 합니다.
원래 버전은 Rabin 지문 과 𝔽 2 [x]에 대한 임의의 비 환원 다항식 을 사용합니다. 대수 수 이론의 관점에서 보면 정수에 대한 임의 소수처럼 동작합니다. 다항식을 차수 32 또는 64로 선택하면 지문이 적절한 길이의 컴퓨터 단어에 완벽하게 맞고 다항식 더하기와 빼기가 모두 비트 XOR로 작동하므로 오버플로가 없습니다.
이제 Sedgewick은 아마도 다항식 링이 작동하는 방식을 설명하고 싶지 않았을 것입니다. 좋아. 이 접근 방식을 실제로 구현해야한다면 저렴한 지침으로 쉽게 수정할 수 있는 최대 값에 가까운 프라임 p를 선택합니다 (저는
2
31 − 2
27 + 1에
부분적입니다
. 실제로 편집 2 31 − 1 여기에 부드러운 소수가 필요하지 않기 때문에 더 잘 작동합니다.) 그리고 [1, p-1]에서 난수를 선택하여 다항식을 평가합니다 (위키피디아가 설명하는 방식입니다). 임의성이 필요한 이유는 그렇지 않으면 무의미한 공격자가 많은 해시 충돌이 보장되는 입력을 선택할 수있어 실행 시간을 심각하게 저하시킬 수 있기 때문입니다.
Sedgewick은 원본보다 조금 더 가깝게 따르기를 원했지만 본질적으로 고정 된 값 x (다항식 링을 사용하는 원본 버전에서는 문자 그대로 x)에서 다항식을 평가합니다. 그는 무의미한 적이 충돌을 설계 할 수 없도록 무작위 소수가 필요합니다. 충분히 큰 숫자를 체질하는 것은 매우 비효율적이므로 그는 소수 정리 (그의 힌트 뒤에있는 수학이지만 점근 적으로 만 유지되며 이론적으로 큰 혼란을 야기 함)와 빠른 소수 테스트 (확률적일 수 있음)를 사용합니다. 실패하는 경우 알고리즘의 정확성에 영향을 미치지 않으며 예상 실행 시간에 영향을 미치지 않을 정도로 드물다).
그가 충돌 확률에 대한 공식적인 한계를 어떻게 증명하는지 잘 모르겠습니다. 내 대략적인 아이디어는 기본적으로 관심 창에 충분한 소수가 있음을 보여주고, 중국 나머지 정리를 사용하여 한 번에 너무 많은 소수에 대해 충돌이 발생하는 것이 불가능하다는 것을 보여주고, 충돌 확률은 다음과 같이 제한된다는 결론을 내립니다. 나쁜 소수를 고를 확률은 낮습니다. 그러나 소수 정리는 점근 적으로 만 유지되므로 기계어 범위에서 소수의 밀도에 관한 컴퓨터 실험에 의존해야합니다. 좋지 않음.