Hashes power Probabilistic Data Structures

Ignacio Hagopian Blocked Unblock Seguir Seguindo 13 de janeiro Foto de Ryan Thomas Ang em Unsplash

As funções hash são usadas em toda a ciência da computação, mas eu quero mencionar que elas são úteis dentro de estruturas de dados e algoritmos probabilísticos. Nós todos sabemos que as estruturas de dados são os blocos de construção da maioria dos algoritmos. Uma má escolha pode levar a soluções difíceis e ineficientes, em vez de soluções elegantes e eficientes.

Como Linus Torvalds disse uma vez falando sobre o Git :

… Na verdade, eu sou um grande defensor de projetar seu código em torno dos dados, em vez
do que o contrário, e eu acho que é uma das razões pelas quais o git tem sido bem sucedido (*).

Além disso:

(*) Eu vou, de fato, afirmar que a diferença entre um programador ruim
e uma boa é se ele considera seu código ou suas estruturas de dados
mais importante. Programadores ruins se preocupam com o código. Bons programadores
preocupar-se com as estruturas de dados e seus relacionamentos.

Se você é um cientista da computação, engenheiro ou programador, você está muito ciente das estruturas de dados em diferentes níveis de detalhe. Um bate-papo de dez minutos com qualquer programador provavelmente levará a ouvir sobre: lista vinculada, árvores, pilhas, mapas, etc.

Eu tive muita discussão com colegas e amigos sobre o quão importante é dominar essas estruturas de dados, dependendo do seu trabalho. Se você é um acadêmico ou trabalha em uma empresa onde o volume é um problema real, então você deve dominá-los.

Na maioria das vezes, se você estiver programando em uma linguagem de alto nível, é um cheiro de código para reinventar a roda e fazer sua própria implementação de algoritmos conhecidos. A maioria dos frameworks tem essas estruturas de dados embutidas ou há bibliotecas ultraeficientes que, com grande chance, farão um ótimo trabalho.

De outro ângulo, a maioria dos mortais trabalha na manutenção de software ou onde as restrições de recursos não são realmente um problema. Estar obcecado com o desempenho ou consumo de recursos como a única métrica para estruturas de dados ou algoritmos de tomada de decisão não é muito sábio, especialmente quando isso não é relevante. Novamente, isso depende do problema que você está resolvendo e da necessidade de escalar.

Mas, às vezes, restrições de recursos são realmente um problema. Nesse caso, você deve considerar uma ferramenta importante em sua caixa de ferramentas: estruturas de dados probabilísticas. Eles comprometem a precisão com requisitos de recursos bastante impressionantes. Se você está resolvendo um problema pequeno, onde o espaço de memória não é limitado, o cálculo não é um gargalo, e precisão exata é uma obrigação, então você pode pensar duas vezes antes de usá-los. Se esse não for o caso, você deve saber a existência deles. Além disso, eles são muito divertidos de aprender.

Existem muitos livros, artigos e artigos que falam sobre esse assunto. Aqui eu vou falar sobre dois deles que eu considero muito bonitos e são muito usados em problemas do mundo real. Usarei alguns cálculos, mas não detalhadamente, porque há muitos recursos excelentes online. Mesmo se você não entender a matemática, você terá a idéia básica deles (que é o objetivo aqui).

Filtros Bloom

Se minha memória me serve corretamente, os filtros Bloom foram a primeira estrutura probabilística de dados que ouvi de alguns anos atrás, enquanto lia sobre algum banco de dados de petascale . Como em muitas outras estruturas probabilísticas de dados, você ficou bastante surpreso com sua eficácia, considerando quão pouco espaço e computação eles precisam.

Digamos que você tenha um grande conjunto de inteiros S e queira verificar se S contém um elemento i . Você pode abordar esse problema usando simplesmente uma lista vinculada com espaço / hora O (n) / O (n) . Além disso, tente uma Árvore Binária Balanceada com O ( n ) / O (log (n)) . Ou, obviamente, um mapa com O (n) / O (1) .

Parece que a maioria das opções requer um espaço de memória linear à cardinalidade de S, o que parece bastante razoável, considerando que, se não armazenarmos o valor de cada elemento de S, como podemos verificar se existe um elemento em S ?

A idéia dos filtros Bloom é codificar todo o conjunto S em uma cadeia binária de tamanho fixo, que chamaremos de Q. Isso é feito codificando cada elemento em S dentro de Q. Como você pode imaginar, o mapeamento de um domínio de tamanho variável em um fixo resultará, eventualmente, em colisões.

Vamos ver um exemplo canônico de um filtro Bloom . Digamos que definimos Q como uma string binária com comprimento fixo de 64 bits. Além disso, escolhemos k funções hash diferentes, como MD5 ou SHA-1. Em seguida, fazemos o seguinte:

  • Pegue o primeiro elemento em S
  • Hash o elemento com as funções k hash, e leve-o módulo 64 para gerar k índices em Q.
  • Defina 1 para cada bit em Q nos índices calculados antes
  • Faça as duas etapas anteriores para cada elemento restante em S

Quando terminamos, temos um valor de 64 bits Q, onde alguns dos bits são definidos como 1 e outros como 0.

Agora queremos verificar se um elemento está em S. Fazemos exatamente o mesmo procedimento acima para verificar quais bits deveriam ter sido definidos em Q. Se algum dos k bits correspondentes não estiver definido, podemos ter certeza de que o elemento não está em S. Se estiverem todos definidos, podemos dizer que o elemento está provavelmente em Q, já que esses bits também podem ser configurados em 1 parcialmente por muitos elementos. Na verdade, enquanto você continua adicionando elementos em S , mais e mais bits são definidos como 1 em Q , assim você continua aumentando a chance.

Os filtros Bloom podem produzir falsos positivos, mas não falsos negativos.

Se aumentarmos o tamanho de Q , evitamos colisões, portanto, a probabilidade de falsos positivos. O valor k também desempenha um papel na probabilidade de colisões. É uma troca entre tamanho (Q) ek e taxa de falsos positivos . Se você está interessado na matemática que quantifica a taxa de falsos positivos, você pode ler aqui . Além disso, você pode ver aqui o tamanho ideal (Q) ek considerando #S ou a taxa de falsos positivos desejada.

Há mais uma consideração importante: escolher as funções de hashing para gerar os índices em Q. Anteriormente, eu mencionei MD5 ou SHA-1, mas essas não são escolhas realmente sábias. As funções hash criptográficas tentam gerar saídas que são impossíveis de reverter. Isso não é uma preocupação aqui. Estamos interessados em saídas aleatórias e fazendo cálculos o mais rápido possível, portanto, há melhores opções.

A maioria das implementações usa uma única função hash para gerar as k saídas desejadas. Em particular, a função MurmurHash , onde alguns conjuntos de base constantes de saídas MurmurHash são calculados e depois k saídas são geradas pela combinação desses hashes de base. Você pode ver aqui uma implementação popular do filtro Bloom no Go.

Há outra estrutura de dados probabilística conhecida como esboço Contagem-min , que estima a frequência de cada item em um conjunto. A ideia é bem parecida com a forma como os filtros Bloom funcionam, então você pode estar interessado em dar uma olhada.

Se você estiver interessado no Ethereum, os filtros Bloom são usados para verificar se um bloco contém logs relacionados a determinados tópicos . No Ethereum, os tópicos estão relacionados a eventos e parâmetros indexados . Um cliente leve, que não armazena dados sobre o estado mundial , transações ou recibos , pode verificar muito rapidamente se um bloco contém registros relacionados a qualquer tópico de interesse. Se a verificação do filtro Bloom corresponder, considerando a pequena chance de falsos positivos , podemos ter certeza de que esse bloco contém uma entrada de log para o tópico consultado. O custo de um falso positivo supera o custo permanente de analisar todos os recebimentos de todas as transações de todos os blocos.

HyperLogLog

O HyperLogLog é um refinamento de ideias anteriores, como LogLog e Linear Counting , que se preocupam com o problema de contagem de distintos .

Suponha que você queira saber a cardinalidade de um grande conjunto S, ou seja: quantos elementos distintos estão em S. Também queremos fazer isso em O (1) espaço e tempo. Citando o documento original em que essa ideia foi apresentada:

Por exemplo, o novo algoritmo possibilita estimar cardinalidades muito além de 10 ? com uma precisão típica de 2%, usando uma memória de apenas 1,5 kilobytes.

A matemática formal nessa estrutura de dados é mais complexa do que no caso dos filtros Bloom, mas a ideia principal é bem simples.

Imagine que você tenha uma coleção de 8000 strings binárias geradas aleatoriamente. Quantos deles esperamos que tenham pelo menos três zeros à esquerda? Bem, a probabilidade de ter pelo menos três zeros à esquerda é 1/8, portanto, aproximadamente, podemos estimar que 1.000 deles seriam. Naturalmente, como este é um processo aleatório, podemos ver de 0 cadeias binárias que satisfazem essa propriedade até 8000, mas a probabilidade de cada caso é importante. Mais geralmente, se tivermos exatamente n zeros à esquerda, parece razoável que a cardinalidade seja 2 ^ n. Essa é a mesma idéia de jogar uma moeda 100 vezes e dizer que veremos aproximadamente 50 caras e 50 caudas.

Quando você mergulhar nos detalhes, logo perceberá que a variação é um problema. E um grande problema, pois cada unidade de erro tem um impacto exponencial na estimativa. Dizendo de outra forma, se por acaso tivermos zeros à esquerda de K + 1 em vez de zeros à esquerda de K, então nossa estimativa dobrará. A ideia usada para melhorar esse aspecto é dividir o conjunto em vários subconjuntos e usar uma média de zeros iniciais máximos encontrados em cada subconjunto.

Uma evolução do LogLog para o HyperLogLog está mudando o tipo de média para a estimativa para controlar a sensibilidade a outliers . Em particular, o LogLog usa a média aritmética em comparação com a média harmônica usada no HyperLogLog. Além disso, coeficientes de correção de viés são aplicados para corrigir ainda mais viés restante.

Repetir o experimento dividindo o conjunto em vários é ótimo, mas gera outro problema: se a cardinalidade do conjunto for muito pequena, não teremos dados suficientes para fazer as estatísticas funcionarem. Isso é resolvido simplesmente identificando o caso e usando outra técnica que funciona melhor nesse contexto.

Como nos filtros Bloom, cada elemento em cada subconjunto é codificado para transformá-lo em uma string binária de comprimento fixo a partir da qual podemos seguir a lógica acima. Mais uma vez, funções de hash Murmur são amplamente utilizadas em implementações.

Linha de fundo

Podemos perceber que, em todos esses casos, as funções hash desempenham um papel essencial. Elegantemente, eles fornecem muitas características que são bastante úteis para estruturas de dados e algoritmos probabilísticos:

  • Eles transformam dados distribuídos não uniformes em distribuições uniformes, o que dá um ponto de partida para as suposições probabilísticas.
  • Identidade universal de dados, o que leva à desduplicação automática que ajuda a resolver problemas como count-distinct , se projetarmos operações como idempotentes .

Aproveitando-se do fato de que a irreversibilidade do hash não é um requisito, as funções de hash não criptográficas são uma opção que pode ser mais rápida, ajudando na velocidade do algoritmo.