Por que a base usada para calcular hashes em Rabin-Karp sempre inicia?

O algoritmo de correspondência de cordas Rabin-Karp requer uma função hash que pode ser calculada rapidamente. Uma escolha comum é

$$h(x_0\ldots x_n) = \sum_{i=0}^n b^i x_i,$$ Onde $b$é primo (todos os cálculos são módulo$2^w$, Onde $w$é a largura de uma palavra de máquina). Por que é importante para$b$ ser primo?

Um resumo rápido primeiro. Estamos à procura de um padrão$P[1\ldots m]$ em uma string $S[1\ldots n]$. O algoritmo Rabin-Karp faz isso definindo uma função hash$h$. Computamos$h(P)$ (ou seja, o hash do padrão) e comparando-o com $h(S[1\ldots m])$, $h(S[2\ldots m+1])$e assim por diante. Se encontrarmos um hash correspondente, é uma possível substring correspondente.

A eficiência do algoritmo depende da capacidade de calcular $h(S[r+1\ldots s+1])$ eficientemente de $h(S[r\ldots s])$. Isso é chamado de "rolling hash". Observe que qualquer função eficiente de hash rotativo funciona, e ainda é Rabin-Karp. A pergunta que você está perguntando é uma opção específica da função hash, onde você usa:

$$h(S[r\ldots s]) = \sum_{i=r}^s S[i]\, p^{s-i} \bmod q$$

onde é um número primo com aproximadamente a mesma ordem de magnitude que o tamanho do conjunto de caracteres, e é outro número primo que define a cardinalidade do intervalo da função hash, normalmente da mesma ordem de magnitude que uma palavra de máquina dividido pelo tamanho do conjunto de caracteres. Se estou lendo corretamente, você está perguntando por que tem que ser primo.$p$$q$$q$

De fato, esta é uma questão mais geral. Em boa parte da literatura antiga (e atual) sobre hash, o conselho é que a função hash seja considerada um número primo (por exemplo, tabelas de hash devem ter um tamanho primo).

Para que uma função hash seja o mais útil possível, seu intervalo precisa ser relativamente uniforme, mesmo quando seu domínio não é. O texto no idioma natural (digamos) não tem uma distribuição de frequência uniforme, mas os valores de hash devem ter.

Se é um número primo, muitos outros números são relativamente primos e, em particular, a soma (especialmente se também for primo!). Isso torna a distribuição de frequência dos valores de hash mais uniforme, mesmo que a função de hash seja relativamente fraca.$q$$p$

É importante entender que fazemos isso porque a função hash é fraca. Se a função hash fosse mais forte, não seria necessário usar o restante quando dividido por um primo; você poderia, por exemplo, pegar o restante quando dividido por uma potência de dois, o que seria uma operação de máscara de bits muito mais barata. No entanto, é difícil projetar funções robustas de hash rotativo que são baratas o suficiente para serem feitas para cada caractere de entrada no algoritmo Rabin-Karp.

Algo que vale ressaltar que essa técnica "restante do auge" costumava ser comum em muitos aplicativos de hash, mas esse conselho é desaconselhável no hardware moderno. O conselho fazia sentido uma vez, porque, embora a instrução de divisão inteira final sempre fosse cara, também eram as operações que você usava para calcular sua função hash, como multiplicação de números inteiros. Em CPUs modernas, é muito mais caro fazer uma divisão inteira, do que uma multiplicação inteira.

Os multiplicadores modernos de somadores de transporte e economia de carga são totalmente canalizados, para que você possa ter várias instruções sendo executadas ao mesmo tempo. Os divisores modernos usam os algoritmos SPH ou Goldschmidt, que são multiciclos e impossíveis de pipeline. Os divisores Goldschmidt também amarram a unidade de multiplicação, tornando o desempenho ainda maior.

Eu tive programas em que essa instrução de divisão era o gargalo, e a parte irritante era que ela estava oculta dentro da biblioteca padrão.

Em uma CPU moderna, vale a pena usar uma função de hash mais sofisticada, construída com operações totalmente pipeleable (por exemplo, multiplica ou até mesmo procura de tabelas) e usa tabelas de hash com potências de dois, portanto a operação do módulo é uma máscara de bits. Faça qualquer coisa para evitar essa operação de divisão.

Apenas não para Rabin-Karp.