Je ne connaissais pas mais d'après google le principe est simple.
La première idée que tu pourrais avoir pour tester si un élement b appartient a un ensemble A sans comparer b a chaque élements de A, c'est d'utiliser une fonction de hash h. Si h donne des valeurs dans [0, m], tu utilise un tableau de booleens v pour marquer les h(a) pour tous les a de A. Ainsi pour tester b tu regarde v[h(b)]. Si tu trouve 0 alors c'est que b n'est pas dans A. Par contre si su trouve 1, ça veut juste dire qu'il y a des chances que b soit dans A, mais sans certitude. En effet un element qui n'est pas dans A peut très bien avoir le même hash code qu'un élement de A. Donc dans ce cas pour être sûr du status de b je vois deux solutions : soit tu le compare a tous les élements de A (ce qui est ce que tu voulais éviter, mais là tu ne le fais que parce que b a des chances d'être dans A), soit tu es malin et tu aura gardé pour chaque entrée de v la liste des élements de A qui ont pour hash code cet indice dans v. Donc tu ne compare b qu'aux élements de A qui donnent le même hash code.
Maintenant les Bloom filters. C'est exactement la même chose, sauf que tu as plusieurs fonctions de hash Hi. Si un des v[Hi(b)] vaut 0 alors tu es sûr que b n'est pas dans A. Si tous les v[Hi(b)] valent 1, alors ils est probable que b soit dans A. Comme tu as plusieurs fonctions de hash, cette probabilite est d'autant plus grande.
Message édité par matafan le 18-10-2003 à 04:38:47
