Le Filtre de Bloom
Découvrez la structure de données probabiliste ultra-performante qui propulse la validation orthographique de 824 026 mots français dans un espace mémoire de seulement 966 Ko.
Capacité
824 026
Mots et formes conjuguées français indexés
Taille du Bit-Array
7,91 M
Bits alloués mathématiquement
Faux Positifs (p)
< 1.0%
Taux d'erreur probabiliste ciblé
Vitesse de Test
< 0.05ms
Vérification instantanée en local
Qu'est-ce qu'un Filtre de Bloom ?
Inventé par Burton Howard Bloom en 1970, le Filtre de Bloom est une structure de données hautement optimisée en mémoire pour tester l'appartenance d'un élément à un ensemble.
Contrairement à un dictionnaire classique ou une table de hachage qui stocke les chaînes de caractères en clair, le filtre de Bloom stocke uniquement des empreintes binaires compressées.
Une règle fondamentale :
"Si le filtre dit que le mot n'est pas présent, c'est garanti à 100%. S'il dit qu'il est présent, il y a une infime chance qu'il se trompe (faux positif)."
Simulation d'un Bit-Array :
Chaque mot est haché 7 fois par la formule mathématique **FNV-1a**, modifiant 7 bits distincts dans le tableau ci-dessus. Pour vérifier un mot, on recalcule les 7 bits : si tous valent 1, le mot existe !
L'Ingénierie Mathématique (FNV-1a)
Pour distribuer uniformément les mots français sur notre tableau de 7,91 millions de bits, nous utilisons l'algorithme de hachage non-cryptographique ultra-rapide FNV-1a (Fowler-Noll-Vo).
Afin de simuler 7 fonctions de hachage indépendantes, nous exécutons l'algorithme avec 7 graines (seeds) entières distinctes. Voici l'implémentation TypeScript stricte utilisée dans notre application :
function fnv1a(str: string, seed: number = 0): number {
let hash = 0x811c9dc5 ^ seed;
for (let i = 0; i < str.length; i++) {
hash ^= str.charCodeAt(i);
// Multiplication 32-bit par le premier FNV (16777619)
hash = Math.imul(hash, 16777619) >>> 0;
}
return hash;
}Note : L'utilisation de `Math.imul` est essentielle en JavaScript pour forcer une multiplication d'entiers signés de 32 bits, garantissant des hashs identiques et reproductibles entre tous les navigateurs et environnements Node.js.
Pourquoi ce choix technique ?
| Structure de Données | Taille Mémoire | Complexité Test | Validation Offline |
|---|---|---|---|
| Tableau Array Standard JSON | 18,5 Mo | O(N) - Lent | Non réaliste en 4G/Mobile |
| Trie Lexical (Pré-compilé) | 36,3 Mo | O(L) - Moyen | Trop lourd au démarrage |
| Filtre de Bloom (FNV-1a)Actif | 966 Ko (1.26 Mo JSON) | O(k) - Instantané | Parfait pour le Offline complet |
Prêt à tester ?
Retournez sur la page d'accueil et faites une recherche de phrase ou un mot rare hors ligne.