Во-первых, основная концепция поисковой системы

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

"Неструктурированные" здесь на самом деле для классической базы данных. Записи в базе данных имеют строгие определения полей (Схема), что является типичным представителем "структурированных" данных. Например, у каждого блюда есть название, и вы хотите съесть Когда речь идет о рыбе, запрос «вареная рыба» очень эффективен.

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

В настоящее время технология информационного поиска может очень помочь нам в том, что характеристика неструктурированных данных заключается в том, что нет строгого определения формата данных, что определяет следующие два основных элемента информационного поиска:

Актуальность: Существует ли достаточная корреляция между запросами пользователей и возвращаемыми результатами, не существует строгого определения. Значение, выраженное на естественном языке, довольно богато. Ключевым моментом является то, как заставить компьютеры лучше «понимать» информационные потребности человека.
Своевременность: сколько времени требуется пользователю, чтобы получить возвращенные результаты после ввода запроса.Для решения корреляции необходимо разработать разумную модель, тогда сложность модели может увеличиться, а также увеличится соответствующий объем вычислений, поэтому требуется эффективная реализация системы.

2. Корреляция

2.1 Булева модель

Предположим, я очень люблю есть варёную рыбу сычуаньской кухни, и её пикантный вкус незабываем.Если я хочу прочитать статью о культуре сычуаньской кухни, проще всего посмотреть, упоминается ли в ней ключевое слово «вода». ". Если есть (возвращает истину), то я считаю это релевантным, если нет (возвращает ложь), я считаю его неактуальным.

Это самая базовая булева модель, если очень просто преобразовать этот запрос в логическое выражение, есть только одно условие:

вареная рыба

Конечно, вы подумаете, что китайская диета имеет долгую историю, как в классической сычуаньской кухне может быть только вареная рыба? Да, я тоже очень люблю свиные ребрышки на пару.В детстве это было обязательным блюдом на Китайский Новый год и праздники.Тогда измените условия

Вареная рыба ИЛИ свиные ребрышки на пару

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

(отварная рыба ИЛИ свиные ребрышки на пару с порошком) И Шанхай

Здесь «шанхай» — необходимое условие, и достаточно либо отварной рыбы, либо свиных ребрышек на пару с мукой. Наконец, мы можем увидеть, в каких статьях упоминается, что рестораны в Шанхае подают блюда сычуаньской кухни и предлагают по крайней мере одно из двух деликатесов: вареную рыбу и свиные ребрышки на пару.Пока вы понимаете логические выражения, вы можете понимать логические модели в информационном поиске. В дополнение к базовым операциям И, ИЛИ НЕ была расширена булева модель.

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

В целом преимущества булевой модели заключаются в том, что она проста и понятна, а стоимость внедрения системы ниже. Однако его слабость заключается в недостаточной характеристике корреляций. Связано это или нет — понятие расплывчатое.Некоторые статьи тесно связаны с условиями запроса, которые полностью соответствуют информационным потребностям пользователей, а другие — нет. Это слишком абсолютно, чтобы выразить только через два значения «истина» и «ложь», и нет никакого способа отразить разницу Итак, есть ли лучшее решение?

2.2 Ранжированная булева модель

Чтобы улучшить булевую модель, нам нужно подумать о том, как оценивать совпадающие документы. Документы с более высокой релевантностью получают более высокие баллы. Первая и наиболее интуитивно понятная идея заключается в том, что вес каждого слова в разных документах разный, что можно использовать для подсчета баллов. Здесь представлен наиболее часто используемый механизм tf-idf.

Предположим, у нас есть коллекция документов (Коллекция), c представляет всю коллекцию, d представляет одну из статей, а t представляет слово. Тогда tf здесь представляет частоту термина (Term Frequency), которая представляет собой количество раз, когда слово t появляется в статье (или в поле статьи). Общее предположение состоит в том, что чем выше tf слова в статье, тем важнее слово t для статьи. Конечно, более длинные документы могут иметь более высокие значения tf.Мы обсудим, как вычислить tf, чтобы сделать его более разумным, во введении к Lucene позже.

В то же время другим часто используемым является idf, который представляет обратную частоту документа (Inverse Document Frequency). Во-первых, df представляет частоту документа (Document Frequency), то есть количество документов с определенным словом t в наборе документов c. Общее предположение состоит в том, что слово t появляется в большем количестве документов в наборе документов c, чем менее оно важно, и наоборот.

Сначала это может показаться немного запутанным, но это нетрудно понять, если подумать. Например, такие слова, как «the, you, me, is», часто встречаются в документах, но не имеют никакого конкретного значения. Другой пример: в сборнике документов, посвященных еде, слово «еда» может встречаться в десятках тысяч статей, но это не делает документ особенным. И наоборот, если есть только 3 статьи, посвященные вареной рыбе, то эти 3 статьи имеют гораздо большее отношение к вареной рыбе, чем другие статьи. Слово «вареная рыба» должно иметь больший вес в сборнике документов. В связи с этим для выражения ее важности обычно используется обратно пропорциональный индекс idf df.Основная формула выглядит следующим образом:

Где N — количество статей во всей коллекции документов, log — чтобы убедиться, что оценка idf не намного выше, чем tf, и похоронить вклад tf, а по умолчанию используется основание 10. Таким образом, чем ниже df слова t, тем выше его idf и тем выше важность t. Таким образом, основная формула tf-idf выглядит следующим образом:

То есть слово t, если его словочастотность tf в документе выше, а idf во всем множестве также высока, то t важнее d.

2.3 Модель векторного пространства

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

Посчитайте в нем слова, предполагая, что после дедупликации осталось 50 разных (Уникальных) слов, тогда вектор текстовой подсказки равен 50 широтам, каждая из которых является значением tf-idf соответствующего ему слова, что выглядит так:

(Сычуань = 1,84, Вареная рыба = 6,30, Альбом = 6,80,…)

Конечно, когда система будет реализована, широта будет представлена не словами, а идентификатором слова. Таким образом, набор документов преобразуется в набор векторов, каждый из которых представляет документ. Это представление игнорирует порядок, в котором слова появляются в статье, что может значительно упростить вычислительную сложность многих моделей, обеспечивая при этом значительную точность.Мы обычно называем этот метод обработки Bag Of Word.Это упоминалось в первой статье о классификации текста и кластеризация.

Точно так же запрос, введенный пользователем, также может быть преобразован в набор векторов, но по сравнению с вектором документа размерность вектора запроса будет очень низкой. Наконец, проблема релевантности превращается в вычисление сходства между вектором запроса и вектором документа. В практической обработке наиболее часто используемой мерой сходства является косинусное расстояние. Поскольку это число от 0 до 1, если направление соответствует, то оно равно 1, а если оно ортогонально, то равно 0, что также соответствует характеристикам процента сходства. Конкретная формула расчета выглядит следующим образом. :

Его графическое объяснение показано на рисунке:

По сравнению со стандартной булевой математической моделью модель векторного пространства имеет следующие преимущества:

Простая модель, основанная на линейной алгебре, очень проста для понимания.
Вес фразы может быть не бинарным, например, при использовании механизма tf-idf
Позволяет вычислять степень непрерывного сходства между документами и указателями и упорядочивать их на основе этого, не ограничиваясь булевой моделью. "истина" и "ложь" два значения
Разрешить частичное соответствие ключевых слов

Конечно, базовая модель векторного пространства тоже оставляет желать лучшего:

Например, для очень длинных документов оценка сходства не будет идеальной; семантика, представленная словами, не учитывается и по-прежнему ограничивается точным совпадением; порядок, в котором слова появляются в документе, не учитывается.

3. Своевременность

После предыдущего обсуждения мы обнаружили, что для решения корреляции необходимо разработать разумную модель в соответствии с требованиями.Чем точнее модель, тем выше вычислительная сложность. В то же время мы должны обеспечить очень высокую эффективность запросов. В эпоху Интернета пользователи — это обычные пользователи, и «освежающий» опыт имеет решающее значение. Поэтому обработка результата поисковиком должна быть в секундах, обычно не более 3 секунд. Сидеть перед компьютером и ждать несколько минут, чтобы узнать, какая завтра будет погода в Гуанчжоу, невообразимо и неприемлемо. Сложность и скорость расчета корреляций кажутся парой непримиримых противоречий, как их решить?

Здесь следует упомянуть, что наиболее классической структурой данных механизма поиска является инвертированный индекс (или обратный индекс). Представим сначала, что вы человек, любящий читать, как, зайдя в библиотеку или книжный магазин, вы быстро найдете любимые книги? Правильно, просто посмотрите на этикетки на книжных полках. Если вы видите полку с пометкой «Кулинария · Местная еда», то поздравляем, вы недалеко от книги, знакомящей с сычуаньской кухней. Что делает инвертированный индекс, так это маркировка. посмотри В приведенном выше примере это исходные данные, которые не были обработаны инвертированным индексом, конечно, реальная статья не будет такой короткой.

Для содержания каждой статьи мы сначала выполняем сегментацию китайских слов, а затем используем сегментированные слова в качестве метки статьи. Например, статью с ID 1 «самая захватывающая и очень вкусная сычуаньская кухня» можно разделить на следующие 5 слов:

Самая, вызывающая привыкание, да, совершенно вкусная, сычуаньская кухня

Тогда статья 1 будет иметь 5 тегов ключевых слов.

Повторно анализируя статью с ID 2 «Обязательная к прочтению серия для поваров: классическая сычуаньская кухня», ее можно разделить на следующие 5 слов:

Шеф-повар, Обязателен к прочтению, Сериал, Классический, Сычуаньская кухня

В сочетании с результатом 1-й метки

Обратите внимание, что ключевое слово «Сычуаньская кухня» с идентификатором 5 появилось в обеих статьях 1 и 2, поэтому мы запишем соответствующий идентификатор документа как «1, 2».

Проанализировав все 5 статей одну за другой, мы получим следующую таблицу, которая является прототипом перевернутого указателя.

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

Сычуаньская кухня И кончик языка

При поиске «сычуаньская кухня» система вернет идентификаторы статей: 1, 2, 3; при поиске «кончик языка» система вернет идентификаторы статей: 3, 4, а затем, взяв пересечение, мы можем найти статью 3 и вернуть его. Операция слияния, выполняющая пересечение, является очень зрелой в компьютерной области и на удивление быстрой.

Учитывая операцию близости булевой модели или других моделей расчета, мы также можем добавить позицию слова и информацию, такую как tf-idf, в структуру данных, Мы не будем здесь расширяться. Наиболее важные выводы здесь: Мы можем поддерживать суперэффективность с инвертированными индексами.