Se pensarmos rapidamente em como procurar uma substring sub numa string text, podemos chegar a esse algoritmo simples:
RUIM:
• para i variando entre 0 e $ ||text|| - ||sub|| $:
• se $text[i] = sub[0]$, então:
• $POS = i$
• para j variando de 0 a $ ||sub|| $
• se $ sub[i] \neq text[i+j] $:
• $POS = -1$
• encerra loop do j
• se $POS \neq -1$:
• printa que achou na posição POS
Ou seja, saímos comparando cada caractere da string com o primeiro caractere da substring e, quando achamos, saímos comparando caractere a caractere. Se alguma dessas comparações disser que os caracteres são diferentes, POS vai guardar -1, evitando que o algoritmo printe que aquela posição é um match.
Como o algoritmo está em função do tamanho da string grande e a cada iteração, ele pode fazer $||sub||$ comparações, então a complexidade é $O( || text || * || sub || )$.
Pergunta: como fazer essa busca de maneira mais eficiente?
Imagine que inventemos uma função $f$ que receba uma string e atribua um valor a ela.
Suponha que $f(sub) = S$.
Suponha também que, para cada substring $subtext$ de $text$ com o mesmo tamanho de $sub$, nós conseguimos calcular $f(subtext)$ em $O(1)$.
Tendo isso, nós podemos apenas comparar os valores de $f$ gerados em $text$ com $S$, e isso nos daria (pelo menos) alguma segurança de que não estamos olhando aquela substring em vão.
Por exemplo, vamos supor o seguinte:
- cada letra equivale a um número, $a =1,b=2,...,z=26$
$ f : string, \text{ }índice \rightarrow número$
$f(S,\, i) = S[i] \text{, se i é a última casa de S}$
$f(S,\, i) = S[i] + f(S, \, i+1) \text{, caso contrário}$
Dado isso, vamos procurar eae dentro de daeaecc.
$f(eae) = 5 + 1 + 5 = 11$
Temos o valor da substring, agora vamos procurar nas substrings do texto.
$f(dae) = 4 + 1 + 5 = 10$ com certeza, aqui não é um match.
$f(aea) = 1 + 5 + 1 = 6$ mesmo coisa aqui.
$f(eae) = 5 + 1 + 5 = 11$ bateu, aqui pode ser um match
$f(aec) = 1 + 5 + 3 = 9$ não bateu.
$f(ecc) = 5 + 3 + 3 = 11$ bateu, aqui pode ser um match.
Podemos ver que, das 5 substrings possíveis, 2 podem ser iguais a eae.
Nesse ponto, podemos pegar os índices onde essas substrings começam e fazer a comparação letra a letra.
Pergunta: isso não é a mesma coisa que comparar letra a letra como no algoritmo RUIM?
É bem parecido, e pode ser até pior, se por exemplo, as funções batem várias vezes e nem mesmo há a substring no texto.
Mas o caminho é esse. Como melhorar a função de forma que a ordem em que as letras aparecem importe?
Se ficarmos comparando todas as substrings cuja função é igual, vamos perder tempo desnecessário.
Para solucionar isso, podemos adicionar em $f$ um fator multiplicativo para cada letra. Isso fará com que a ordem em que eles aparecem importe.
Vamos montar uma nova definição de $f$:
$ f : string, \, índice, \, fator \rightarrow número$
$f(S,\, i, \, p) = S[i]*p \text{, se i é a última casa de S}$
$f(S,\, i, \, p) = S[i]*p + f(S, \, i+1, \, p*10) \text{, caso contrário}$
Ou seja, a função de uma string S será:
$$\sum_{i=0}^{n-1} S[i]*10^i$$
Vamos fazer o teste:
$f(eae) = 5*1 + 1*10 + 5*100 = 515$
$f(dae) = 4*1 + 1*10 + 5*100 = 514$
$f(aea) = 1*1 + 5*10 + 1*100 = 151$
$f(eae) = 5*1 + 1*10 + 5*100 = 515 \quad \quad match$
$f(aec) = 1*1 + 5*10 + 3*100 = 351$
$f(ecc) = 5*1 + 3*10 + 3*100 = 335$
Já melhorou, mas ainda temos alguns problemas, como por exemplo:
$f(ja) = f(t) \text{, pois 10 + 1*10 = 20}$
Um dos segredos é que o fator multiplicativo tem que ser maior ou igual ao número possível de caracteres, ou seja, ele deve ser maior ou igual a 26 (no caso de a até e).
Vamos chamar esse fator de base.
Se disséssemos que a base é 100, por exemplo, $f(ja) = 1 + 10*100 = 1001$ e $f(t) = 20$.
Resumidamente, o que estamos tentando fazer é evitar colisões, isso torna $f$ uma função de hashing.
Vamos considerar, por enquanto, o hash da string S (de tamanho n) como sendo:
$$H(S) = \sum_{i=0}^{n-1} S[i]*B^i $$
A questão é, como calcular todos os hashes das substrings em tempo linear?
Não podemos simplesmente fazer $\left( \sum_{i=0}^{n-1} S[i]*S^{i} \right) $ + $\left( \sum_{i=1}^{n} S[i]*S^{i} \right) $ + $\left( \sum_{i=2}^{n+1} S[i]*S^{i} \right) $ + ...
A técnica que o Rabin-Karp usa chama-se Rolling Hash, que é calcular o próximo hash em função do anterior, dado que se o hash tem tamanho n, hashes consecutivos tem n-2 termos em comum.
Uma forma possível de calcular o próximo hash usando o hash atual anterior é assim:
• O único valor do hash que não está em função da base é o primeiro ($S[0] * B^0$)
• Se subtrairmos o esse valor do valor do hash, o resultado será múltiplo de B
• Se dividirmos o resultado por B, estamos movendo o hash um passo à frente
• Somamos o termo referente ao próximo (e último) caractere do novo hash
Para visualizar isso, vamos calcular o hash de substrings de tamanho n consecutivas em uma string S, iniciando na posição i.
Sabemos que:
$H_{atual}(S) = S[i]*B^0 + S[i+1]*B^1 + ... + S[i+n-1]*B^{n-1}$
$H_{próximo}(S) = S[i+1]*B^0 + S[i+2]*B^1 + ... + S[i+n]*B^{n-1}$
Vamos aplicar os passos em $H_{atual}(S)$ para ver o que acontece:
0 - inicialmente $H_{atual}(S)$ é:
$(S[i]*B^0) + (S[i+1]*B^1) + ... + (S[i+n-1]*B^{n-1})$
1 - subtrair o primeiro valor do hash:
$(S[i + 1]*B^1) + (S[i+2]*B^2) + ... + (S[i+n-1]*B^{n-1})$
2 - dividir o resultado por B:
$(S[i + 1]*B^0) + (S[i+2]*B^1) + ... + (S[i+n-1]*B^{n-2})$
3 - somar o termo do próximo caractere
$(S[i+1]*B^0) + (S[i+1]*B^1) + ... + (S[i+n-1]*B^{n-2}) + (S[i+n]*B^{n-1})$
Com isso, chegamos a $H_{próximo}(S)$.
Essa técnica funciona bem para hashes com base pequena.
Pergunta: o que acontece quando as strings são imensas?
Até agora tratamos strings pequenas, mas se aplicássemos $f$ numa string de tamanho $10000$, por exemplo, o que aconteceria?
É impraticável manter uma coisa na forma $x^{10000}$ em uma variável como int ou long.
Devemos fazer uso de módulo para que o hash fique restrito a um certo intervalo.
Como fazemos isso? Simples, basta integrar o módulo à função do hash:
$$H(S) = \left( \sum_{i=0}^{n-1} S[i]*B^i \right) \, mod \, M$$
Obviamente isso é a visão matemática, porque tecnicamente pode haver um overflow dentro do somatório. Podemos colocar o módulo lá dentro também.
Dado que integramos o módulo, temos um último problema: a divisão.
Na aritmética modular, não existe divisão. Leve em conta esse exemplo:
Base: 50
Módulo: 2550
substring: aaa
texto: baaa
$H(aaa) = 1*50^0 + 1*50^1 + 1*50^2 = 2501 \; mod \; 2500 = 1$
$H(baa) = 2*50^0 + 1*50^1 + 1*50^2 = 2501 \; mod \; 2500 = 2$
$H(aaa) = \frac{H(baa) - b}{50} + (1*50^2) = \frac{0}{50} + 2500 = 2500 \neq 1$
Quando o valor passa do módulo, a divisão se torna obsoleta. Por isso ela não é aplicada na aritmética modular.
Existem duas soluções para esse problema:
• Ao invés de dividir, multiplicar pelo inverso modular da base no módulo dado.
• Fazer o hash "ao contrário".
Vamos tratar apenas da segunda (é uma solução mais curta que a primeira, já que para achar inverso multiplicativo, temos que implementar o Algoritmo Estendido de Euclides ou já ter a base, módulo e inverso decorados, enquanto a segunda não requer implementação extra).
Pergunta: o que quer dizer fazer o hash ao contrário?
Quando falo do hash ao contrário, me refiro somente à ordem das potências da base.
Ao invés de seguir de 0 a (n-1), seguir de (n-1) a 0.
Pergunta: que diferença isso faz?
• A diferença é que, fazendo isso, conseguimos evitar que haja uma divisão.
• Se subtrairmos o primeiro elemento, tiramos a maior potência de cara.
• Depois, se multiplicarmos o resultado pela base, obtemos um "próximo hash".
• Por último, basta acrescentar o último valor do novo hash.
Observemos:
0 - inicialmente $H_{atual}(S)$ é:
$(S[i]*B^{n-1}) + (S[i+1]*B^{n-2}) + ... + (S[i+n-1]*B^0)$
1 - subtrair o primeiro valor do hash:
$(S[i + 1]*B^{n-2}) + (S[i+2]*B^{n-3}) + ... + (S[i+n-1]*B^0)$
2 - multiplicar o resultado por B:
$(S[i + 1]*B^{n-1}) + (S[i+2]*B^{n-2}) + ... + (S[i+n-1]*B^1)$
3 - somar o termo do próximo caractere
$(S[i + 1]*B^{n-1}) + (S[i+2]*B^{n-2}) + ... + (S[i+n-1]*B^1) + (S[i+n]*B^0)$
Com isso, geramos um hash sensível a ordem, persistente em módulo e bem disperso.
Uma dica referente a desempenho: usar um módulo que seja potência de 2 agiliza o processo no computador. Também temos o tipo unsigned (presente em C++) que não aceita negativos, ou seja, um unsigned int que passe de $2^32$ volta a ser 0, funcionando como um $mod \; 2^32$.
Um dica referente à melhoria do hashing é usar um módulo e uma base que sejam primos entre si, mas caso optemos em usar um módulo que seja potência de 2, qualquer base ímpar já satisfaz. Se eles não forem primos entre si, a chance de haver colisão aumenta.
Por último, nós podemos abordar o algoritmo de duas formas, uma é supondo que sempre que os hashes baterem, existe um match (inseguro porém rápido), a outra é comparar letra a letra quando os hashes baterem para ter certeza que há um match (seguro porém mais lento). O método inseguro tem uma complexidade $O(||text||)$.
A implementação a seguir usa o método seguro.
Ou seja, a função de uma string S será:
$$\sum_{i=0}^{n-1} S[i]*10^i$$
para uma string de tamanho n.
Vamos fazer o teste:
$f(eae) = 5*1 + 1*10 + 5*100 = 515$
$f(dae) = 4*1 + 1*10 + 5*100 = 514$
$f(aea) = 1*1 + 5*10 + 1*100 = 151$
$f(eae) = 5*1 + 1*10 + 5*100 = 515 \quad \quad match$
$f(aec) = 1*1 + 5*10 + 3*100 = 351$
$f(ecc) = 5*1 + 3*10 + 3*100 = 335$
Já melhorou, mas ainda temos alguns problemas, como por exemplo:
$f(ja) = f(t) \text{, pois 10 + 1*10 = 20}$
Um dos segredos é que o fator multiplicativo tem que ser maior ou igual ao número possível de caracteres, ou seja, ele deve ser maior ou igual a 26 (no caso de a até e).
Vamos chamar esse fator de base.
Se disséssemos que a base é 100, por exemplo, $f(ja) = 1 + 10*100 = 1001$ e $f(t) = 20$.
Resumidamente, o que estamos tentando fazer é evitar colisões, isso torna $f$ uma função de hashing.
Vamos considerar, por enquanto, o hash da string S (de tamanho n) como sendo:
$$H(S) = \sum_{i=0}^{n-1} S[i]*B^i $$
A questão é, como calcular todos os hashes das substrings em tempo linear?
Não podemos simplesmente fazer $\left( \sum_{i=0}^{n-1} S[i]*S^{i} \right) $ + $\left( \sum_{i=1}^{n} S[i]*S^{i} \right) $ + $\left( \sum_{i=2}^{n+1} S[i]*S^{i} \right) $ + ...
A técnica que o Rabin-Karp usa chama-se Rolling Hash, que é calcular o próximo hash em função do anterior, dado que se o hash tem tamanho n, hashes consecutivos tem n-2 termos em comum.
Uma forma possível de calcular o próximo hash usando o hash atual anterior é assim:
• O único valor do hash que não está em função da base é o primeiro ($S[0] * B^0$)
• Se subtrairmos o esse valor do valor do hash, o resultado será múltiplo de B
• Se dividirmos o resultado por B, estamos movendo o hash um passo à frente
• Somamos o termo referente ao próximo (e último) caractere do novo hash
Para visualizar isso, vamos calcular o hash de substrings de tamanho n consecutivas em uma string S, iniciando na posição i.
Sabemos que:
$H_{atual}(S) = S[i]*B^0 + S[i+1]*B^1 + ... + S[i+n-1]*B^{n-1}$
$H_{próximo}(S) = S[i+1]*B^0 + S[i+2]*B^1 + ... + S[i+n]*B^{n-1}$
Vamos aplicar os passos em $H_{atual}(S)$ para ver o que acontece:
0 - inicialmente $H_{atual}(S)$ é:
$(S[i]*B^0) + (S[i+1]*B^1) + ... + (S[i+n-1]*B^{n-1})$
1 - subtrair o primeiro valor do hash:
$(S[i + 1]*B^1) + (S[i+2]*B^2) + ... + (S[i+n-1]*B^{n-1})$
2 - dividir o resultado por B:
$(S[i + 1]*B^0) + (S[i+2]*B^1) + ... + (S[i+n-1]*B^{n-2})$
$(S[i+1]*B^0) + (S[i+1]*B^1) + ... + (S[i+n-1]*B^{n-2}) + (S[i+n]*B^{n-1})$
Com isso, chegamos a $H_{próximo}(S)$.
Essa técnica funciona bem para hashes com base pequena.
Pergunta: o que acontece quando as strings são imensas?
Até agora tratamos strings pequenas, mas se aplicássemos $f$ numa string de tamanho $10000$, por exemplo, o que aconteceria?
É impraticável manter uma coisa na forma $x^{10000}$ em uma variável como int ou long.
Devemos fazer uso de módulo para que o hash fique restrito a um certo intervalo.
Como fazemos isso? Simples, basta integrar o módulo à função do hash:
$$H(S) = \left( \sum_{i=0}^{n-1} S[i]*B^i \right) \, mod \, M$$
Obviamente isso é a visão matemática, porque tecnicamente pode haver um overflow dentro do somatório. Podemos colocar o módulo lá dentro também.
Dado que integramos o módulo, temos um último problema: a divisão.
Na aritmética modular, não existe divisão. Leve em conta esse exemplo:
Base: 50
Módulo: 2550
substring: aaa
texto: baaa
$H(aaa) = 1*50^0 + 1*50^1 + 1*50^2 = 2501 \; mod \; 2500 = 1$
$H(baa) = 2*50^0 + 1*50^1 + 1*50^2 = 2501 \; mod \; 2500 = 2$
$H(aaa) = \frac{H(baa) - b}{50} + (1*50^2) = \frac{0}{50} + 2500 = 2500 \neq 1$
Quando o valor passa do módulo, a divisão se torna obsoleta. Por isso ela não é aplicada na aritmética modular.
Existem duas soluções para esse problema:
• Ao invés de dividir, multiplicar pelo inverso modular da base no módulo dado.
• Fazer o hash "ao contrário".
Vamos tratar apenas da segunda (é uma solução mais curta que a primeira, já que para achar inverso multiplicativo, temos que implementar o Algoritmo Estendido de Euclides ou já ter a base, módulo e inverso decorados, enquanto a segunda não requer implementação extra).
Pergunta: o que quer dizer fazer o hash ao contrário?
Quando falo do hash ao contrário, me refiro somente à ordem das potências da base.
Ao invés de seguir de 0 a (n-1), seguir de (n-1) a 0.
Pergunta: que diferença isso faz?
• A diferença é que, fazendo isso, conseguimos evitar que haja uma divisão.
• Se subtrairmos o primeiro elemento, tiramos a maior potência de cara.
• Depois, se multiplicarmos o resultado pela base, obtemos um "próximo hash".
• Por último, basta acrescentar o último valor do novo hash.
Observemos:
0 - inicialmente $H_{atual}(S)$ é:
$(S[i]*B^{n-1}) + (S[i+1]*B^{n-2}) + ... + (S[i+n-1]*B^0)$
1 - subtrair o primeiro valor do hash:
$(S[i + 1]*B^{n-2}) + (S[i+2]*B^{n-3}) + ... + (S[i+n-1]*B^0)$
2 - multiplicar o resultado por B:
$(S[i + 1]*B^{n-1}) + (S[i+2]*B^{n-2}) + ... + (S[i+n-1]*B^1)$
$(S[i + 1]*B^{n-1}) + (S[i+2]*B^{n-2}) + ... + (S[i+n-1]*B^1) + (S[i+n]*B^0)$
Com isso, geramos um hash sensível a ordem, persistente em módulo e bem disperso.
Uma dica referente a desempenho: usar um módulo que seja potência de 2 agiliza o processo no computador. Também temos o tipo unsigned (presente em C++) que não aceita negativos, ou seja, um unsigned int que passe de $2^32$ volta a ser 0, funcionando como um $mod \; 2^32$.
Um dica referente à melhoria do hashing é usar um módulo e uma base que sejam primos entre si, mas caso optemos em usar um módulo que seja potência de 2, qualquer base ímpar já satisfaz. Se eles não forem primos entre si, a chance de haver colisão aumenta.
Por último, nós podemos abordar o algoritmo de duas formas, uma é supondo que sempre que os hashes baterem, existe um match (inseguro porém rápido), a outra é comparar letra a letra quando os hashes baterem para ter certeza que há um match (seguro porém mais lento). O método inseguro tem uma complexidade $O(||text||)$.
A implementação a seguir usa o método seguro.
typedef long long ll; //chamaremos long long de ll #define B 257 //base #define M 2147483647 //módulo
//função para calcular módulo de positivos e negativos
ll mod(ll a){
return (a % M + M) % M;
}
//função para calcular exponenciação modular rápida
ll power(ll n, ll e){
ll r = 1;
for(; e > 0; e >>= 1, n = (n*n) % M)
if(e&1) r = (r * n) % M;
return r;
}
//função hashing, par formado por (hash, primeiro_elemento)//guardamos esses valores para que sempre tenhamos acesso//ao valor total do hash e ao primeiro elemento, que é o//que precisamospair<ll, ll> H(char sub[], int s){ int first = mod(sub[0] * power(B, s - 1)); ll h = first; for(ll i = 1; i < s; i++) h = mod(h + mod(power(B, s - i - 1) * sub[i])); return make_pair(h, first);
}
//checagem força-bruta para quando hashes baterem
bool check(char text[], char sub[], int ini, int s){
int i = 0;
while(text[ini + i] == sub[i] && i < s) i++;
return i == s;
}
//método principal
void RabinKarp(char text[], char sub[]){
int t = strlen(text), s = strlen(sub);
pair<ll, ll> hs = H(sub, s), ht = H(text, s);
int lim = t - s;
for(int i = 0; i <= lim; i++){
if(ht.first == hs.first)
if(check(text, sub, i, s))
printf("MATCH EM %d\n", i);
ht.first -= ht.second; //subtrai o primeiro
ht.second = mod(text[i + 1] * power(B, s - 1)); //atualiza o primeiro
ht.first = mod(ht.first * B); //multiplica pela base
ht.first += text[i + s]; //soma o novo termo
}
}
int main(){
char text[] = "abracadabra abaca";
char sub[] = "aca";
char sub2[] = "cada";
RabinKarp(text, sub);
printf("----------------------------\n");
RabinKarp(text, sub2);
}
Resumindo: O Rabin-Karp se baseia em usar hashing para filtrar a abordagem força-bruta.
Apesar de tudo, o hash não garante que nunca haverá colisão, então é possível (apesar de muito difícil) que o Rabin-Karp seja tão ruim quanto RUIM, mas em média ele é bem melhor:
Complexidade do Rabin-Karp:
Em média: O(||text|| + ||sub||)
Pior caso: O(||text|| * ||sub||)
Em alguns casos, onde as strings são pequenas e cabem numa base pequena, é possível pensarmos em um hash perfeito, excluindo a necessidade de checar a veracidade dos matches e levando a complexidade a $O(||text||)$.
Outros algoritmos de busca eficientes são:
• KMP (Knuth-Morris-Pratt)
• Aho-Corasick
• Boyer-Moore
Nenhum comentário:
Postar um comentário