Linear Counting: cómo estimar el número de valores distintos

¿Cómo podríamos contar el número de valores distintos de un conjunto de datos si hay muchísimos datos? Imagina, por ejemplo, un servicio que mide el número de usuarios únicos de una web enorme, o incluso de todo el dominio .es/.com/.whatever o algo así.

El método ingenuo

Vale, no hay nada que pensar: recorremos los datos y guardamos cada valor exactamente una vez en alguna estructura de datos adecuada. En Python podríamos escribirlo más o menos así (el código es innecesariamente verboso, y es a propósito):

nonunique_values = [1, 2, 3, 2, 2, 4, 1, 1, 3, 5, 2]

def count_unique(values):
    found = set()
    for item in values:
        if item not in found:
            found.add(item)
    return len(found)

print count_unique(nonunique_values) # 5

Funciona. Pero ¿y si los datos son identificadores únicos uuid v4 de 36 caracteres y hay, por ejemplo, diez millones de identificadores distintos? El programa sigue calculando el valor correcto, pero ¿cuánta memoria ocupa? Podemos intentar calcularlo. Para simplificar, supondremos que guardamos cada uuid como una cadena de 36 caracteres. Un uuid ocupa entonces 36 bytes y diez millones de identificadores ocupan 360 MB.

Reconozcámoslo: no es poco. Si los identificadores únicos fueran cien millones, ya estaríamos en el orden de los gigabytes de memoria ocupada. Y eso contando solo lo que ocupan los datos. Añade la sobrecarga (overhead) de Python o JavaScript y podrías llegar al orden de los gigabytes incluso con diez millones de identificadores:

No quieres eso. ¿Cómo salir de aquí?

Podemos intentar guardar los propios identificadores de forma más eficiente, podemos usar C en lugar de Python, con lo que reduciremos mucho el consumo de memoria, pero seguirá sin ser lo ideal y el programa continuaría ocupando una cantidad enorme de espacio. Queda preguntarse: ¿de verdad necesitamos saber con precisión absoluta si hay exactamente 9.563.618 valores distintos? ¿Pasaría algo si trabajáramos con 9.547.666? Si tu respuesta es que sí pasaría y que lo quieres exacto, pues adelante, tú mismo. En caso contrario, veamos cómo estimar el número de valores distintos de un conjunto de datos con la mayor precisión y rapidez posibles y con un consumo mínimo de memoria.

La función hash, nuestra salvación

Consideremos una función hash que recibe una cadena y devuelve un número de n bits. Si estás acostumbrado a funciones hash que «devuelven una cadena», imagina simplemente que esa cadena se convierte después en un número; no tiene mayor misterio. El número de bits indica lo grande que es el número. Una función de 8 bits devuelve un número que ocupa ocho bits, y en ocho bits caben 2⁸ valores distintos, normalmente los números enteros de 0 a 255. De ahora en adelante trabajaremos con una función hash de 24 bits. Una función así devuelve 2²⁴ valores distintos, es decir, 16.777.216.

En lugar de guardar los valores en sí, guardaremos sus hashes de 24 bits. Para guardar diez millones de hashes de 24 bits necesitamos 30 MB. Es un orden de magnitud mejor que los 360 MB anteriores. El código podría ser así:

def nhash(item, n):
    return hash(item) % (2 ** n)

nonunique_values = [1, 2, 3, 2, 2, 4, 1, 1, 3, 5, 2]

def count_unique_using_nhash(values):
    found = set()
    for item in values:
        checksum = nhash(item, 24)
        if checksum not in found:
            found.add(checksum)
    return len(found)

print count_unique_using_nhash(nonunique_values) # 5

La función hash es una función nativa de Python y devuelve un número entero; la función nhash muestra una implementación ingenua de una función hash de n bits; no es importante entender cómo funciona, porque de todos modos no funciona bien —el resultado de esa función no ocupa 24 bits—, pero eso ahora da igual, lo que me interesa es el principio.

A continuación viene la función count_unique_using_nhash, que cuenta los valores distintos. Recorre todos los valores, calcula su hash y lo guarda en la variable found si ese valor no estaba ya.

El problema de este método es que la función hash puede devolver el mismo checksum para cadenas distintas —puede producirse una colisión—. Cuantas más colisiones se producen, menos exacto es el resultado. La función count_unique_using_nhash casi siempre devolverá un número de valores distintos menor que el real.

¿Y qué función hash elegir? No importa tanto, pero en general se recomienda alguna variante de MurmurHash.

Mapas de bits

¿Prestaste atención en tu curso de introducción a la programación en C? Si es así, conoces los mapas de bits. ¿Cómo podríamos usarlos?

Esbocemos la idea con un array. No necesitamos conservar los checksums calculados: podemos crear un array de longitud 2²⁴ e inicializar todos sus elementos a cero. Entonces, cada vez que encontremos un checksum —¡que es un número!—, escribimos un uno en el array, en el índice checksum, con lo que anotamos que ya hemos encontrado ese checksum. El número de elementos distintos será aproximadamente igual al número de unos del array. El código podría ser así:

def count_unique_using_array(values):
    # lista de longitud 2^24 con todos los elementos inicializados a cero
    array = [0] * (2 ** 24) 
    for item in values:
        array[nhash(item, 24)] = 1
    return sum(array)

print count_unique_using_array(nonunique_values)

Sin embargo, usar un array es en este caso muy costoso en memoria, porque en cada celda necesitamos guardar siempre un uno o un cero. En su lugar podemos usar un array de bits. Para que lo entiendas: un número entero (integer) se puede guardar, por ejemplo, en 32 bits. Si pasamos el número 354 al sistema binario, obtenemos 101100010. El número 354 se guardaría entonces en el ordenador como un entero de 32 bits así (no nos importan los detalles, ¿vale?):

00000000 00000000 00000001 01100010

Es un formato bastante práctico que podríamos aprovechar, ¿verdad? En nuestra función solo queremos guardar unos y ceros, y acabamos de comprobar que un número corriente no es más que un montón de ceros y unos (como casi todo en el ordenador…). En resumen, con operadores a nivel de bits podemos guardar un uno de modo que ocupe realmente un solo bit.

Volvamos a nuestra función con el array. Si la reescribiéramos con arrays de bits, para una función hash de 24 bits nos bastaría un array de bits de tamaño 2²⁴ bits, es decir, 2 MiB. ¡Una mejora considerable!

Con una función hash de 32 bits, que tiene 2³² valores de salida distintos, es decir, 4.294.967.296, necesitaríamos un array de bits de medio gigabyte. No está nada mal, teniendo en cuenta que así podemos contar valores distintos hasta del orden de miles de millones.

Linear Counting

Ya he mencionado que al usar una función hash obtenemos solo una estimación del número de valores distintos. Esta estimación es tanto más imprecisa cuanto más se acerca el número de valores distintos al número de valores de salida distintos de la función hash. Es lógico que, si tenemos un conjunto de datos con cinco mil millones de valores distintos, una función hash de 24 bits no pueda contarlos.

No obstante, la estimación que calculamos con funciones hash se puede afinar más. Se usa para ello una idea sencilla: cuantos más valores distintos hay en el conjunto de datos, más probable es que con el tiempo aparezcan colisiones. (Colisión = dos entradas distintas tienen la misma salida de la función hash, el mismo checksum.) Ahora vamos a hacer algunos cálculos, así que introduzcamos unas cuantas variables:

Trabajaremos con una función hash h de n bits.
El número de todas las salidas posibles de la función h es entonces igual a 2ⁿ. Lo designamos con la letra m, es decir: m=2ⁿ.
El array de bits en el que guardaremos qué checksums hemos encontrado lo designamos con la letra mayúscula A. El array A tiene longitud m.
Cuando el algoritmo haya recorrido todo el conjunto de datos, algunos valores del array de bits serán ceros y otros unos. Nos interesará sobre todo el cociente «número de ceros dividido entre la longitud del array», que nos da la proporción relativa de ceros en el array de bits. Al principio esa proporción es 1, porque el array está inicializado a cero. Si estuviera mitad y mitad, la proporción sería un medio, etc. Designamos este valor con Z y lo calculamos como Z = número de ceros / m.

En este momento, cuanto mayor es el valor de Z, mayor es la seguridad de que nuestra estimación del número de valores distintos es exacta. Si, por ejemplo, recorremos un conjunto de datos vacío, en el array de bits quedarán solo ceros y el valor de Z será igual a uno; tenemos así plena seguridad de que en nuestro conjunto de datos hay tantos elementos distintos como unos hay en el array de bits: cero.

Si el valor de Z es 0,99, significa que una centésima del array de bits está llena de unos. El 99 % del array contiene ceros. Eso todavía es bueno: es probable que durante el cálculo no se hayan producido demasiadas colisiones y que haga falta poca o ninguna corrección. Pero si el valor de Z es 0,05, solo el 5 % del array ha quedado a cero y probablemente nos hemos topado con muchísimas colisiones: hará falta una corrección grande.

Pero ¿cómo calcular esa corrección? Nos ayudaremos del logaritmo, una función que tiene esta forma:

Nos interesa la parte roja en el intervalo (0, 1]. Si en el eje x representamos el valor de Z, conseguimos que cuanto mayor sea Z, más se acerque el valor de y a cero. Y al revés: cuanto menor sea Z, menor será y. La estimación final se obtiene multiplicando este número por -m. Fíjate en que, para un valor de Z suficientemente bajo, obtenemos un número que es incluso menor que -1, y si multiplicamos este valor por -m, obtenemos una estimación mayor que m: hemos estimado que el número de valores distintos es mayor que el número de todos los checksums posibles que pueden salir de la función hash h.

La fórmula completa para calcular el número p de valores distintos sería esta:

$p = - m \cdot \ln Z$

Una implementación (sin arrays de bits, solo con arrays normales) podría ser así:

from uuid import uuid4
from math import log

number_of_unique_values = 10000
nonunique_values = [uuid4() for _ in xrange(number_of_unique_values)]
nonunique_values += nonunique_values

def nhash(item, n):
    return hash(item) % (2 ** n)

def count_unique_using_array(values, n):
    array = [0] * (2 ** n)
    for item in values:
        array[nhash(item, n)] = 1
    return sum(array)

def linear_counting(values, n):
    estimate = count_unique_using_array(values, n)
    m = 2 ** n
    number_of_zeros = m - estimate
    Z = float(number_of_zeros) / m
    # log es aqui el logaritmo neperiano (de base e)
    p = (-m) * log(Z)      
    p = int(round(p))
    print "Debug info: estimate=%s, m=%s, number_of_zeros=%s, Z=%s, p=%s" % \
          (estimate, m, number_of_zeros, Z, p)
    return p

print "Cardinality: %s" % linear_counting(nonunique_values, 16)

En la función linear_counting calculamos primero una primera estimación con el algoritmo anterior, que usa una función hash de n bits. Después calculamos la proporción de ceros del array y aplicamos la corrección según la fórmula. El logaritmo del código es el logaritmo neperiano. La variable nonunique_values contiene number_of_unique_values cadenas distintas; en este ejemplo, por tanto, la lista nonunique_values contiene diez mil valores distintos. Esa línea rara, la sexta, hace que en el array haya más valores iguales: simplemente añadimos al final de la lista la misma lista de valores, de modo que cada valor aparece dos veces. Y ya podemos calcular. Lo ideal es que la función devuelva que la lista contiene diez mil valores distintos. Salida:

Debug info: estimate=9289, m=65536, number_of_zeros=56247, 
Z=0.858261108398, p=10017
Cardinality: 10017

Como cada vez se genera una lista nonunique_values distinta, los resultados variarán en cada ejecución. Hemos usado una función hash de 16 bits. Vemos que la primera estimación de la función count_unique_using_array fue que la lista contiene 9289 valores distintos. Con la corrección hemos afinado esa estimación hasta 10.017, que ya es bastante decente: nuestra estimación es mayor solo en un 0,17 %, mientras que antes era menor en un 7,11 %, que es bastante.

Si tomáramos una función hash «más grande», por ejemplo de 24 bits, obtendríamos un resultado más exacto:

Debug info: estimate=9997, m=16777216, number_of_zeros=16767219, 
Z=0.999404132366, p=10000
Cardinality: 10000

La estimación original ya era buena, y con la corrección hemos llegado a diez mil exactos. Como demostración, podemos probar con un millón de identificadores únicos, es decir, number_of_unique_values = 1000000. Con una función hash de 24 bits obtenemos estos resultados:

Debug info: estimate=971033, m=16777216, number_of_zeros=15806183, 
Z=0.94212192297, p=1000267
Cardinality: 1000267

Nada mal. Y eso que, si lo implementamos como array de bits, el array ocuparía solo los dos megabytes mencionados (más lo que consuma el lenguaje). Para mí, bastante bien. But we can do better! Much better. Pero eso será en la próxima entrega.

Mientras tanto, puedes leer el artículo A Linear-Time Probabilistic Counting Algorithm for Database Applications [PDF]. O puedes pasar a la siguiente parte de la serie: el algoritmo Min Value.

Capítulos: Linear Counting: cómo estimar el número de valores distintos, Min Value: cómo estimar el número de valores distintos, LogLog: cómo estimar el número de valores distintos, HyperLogLog: cómo estimar con precisión el número de valores distintos

« Anterior: Conversión de un autómata en una expresión regular

Siguiente: Min Value: cómo estimar el número de valores distintos »