Это четвертая статья из серии “Перевернутый индекс”, о которой я пишу dev.to . Мы будем говорить о первом компоненте, то есть Словарь в этой статье и другие компоненты, то есть списки публикаций в следующих статьях. Этот пост очень тесно связан с моей последней статьей о введении в инвертированный индекс Пожалуйста, прочтите его, прежде чем читать это, для лучшего понимания.
Пожалуйста, не принимайте словарь за словарь python/HashMap. В этом есть что-то еще. 😌
Темы быть охваченным
* Overview and need for Dictionary * Supported Operations * Types of Dictionary * Sort-based Dictionary * Hash-based Dictionary * Which one is better?
Обзор
Давайте вспомним простое представление перевернутого индекса, которое мы видели в нашем последнем посте
В этой статье мы сосредоточимся на столбце терминов в представлении перевернутого индекса на приведенной выше диаграмме.
Поскольку этот столбец терминов содержит все слова/термины в нашей коллекции, мы также называем его нашим перевернутым индексом dictionary .
🙋 Но зачем мне нужен словарь? Ответ довольно прост, как видно на диаграмме, основная цель словарных терминов – управлять набором терминов в текстовой коллекции и обеспечивать сопоставление набора индексных терминов с местоположениями их списков размещения. Столбец списков публикации содержит не данные, а указатель/ссылку на фактическое хранилище данных, это просто ссылки на фактические текстовые данные, доступные в памяти или на диске.
Поддерживаемые операции по словарю 🚀
Реализации “базового” словаря в инвертированных индексах/поисковых системах обычно обеспечивают следующие операции:
- Вставить новую запись в словарь
- Поиск/Найти ключ в словаре:
- Найдите определенный ключ/термин и верните запись списка проводок.
- Найдите записи для всех терминов, которые начинаются с заданного префикса.
- Обновите записи терминов словаря в соответствии с новыми входящими данными. Операция удаления также может быть частью этого, поскольку удаление старых терминов является своего рода обновлением словаря на основе новых поступающих данных.
Мы разберемся с операцией поиска/поиска и вставки прямо сейчас в этом посте.
Проблема в нашем прекрасном словаре? ❓ Давайте предположим, что в моем словаре 10 000 000 терминов. И я планирую поискать термин “Скрэнтон” в этом словаре. Это само по себе становится проблемой, поскольку сканирование/поиск по словарю приведет к временной сложности O (n). Как нам уменьшить его? А теперь присаживайтесь и позвольте мне объяснить вам это двумя наиболее популярными способами достижения этой цели:
Типы для хранения словарных терминов :
- Словарь на основе сортировки
- Дерево поиска
- Список лексикографического порядка
- Словарь на основе хэша.
Опять же, идеальных решений не существует, вы можете выбрать тип в зависимости от ваших требований. Мы рассмотрим плюсы и минусы каждой реализации, которые помогут вам выбрать лучший подход, основанный на проблеме/сценарии.
Словарь на основе сортировки 👀
Как следует из названия, эта реализация основана на расположении нашей коллекции текстов (она же словарь) в отсортированном виде. Эта лексикографически отсортированная форма может быть реализована двумя способами: один – это отсортированные массивы , а другой – деревья поиска . Поиск по текстовой коллекции (она же словарь) выполняется с использованием двоичного поиска в случае отсортированных массивов и обхода дерева в случае деревьев поиска.
Словарь на основе хэша 👀
Для словарей на основе хэша мы можем использовать хэш-таблицы. Где каждый термин имеет соответствующую запись в хэш-таблице. Хэш-таблицы работают удивительно быстро, когда мы ищем определенный термин, но в этом есть подвох, который мы обсудим позже в статье (т.Е. совпадения префиксов). Кроме того, большинство людей считают, что поиск и вставки происходят в хэш-таблицах с O (1) временной сложностью, но ЭТО НЕ ТАК. Чтобы понять это, вы можете прочитать этот ответ на stackoverflow
Сравнение словарей на основе хэша и сортировки. 🚀
- Если размер хэш-таблицы выбран правильно, реализация хэш-таблицы для поиска определенного термина обычно выполняется быстрее, чем словарь на основе сортировки. Потому что, в отличие от подхода, основанного на сортировке, двоичный поиск или обход дерева не требуются.
- Давайте рассмотрим запрос, который требует совпадения префиксов, например, поиск “Jef *” в словаре должен соответствовать всем индексным терминам, начинающимся с “Jef” -> Джефф Безос, Джеффри Арчер и т.д. Для выполнения этого требования хэш-таблицам потребуется, чтобы система сканировала всю хэш-таблицу (т.Е. коллекцию терминов) для этого, тогда как при подходе, основанном на сортировке, обычно это будет намного быстрее ~ O (log (n)). По этой причине функция автозаполнения на таких веб-сайтах, как amazon.com будет использоваться (своего рода) сопоставление префикса с данными каталога продуктов где-то в фоновом режиме, и для того, чтобы оно было удивительно быстрым, вы просто не можете получить его за O (n) временной сложности, оно должно быть O (log (n)) или даже меньше. И эта структура данных предпочтительно должна представлять собой удивительно быстрое дерево поиска. Кроме того, это основная функциональность, которая ожидается от любой поисковой системы или инвертированного индекса, потому что в конце дня вы просто хотите ввести “lap” и получить параметры, как показано на изображении здесь: (Примите это, вам нравится эта функция, и вы используете ее каждый день, примите это, черт возьми) 😜
Но в соответствии с нашей человеческой склонностью, мы всегда хотим знать, кто лучше кого, верно? Месси ПРОТИВ Роналду? Роберт Дениро Против Аль Пачино? dev.to ПРОТИВ среднего? 🙄
🙋 Итак, какой из словарей на основе сортировки и хэша лучше?
Томас Соуэлл однажды сказал: Решений Нет, Есть Только Компромиссы. Итак, учитывая утверждение Томаса, ответ таков: Словари на основе сортировки с использованием деревьев поиска . ((конечно, с приличными компромиссами во времени обработки запросов).
Помимо поддержки запросов с префиксом, предсказуемой производительности, есть еще одна причина, по которой я сказал, что “Индексы на основе сортировки лучше”. Вы когда-нибудь слышали о Люсене? самая популярная поисковая система, используемая elasticsearch и Solr под капотом. Для индекса полнотекстового поиска Apache Lucene с индексом памяти Lucene использует подход, основанный на сортировке по словарю. Не поверите, проверьте исходный код самостоятельно. Здесь (Я попросил коммиттеров Lucene подтвердить это, также обновлю это после получения от них подтверждения)
Бонусный Гяан : к вашему сведению: SortedMap – это не что иное , как красивое Красно-черное дерево . 🖖 Кроме того, в священном “Введении в алгоритм” Томаса Кормена говорится, что “Красно-черные деревья создают хорошие деревья поиска”. с доказательством на странице 309. Я обязательно расскажу об этом в некоторых своих будущих постах. Надеюсь, вы сможете присоединиться к ссылкам отсюда.
Итак, в этой статье мы обсудили все основные компромиссы между реализацией словаря. В следующей статье мы снова рассмотрим кое-что, связанное с реализацией словаря, то есть с токенизацией термина. На данный момент мы рассматриваем только “пробел” между предложениями/документами для определения терминов, но есть много других вещей, которые необходимо учитывать.
Кроме того, надеюсь, вам понравилась статья и она была вам полезна. Как всегда, я открыт для предложений и отзывов по поводу сериала.
Оригинал: “https://dev.to/im_bhatman/components-of-inverted-index-the-dictionary-1gf5”