Вы когда-нибудь задумывались, как Google выполняет поиск по всему Интернету за доли секунды?

В информатике мы всегда беспокоимся о n количестве операций, которые наш код должен выполнить для определения объема имеющихся данных.

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

Если бы программа сделала это для этой статьи и искала бы, например, слово «рыба», это не имело бы большого значения, потому что наше n относительно невелико.

Теперь, если вам нужно искать каждое слово в Интернете , это будет иметь большое значение, потому что в Интернете много слов. У Google действительно быстрые компьютеры, но он не может сделать это за 0,7 секунды.

Перевернутый индекс на помощь

Этот перевернутый индекс не позволяет искать каждое слово в Интернете, но это отличный способ упорядочить их, чтобы их было легче найти. Это позволяет нам выполнить только одну операцию (ну, обычно) для выполнения этого поиска.

Итак, как это осуществить?

Волшебный соус - это хеш-таблицы.

Уловки, чтобы добраться до O (1)

В хэш-таблицах есть два важных элемента: сегменты и функция хеширования.

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

Наша хеш-таблица объединяет слова в пронумерованные сегменты (массив) в зависимости от номера, присвоенного ему хеш-функцией. Итак, если наша функция хеширования посмотрит на слово красный, она скажет: «Поместите его в третье ведро!».

Это означает, что, когда мы хотим найти его снова, нам просто нужно проделать ту же операцию с тем же словом.

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

Сравните это с другими методами поиска, при которых вам, возможно, придется просматривать каждый элемент, пока не найдете то, что ищете (линейный поиск).

Недостатком является то, что заранее требуется больше работы и больше места для хранения таблицы.

Это иллюстрирует компромисс, на который мы, программисты, часто вынуждены идти: использовать больше места или дольше работать. В случае с поисковой системой важнее всего скорость.

Что такое перевернутый индекс?

Инвертированный индекс - это хеш-таблица, состоящая из пар "ключ-значение". Это означает, что хеш-таблица сообщает вам, где найти ключ, а ключ знает, где найти значение.

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

Например:

One fish two fish red fish blue fish

Если мы сопоставим каждое слово с индексом («One» находится в индексе 0, «рыба» - в индексе 1 и т. Д.), Инвертированный индекс слов в этом предложении будет выглядеть следующим образом:

One : [0],
fish : [1, 3, 5, 7],
two: [2],
red: [4],
blue: [6]

Если я хочу знать, где найти слово fish, я могу просто найти его в обратном индексе и увидеть, что оно отображается в индексах 1, 3, 5 и 7.

Поскольку это находится в хеш-таблице, мы можем найти везде, где слово появляется почти мгновенно.

Давайте посмотрим на код

Python упрощает это благодаря словарям. Словари - это, по сути, хеш-таблицы под капотом, поэтому мы можем добавлять методы для создания инвертированного индекса.

Если вы храните много данных, вам нужно сделать это по-другому, но это работает в качестве примера.

Наша поисковая система будет искать только отдельные слова и сообщать вам, где их найти в коллекции файлов.

Google, например, может выполнять более сложные операции (PageRank), чтобы выяснить, насколько результат релевантен для вашего поиска.

Сноска о сканировании в Интернете

Чтобы сделать эту информацию доступной для поиска, вам нужно просмотреть и проиндексировать ее. Для этого поисковые системы используют веб-сканеры (также иногда называемые пауками), чтобы переходить по всем ссылкам и индексировать все на каждой веб-странице.

Дайте мне знать, если вы хотите увидеть вторую часть о пауках!