Вы когда-нибудь задумывались, как 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), чтобы выяснить, насколько результат релевантен для вашего поиска.
Сноска о сканировании в Интернете
Чтобы сделать эту информацию доступной для поиска, вам нужно просмотреть и проиндексировать ее. Для этого поисковые системы используют веб-сканеры (также иногда называемые пауками), чтобы переходить по всем ссылкам и индексировать все на каждой веб-странице.
Дайте мне знать, если вы хотите увидеть вторую часть о пауках!