Реализация схемы сравнения ключевых слов (обратный поиск)

Question

У меня постоянно растет база данных ключевых слов. Мне нужно проанализировать входящие текстовые входы (статьи, каналы и т. Д.) И найти, какие ключевые слова из базы данных присутствуют в тексте. База данных ключевых слов намного больше, чем текст.

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

Самой наивной реализацией было бы создание простого запроса SELECT к таблице ключевых слов с гигантским предложением IN, в котором перечислены все найденные ключевые слова.

SELECT user_id,keyword FROM keywords WHERE keyword IN ('keyword1','keyword2',...,'keywordN');

Другим подходом было бы создать хеш-таблицу в памяти (используя что-то вроде memcache) и проверить ее таким же образом.

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

Answer 1

Классическим способом поиска текстового потока по нескольким ключевым словам является конечный автомат Aho-Corasick , который использует линейное время в искомом тексте. Вам потребуются небольшие изменения, чтобы распознавать строки только по границам слов, или, возможно, было бы проще просто проверить найденные ключевые слова и убедиться, что они не встроены в более крупные слова.

Вы можете найти реализацию в fgrep. Более того, Престон Бриггс (Preston Briggs) написал довольно неплохую реализацию на C, которая выполняет именно тот поиск по ключевым словам, о котором вы говорите. (Он ищет в программах случаи «интересных» идентификаторов.) Реализация Престона распространяется как часть инструмента грамотного программирования Noweb . Вы можете найти способ вызвать этот код из PHP или переписать его на PHP - само распознавание составляет около 220 строк C, а основная программа - еще 135 строк.

Все предложенные решения, , включая Aho-Corasick, имеют следующие общие свойства:

• Этап предварительной обработки, который занимает время и пространство, пропорциональные количеству ключевых слов в базе данных.

• Шаг поиска, который занимает время и пространство, пропорциональные длине текста плюс количество найденных ключевых слов.

Aho-Corasick предлагает значительно лучшие константы пропорциональности на этапе поиска, но если ваши тексты маленькие, это не будет иметь значения. На самом деле, если ваши тексты маленькие, а база данных большая, вы, вероятно, захотите минимизировать объем памяти, используемый на этапе предварительной обработки. Структура данных DAWG Эндрю Аппеля из самой быстрой в мире программы скрэбблинга , вероятно, сработает.

Answer 2

В общем

1. разбить текст на слова

   б. преобразовать слова обратно в каноническую корневую форму

   с. отбросить общеупотребительные слова

   д. дубликаты полосы

2. вставьте слова во временную таблицу, затем выполните внутреннее соединение с таблицей ключевых слов, или (как вы предложили) встроить ключевые слова в сложные критерии запроса

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

Answer 3

Я взломал некоторый код для сканирования нескольких ключевых слов с использованием dawg (как предложено выше со ссылкой на статью Scrabble), хотя я написал это из первых принципов и не знаю, является ли это чем-то вроде алгоритма AHO или нет. 1001 *

http://www.gtoal.com/wordgames/spell/multiscan.c.html

Мой друг сделал несколько хаков на мой код после того, как я впервые опубликовал его в списке рассылки программистов wordgame, и его версия, вероятно, более эффективна:

http://www.gtoal.com/wordgames/spell/multidawg.c.html

Весы довольно хорошие ...

G

Answer 4

Рассматривали ли вы переход к полнотекстовому решению, такому как Sphinx ?

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

Вот блог об использовании Sphinx в качестве решения для полнотекстового поиска в MySQL.

Answer 5

Я бы сделал 2 вещи здесь.

Во-первых (и это не имеет прямого отношения к вопросу), я бы разбил и разделил пользовательские ключевые слова по пользователям. Наличие большего количества таблиц с меньшим количеством данных, в идеале на разных серверах для распределенных поисков, где на разных срезах существуют срезы или диапазоны пользователей. Ака, все данные пользователя находятся на первом слое, userb на втором и т. Д.

Во-вторых, у меня есть какая-то хэш-таблица в памяти, чтобы определить наличие ключевых слов. Скорее всего, это будет федерация для распространения поиска. Для n серверов существования ключевых слов хэшируйте ключевое слово и изменяйте его по n, а затем распределяйте диапазоны этих ключей по всем серверам memcached. Этот быстрый способ позволяет вам сказать, что ключевое слово x отслеживается, хэшировать его и определять, на каком сервере оно будет жить. Затем выполните поиск и соберите / агрегируйте отслеживаемые ключевые слова.

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

Вкратце: SQL здесь не идеальное решение.

Answer 6

Я не на 100% ясно понимаю, о чем вы спрашиваете, но, возможно, вы ищете это инвертированный индекс ?

Обновление:

Вы можете использовать инвертированный индекс для сопоставления нескольких ключевых слов одновременно.

Разделите новый документ на токены и вставьте токены в паре с идентификатором документа в таблицу инвертированных индексов. (Довольно денормализованная) таблица перевернутых индексов:

inverted_index
-----
document_id keyword

Если вы ищете 3 ключевых слова вручную:

select document_id, count(*) from inverted_index
  where keyword in (keyword1, keyword2, keyword3)
  group by document_id 
  having count(*) = 3

Если у вас есть таблица ключевых слов, которые вас интересуют, просто используйте внутреннее объединение, а не операцию in ():

keyword_table
----
keyword othercols

select keyword_table.keyword, keyword_table.othercols from inverted_index 
   inner join keyword_table on keyword_table.keyword=inverted_index.keyword
   where inverted_index.document_id=id_of_some_new_document

что-нибудь из этого ближе к тому, что вы хотите?