Чтобы понять суть идеи фильтра Блума, Миценмахер предлагает рассмотреть поисковую систему Google, которая сканирует весь интернет и индексирует каждую страницу. Интернет составляет более триллиона URL-адресов, а средний URL длиной примерно в 77 знаков. Когда поисковый механизм считывает какой-то URL, как он может понять, была ли эта страница ранее обработана или нет? Чтобы просто хранить список всех уже посещенных страниц, требуется огромное пространство, и повторный поиск по этому списку (пусть даже полностью отсортированному) – это кошмар! В данной ситуации можно сказать, что лечение хуже самой болезни. Другими словами, каждый раз проверять, не была ли эта страница уже проиндексирована, будет гораздо более затратным по времени, чем просто индексировать случайную страницу дважды.
Но что, если нам всего-то и нужно знать, что этот URL новый для нас? Вот тут на сцену и выходит фильтр Блума. Названный по имени его создателя, Бёртона Блума, этот фильтр работает по принципу, схожему с тестом Миллера – Рабина: URL подставляется в ряд уравнений, которые, по сути, проверяют «свидетелей» его новизны (вместо того чтобы объявить «n не является простым числом», эти уравнения говорят «я не видел n раньше»). Если вас устроит коэффициент погрешности 1–2 %, хранение полученных результатов в такой вероятностной структуре данных, как фильтр Блума, позволит вам сэкономить очень много времени и пространства. И польза подобных фильтров не ограничивается только поисковыми системами: фильтры Блума интегрированы в большинство современных браузеров для сверки URL-адресов со списком известных вредоносных сайтов, они также являются важной частью пиринговых платежных систем вроде Bitcoin.
По словам Миценмахера, «идея ошибочного компромисса пространства – думаю, основная проблема в том, что люди не связывают это с вычислениями. Они полагают, что компьютер должен просто выдать ответ. Поэтому, когда на лекции, посвященной алгоритмам, вы слышите: "У вас должен получиться один ответ; но этот ответ может быть неправильным", – мне нравится думать, что это заставляет их [студентов] собраться. Думаю, люди просто не осознают, насколько часто они сталкиваются с этим в своей жизни, и не могут принять это».
Река извивается, потому что она не умеет думать.
Ричард Кенни
Случайность также зарекомендовала себя как мощное оружие в борьбе с проблемами дискретной оптимизации, такими как создание расписания баскетбольных матчей NCAA или поиск кратчайшего маршрута для коммивояжера. В предыдущей главе мы увидели, как релаксация помогает снизить количество подобных проблем, но тактическое использование случайности стало, возможно, даже более значимым способом.