Primos aleatórios e pesquisa de substring Rabin Karp

Aug 17 2020

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 inte o usa como uma constante.

Mas então o resto da explicação diz:

Usaremos um longvalor maior do que 10^20tornar a probabilidade de uma colisão acontecer menor que10^-20

Essa parte me deixou confuso, pois um longnão pode caber 10^20muito 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^20mencionado uma vez que está fora do intervalo de long?
c) Como essa dica é útil? O que isso significa exatamente?

Respostas

3 DavidEisenstat Aug 17 2020 at 14:09

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.