Oi, habrozhiteli! Algoritmos são o coração e a alma da ciência da computação. Você não pode ficar sem eles, eles estão por toda parte - desde roteamento de rede e cálculos genômicos até criptografia e aprendizado de máquina. O "Algoritmo Perfeito" o transformará em um verdadeiro profissional que definirá tarefas e as solucionará com maestria na vida e em uma entrevista ao contratar qualquer empresa de TI.
No segundo livro, Tim Rafgarden, o guru dos algoritmos, fala sobre a pesquisa de gráficos e sua aplicação, o algoritmo de pesquisa de caminho mais curto e o uso e implementação de algumas estruturas de dados: pilhas, árvores de pesquisa, tabelas de hash e o filtro Bloom.
Este post apresenta um trecho de Bloom Filters: The Basics.
Sobre o que é este livro
A segunda parte do livro “Algoritmo Perfeito” é um curso introdutório sobre os fundamentos da alfabetização nos três tópicos a seguir.
Pesquisa e aplicações gráficas . Os gráficos modelam vários tipos diferentes de redes, incluindo estradas, comunicação, redes sociais e redes de dependências entre tarefas. Os gráficos podem ser complexos, mas existem algumas primitivas incrivelmente rápidas para falar sobre a estrutura dos gráficos. Começaremos com algoritmos de busca de gráfico em tempo linear, desde aplicativos que vão da análise de rede até a construção de uma sequência de operações.
Os caminhos mais curtos . No problema do caminho mais curto, o objetivo é calcular a melhor rota da rede do ponto A ao ponto B. Essa tarefa tem aplicações óbvias, como o cálculo de rotas de tráfego, e também aparece mascarada em muitas outras tarefas universais. Generalizaremos um de nossos algoritmos de busca de gráficos e chegaremos ao famoso algoritmo de busca de caminho mais curto da Dijkstra.
Estruturas de dados . Este livro fará de você um usuário altamente instruído de várias estruturas de dados diferentes projetadas para oferecer suporte a um conjunto de objetos em evolução com suas chaves associadas. O objetivo principal é desenvolver uma intuição sobre qual estrutura de dados é adequada para seu aplicativo. Seções adicionais fornecem diretrizes para implementar essas estruturas de dados do zero.
Primeiro, discutimos pilhas que podem identificar rapidamente o objeto armazenado com a menor chave e também são úteis para classificar, implementar uma fila de prioridade e implementar o algoritmo quase linear-temporal de Dijkstra. As árvores de pesquisa mantêm a ordem completa das chaves nos objetos armazenados e suportam uma gama ainda maior de operações. As tabelas de hash são otimizadas para operações de pesquisa ultra-rápidas e são difundidas em programas modernos. Também observamos o filtro Bloom, um parente próximo da tabela de hash, que usa menos espaço devido a erros aleatórios.
Você pode se familiarizar com o conteúdo do livro em mais detalhes nas seções “Conclusões”, que completam cada capítulo e identificam os pontos mais importantes. As seções do livro, marcadas com um asterisco, são as mais avançadas em termos do nível de informação apresentado. Se o livro for projetado para uma familiarização superficial com o tópico, o leitor poderá ignorá-los sem perder a integridade dos escritos.
Tópicos abordados em três outras partes . A primeira parte do livro “Perfect Algorithm. Fundamentos ”abrange notações assintóticas (a notação O-large e seus parentes próximos), algoritmos de“ dividir e conquistar ”e o principal teorema da relação de recorrência - o método principal, classificação rápida aleatória e sua análise e algoritmos de seleção linear-temporal. A terceira parte trata de algoritmos gananciosos (planejamento, árvores abrangentes mínimas, clustering, códigos de Huffman) e programação dinâmica (problema de mochila, alinhamento de sequência, caminhos mais curtos, árvores de pesquisa ideais). A quarta parte é dedicada à integridade do NP, o que significa para um projetista de algoritmos e estratégias para resolver problemas insolúveis em computação, incluindo análise heurística e pesquisa local.
12.5 Filtros Bloom: O básico
Os filtros Bloom são parentes próximos de tabelas de hash. Eles são muito compactos, mas cometem erros periodicamente. Esta seção descreve como os filtros Bloom são bons e como eles são implementados, enquanto a seção 12.6 estabelece uma curva de compromisso entre a quantidade de espaço usado pelo filtro e sua taxa de erro.
12.5.1 Operações Suportadas
O motivo da existência de filtros Bloom é essencialmente o mesmo de uma tabela de hash: operações de inserção e exibição super rápidas, graças às quais você pode se lembrar rapidamente do que viu e do que não viu. Por que deveríamos ser incomodados por uma estrutura de dados diferente com o mesmo conjunto de operações? Como os filtros Bloom são preferíveis às tabelas de hash em aplicativos em que o espaço vale seu peso em ouro, e um erro aleatório não é um obstáculo para a transação.
Como tabelas de hash com endereçamento aberto, os filtros Bloom são muito mais fáceis de implementar e imaginar quando suportam apenas as operações Insert e View (e sem a operação Delete). Vamos nos concentrar neste caso.
FILTROS DE FLOR: OPERAÇÕES SUPORTADAS
Visualização: com a tecla k, retorne “yes” se k tiver sido inserido anteriormente no filtro Bloom e “no” caso contrário.
Colar: adicione uma nova chave k ao filtro Bloom.
Os filtros Bloom são muito eficientes espacialmente; normalmente, eles podem exigir apenas 8 bits por inserção. Isso é inacreditável, pois 8 bits é completamente insuficiente para lembrar até mesmo uma chave de 32 bits ou um ponteiro para um objeto! Por esse motivo, a operação View no filtro Bloom retorna apenas a resposta “yes” / “no”, enquanto na tabela de hash, essa operação retorna um ponteiro para o objeto desejado (se for encontrado). É por isso que a operação Inserir agora aceita apenas a chave, e não o (ponteiro para) o objeto.
Ao contrário de todas as outras estruturas de dados que estudamos, os filtros Bloom podem estar errados. Existem dois tipos de erros: negativos negativos quando a operação View retorna "false", mesmo que a chave solicitada já tenha sido inserida anteriormente, e declarações falsas (ou disparam) quando a operação View retorna "true", embora a chave solicitada ainda não tenha sido inserida no passado . Na seção 12.5.3, veremos que os filtros Bloom básicos nunca sofrem com falsos negativos, mas podem ter "elementos fantasmas" na forma de declarações falsas. A Seção 12.6 mostra que a frequência de declarações falsas pode ser controlada ajustando adequadamente o uso do espaço. Uma implementação típica de um filtro Bloom pode ter uma taxa de erro de cerca de 1% ou 0,1%.
Os tempos de execução para as operações Insert e View são tão rápidos quanto na tabela de hash. E melhor ainda, é garantido que essas operações sejam executadas em tempo constante, independentemente da implementação do filtro Bloom e do conjunto de dados1. No entanto, a implementação e o conjunto de dados afetam a taxa de erro do filtro.
Para resumir as vantagens e desvantagens dos filtros Bloom sobre tabelas de hash:
FILTRO DE FLOR CONTRA MESAS DE HASH
1. Prós: mais espacialmente eficazes.
2. Prós: operações de tempo permanente garantidas para cada conjunto de dados.
3. Contras: não é possível armazenar ponteiros para objetos.
4. Contras: exclusões mais complexas em comparação com uma tabela de hash com uma embreagem.
5. Contras: probabilidade diferente de zero de uma declaração falsa.
A lista de indicadores para os filtros Bloom básicos é a seguinte.
Quadro 12.4 Filtros Bloom básicos: operações suportadas e seu tempo de execução. O sinal da adaga (†) indica que a operação View tem uma probabilidade controlável, mas diferente de zero, de declarações falsas
Os filtros Bloom devem ser usados em vez de tabelas de hash em aplicativos em que suas vantagens são importantes e suas desvantagens não são um obstáculo para a transação.
QUANDO USAR O FILTRO DE FLOR
Se um aplicativo requer uma pesquisa rápida com um conjunto de objetos em evolução dinâmica, o espaço vale seu peso em ouro e um pequeno número aceitável de declarações falsas, então o filtro Bloom geralmente é a estrutura de dados preferida.
12.5.2 Aplicações
A seguir, há três usos com verificações repetidas, nas quais economizar espaço pode ser importante e declarações falsas não são um obstáculo para a transação.
Corretor ortográfico. Na década de 1970, os filtros Bloom eram usados para implementar verificadores ortográficos - verificadores ortográficos. No estágio de pré-processamento, cada palavra no dicionário é inserida no filtro Bloom. A ortografia de um documento se resume a uma operação: observe uma palavra em um documento, marcando as palavras para as quais essa operação retorne "não".
Neste apêndice, uma declaração falsa corresponde a uma palavra inválida que o verificador ortográfico aceita inadvertidamente. Tais erros não tornaram ideal o corretor ortográfico. No entanto, no início da década de 1970, o espaço valia seu peso em ouro; portanto, o uso de filtros Bloom naquela época era uma estratégia em que todos ganhavam.
Senhas proibidas . Um aplicativo antigo que permanece válido até hoje controla senhas proibidas - senhas muito comuns ou fáceis de adivinhar. Inicialmente, todas as senhas proibidas são inseridas no filtro Bloom; senhas proibidas adicionais podem ser inseridas posteriormente, conforme necessário. Quando um usuário tenta definir ou redefinir sua senha, o sistema procura a senha proposta no filtro Bloom. Se a pesquisa retornar "yes", o usuário será solicitado a tentar novamente com uma senha diferente. Aqui, uma declaração falsa é traduzida em uma senha forte, que o sistema rejeita.
Desde que a taxa de erro não seja muito alta, diga não mais que 1% ou 0,1%, isso não importa muito. De tempos em tempos, alguns usuários precisarão de uma tentativa adicional para encontrar uma senha aceitável pelo sistema.
Roteadores da Internet . Um número de aplicativos impressionantes de hoje dos filtros Bloom ocorre na Internet, onde os pacotes de dados passam por roteadores com velocidade de streaming. Há muitas razões pelas quais um roteador pode querer se lembrar rapidamente do que viu no passado. Por exemplo, um roteador pode querer encontrar o endereço IP de origem de um pacote na lista de endereços IP bloqueados, rastrear o conteúdo do cache para evitar visualizações espúrias do cache ou manter estatísticas que ajudem a identificar um ataque à rede de negação de serviço. A taxa de chegada de pacotes requer visualizações super rápidas, e a memória limitada do roteador faz com que o espaço valha seu peso em ouro. Esses aplicativos são gerenciados diretamente pelo filtro Bloom.
12.5.3 Implementação
Olhando dentro do filtro Bloom, você pode ver uma implementação elegante. A estrutura de dados suporta uma seqüência de n bits ou, da mesma forma, uma matriz A de comprimento n na qual cada elemento é 0 ou 1. (Todos os elementos são inicializados em zero.) Essa estrutura também usa m funções de hash h1, h2, ..., hm , enquanto cada um mapeia o universo U de todas as chaves possíveis para o conjunto {0, 1, 2, ..., n - 1} de posições na matriz. O parâmetro m é proporcional ao número de bits usado pelo filtro Bloom para inserção e, como regra, é uma pequena constante (por exemplo, 5).
Sempre que uma chave é inserida em um filtro Bloom, cada uma das funções de m hash define um sinalizador, configurando o bit correspondente da matriz A como 1.
FILTRO DE FLOR: INSERIR (NA CHAVE)
for i = 1 to m do A[hi(k)] := 1
Por exemplo, se m = 3 e h1 (k) = 23, h2 (k) = 17 e h3 (k) = 5, inserir k faz com que os 5º, 17º e 23º bits da matriz sejam definidos iguais 1 (Fig. 12.5).
Na operação Exibir, o filtro Bloom procura a impressão digital que pode ter permanecido na inserção k.
FILTRO DE FLOR: VISTA (CHAVE CHAVE)
for i = 1 to m do if A [hi (k)] = 0 then return «» return «»
Agora podemos ver por que os filtros Bloom não podem sofrer falsos negativos. Quando a tecla k é inserida, os m bits correspondentes são definidos como 1. Durante a vida útil do filtro Bloom, os bits podem alterar seu valor de 0 para 1, mas não vice-versa. Assim, esses m bits permanecem 1 para sempre. É garantido que cada operação subsequente do View k retorne a resposta correta.
Também podemos ver como surgem afirmações falsas. Suponha que m = 3 e as quatro chaves k1, k2, k3, k4 tenham os seguintes valores de hash:
Suponha que inserimos k1, k2, k3 e k4 em um filtro Bloom (Figura 12.6). Essas três inserções levam a um total de nove bits sendo definido como 1, incluindo três bits na impressão digital da chave k1 (5, 17 e 23). Nesse ponto, o filtro Bloom não pode mais distinguir se a chave k1 foi inserida ou não. Mesmo que k1 não tenha sido inserido no filtro, a pesquisa retornará "yes", que é uma declaração falsa.
Intuitivamente, podemos supor que, com um aumento no tamanho n do filtro Bloom, o número de sobreposições entre as impressões digitais de chaves diferentes diminua, o que, por sua vez, leva a um número menor de declarações falsas. Mas o objetivo principal do filtro Bloom é economizar espaço. Existe um meio termo onde n e a frequência de declarações falsas são simultaneamente pequenas? A resposta não é óbvia e requer algumas análises matemáticas realizadas na próxima seção.
»Mais informações sobre o livro podem ser encontradas no
site do editor»
Conteúdo»
TrechoPara Khabrozhiteley 20% de desconto no cupom -
AlgoritmosApós o pagamento da versão impressa do livro, um livro eletrônico é enviado por e-mail.