Hashing de strings

Los algoritmos de hashing son útiles para resolver muchos problemas.

Queremos resolver el problema de comparar strings de forma eficiente. La forma por fuerza bruta es simplemente comparar las letras de ambos strings, lo que tiene complejidad temporal $O(\min(n_1, n_2))$ si $n_1$ y $n_2$ son los tamaños de los dos strings. Queremos hacerlo mejor. La idea detrás del hashing de strings es la siguiente: mapeamos cada string a un entero y comparamos esos enteros en lugar de los strings. Hacer esto nos permite reducir el tiempo de ejecución de la comparación de strings a $O(1)$ .

Para la conversión necesitamos una función de hash (hash function). Su objetivo es convertir un string en un entero, el llamado hash del string. Tiene que cumplirse la siguiente condición: si dos strings $s$ y $t$ son iguales ( $s = t$ ), entonces sus hashes también tienen que ser iguales ( $\text{hash}(s) = \text{hash}(t)$ ). En caso contrario, no podremos comparar strings.

Nótese que la dirección contraria no tiene por qué cumplirse. Si los hashes son iguales ( $\text{hash}(s) = \text{hash}(t)$ ), entonces los strings no tienen por qué ser necesariamente iguales. Por ejemplo, una función de hash válida sería simplemente $\text{hash}(s) = 0$ para cada $s$ . Ahora, esto es solo un ejemplo tonto, porque esta función será completamente inútil, pero es una función de hash válida. La razón por la que la dirección contraria no tiene por qué cumplirse es que hay exponencialmente muchos strings. Si solo queremos que esta función de hash distinga entre todos los strings formados por caracteres en minúscula de longitud menor que 15, entonces el hash ya no cabría en un entero de 64 bits (p. ej. unsigned long long), porque hay demasiados. Y, por supuesto, no queremos comparar enteros arbitrariamente largos, porque eso también tendría complejidad $O(n)$ .

Así que, por lo general, queremos que la función de hash mapee los strings a números de un rango fijo $[0, m)$ ; entonces comparar strings es simplemente comparar dos enteros de longitud fija. Y, por supuesto, queremos que $\text{hash}(s) \neq \text{hash}(t)$ sea muy probable si $s \neq t$ .

Esa es la parte importante que hay que tener presente. Usar hashing no será 100% correcto de forma determinista, porque dos strings completamente distintos pueden tener el mismo hash (los hashes colisionan). Sin embargo, en una amplia mayoría de tareas esto se puede ignorar con seguridad, ya que la probabilidad de que colisionen los hashes de dos strings distintos sigue siendo muy pequeña. Y en este artículo discutiremos algunas técnicas para mantener muy baja la probabilidad de colisiones.

Cálculo del hash de un string

La forma buena y ampliamente usada de definir el hash de un string $s$ de longitud $n$ es

$\begin{aligned} hash (s) & = s [0] + s [1] \cdot p + s [2] \cdot p^{2} + . . . + s [n - 1] \cdot p^{n - 1} m o d m \\ = \sum_{i = 0}^{n - 1} s [i] \cdot p^{i} m o d m, \end{aligned}$

donde $p$ y $m$ son algunos números positivos elegidos. Se llama función de hash polinómico rolling (polynomial rolling hash).

Es razonable tomar $p$ como un número primo aproximadamente igual a la cantidad de caracteres del alfabeto de entrada. Por ejemplo, si la entrada está compuesta solo por letras minúsculas del alfabeto inglés, $p = 31$ es una buena elección. Si la entrada puede contener letras mayúsculas y minúsculas, entonces $p = 53$ es una elección posible. El código de este artículo usará $p = 31$ .

Obviamente $m$ debería ser un número grande, ya que la probabilidad de que colisionen dos strings aleatorios es aproximadamente $\approx \frac{1}{m}$ . A veces se elige $m = 2^{64}$ , porque entonces los desbordamientos de enteros de 64 bits funcionan exactamente como la operación módulo. Sin embargo, existe un método que genera strings que colisionan (y funciona independientemente de la elección de $p$ ). Así que, en la práctica, no se recomienda $m = 2^{64}$ . Una buena elección para $m$ es algún número primo grande. El código de este artículo usará simplemente $m = 10^9+9$ . Este es un número grande, pero todavía lo bastante chico como para poder multiplicar dos valores usando enteros de 64 bits.

Acá hay un ejemplo de cómo calcular el hash de un string $s$ que contiene solo letras minúsculas. Convertimos cada carácter de $s$ a un entero. Acá usamos la conversión $a \rightarrow 1$ , $b \rightarrow 2$ , $\dots$ , $z \rightarrow 26$ . Convertir $a \rightarrow 0$ no es una buena idea, porque entonces los hashes de los strings $a$ , $aa$ , $aaa$ , $\dots$ todos evalúan a $0$ .


long long compute_hash(string const& s) {
    const int p = 31;
    const int m = 1e9 + 9;
    long long hash_value = 0;
    long long p_pow = 1;
    for (char c : s) {
        hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;
        p_pow = (p_pow * p) % m;
    }
    return hash_value;
}

Precomputar las potencias de $p$ puede dar una mejora de rendimiento.

Tareas de ejemplo

Buscar strings duplicados en un arreglo de strings

Problema: Dada una lista de $n$ strings $s_i$ , cada uno de no más de $m$ caracteres, encontrar todos los strings duplicados y dividirlos en grupos.

Con el algoritmo obvio que ordena los strings, obtendríamos una complejidad temporal de $O(n m \log n)$ , donde el ordenamiento requiere $O(n \log n)$ comparaciones y cada comparación tarda $O(m)$ . Sin embargo, usando hashes reducimos el tiempo de comparación a $O(1)$ , lo que nos da un algoritmo que corre en tiempo $O(n m + n \log n)$ .

Calculamos el hash de cada string, ordenamos los hashes junto con los índices, y después agrupamos los índices por hashes idénticos.


vector<vector<int>> group_identical_strings(vector<string> const& s) {
    int n = s.size();
    vector<pair<long long, int>> hashes(n);
    for (int i = 0; i < n; i++)
        hashes[i] = {compute_hash(s[i]), i};

    sort(hashes.begin(), hashes.end());

    vector<vector<int>> groups;
    for (int i = 0; i < n; i++) {
        if (i == 0 || hashes[i].first != hashes[i-1].first)
            groups.emplace_back();
        groups.back().push_back(hashes[i].second);
    }
    return groups;
}

Cálculo rápido del hash de subcadenas de un string dado

Problema: Dado un string $s$ e índices $i$ y $j$ , encontrar el hash de la subcadena $s [i \dots j]$ .

Por definición, tenemos:

$\text{hash}(s[i \dots j]) = \sum_{k = i}^j s[k] \cdot p^{k-i} \mod m$

Al multiplicar por $p^i$ obtenemos:

$\begin{aligned} hash (s [i \dots j]) \cdot p^{i} & = \sum_{k = i}^{j} s [k] \cdot p^{k} m o d m \\ = hash (s [0 \dots j]) - hash (s [0 \dots i - 1]) m o d m \end{aligned}$

Así, conociendo el valor del hash de cada prefijo del string $s$ , podemos calcular el hash de cualquier subcadena directamente con esta fórmula. El único problema que enfrentamos al calcularlo es que debemos poder dividir $\text{hash}(s[0 \dots j]) - \text{hash}(s[0 \dots i-1])$ por $p^i$ . Por lo tanto hay que encontrar el inverso multiplicativo modular de $p^i$ y después multiplicar por ese inverso. Podemos precomputar el inverso de cada $p^i$ , lo que permite calcular el hash de cualquier subcadena de $s$ en tiempo $O(1)$ .

Sin embargo, existe una forma más fácil. En la mayoría de los casos, en lugar de calcular los hashes de las subcadenas de forma exacta, basta con calcular el hash multiplicado por alguna potencia de $p$ . Supongamos que tenemos dos hashes de dos subcadenas, uno multiplicado por $p^i$ y el otro por $p^j$ . Si $i < j$ entonces multiplicamos el primer hash por $p^{j-i}$ ; en caso contrario, multiplicamos el segundo hash por $p^{i-j}$ . Al hacer esto, obtenemos ambos hashes multiplicados por la misma potencia de $p$ (que es el máximo de $i$ y $j$ ) y ahora estos hashes se pueden comparar fácilmente sin necesidad de ninguna división.

Aplicaciones del hashing

Acá hay algunas aplicaciones típicas del hashing:

Algoritmo de Rabin-Karp para búsqueda de patrones en un string en tiempo $O(n)$
Calcular el número de subcadenas distintas de un string en $O(n^2)$ (ver más abajo)
Calcular el número de subcadenas palindrómicas de un string.

Determinar el número de subcadenas distintas de un string

Problema: Dado un string $s$ de longitud $n$ , formado solo por letras minúsculas inglesas, encontrar el número de subcadenas distintas de este string.

Para resolver este problema, iteramos sobre todas las longitudes de subcadena $l = 1 \dots n$ . Para cada longitud de subcadena $l$ construimos un arreglo de hashes de todas las subcadenas de longitud $l$ multiplicados por la misma potencia de $p$ . El número de elementos distintos en el arreglo es igual al número de subcadenas distintas de longitud $l$ en el string. Este número se suma a la respuesta final.

Por conveniencia, usaremos $h[i]$ como el hash del prefijo con $i$ caracteres, y definimos $h[0] = 0$ .


int count_unique_substrings(string const& s) {
    int n = s.size();
    
    const int p = 31;
    const int m = 1e9 + 9;
    vector<long long> p_pow(n);
    p_pow[0] = 1;
    for (int i = 1; i < n; i++)
        p_pow[i] = (p_pow[i-1] * p) % m;

    vector<long long> h(n + 1, 0);
    for (int i = 0; i < n; i++)
        h[i+1] = (h[i] + (s[i] - 'a' + 1) * p_pow[i]) % m;

    int cnt = 0;
    for (int l = 1; l <= n; l++) {
        unordered_set<long long> hs;
        for (int i = 0; i <= n - l; i++) {
            long long cur_h = (h[i + l] + m - h[i]) % m;
            cur_h = (cur_h * p_pow[n-i-1]) % m;
            hs.insert(cur_h);
        }
        cnt += hs.size();
    }
    return cnt;
}

Nótese que $O(n^2)$ no es la mejor complejidad temporal posible para este problema. Una solución en $O(n \log n)$ se describe en el artículo sobre arreglos de sufijos, y hasta es posible calcularlo en $O(n)$ usando un árbol de sufijos o un autómata de sufijos.

Mejorar la probabilidad de no colisión

Muy a menudo el hash polinómico mencionado arriba es suficientemente bueno, y no habrá colisiones durante los casos de prueba. Recordemos que la probabilidad de que ocurra una colisión es solo $\approx \frac{1}{m}$ . Para $m = 10^9 + 9$ la probabilidad es $\approx 10^{-9}$ , que es bastante baja. Pero nótese que solo hicimos una comparación. ¿Qué pasa si comparamos un string $s$ con $10^6$ strings distintos? La probabilidad de que ocurra al menos una colisión es ahora $\approx 10^{-3}$ . Y si queremos comparar $10^6$ strings distintos entre sí (p. ej. contando cuántos strings únicos existen), entonces la probabilidad de que ocurra al menos una colisión ya es $\approx 1$ . Está prácticamente garantizado que esta tarea terminará con una colisión y devolverá el resultado incorrecto.

Hay un truco realmente fácil para obtener mejores probabilidades. Podemos simplemente calcular dos hashes distintos para cada string (usando dos $p$ distintos, y/o distintos $m$ ) y comparar esos pares en su lugar. Si $m$ es del orden de $10^9$ para cada una de las dos funciones de hash, entonces esto es más o menos equivalente a tener una sola función de hash con $m \approx 10^{18}$ . Al comparar $10^6$ strings entre sí, la probabilidad de que ocurra al menos una colisión queda reducida a $\approx 10^{-6}$ .