Алгоритми та структури даних · Senior · Запитання 43 з 75
Який підхід відповідає на «чи є це слово в словнику?» для мільйонів слів із найменшою пам'яттю, якщо рідкісні хибнопозитивні прийнятні?
- 1Trie з усіх слів
- 2Відсортований масив із бінарним пошуком
- ✓Правильна відповідь: Фільтр Блума
Пояснення
Фільтру Блума потрібно близько 10 бітів на слово для 1% хибнопозитивних, незалежно від довжини слова. Trie чи відсортований масив зберігають самі слова, а це значно більше пам'яті.