Hashing de strings usando la función hash rodante polinomial

Función hash

Una función Hash es una función que asigna cualquier tipo de datos de tamaño arbitrario a valores de tamaño fijo. Los valores devueltos por la función se denominan valores hash o resúmenes. Hay muchas funciones hash populares como DJBX33A, MD5 y SHA-256. Esta publicación discutirá las características clave, la implementación, las ventajas y los inconvenientes de la función Polynomial Rolling Hash.

Tenga en cuenta que si dos strings son iguales, sus valores hash también deberían ser iguales. Pero lo contrario no tiene por qué ser cierto.

La función hash rodante polinomial

La función hash rodante polinomial es una función hash que usa solo multiplicaciones y sumas. La siguiente es la función:

$\text{hash(s)} = \text{s}[0] + \text{s}[1]\cdot p + \text{s}[2]\cdot p^2 + \dots + \text{s}[n - 1]\times p^{n - 1}\quad \text{mod}\ m$

o simplemente,

$\text{hash(s)} = \displaystyle\sum_{i = 0}^{n - 1} s[i]\cdot p^i\quad \text{mod}\ m$

Dónde

La entrada a la función es una string $s$ de longitud $norte$ .
$pags$ y $metro$ son algunos enteros positivos.
La elección de $pags$ y $metro$ afecta el rendimiento y la seguridad de la función hash.
Si la string consta solo de letras minúsculas, entonces es una buena opción.
- Los programadores competitivos prefieren usar un valor mayor para $pags$ . Los ejemplos incluyen $29791$ , $11111$ , $111111$ .
$metro$ será necesariamente un primo grande ya que la probabilidad de que dos claves colisionen (produzcan el mismo hash) es casi $\cfrac{1}{m}$ . $10^9 + 7$ y $10^9 + 9$ son valores ampliamente utilizados para $metro$ .
La salida de la función es el valor hash de la string $s$ que oscila entre $0$ e $(m - 1)$ inclusive.

A continuación se muestra la implementación de la función Polynomial Rolling Hash

C

#include <stdio.h>
#include <string.h>
 
int get_hash(const char* s, const int n) {
    const int p = 31, m = 1e9 + 7;
    int hash = 0;
    long p_pow = 1;
    for(int i = 0; i < n; i++) {
        hash = (hash + (s[i] - 'a' + 1) * p_pow) % m;
        p_pow = (p_pow * p) % m;
    }
    return hash;
}
 
int main() {
    char s[] = "geeksforgeeks";
    int n = strlen(s);
    printf("Hash of %s is %d\n", s, get_hash(s, n));
    return 0;
}

C++

#include <bits/stdc++.h>
using namespace std;
 
struct Hash {
    const int p = 31, m = 1e9 + 7;
    int hash_value;
    Hash(const string& s) {
        int hash_so_far = 0;
        long p_pow = 1;
        const int n = s.length();
        for (int i = 0; i < n; ++i) {
            hash_so_far = (hash_so_far + (s[i] - 'a' + 1) * p_pow) % m;
            p_pow = (p_pow * p) % m;
        }
        hash_value = hash_so_far;
    }
    bool operator==(const Hash& other) {
        return (hash_value == other.hash_value);
    }
};
 
int main() {
    const string s = "geeksforgeeks";
    Hash h(s);
    cout << "Hash of " << s << " is: " << h.hash_value << '\n';
    return 0;
}

Java

class Hash {
    final int p = 31, m = 1000000007;
    int hash_value;
    Hash(String S) {
        int hash_so_far = 0;
        final char[] s = S.toCharArray();
        long p_pow = 1;
        final int n = s.length;
        for (int i = 0; i < n; i++) {
            hash_so_far = (int)((hash_so_far + (s[i] - 'a' + 1) * p_pow) % m);
            p_pow = (p_pow * p) % m;
        }
        hash_value = hash_so_far;
    }
}
 
class Main {
    public static void main(String[] args) {
        String s = "geeksforgeeks";
        Hash h = new Hash(s);
        System.out.println("Hash of " + s + " is " + h.hash_value);
    }
}

Python3

class Hash:
    def __init__(self, s: str):
        self.hash_value = 0
        self.p, self.m = 31, 10**9 + 7
        self.length = len(s)
        hash_so_far = 0
        p_pow = 1
        for i in range(self.length):
            hash_so_far = (hash_so_far + (1 + ord(s[i]) - ord('a')) * p_pow) % self.m
            p_pow = (p_pow * self.p) % self.m
        self.hash_value = hash_so_far
     
    def __eq__(self, other):
        return self.hash_value == other.hash_value
 
 
if __name__ == '__main__':
    s = "geeksforgeeks"
    h = Hash(s)
    print("Hash value of {} is {}".format(s, h.hash_value))

Producción

Hash of geeksforgeeks is 609871790

Colisiones en polinomio Rolling Hash

Dado que la salida de la función Hash es un número entero en el rango $[0, m)$ , hay muchas posibilidades de que dos strings produzcan el mismo valor hash.

Por ejemplo, las strings $\text{``contraorden''}$ y $\text{``horno''}$ producen el mismo valor hash para $p = 31$ y $metro = 10^9 + 7$ .

Además, las strings $\text{``respuestas''}$ y $\text{``lugar''}$ producen el mismo valor hash para $pag = 37$ y $metro = 10^9 + 9$ .

Podemos garantizar una colisión dentro de un dominio muy pequeño. Considere un conjunto de strings, $S$ , que consta solo de letras minúsculas, de modo que la longitud de cualquier string $S$ no exceda $7$ .

tenemos $|S| = (26 + 26^2 + 26^3 + 26^4 + 26^5 + 26^6 + 26^7) = 8353082582\gt 10^9 + 7$ _ Dado que el rango de la función Hash es $[0, m)$ , el mapeo uno a uno es imposible. Por lo tanto, podemos garantizar una colisión generando arbitrariamente dos strings cuya longitud no exceda $7$ .

Resolución de colisión

Podemos notar que el valor de $metro$ afecta las posibilidades de colisión. Hemos visto que la probabilidad de colisión es $\cfrac{1}{m}$ . Podemos aumentar el valor de $metro$ para reducir la probabilidad de colisión. Pero eso afecta la velocidad del algoritmo. Cuanto mayor sea el valor de $metro$ , más lento será el algoritmo. Además, algunos lenguajes (C, C++, Java) tienen un límite en el tamaño del número entero. Por lo tanto, no podemos aumentar el valor de $metro$ a un valor muy grande.

Entonces, ¿cómo podemos minimizar las posibilidades de una colisión?

Tenga en cuenta que el hash de una string depende de dos parámetros: $pags$ y $metro$ .

Hemos visto que las strings $\text{``contraorden''}$ y $\text{``horno''}$ producen el mismo valor hash para $p = 31$ y $metro = 10^9 + 7$ . Pero para $pag = 37$ y $metro = 10^9 + 9$ , producen hashes diferentes.

Observación:

Si dos strings producen los mismos valores hash para un par $(p1, m1)$ , producirán valores hash diferentes para un par diferente, $(p2, m2)$ .

Estrategia:

Sin embargo, no podemos anular las posibilidades de colisión porque hay infinitas strings. Pero, seguramente, podemos reducir la probabilidad de que dos cuerdas choquen.

Podemos reducir la probabilidad de colisión generando un par de hashes para una string determinada. El primer hash se genera usando $p = 31$ y $metro = 10^9 + 7$ , mientras que el segundo hash se genera usando $pag = 37$ y $metro = 10^9 + 9$ .

¿Por qué funcionará esto?

Estamos generando dos hashes utilizando dos valores de módulo diferentes, $m1$ y $m2$ . La probabilidad de una colisión es ahora $\cfrac{1}{m1} \times \cfrac{1}{m2}$ . Dado que ambos $m1$ y $m2$ son mayores que $10^9$ , la probabilidad de que ocurra una colisión ahora es menor, lo $\displaystyle10^{-18}$ que es mucho mejor que la probabilidad original de colisión, $10^{-9}$ .

A continuación se muestra la implementación para el mismo

C

#include <stdio.h>
#include <string.h>
 
int get_hash1(const char* s, int length) {
    const int p = 31, m = 1e9 + 7;
    int hash_value = 0;
    long p_pow = 1;
    for(int i = 0; i < length; i++) {
        hash_value = (hash_value + (s[i] - 'a' + 1) * p_pow) % m;
        p_pow = (p_pow * p) % m;
    }
    return hash_value;
}
 
int get_hash2(const char* s, int length) {
    const int p = 37, m = 1e9 + 9;
    int hash_value = 0;
    long p_pow = 1;
    for(int i = 0; i < length; i++) {
        hash_value = (hash_value + (s[i] - 'a' + 1) * p_pow) % m;
        p_pow = (p_pow * p) % m;
    }
    return hash_value;
}
 
int main() {
    char s[] = "geeksforgeeks";
    int length = strlen(s);
    int hash1 = get_hash1(s, length);
    int hash2 = get_hash2(s, length);
    printf("Hash values of %s are: (%d, %d)\n", s, hash1, hash2);
    return 0;
}

C++

#include <bits/stdc++.h>
using namespace std;
 
struct Hash {
    const int p1 = 31, m1 = 1e9 + 7;
    const int p2 = 37, m2 = 1e9 + 9;
    int hash1 = 0, hash2 = 0;
    Hash(const string& s) {
        compute_hash1(s);
        compute_hash2(s);
    }
 
    void compute_hash1(const string& s) {
        long p_pow = 1;
        for(char ch: s) {
            hash1 = (hash1 + (ch + 1 - 'a') * p_pow) % m1;
            p_pow = (p_pow * p1) % m1;
        }
    }
 
    void compute_hash2(const string& s) {
        long p_pow = 1;
        for(char ch: s) {
            hash2 = (hash2 + (ch + 1 - 'a') * p_pow) % m2;
            p_pow = (p_pow * p2) % m2;
        }
    }
 
    // For two strings to be equal
    // they must have same hash1 and hash2
    bool operator==(const Hash& other) {
        return (hash1 == other.hash1 && hash2 == other.hash2);
    }
};
 
int main() {
    const string s = "geeksforgeeks";
    Hash h(s);
    cout << "Hash values of " << s << " are: ";
    cout << "(" << h.hash1 << ", " << h.hash2 << ")" << '\n';
    return 0;
}

Java

class Hash {
    final int p1 = 31, m1 = 1000000007;
    final int p2 = 37, m2 = 1000000009;
    int hash_value1, hash_value2;
    Hash(String s) {
        compute_hash1(s);
        compute_hash2(s);
    }
    void compute_hash1(String s) {
        int hash_so_far = 0;
        final char[] s_array = s.toCharArray();
        long p_pow = 1;
        final int n = s_array.length;
        for (int i = 0; i < n; i++) {
            hash_so_far = (int)((hash_so_far + (s_array[i] - 'a' + 1) * p_pow) % m1);
            p_pow = (p_pow * p1) % m1;
        }
        hash_value1 = hash_so_far;
    }
    void compute_hash2(String s) {
        int hash_so_far = 0;
        final char[] s_array = s.toCharArray();
        long p_pow = 1;
        final int n = s_array.length;
        for (int i = 0; i < n; i++) {
            hash_so_far = (int)((hash_so_far + (s_array[i] - 'a' + 1) * p_pow) % m2);
            p_pow = (p_pow * p2) % m2;
        }
        hash_value2 = hash_so_far;
    }
}
 
class Main {
    public static void main(String[] args) {
        String s = "geeksforgeeks";
        Hash h = new Hash(s);
        System.out.println("Hash values of " + s + " are: " + h.hash_value1 + ", " + h.hash_value2);
    }
}

Python3

class Hash:
    def __init__(self, s: str):
        self.p1, self.m1 = 31, 10**9 + 7
        self.p2, self.m2 = 37, 10**9 + 9
        self.hash1, self.hash2 = 0, 0
        self.compute_hashes(s)
 
    def compute_hashes(self, s: str):
        pow1, pow2 = 1, 1
        hash1, hash2 = 0, 0
        for ch in s:
            seed = 1 + ord(ch) - ord('a')
            hash1 = (hash1 + seed * pow1) % self.m1
            hash2 = (hash2 + seed * pow2) % self.m2
            pow1 = (pow1 * self.p1) % self.m1
            pow2 = (pow2 * self.p2) % self.m2
        self.hash1, self.hash2 = hash1, hash2
 
    def __eq__(self, other):
        return self.hash1 == other.hash1 and self.hash2 == other.hash2
 
    def __str__(self):
        return f'({self.hash1}, {self.hash2})'
 
 
if __name__ == '__main__':
    s = "geeksforgeeks"
    hash = Hash(s)
    print("Hash of " + s + " is " + str(hash))

Producción

Hash values of geeksforgeeks are: (609871790, 642799661)

Características de la función hash rodante polinomial

Cálculo de hashes de cualquier substring de una string dada en $O(1)$

Tenga en cuenta que calcular el hash de la string S también calculará los hash de todos los prefijos. Solo tenemos que almacenar los valores hash de los prefijos mientras computamos. Digamos que \text{hash[i]} denota el hash del prefijo \text{S[0…i]}, tenemos

$\text{hash[i...j]}\cdot p^i = \text{hash[0...j]} - \text{hash[0...(i - 1)]}$

Esto nos permite calcular rápidamente el hash de la substring $\text{S[i...j]}$ siempre $O(1)$ que tengamos poderes de $p$ preparación.

El comportamiento del hash cuando se cambia un carácter.

Recuerde que el hash de una string $s$ viene dado por

$\text{hash(s)} = \displaystyle\sum_{i = 0}^{n - 1} s[i]\cdot p^i\quad \text{mod}\ m$

Digamos que cambiamos un carácter $ch1$ en algún índice $i$ a algún otro carácter $ch2$ . ¿Cómo cambiará el hash?

Si $\text{hash\_old}$ denota el valor hash antes de cambiar y $\text{hash\_new}$ es el valor hash después de cambiar, entonces la relación entre ellos viene dada por

$\text{hash\_new} = \text{hash\_old} - p^i\cdot(ch1) + p^i\cdot(ch2)$

Por lo tanto, las consultas se pueden realizar muy rápidamente en lugar de volver a calcular el hash desde el principio, siempre que tengamos los poderes de $p$ listo.

A continuación se proporciona una implementación más elegante.

C++

#include <bits/stdc++.h>
using namespace std;
 
long long power(long long x, long long y, long long p) {
    long long result = 1;
    for(; y; y >>= 1, x = x * x % p) {
        if(y & 1) {
            result = result * x % p;
        }
    }
    return result;
}
 
long long inverse(long long x, long long p) {
    return power(x, p - 2, p);
}
 
class Hash {
private:
    int length;
    const int mod1 = 1e9 + 7, mod2 = 1e9 + 9;
    const int p1 = 31, p2 = 37;
    vector<int> hash1, hash2;
    pair<int, int> hash_pair;
 
public:
    inline static vector<int> inv_pow1, inv_pow2;
    inline static int inv_size = 1;
     
    Hash() {}
 
    Hash(const string& s) {
        length = s.size();
        hash1.resize(length);
        hash2.resize(length);
 
        int h1 = 0, h2 = 0;
        long long p_pow1 = 1, p_pow2 = 1;
        for(int i = 0; i < length; i++) {
            h1 = (h1 + (s[i] - 'a' + 1) * p_pow1) % mod1;
            h2 = (h2 + (s[i] - 'a' + 1) * p_pow2) % mod2;
            p_pow1 = (p_pow1 * p1) % mod1;
            p_pow2 = (p_pow2 * p2) % mod2;
            hash1[i] = h1;
            hash2[i] = h2;
        }
        hash_pair = make_pair(h1, h2);
 
        if(inv_size < length) {
            for(; inv_size < length; inv_size <<= 1);
             
            inv_pow1.resize(inv_size, -1);
            inv_pow2.resize(inv_size, -1);
 
            inv_pow1[inv_size - 1] = inverse(power(p1, inv_size - 1, mod1), mod1);
            inv_pow2[inv_size - 1] = inverse(power(p2, inv_size - 1, mod2), mod2);
             
            for(int i = inv_size - 2; i >= 0 && inv_pow1[i] == -1; i--) {
                inv_pow1[i] = (1LL * inv_pow1[i + 1] * p1) % mod1;
                inv_pow2[i] = (1LL * inv_pow2[i + 1] * p2) % mod2;
            }
        }
    }
 
    int size() {
        return length;
    }
 
    pair<int, int> prefix(const int index) {
        return {hash1[index], hash2[index]};
    }
 
    pair<int, int> substr(const int l, const int r) {
        if(l == 0) {
            return {hash1[r], hash2[r]};
        }
        int temp1 = hash1[r] - hash1[l - 1];
        int temp2 = hash2[r] - hash2[l - 1];
        temp1 += (temp1 < 0 ? mod1 : 0);
        temp2 += (temp2 < 0 ? mod2 : 0);
        temp1 = (temp1 * 1LL * inv_pow1[l]) % mod1;
        temp2 = (temp2 * 1LL * inv_pow2[l]) % mod2;
        return {temp1, temp2};
    }
 
    bool operator==(const Hash& other) {
        return (hash_pair == other.hash_pair);
    }
};
 
 
int main() {
    string my_str = "geeksforgeeks";
    const int n = my_str.length();
    auto hash = Hash(my_str);
    auto hash_pair = hash.substr(0, n - 1);
    cout << "Hashes of the string " << my_str << " are:\n";
    cout << hash_pair.first << ' ' << hash_pair.second << '\n';
    return 0;
}

En la implementación anterior, estamos calculando las inversas de las potencias de $p$en tiempo lineal.

Aplicaciones:

Considere este problema: Dada una secuencia S de N strings y Q consultas. En cada consulta, se le dan dos índices, i y j, su tarea es encontrar la longitud del prefijo común más largo de las strings S[i] y S[j].

Antes de entrar en el enfoque para resolver este problema, tenga en cuenta que las restricciones son:

$1\le N \le 10^5\\ 1\le Q \le 10^5\\ 1\le |S| \le 10^5\\ \text{The Sum of |S| over all test cases doesn't exceed } 10^6$

Usando Hashing, el problema se puede resolver en O(N + Q/log|S|_{max}). El enfoque es calcular hashes para todas las strings en tiempo O (N). Luego, para cada consulta, podemos buscar binariamente la longitud del prefijo común más largo usando hashing. La implementación de este enfoque se proporciona a continuación.

C++14

#include <bits/stdc++.h>
using namespace std;
 
long long power(long long x, long long y, long long p) {
    long long result = 1;
    for(; y; y >>= 1, x = x * x % p) {
        if(y & 1) {
            result = result * x % p;
        }
    }
    return result;
}
 
long long inverse(long long x, long long p) {
    return power(x, p - 2, p);
}
 
class Hash {
private:
    int length;
    const int mod1 = 1e9 + 7, mod2 = 1e9 + 9;
    const int p1 = 31, p2 = 37;
    vector<int> hash1, hash2;
    pair<int, int> hash_pair;
 
public:
    inline static vector<int> inv_pow1, inv_pow2;
    inline static int inv_size = 1;
     
    Hash() {}
 
    Hash(const string& s) {
        length = s.size();
        hash1.resize(length);
        hash2.resize(length);
 
        int h1 = 0, h2 = 0;
        long long p_pow1 = 1, p_pow2 = 1;
        for(int i = 0; i < length; i++) {
            h1 = (h1 + (s[i] - 'a' + 1) * p_pow1) % mod1;
            h2 = (h2 + (s[i] - 'a' + 1) * p_pow2) % mod2;
            p_pow1 = (p_pow1 * p1) % mod1;
            p_pow2 = (p_pow2 * p2) % mod2;
            hash1[i] = h1;
            hash2[i] = h2;
        }
        hash_pair = make_pair(h1, h2);
 
        if(inv_size < length) {
            for(; inv_size < length; inv_size <<= 1);
             
            inv_pow1.resize(inv_size, -1);
            inv_pow2.resize(inv_size, -1);
 
            inv_pow1[inv_size - 1] = inverse(power(p1, inv_size - 1, mod1), mod1);
            inv_pow2[inv_size - 1] = inverse(power(p2, inv_size - 1, mod2), mod2);
             
            for(int i = inv_size - 2; i >= 0 && inv_pow1[i] == -1; i--) {
                inv_pow1[i] = (1LL * inv_pow1[i + 1] * p1) % mod1;
                inv_pow2[i] = (1LL * inv_pow2[i + 1] * p2) % mod2;
            }
        }
    }
 
    int size() {
        return length;
    }
 
    pair<int, int> prefix(const int index) {
        return {hash1[index], hash2[index]};
    }
 
    pair<int, int> substr(const int l, const int r) {
        if(l == 0) {
            return {hash1[r], hash2[r]};
        }
        int temp1 = hash1[r] - hash1[l - 1];
        int temp2 = hash2[r] - hash2[l - 1];
        temp1 += (temp1 < 0 ? mod1 : 0);
        temp2 += (temp2 < 0 ? mod2 : 0);
        temp1 = (temp1 * 1LL * inv_pow1[l]) % mod1;
        temp2 = (temp2 * 1LL * inv_pow2[l]) % mod2;
        return {temp1, temp2};
    }
 
    bool operator==(const Hash& other) {
        return (hash_pair == other.hash_pair);
    }
};
 
void query(vector<Hash>& hashes, const int N) {
    int i = 0, j = 0;
    cin >> i >> j;
    i--, j--;
    int lb = 0, ub = min(hashes[i].size(), hashes[j].size());
    int max_length = 0;
    while(lb <= ub) {
        int mid = (lb + ub) >> 1;
        if(hashes[i].prefix(mid) == hashes[j].prefix(mid)) {
            if(mid + 1 > max_length) {
                max_length = mid + 1;
            }
            lb = mid + 1;
        }
        else {
            ub = mid - 1;
        }
    }
    cout << max_length << '\n';
}
 
int main() {
    int N = 0, Q = 0;
    cin >> N >> Q;
    vector<Hash> hashes;
    for(int i = 0; i < N; i++) {
        string s;
        cin >> s;
        hashes.push_back(Hash(s));
    }
    for(; Q > 0; Q--) {
        query(hashes, N);
    }
    return 0;
}

Input:
5 4
geeksforgeeks geeks hell geeksforpeaks hello
1 2
1 3
3 5
1 4

Expected Output:
5
0
4
8

Publicación traducida automáticamente

Artículo escrito por 7maestro y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Función hash

La función hash rodante polinomial

C

C++

Java

Python3

Colisiones en polinomio Rolling Hash

Resolución de colisión

Observación:

Estrategia:

¿Por qué funcionará esto?

C

C++

Java

Python3

Características de la función hash rodante polinomial

Cálculo de hashes de cualquier substring de una string dada en

El comportamiento del hash cuando se cambia un carácter.

C++

Aplicaciones:

C++14

Deja una respuesta Cancelar la respuesta

Cálculo de hashes de cualquier substring de una string dada en $O(1)$