Ответ 1

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

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

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

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

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

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

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

• Обработка HTML
• Обработка текста
• Индексация
• индексирование
• Рейтинг

Обработка HTML

Здесь есть два подхода.

• Разделение На странице, на которую вы ссылаетесь, обсуждаются методы, обычно известные как удаление, которые включают удаление всех элементов HTML, которые не будут отображаться, и перевод других в их отображаемую форму. Лично я предварительно обрабатывал Perl и индексировал полученные текстовые файлы. Но для интегрированного решения, в частности того, где вы хотите записывать метки значимости (например, <h1 > , <h2 > ), вы, вероятно, хотите, чтобы ваша роль была собственной. Ниже приведена частичная реализация процедуры сглаживания С++ (появляется в Thinking in С++, окончательная версия книги здесь), из которого вы могли бы построить.

• Разбор Уровень сложности при удалении - это синтаксический анализ html, который поможет в вашем случае записывать метки значимости. Однако хороший С++ HTML-парсер трудно найти. Некоторые параметры могут быть htmlcxx (никогда не использовали его, но активно и выглядели многообещающими) или hubbub (библиотека C, часть NetSurf, но утверждает, что она переносима).

  Если вы имеете дело с XHTML или хотите использовать конвертер HTML-to-XML, вы можете использовать один из многих доступных синтаксических анализаторов XML. Но опять же, конвертеры HTML-to-XML трудно найти, единственное, что я знаю, это HTML Tidy. Помимо преобразования в XHTML, его основная цель - исправить недостающие/сломанные теги, а имеет API, который можно было бы использовать для интеграции это приложение. Учитывая документы XHTML, существует много хороших парсеров XML, например. Xerces-С++ и tinyXML.

Обработка текста

Для английского языка, по крайней мере, обработка текста словами довольно проста. При поиске есть несколько осложнений.

• Остановить слова - это слова, известные априори, чтобы не давать полезного различия между документами в наборе, такими как статьи и предложения. Часто эти слова не индексируются и не фильтруются из потоков запросов. В Интернете доступно множество списков стоп-слов, таких как one.

• Stemming включает в себя предварительную обработку документов и запросов для определения корня каждого слова для лучшего обобщения поиска. Например. поиск "foobarred" должен давать "foobarred", "foobarring" и "foobar". Индекс можно строить и искать только на корнях. Два общих подхода к истощению основаны на словах (поиск из слова == > root) и основанный на алгоритме. Алгоритм Портера очень распространен, и доступны несколько реализаций, например. С++ здесь или C здесь, Освобождение в Библиотека Snowball C поддерживает несколько языков.

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

Индексация

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

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

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

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

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

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

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

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

Рейтинг

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

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

score [j] = sum_over_i (word_freq [i, j] * inv_doc_freq [i])

где word_freq [i, j] - количество вхождений слова я в документ j и

inv_doc_freq [i] = log (M/doc_freq [i])

где M - количество документов, а doc_freq [i] - количество документов, содержащих слово i. Обратите внимание, что слова, которые встречаются во всех документах, не будут способствовать оценке. Более сложная модель скоринга, которая широко используется, BM25, которая включена как в Lucene, так и в Xapian.

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

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

Ответ 2

В зависимости от размера и количества статических страниц вы можете посмотреть уже существующее решение поиска.

"Как вы реализуете полнотекстовый поиск для этой таблицы в 10+ миллионов строк, не отставайте от нагрузки и сохраняете актуальность? Sphinx хорош в таких загадках."

Я бы выбрал Sphinx для full text searching. Лицензия GPL, но также доступна версия commercial. Он предназначен для автономного [2], но он также может быть встроен в приложения путем извлечения необходимой функциональности (будь то indexing [1], searching [3], stemming и т.д.).

Данные должны быть получены путем разбора входных файлов HTML и преобразования их в plain-text с помощью парсера типа libxml2 HTMLparser (Я не использовал его, но они говорят, что он может анализировать даже искаженный HTML). Если вы не привязаны к C/C++, вы можете взглянуть на Beautiful Soup.

После получения простых текстов вы можете сохранить их в базе данных, например MySQL или PostgreSQL. Если вы хотите сохранить все встроенное, вы должны пойти с sqlite.

Обратите внимание, что Sphinx не работает из-за коробки с sqlite, но есть попытка добавить поддержку (sphinx-sqlite3).

Ответ 3

Я бы атаковал это с помощью небольшой базы данных sqlite. У вас могут быть таблицы для "страницы", "срок" и "срок страницы". "Страница" будет иметь столбцы, такие как id, текст, заголовок и URL. "Термин" будет содержать столбец, содержащий слово, а также первичный идентификатор. "Термин" срок страницы "будет иметь внешние ключи для идентификатора страницы и идентификатора термина, а также может хранить вес, рассчитанный с расстояния от вершины и количества вхождений (или того, что вы хотите).

Возможно, более эффективным способом было бы иметь только две таблицы - "страница", как и раньше, и "термин страницы", который имел бы идентификатор страницы, вес и хэш слова слова.

Пример запроса - вы хотите найти "foo". Вы hash "foo", затем запросите все строки с фразами страниц, которые имеют этот хэш. Сортировать по убыванию веса и показать десятку результатов.

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

Ответ 4

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

Удачи!