Этот процесс обычно известен как поиск информации . Вы, вероятно, найдете эту онлайн-книгу полезной.

Существующие библиотеки

Вот два существующих решения, которые можно полностью интегрировать в приложение, не требуя отдельного процесса (я считаю, что оба будут компилироваться с VC ++).

Xapian является зрелым и может делать многое из того, что вам нужно, от индексации до ранжированного поиска.Отдельный синтаксический анализ HTML потребуется, потому что, AFAIK, он не анализирует HTML (у него есть сопутствующая программа Omega , которая является интерфейсом для индексирования веб-сайтов).

Lucene - это библиотека Apache для индексации / поиска на Java с официальной предварительной версией C lucy и неофициальной версией C ++ CLucene .

Реализация поиска информации

Если по какой-то причине вышеперечисленные варианты не работают, вот некоторая информация об отдельных этапах построения и использования индекса. Индивидуальные решения могут быть от простых до очень сложных, в зависимости от того, что вам нужно для вашего приложения. Я разбил процесс на 5 шагов

1. Обработка HTML
2. Обработка текста
3. Индексирование
4. Получение
5. Ранжирование

Обработка 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». Индекс можно построить и искать только по корням.Два основных подхода к поиску корня основаны на словарях (поиск из слова ==> корень) и алгоритмах. Алгоритм Портера очень распространен, и доступно несколько реализаций, например C ++ здесь или C здесь . Создание в библиотеке Snowball C поддерживает несколько языков.

• Кодирование Soundex Одним из методов повышения устойчивости поиска к орфографическим ошибкам является кодирование слов с помощью фонетического кодирования. Затем, когда в запросах есть фонетические ошибки, они по-прежнему будут отображаться напрямую в проиндексированные слова. Существует множество реализаций, вот одна .

Индексирование

Структура данных слова ==> страницы известна как инвертированный индекс . Его инвертированный, потому что он часто генерируется из прямого индекса страницы ==> слов. Инвертированные индексы обычно бывают двух видов: инвертированный индекс файла , который сопоставляет слова с каждым документом, в котором они встречаются, и полный инвертированный индекс , который сопоставляет слова с каждой позицией в каждом документе, в котором они встречаются. in.

Важным решением является то, какой бэкэнд использовать для индекса, некоторые возможности в порядке простоты реализации:

1. SQLite или Berkly DB - оба они являются базой данных движки с API C ++, которые интегрированы в проект, не требуя отдельного серверного процесса. Постоянные базы данных по сути являются файлами, поэтому поиск по нескольким индексным наборам можно выполнить, просто изменив связанный файл. Использование СУБД в качестве серверной части упрощает создание, обновление и поиск индексов.
2. В структуре данных памяти - если вы используете инвертированный индекс файла, который не является чрезмерно большим (потребление памяти и время загрузки), это может быть реализовано как std :: map , используя boost :: serialization для сохранения.
3. О структуре данных на диске - я слышал о невероятно быстрых результатах при использовании файлов с отображением памяти для такого рода вещей, YMMV.Наличие инвертированного индекса файла потребует наличия двух файлов индекса, один из которых представляет слова с чем-то вроде struct {char word [n]; беззнаковое целое смещение; беззнаковое целое число; }; , а второй представляет кортежи (слово, документ) только с unsigned int s (слова, неявные в смещении файла). Смещение - это смещение файла для идентификатора первого документа для слова во втором файле, count - это количество идентификаторов документов, связанных с этим словом (количество идентификаторов для чтения из второй файл). Затем поиск сводится к двоичному поиску по первому файлу с указателем в файле с отображением в память. Обратной стороной является необходимость дополнения / усечения слов для получения постоянного размера записи.

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

Библиотека GNU mifluz реализует инвертированные индексы с хранилищем, но без синтаксического анализа документов или запросов. GPL, поэтому, возможно, не является жизнеспособным вариантом, но даст вам представление о сложностях, связанных с инвертированным индексом, который поддерживает большое количество документов.

Извлечение

Очень распространенным методом является логическое извлечение, которое представляет собой просто объединение / пересечение документов, проиндексированных для каждого из слов запроса, которые соединены с помощью или / и, соответственно. Эти операции эффективны, если идентификаторы документов хранятся в отсортированном порядке для каждого термина, чтобы можно было напрямую применять такие алгоритмы, как std :: set_union или std :: set_intersection .

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

Ранжирование

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

Идея, лежащая в основе этой формулы, заключается в том, что если слово запроса часто встречается в документе, этот документ должен иметь более высокий балл, но слово, которое встречается во многих документах, менее информативно, поэтому это слово должно быть понижено. Формула: по условиям запроса i = 1..N и документу j

оценка [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 - количество документов, а doc_freq [i] - количество документов, содержащих слово i.Обратите внимание, что слова, встречающиеся во всех документах, не влияют на оценку. Широко используется более сложная скоринговая модель BM25 , которая включена как в Lucene, так и в Xapian.

Часто эффективное ранжирование для конкретной области достигается путем корректировки методом проб и ошибок.Отправной точкой для корректировки ранжирования по контексту заголовка / абзаца может быть увеличение word_freq для слова на основе контекста заголовка / абзаца, например 1 для абзаца, 10 для заголовка верхнего уровня. Что касается некоторых других идей, вы можете найти эту статью интересной, где авторы скорректировали рейтинг BM25 для позиционной оценки (идея состоит в том, что слова ближе к началу документа более релевантны, чем слова ближе к концу).

Объективная количественная оценка эффективности ранжирования получается с помощью кривых точности-отзыва или средней средней точности, подробно здесь . Для оценки требуется идеальный набор запросов, сопряженный со всеми соответствующими документами в наборе.