Грокаем алгоритмы

Или представьте себя на месте поискового бота Google. Обрабатывать веб-страницу нужно только в том случае, если она еще не обрабатывалась ранее. Итак, нужно проверить, обрабатывалась ли страница ранее.

Или представьте себя на месте bit.ly — сервиса сокращения URL. Пользователи не должны перенаправляться на вредоносные сайты. У вас имеется набор URL-адресов, которые считаются вредоносными. Теперь нужно выяснить, не направляется ли пользователь на URL-адрес из этого набора.

Во всех этих примерах возникает одна проблема. Имеется очень большой набор данных.

Появляется новый объект, и вы хотите узнать, содержится ли он в существующем наборе. Эта задача быстро решается при помощи хеша. Например, представьте, что Google создает большой хеш, ключами которого являются все обработанные страницы.

Как узнать, обрабатывался ли сайт adit.io? Нужно заглянуть в хеш.

У adit.io имеется свой ключ в хеше, а значит, адрес уже обрабатывался. Среднее время обращения к элементам в хеш-таблице составляет O(1). Таким образом, вы узнали о том, что страница adit.io уже проиндексирована за постоянное время. Неплохо!

Вот только этот хеш получится просто огромным. Google индексирует триллионы веб-страниц. Если хеш содержит все URL-адреса, индексируемые Google, он займет слишком много места. У Reddit и bit.ly возникает аналогичная проблема. Сталкиваясь с такими объемами данных, приходится действовать более изобретательно!

Фильтры Блума

Для решения проблемы можно воспользоваться вероятностными структурами данных, которые называются фильтрами Блума. Они дают ответ, который может оказаться ложным, но с большой вероятностью является правильным. Вместо того чтобы обращаться к хешу, вы спрашиваете у фильтра Блума, обрабатывался ли этот URL-адрес ранее. Хеш-таблица даст точный ответ. Фильтр Блума дает ответ, правильный с высокой вероятностью:

• возможны ложно-положительные срабатывания. Фильтр скажет: «Этот сайт уже обрабатывался», хотя этого не было;

• ложно-отрицательные срабатывания исключены. Если фильтр утверждает, что сайт не обрабатывался, вы можете быть в этом уверены.

Фильтры Блума хороши тем, что занимают очень мало места. Хеш-таблице пришлось бы хранить все URL-адреса, обрабатываемые Google, а фильтру Блума это не нужно. Фильтры Блума очень удобны тогда, когда не нужно хранить точный ответ (как во всех приведенных примерах). Например, bit.ly может сказать: «Мы полагаем, что сайт может оказаться вредоносным, будьте особенно внимательны».

HyperLogLog

Примерно так же действует другой алгоритм, который называется HyperLogLog. Предположим, Google хочет подсчитать количество уникальных поисков, выполненных пользователями. Или Amazon хочет подсчитать количество уникальных предметов, просмотренных пользователями за сегодняшний день. Для получения ответов на эти вопросы потребуется очень много места! Так, в примере с Google придется вести журнал всех уникальных вариантов поиска. Когда пользователь что-то ищет, вы сначала проверяете, присутствует ли условие в журнале, и если нет, добавляете его. Даже для одного дня этот журнал получится гигантским.

HyperLogLog аппроксимирует количество уникальных элементов в множестве. Как и фильтры Блума, он не дает точного ответа, но выдает достаточно близкий результат с использованием малой части памяти, которую обычно занимает такая задача.

Если вы используете большие объемы данных и вас устраивают приближенные ответы — воспользуйтесь вероятностными алгоритмами!

Алгоритмы SHA

Помните процедуру хеширования из главы 5? На всякий случай освежу вашу память: имеется ключ, вы хотите поместить связанное с ним значение в массив.

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

Элемент, в котором размещается значение, определяется хеш-функцией.

Значение сохраняется в соответствующей позиции массива.

Хеширование позволяет выполнять поиск с постоянным временем. Когда вам потребуется узнать значение, связанное с ключом, вы снова применяете хеш-функцию, и она за время O(1) сообщает, какую позицию следует проверить.

Хеш-функция должна обеспечивать достаточно равномерное распределение. Итак, хеш-функция получает строку и возвращает номер ячейки, соответствующий этой строке.

Сравнение файлов

Одну из разновидностей хеш-функций составляет алгоритм SHA (Secure Hash Algorithm). Он получает строку и возвращает хеш-код этой строки.

Возможно, терминология не настолько проста, насколько хотелось бы. Алгоритм SHA — хеш-функция; эта функция генерирует хеш-код, который представляет собой короткую строку. Хеш-функция для хеш-таблиц преобразует строку в индекс массива, тогда как SHA преобразует строку в другую строку.

Для каждой строки алгоритм SHA генерирует свой уникальный хеш-код.

примечание

Хеш-коды SHA достаточно длинные. Здесь приводится только начало.