Как работает поисковая система? Образовательный поход через формат сообщений Lucene

Новая функция Lucene 4 — подключаемые кодеки — позволяет модифицировать базовый механизм хранения Lucene. Работа с кодеками и изучение их выходных данных дает захватывающее понимание того, как именно поиск Lucene работает в его наиболее фундаментальной форме.

Центральным элементом кодека Lucene является формат сообщений. Сообщения  обычно распространяются вокруг слов в пространстве Lucene. Формат сообщений — это представление инвертированного поискового индекса — базовой структуры данных, используемой для поиска документов, содержащих термин. Я думаю, что ничто в действительности не отражает логический внешний вид публикаций Люсена лучше, чем SimpleTextPostingsFormat Майка МакКэндлесса  . SimpleText представляет собой текстовое представление сообщений, созданных в образовательных целях. Я проиндексировал несколько документов в Lucene, используя SimpleText, чтобы продемонстрировать, как структурированы публикации для быстрого поиска:

Образцы документов

doc0:
author:DougTurnbull
text:where oh where are myUnicorns!
doc1:
author:ScottStults
text:Unicorns!Unicorns!

Если мы говорим Lucene , чтобы разделить слова на пробельном (Lucene в WhitespaceAnalyzer ), указать SimpleText кодек, и записывать эти документы, используя в IndexWriter, мы получаем проводки Lucene в сериализовать на диск в этом славном удобочитаемом формате:

field author
  term Doug
    doc 0
      freq 1
      pos 0
  term Scott
    doc 1
      freq 1
      pos 0
  term Stults
    doc 1
      freq 1
      pos 1
  term Turnbull
    doc 0
      freq 1
      pos 1
field text
  term Unicorns!
    doc 0
      freq 1
      pos 5
    doc 1
      freq 2
      pos 0
      pos 1
  term are
    doc 0
      freq 1
      pos 3
  term my
    doc 0
      freq 1
      pos 4
  term oh
    doc 0
      freq 1
      pos 1
  term where
    doc 0
      freq 2
      pos 0
      pos 2END

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

Больше, чем просто срок -> Номер страницы

Хотя индекс в книге является полезной метафорой, которую мы можем и будем покорно использовать, индексы книг не содержат частоту этого термина на странице. Они также не указывают позицию на странице, где встречаются термины. Эта информация фиксируется в формате сообщений. Раздел для «Единорогов!» термин хорошо отражает это понятие:

term Unicorns!
    doc 0
      freq 1
      pos 5
    doc 1
      freq 2
      pos 0
      pos 1

Почему термин частота и позиция очень полезны для поисковых систем?

Частота термина помогает нам определить, насколько документ соответствует данному термину. Если в документе 1 будет сравнительно больше «единорогов», то он будет оценен выше. Эта модель известна как модель  TF-IDF, названный в честь очень простой математики, которая отражает эту идею. В качестве примера, распространите это на нашу метафору книги. Допустим, вы ищете «Эдгара Аллена По» в книге о литературе 19-го века. Если бы по индексу этой книги вы знали, что на странице 15 упоминается больше Эдгара Аллена По, а на странице 5 меньше, вероятно, вы с большей вероятностью перейдете на страницу 15. Это потому, что вы, вероятно, различаете эту страницу 15 с ее более частые упоминания «Эдгара Аллена По», скорее всего, будут лучшей страницей для перехода. Это понятие соответствует ожиданиям большинства людей при поиске и лежит в основе поискового рейтинга Lucene.

Срочные позиции также полезны. Представьте в нашем предыдущем примере, если мы не указали «Эдгар Аллен По» в указателе книги. Вместо этого у нас были отдельные слова «Эдгар», «Аллен» и «По». Мы могли бы, однако, выяснить, было ли строгое упоминание фразы «Эдгар Аллен По», если бы мы записали положение каждого термина на странице в указателе нашей книги. Например, «Эдгар» — это слово № 3 на странице 5; «По» — это слово № 17 на странице 5 и т. Д. Это было бы болезненным и раздражающим для нас, людей, но мы могли бы это сделать. Тем не менее, это легко для компьютера — компьютерам легче разбирать текст на пустом месте и труднее узнавать имена опытных авторов. Поэтому именно это делает Lucene. Lucene может быстро определить расстояние и расположение поисковых терминов в документе во время запроса. Если термины «Эдгар», «Аллен»,и «Poe» — это совпадения И находятся рядом и в правильном порядке, тогда Lucene может определить, что эта страница является попаданием. Эта способность позволяет Lucene поддерживать запросы с учетом терминов, например Фразовые запросы  и запросы span .

Дьявол в деталях

Так как же работает поисковая система? Вот и все. Ну вроде как. Это больше похоже на обучение тому, как складывать и вычитать, и ожидать, что вы получите алгебру. Сложной частью часто является создание и использование этого инвертированного индекса для реального ориентированного на пользователя приложения. Одна из проблем, упомянутых выше, заключается в том, как правильно анализировать и разбивать контент на части — сложно в зависимости от языка и характера контента. Пробельные символы в большинстве случаев не вырезаются, как будто вы индексируете фрагменты кода и хотите использовать токены в camelCase. Может быть, вы хотели бы нормализовать ваш текст в корневой форме слов. Или включить синонимы в указатель. Выше также упоминается, что хотя TF-IDF формирует корень оценки по умолчанию Lucene, он не охватывает все включенные переменные. Есть много настроек по пути,включая нормы — смещение результатов поиска к более коротким полям — и пользовательское усиление — пользователи отдают предпочтение попаданиям из определенных полей или по конкретным запросам. Есть также вопрос о стратегии поиска, которую вы используете для своего приложения. Вы только делаете прямой поиск? Вам нужны диапазонные запросы? Обыскиваются ли отдельные поля или несколько одновременно ? Хотите ли вы включить такие функции, как огранка? Эти и многие другие соображения вступают в игру, когда вы пытаетесь заставить инвертированный индекс Lucene выполнять ваши ставки.

Более фундаментально, есть факт, что это, конечно, образовательная реализация инвертированного индекса. Хорошая, быстрая структура данных, которая не пойдет в течение нескольких минут, чтобы дать вам ответ, действительно необходима. Короче говоря, есть много и много хардкорных структур данных, задуманных над тем, как именно это работает. Если вы хотите получить опыт работы с доктором наук, я рекомендую вам как можно скорее погрузиться в Lucene42PostingsFormat. Вот  вкус чего-то, что  поможет вам начать. Как только вы дойдете до сути этого формата сообщений —  позвоните мне … для работы   .