Существует ли эффективный алгоритм для выполнения инвертированного полнотекстового поиска?

Question

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

Answer 1

Я думаю, что некоторые ответы до сих пор неправильно понимают проблему, которая задается.Насколько я понимаю, у вас есть (большой) список слов и (большой) текст.Вы хотите знать, какие слова объединяют оба списка , это правильно?

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

Предполагая, что список ключевых слов уже отсортирован, вы можете извлечь и отсортировать слова из основного текста в O(n logn) время, а затем сканирование по обоим спискам одновременно равно O (n + m) (где n - количество слов в тексте, а m - количество слов в списке ключевых слов).

Answer 2

Вы можете использовать любое из приведенных выше описанных решений, однако все они в основном делают одно и то же (затем добавляют прибамбасы)

Итак, основной подход:

1. Разделениеваш поисковый ввод в слова
2. Удаление шума (это могут быть очень распространенные слова, знаки препинания и т. д.)
3. Ваша база данных должна содержать ваши ключевые фразы (вы сказали, что ключевое слово может содержать несколько слов, поэтому егоключевая фраза)
4. У вас есть карта слов в ключевой фразе

например,

keyphraseID: 1 ключевая фраза: "быстрая коричневая лиса"

wordID: 1 Слово:

wordID: 2 Слово: быстрый

mapID: 1 идентификатор ключевой фразы: 1 идентификатор слова: 1 позиция: 1

mapID: 2 идентификатор ключевой фразы: 1 идентификатор слова: 2 позиция: 2

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

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

Редактировать: -

Вы также можете взглянуть на основание - где вы берете слова обратно ктот же корень, например, исправление и исправление обоих корней в «fix».Общий алгоритм стволов называется портером.

Answer 3

Вы можете использовать такие решения, как Apache Lucene или Apache Solr (полнотекстовый сервис HTTP на основе Lucene) для достижения этой цели.

Apache Lucene предоставляет API для индексации любых данных, которые вы себе представляете.

Исходя из своих потребностей, вы можете выбрать один из следующих вариантов:

• Lucene: индекс, встроенный в ваше приложение . Кроме того, Lucene предлагает хранение индексов файловой системы или в памяти. Более того, одним из важных соображений является то, что Lucene реализован не на всех языках программирования .
• Solr: служба централизованного индексирования. Если вам нужен распределенный доступ к этой информации, Solr - это то, что вам нужно. Кроме того, он предлагает некоторую абстракцию от сложных концепций Lucene, упрощая его использование. Благодаря использованию HTTP-протокола и XML для обмена информацией между точками, является наилучшим решением для разнородных платформ .

Что касается функции проверки правописания, Solr включает проверку предложений "Spell" с использованием встроенного компонента

Некоторые уроки / информация:

• Solr: Wiki - единственный ресурс, который вам нужен.
• Lucene: в StackOverflow вы можете найти вопросы об учебниках, например this

Answer 4

Я не знаю, какую базу данных вы используете, но знаю, что если это Oracle, вы должны иметь доступ к функциональности Oracle Text (или вы можете попросить своего администратора базы данных включить ее). С помощью дополнительных функций, таких как CONTAINS и правильного использования индексов Oracle Text, вы можете достичь именно того, что вам нужно, даже ища слова с ошибками. Это достигается путем объединения CONTAINS с функцией, которая вычисляет расстояние Левенштейна между двумя строками. В Oracle Text эта функция FUZZY.

Прекрасный пример для вас в этой документации Oracle .

Я не знаю достаточно других типов баз данных, но я был почти уверен, что у крупных поставщиков есть что-то для поиска текста. Просто быстро погуглив, есть полнотекстовый поиск в:

• Сервер Sql
• PostgresSQL
• DB2
• MySQL
• ... и, конечно, другие СУБД

В любом случае, гораздо быстрее использовать встроенные функции / процедуры СУБД, чем создавать свои собственные пользовательские функции или даже осуществлять поиск по вашему языку программирования (хотя тысячи ключевых слов не так уж и много)

Редактировать: После прочтения вашего вопроса снова и ответа Дина Хардинга я почувствовал, что не отвечаю на вопрос должным образом. Используя Oracle Text, вместо использования функции CONTAINS вы можете использовать функцию MATCHES (см. Пункт 4.1.3 ), которая делает именно это: запрашивает список ключевых слов, хранящихся в таблице, по некоторым текст и возвращая идентификаторы ключевых слов, которые были найдены. Ниже я скопирую пример, найденный в документации (с добавлением моих собственных комментариев):

create table queries (
  query_id      number,
  query_string  varchar2(80)
);

// Here we populate the table with the keywords
insert into queries values (1, 'oracle');
insert into queries values (2, 'larry or ellison');
insert into queries values (3, 'oracle and text');
insert into queries values (4, 'market share');

create index queryx on queries(query_string)
  indextype is ctxsys.ctxrule;

// This query will return the ids of the matched keywords
select query_id from queries
 where matches(query_string, 
               'Oracle announced that its market share in databases 
                increased over the last year.')>0

Я надеюсь, что это поможет немного больше, чем моя первая попытка.

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

Answer 5

Поиск в интернете алгоритма Aho-Corasick.

Answer 6

Правильный способ *1001* состоит в том, чтобы построить Автомат.

Автомат (по определению) создан для распознавания слов языка, который в данном случае является вашей коллекцией ключевых слов.

Конечно, в вашем случае это немного сложнее, потому что у вас могут быть перекрывающиеся ключевые слова, но это не так уж и отличается.

Итак, с чисто теоретической точки зрения:

• Создание автомата из набора ключевых слов
• Сканирование основной части текста благодаря этому автомату

Последняя часть - O (n), первая может быть немного хитрее.