Vídeo: Contador de Fluxo de Pessoas CFP100 2024
Aprender a contar objetos em um fluxo pode ajudá-lo a encontrar os itens mais freqüentes ou a classificar eventos comuns e incomuns. Este algoritmo aproveita as funções de hash e os esboços aproximados. Ele faz isso depois de filtrar objetos duplicados e contar elementos distintos que apareceram no fluxo de dados.
Você usa esta técnica para resolver problemas, como encontrar as consultas mais freqüentes em um mecanismo de pesquisa, os itens mais vendidos de um revendedor online, as páginas altamente populares em um site ou os estoques mais voláteis (contando os tempos de estoque) vendido e comprado).
Você aplica a solução para este problema, Count-Min Sketch, para um fluxo de dados. Requer apenas uma passagem de dados e armazena a menor informação possível. Este algoritmo é aplicado em muitas situações do mundo real (como analisar o tráfego de rede ou gerenciar fluxos de dados distribuídos). A receita requer o uso de um monte de funções de hash, cada uma associada a um vetor de bits, de uma maneira que se assemelha a um filtro Bloom, como mostrado na figura:
- Inicialize todos os vetores de bits em zero em todas as posições.
- Aplica a função hash para cada vetor de bits ao receber um objeto de um fluxo. Use o endereço numérico resultante para incrementar o valor nessa posição.
- Aplicar a função hash a um objeto e recuperar o valor na posição associada quando solicitado a estimar a freqüência de um objeto. De todos os valores recebidos dos vetores de bits, você toma a menor freqüência do fluxo.
Como as colisões são sempre possíveis ao usar uma função de hash, especialmente se o vetor de bits associado tiver alguns slots, ter vários vetores de bits à mão garante que pelo menos um deles mantenha o valor correto. O valor de escolha deve ser o menor porque não é misturado com contagens falsas positivas devido a colisões.
