Min Value: como estimar o número de valores distintos

No artigo anterior sobre Linear Counting, vimos os algoritmos básicos para calcular e estimar o número de valores distintos em algum conjunto de dados. Hoje nos espera outro algoritmo probabilístico, que permite estimar o número de valores distintos com precisão razoável e pouca memória.

Min Value

Neste artigo vamos trabalhar apenas com números reais do intervalo unitário ]0, 1[. Imagine um conjunto de números desse intervalo que estejam distribuídos uniformemente, por exemplo o conjunto de números {0,25; 0,5; 0,75}. Números vizinhos estão sempre separados (e separados de zero e de um) por exatamente 0,25. Como isso nos ajuda a contar o número de elementos distintos?

Se eu disser que temos um conjunto de números do intervalo unitário distribuídos uniformemente e que esses números têm entre si uma distância de exatamente 0,2 — você consegue calcular quantos elementos esse conjunto tem? Claro, trata-se do conjunto {0,2; 0,4; 0,6; 0,8}, cuja cardinalidade é igual a quatro. Se temos na entrada números do intervalo unitário distribuídos uniformemente e conhecemos a distância entre números vizinhos, conseguimos calcular facilmente o número de elementos.

Além disso, a distância entre números vizinhos é igual ao menor elemento do conjunto — a distância entre elementos vizinhos do conjunto {0,25; 0,5; 0,75} é 0,25 etc. Para calcular o número de elementos de um conjunto de números distribuídos uniformemente, basta descobrirmos de algum modo o menor elemento. Então podemos calcular o número de elementos p com uma fórmula simples:

$$p=\frac{1}{m}-1$$

em que m é aquele menor elemento.

E de novo vamos aplicar hash…

Pois é, mas como usar isso se na entrada temos strings ou outros valores que não satisfazem exatamente a condição de distribuição uniforme no intervalo unitário? Vamos recorrer de novo à boa e velha função hash, que pode nos devolver, para qualquer entrada, um número racional do intervalo unitário. Construir uma função hash assim será fácil.

Com isso obteríamos dos dados números racionais, mas como fazer com que esses números sejam distribuídos uniformemente? Isso não será possível, mas podemos dar um jeito de outra forma. A função hash se comporta, do nosso ponto de vista, de modo bastante “aleatório”. Para palavras muito parecidas, como “casa”, “cala” e “caso”, a função hash provavelmente nos devolverá checksums muito diferentes. Em outras palavras: se aplicarmos hash em mil valores diferentes no intervalo unitário, é muito improvável que uma maioria expressiva dos números seja, por exemplo, menor do que um meio. Pelo contrário, é muito provável que esses números fiquem distribuídos mais ou menos regularmente. Quanto mais dados passamos pelo hash, mais regular será essa distribuição.

Dessa ideia sai um algoritmo simples: percorremos os dados de entrada, aplicamos hash em cada elemento no intervalo unitário e memorizamos o menor elemento. Estimamos o número de elementos distintos pela fórmula anterior. Implementação em Python:

from uuid import uuid4

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

def unit_interval_hash(item, n):
    integer_hash = nhash(item, n) + 1
    return integer_hash / float(2 ** n)

def count_unique_using_minimum(values, n):
    numbers_from_unit_interval = (unit_interval_hash(item, n) for item in values)
    minimum = min(numbers_from_unit_interval)
    return int(1 / minimum) - 1

for _ in xrange(10):
    print count_unique_using_minimum((uuid4() for _ in xrange(10000)), 16)

A função unit_interval_hash devolve um número decimal do intervalo ]0, 1]. A função count_unique_using_minimum primeiro converte todos os valores de entrada justamente nesse número, encontra o mínimo e devolve 1 / minimum - 1. Observe que não importa em nada quantos valores iguais há no conjunto de dados — para dois valores iguais, a função hash nos devolve o mesmo número racional, o que não influencia de modo algum o mínimo resultante. Por isso, com esse algoritmo contamos o número de elementos distintos.

Quais são os resultados? (Em cada linha está a cardinalidade estimada; a cardinalidade correta é 10.000.)

5957
16384
13107
9362
65536
8192
21845
13107
21845
8192

Bom, nada de mais, né? O algoritmo percorreu dez conjuntos diferentes de IDs, nos quais havia sempre dez mil valores distintos. As estimativas calculadas estão, em sua maioria, bem longe. Se tirássemos a média delas, chegaríamos ao valor 18.352. Ainda está bem longe, mas, por outro lado, olhe para o consumo de memória — ele é constante! Para encontrar o mínimo, basta guardar na memória uma única variável, na qual você guarda o mínimo atual, e pronto. Então é isso: estimativa fraca, mas quase não custa nada.

Melhorando

Vemos que o algoritmo é, sobretudo, instável — uma vez nos devolve uma estimativa bem razoável (9362), outra vez nos devolve uma estimativa completamente fora (65536). Como sair dessa? Podemos resolver isso dividindo os dados de entrada em várias partes, calculando o número de elementos distintos de cada parte e, por fim, tirando a média de tudo direitinho. Poderíamos decidir pelo primeiro caractere do nosso ID. Assim, calculamos separadamente o número de valores distintos para os IDs que começam com a letra “a”, depois para os que começam com a letra “b” etc. Código:

from uuid import uuid4

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

def unit_interval_hash(item, n):
    integer_hash = nhash(item, n) + 1
    return integer_hash / float(2 ** n)

def count_unique_using_minimum(values, n):
    min_values = {}
    for item in values:
        first_char = str(item)[0]
        hashed_value = unit_interval_hash(item, n)
        min_values[first_char] = min(min_values.get(first_char, 1), hashed_value)
    average_minimum = sum(min_values.values()) / len(min_values)
    return (int(1 / average_minimum) - 1) * len(min_values)

for _ in xrange(10):
    print count_unique_using_minimum((uuid4() for _ in xrange(10000)), 16)

As mudanças estão na função count_unique_using_minimum. Na variável min_values guardamos os mínimos de cada grupo. No fim, somamos todos os mínimos e os dividimos pelo número de todos os valores guardados — obtemos o mínimo médio. Com a expressão 1/average_minimum descobrimos qual é o número médio de valores distintos em cada grupo — então multiplicamos esse valor ainda pelo número de grupos e obtemos o número estimado de valores distintos no conjunto de dados fornecido. E como funciona esse procedimento modificado?

11312
7504
10560
8160
9344
12688
10976
11616
16240
6832

Bom, ainda não está bom, mas com certeza é melhor. O algoritmo está mais estável. Podemos tentar modificar a função de modo que os grupos não sejam formados pelo primeiro caractere, mas, por exemplo, pelos dois primeiros caracteres do ID, ou seja, assim:

first_char = str(item)[0:2] # ToDo: choose better name for variable

Os resultados seriam então estes:

9728
9728
9984
10240
8960
10752
9728
9472
11264
9472

Bom, isso já não está nada mal, né? Se ainda tentarmos cem mil valores distintos, os dois primeiros caracteres e n = 24, obtemos estes resultados:

103936
110080
102656
101120
101376
108288
97536
97024
107776
92416

Até que passa. Mas ainda existem algoritmos melhores, não se preocupe.

E qual é o consumo de memória? Precisamos guardar o mínimo de cada grupo, nada mais. Se temos IDs em formato hexadecimal, isso significa que precisamos lembrar no máximo 16^x mínimos, em que x é o número de caracteres com que formamos a chave do grupo. Um mínimo é um número racional, isto é, algum tipo double ou float.

Observação final: pudemos nos dar ao luxo de dividir a entrada em vários grupos porque tínhamos na entrada IDs que se comportavam como uma string aleatória. Se não tivéssemos na entrada uma string aleatória, mas dados em algum formato específico, teríamos de fazer a divisão de outro jeito. Se, por exemplo, todo ID começasse com o prefixo userid-, a divisão em grupos pelo primeiro caractere provavelmente não funcionaria muito bem, né?