TP3 — Intersection de fichiers par Filtre de Bloom

HONGBO Bryan

Fichiers sources

• bloom.h / bloom.c : implémentation du filtre (bitset et k-hachage)
• hash.h : définition du type de fonction de hachage
• hash_f.h / hash_f.c : les 12 fonctions de hachage disponibles
• utils.h / utils.c : fonctions de lecture, stats et calcul premier
• Tp3_main.c : programme principal

Compilation

Avec le Makefile fourni :

make

Pour forcer une recompilation propre (recommande en cas d'erreur de lien) :

make re

Ou manuellement :

gcc -Wall -Wextra  -O2 -o tp3 Tp3_main.c hash.c hash_f.c bloom.c utils.c -lm

Utilisation

./tp3 <fichier1> <fichier2>

Le programme calcule la taille idéale du filtre ($5 \times \text{lignes}$), insère les mots de fichier1, affiche le taux d'occupation des bits, puis identifie les mots communs avec fichier2.

Exemple

./tp3 words1.txt words2.txt

Configuration du filtre

Dans Tp3_main.c, ligne bloom_filter *bf = bloom_init(capacite, 3); Vous pouvez modifier le deuxième argument (3) pour changer le nombre de fonctions de hachage utilisées (jusqu'à 12).

Les fonctions sont tirées du tableau hashf dans hash_f.c :

• hash_1 à hash_7
• a1_hash_function, a2_hash_function
• Bernstein_hachage, L_hachage_original, s_bon_hachage