Базовая структура данных для системы поиска текста - это Инвертированный индекс . По сути, это список слов, найденных в коллекции документов, со списком документов, в которых они встречаются. Он также может содержать метаданные о вхождении для каждого документа, например, количество раз, когда слово появляется.
Документы, содержащие слова, могут быть запрошены путем сопоставления по условиям поиска. Чтобы определить релевантность, по хитам рассчитывается эвристика, известная как Рейтинг косинусов . Это работает путем построения n-мерного вектора с одним компонентом для каждого из n поисковых терминов. Вы также можете взвесить условия поиска, если хотите. Этот вектор дает точку в n-мерном пространстве, которая соответствует вашим условиям поиска.
Аналогичный вектор на основе взвешенных вхождений в каждом документе может быть построен из инвертированного индекса с каждой осью в векторе, соответствующем оси для каждого поискового термина. Если вы вычислите скалярное произведение этих векторов, вы получите косинус угла между ними. 1.0 эквивалентно cos (0), что предполагает, что векторы занимают общую линию от начала координат. Чем ближе друг к другу векторы, тем меньше угол и ближе косинус к 1,0.
Если вы отсортируете результаты поиска по косинусу (или поместите их в очередь с приоритетами, как это делает mg ), вы получите наиболее релевантное. Более умные алгоритмы релевантности имеют тенденцию возиться с весами поисковых терминов, искажая точечный продукт в пользу терминов с высокой релевантностью.
Если вы хотите немного покопаться, Управление гигабайтами от Bell и Moffet обсуждает внутреннюю архитектуру систем поиска текста.