Primos aleatórios e pesquisa de substring Rabin Karp
Estou lendo o algoritmo Rabin-Karb de Sedgewick. O livro diz:
Usamos um Q principal aleatório tomando o maior valor possível, evitando o estouro
Na primeira leitura não notei o significado de aleatório e quando vi que no código a long
é usado, meus primeiros pensamentos foram:
a) Use a peneira de Eratóstene para encontrar um grande primo que se encaixe em a long
ou
b) procure em uma lista de inicia qualquer número primo grande o suficiente que seja maior que int
e o usa como uma constante.
Mas então o resto da explicação diz:
Usaremos um
long
valor maior do que10^20
tornar a probabilidade de uma colisão acontecer menor que10^-20
Essa parte me deixou confuso, pois um long
não pode caber 10^20
muito menos um valor maior do que isso. Então, quando verifiquei o cálculo do primo, o livro mudou para um exercício que tem apenas a seguinte dica:
Um número aleatório de n dígitos é primo com probabilidade proporcional a 1 / n
O que isso significa?
Então, basicamente, o que eu não entendo é:
a) qual é o significado de usar um primo aleatório ? Por que não podemos simplesmente pré-calculá-lo e usá-lo como uma constante?
b) por que é 10^20
mencionado uma vez que está fora do intervalo de long
?
c) Como essa dica é útil? O que isso significa exatamente?
Respostas
Mais uma vez , Sedgewick tentou simplificar um algoritmo e obteve os detalhes ligeiramente errados. Primeiro, como você observa, 10 20 não pode ser representado em 64 bits. Mesmo obtendo um primo próximo a 2 63-1 , no entanto, você provavelmente desejaria um pouco de espaço para multiplicar da maneira normal sem transbordar, de modo que o módulo subsequente esteja correto. A resposta usa um número primo de 31 bits, o que torna isso fácil, mas oferece apenas probabilidades de colisão na faixa de 10-9 .
A versão original usa impressões digitais de Rabin e um polinômio irredutível aleatório sobre 𝔽 2 [x], que da perspectiva da teoria dos números algébricos se comporta muito como um primo aleatório sobre os inteiros. Se escolhermos o polinômio de grau 32 ou 64, então as impressões digitais se encaixam perfeitamente em uma palavra de computador de comprimento apropriado, e a adição e subtração de polinômios funcionam para o XOR bit a bit, então não há estouro.
Bem, Sedgewick provavelmente não queria explicar como os anéis polinomiais funcionam. Bem. Se eu tivesse que implementar esta abordagem na prática, eu escolheria um p primo próximo ao máximo que fosse fácil de modificar com instruções baratas (eu sou parcial para
2
31 - 2
27 + 1
; EDIT na verdade 2 31 - 1 funciona ainda melhor, já que não precisamos de um número primo suave aqui) e, em seguida, escolha um número aleatório em [1, p − 1] para avaliar os polinômios (é assim que a Wikipedia o explica). A razão pela qual precisamos de alguma aleatoriedade é que, caso contrário, o adversário inconsciente poderia escolher uma entrada que teria a garantia de muitas colisões de hash, o que degradaria gravemente o tempo de execução.
Sedgewick queria seguir o original um pouco mais de perto do que isso, entretanto, que basicamente avalia os polinômios em um valor fixo de x (literalmente x na versão original que usa anéis polinomiais). Ele precisa de um número primo aleatório para que o adversário inconsciente não consiga criar colisões. Peneirar números grandes o suficiente é bastante ineficiente, então ele se volta para o Teorema dos Números Primos (que é a matemática por trás de sua dica, mas se mantém apenas assintoticamente, o que faz uma grande bagunça teoricamente) e um teste rápido de primalidade (que pode ser probabilístico; o casos em que ele falha não influenciam a exatidão do algoritmo e são raros o suficiente para não afetar o tempo de execução esperado).
Não tenho certeza de como ele prova um limite formal sobre a probabilidade de colisão. Minha ideia geral é basicamente mostrar que há primos suficientes na janela de interesse, usar o Teorema do Remanescente Chinês para mostrar que é impossível haver uma colisão de muitos primos de uma vez, concluir que a probabilidade de colisão é limitada pelo probabilidade de escolher um primo ruim, que é baixa. Mas o teorema dos números primos se mantém apenas assintoticamente, então temos que confiar em experimentos de computador com relação à densidade dos primos em intervalos de palavras de máquina. Nada bom.