Этот процесс обычно известен как поиск информации .Вы, вероятно, найдете эту онлайн-книгу полезной.
Существующие библиотеки
Вот два существующих решения, которые можно полностью интегрировать в приложение, не требуя отдельного процесса (яверю, что оба будут компилироваться с VC ++).
Xapian является зрелым и может делать многое из того, что вам нужно, от индексации до ранжированного поиска.Требуется отдельный разбор HTML, потому что, AFAIK, он не анализирует html (у него есть сопутствующая программа Omega , которая является интерфейсом для индексации веб-сайтов).
Lucene - это индексная / поисковая библиотека Apache на Java с официальной предварительной версией C lucy и неофициальной версией C ++ CLucene .
Реализация информацииretrieval
Если вышеуказанные опции по какой-либо причине не являются жизнеспособными, вот некоторая информация об отдельных шагах построения и использования индекса.Индивидуальные решения могут быть как простыми, так и очень сложными, в зависимости от того, что вам нужно для вашего приложения.Я разбил процесс на 5 этапов
- Обработка HTML
- Обработка текста
- Индексирование
- Извлечение
- Рейтинг
Обработка HTML
Здесь есть два подхода
Разборка На странице, на которую вы ссылаетесь, обсуждается общеизвестная техникакак разбор, который включает в себя удаление всех HTML-элементов, которые не будут отображаться, и перевод других в их форму отображения.Лично я бы предпочел использовать perl и индексировать полученные текстовые файлы.Но для интегрированного решения, особенно для того, где вы хотите записать теги значимости (например,
, ), вы, вероятно, захотите сыграть свою роль. Вот частичная реализация подпрограммы разборки C ++ (появляется в Thinking in C ++ , окончательная версия книги здесь ), из которой вы могли бы построить.
Синтаксический анализ Повышение уровня сложности от разбора - это html-разбор, который поможет в вашем случае для записи значимых тегов.Тем не менее, хороший синтаксический анализатор C ++ HTML трудно найти .Некоторые параметры могут быть htmlcxx (никогда не использовал, но активен и выглядит многообещающе) или hubbub (библиотека C, часть NetSurf, но претендует на переносимость).
Если вы имеете дело с XHTML или хотите использовать конвертер HTML-в-XML, вы можете использовать один из многих доступных анализаторов XML.Но опять же, конвертеры HTML-в-XML найти сложно, я знаю только один HTML Tidy .В дополнение к преобразованию в XHTML, его основная цель состоит в том, чтобы исправить отсутствующие / сломанные теги, и он имеет API , который мог бы использоваться для интеграции его в приложение.Для документов XHTML существует много хороших анализаторов XML, например, Xerces-C ++ и tinyXML .
Обработка текста
По крайней мере, для английского языка обработка текста в слова довольно проста.Однако при поиске возникает пара сложностей.
Стоп-слова - это слова, известные априори, которые не дают полезного различия между документами в наборе, напримеркак статьи и предложения.Часто эти слова не индексируются и не фильтруются из потоков запросов.В Интернете доступно множество списков стоп-слов, например, этот один .
Основа включает в себя предварительную обработку документов и запросов для определения корня каждого слова, чтобы лучше обобщить поиск.Например, поиск «foobarred» должен привести к «foobarred», «foobarring» и «foobar».Индекс можно построить и искать только по корням.Два основных подхода к основам - это словарь (поиск по слову ==> root) и алгоритм.Алгоритм Портера очень распространен, и доступно несколько реализаций, например, C ++ здесь или C здесь .Stemming в библиотеке Snowball C поддерживает несколько языков.
Кодировка Soundex Одним из способов сделать поиск более устойчивым к орфографическим ошибкам является кодирование слов с помощью фонетического кодирования.Затем, когда запросы имеют фонетические ошибки, они все равно будут отображаться непосредственно в проиндексированные слова.Есть много реализаций вокруг, вот одна .
Индексирование
Структура данных страницы ==> карты данных известна как инвертированный индекс .Он инвертирован, потому что его часто генерируют из прямого индекса страниц ==> слов.Инвертированные индексы обычно бывают двух видов: индекс инвертированного файла , который отображает слова в каждый документ, в котором они встречаются, и полный инвертированный индекс , который отображает слова в каждую позицию в каждом документе, в котором они встречаютсядюйма
Важным решением является то, какой бэкэнд использовать для индекса, некоторые возможности в порядке простоты реализации:
- SQLite или Berkly DB - оба они являются ядрами баз данных с API-интерфейсами C ++, которые интегрированы в проект без отдельного серверного процесса.Постоянные базы данных по сути являются файлами, поэтому поиск по нескольким наборам индексов можно выполнить, просто изменив связанный файл.Использование СУБД в качестве бэкэнда упрощает создание, обновление и поиск индекса.
- В структуре данных памяти - если вы используете инвертированный индекс файла, который не слишком велик (потребление памяти и время загрузки), это можно реализоватькак
std::map<std::string,word_data_class>, используя boost :: serialization для сохранения. - В структуре данных на диске - я слышал о невероятно быстрых результатах с использованием файлов с отображением в памяти для такого рода вещей, YMMV,Наличие инвертированного индекса файла подразумевало бы наличие двух файлов индекса, один из которых представлял бы слова с чем-то вроде
struct {char word[n]; unsigned int offset; unsigned int count; };, а второй представлял кортежи (слово, документ) всего с unsigned int s (слова, неявные в смещении файла).offset - это смещение файла для первого идентификатора документа для слова во втором файле, count - это число идентификаторов документов, связанных с этим словом (количество идентификаторов, которые нужно прочитать из второго файла).Поиск затем сводится к двоичному поиску по первому файлу с указателем на файл, отображенный в памяти.Обратной стороной является необходимость дополнения / усечения слов для получения постоянного размера записи.
Процедура индексации зависит от того, какой бэкэнд вы используете.Классический алгоритм генерации инвертированного индекса файла ( подробно здесь ) начинается с чтения каждого документа и расширения списка кортежей (идентификатор страницы, слово), игнорируя повторяющиеся слова в каждом документе.После обработки всех документов отсортируйте список по словам, а затем сверните в (word, (id страницы 1, id страницы 2, ...)).
Библиотека mifluz gnu реализует инвертированные индексыс хранилищем, но без разбора документа или запроса.GPL, поэтому не может быть приемлемым вариантом, но даст вам представление о сложностях, связанных с инвертированным индексом, который поддерживает большое количество документов.
Извлечение
Очень распространенным методом являетсялогическое извлечение, которое представляет собой просто объединение / пересечение документов, проиндексированных для каждого из слов запроса, которые соединяются с или / и, соответственно.Эти операции эффективны, если идентификаторы документов хранятся в отсортированном порядке для каждого термина, поэтому алгоритмы, такие как std::set_union или std::set_intersection, могут применяться напрямую.
Существуют варианты поиска, Википедия имеет обзор, но стандартное логическое значение хорошо для многих / большинства приложений.
Ранжирование
Существует множество методов ранжирования.документы, возвращенные логическим поиском.Общие методы основаны на модели мешка слов, что означает, что относительное положение слов игнорируется.Общий подход заключается в оценке каждого извлеченного документа относительно запроса и ранжировании документов на основе их вычисленной оценки.Существует много методов оценки, но хорошей отправной точкой является формула частота-обратная частота документа формула.
Идея, лежащая в основе этой формулы, состоит в том, что если слово запроса часто встречается в документе, этот документ должен иметь более высокий балл, но слово, встречающееся во многих документах, является менее информативным, поэтому это слово должно быть взвешено.Формула для терминов запроса i = 1..N и документа j
score [j] = sum_over_i (word_freq [i, j] * inv_doc_freq [i])
где word_freq[i, j] - количество вхождений слова i в документе j, а
inv_doc_freq [i] = log (M / doc_freq [i])
, где M - числоDocuments and doc_freq [i] - количество документов, содержащих слово i.Обратите внимание, что слова, встречающиеся во всех документах, не влияют на оценку.Более сложная модель оценки, которая широко используется, это BM25 , которая включена как в Lucene, так и в Xapian.
Часто эффективное ранжирование для определенного домена получается путем корректировки методом проб и ошибок.Начальным местом для корректировки ранжирования по контексту заголовка / абзаца может быть накачка word_freq для слова на основе контекста заголовка / абзаца, например, 1 для абзаца, 10 для заголовка верхнего уровня.Для некоторых других идей вам может показаться эта статья интересной, где авторы скорректировали ранжирование BM25 для позиционной оценки (идея заключается в том, что слова ближе к началу документа более актуальны, чем слова ближе к концу).
Объективная количественная оценка эффективности ранжирования получается с помощью кривых точного отзыва или средней средней точности, детально здесь .Оценка требует идеального набора запросов в паре со всеми соответствующими документами в наборе.