Algorytmy i struktury danych · Senior · Pytanie 43 z 75
Które podejście odpowiada na „czy to słowo jest w słowniku?” dla milionów słów przy najmniejszej pamięci, jeśli rzadkie fałszywe alarmy są w porządku?
- 1Trie ze wszystkich słów
- 2Posortowana tablica z wyszukiwaniem binarnym
- ✓Poprawna odpowiedź: Filtr Blooma
Wyjaśnienie
Filtr Blooma potrzebuje około 10 bitów na słowo dla 1% fałszywych alarmów, niezależnie od długości słowa. Trie lub posortowana tablica przechowują same słowa, co zajmuje dużo więcej pamięci.