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

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

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

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

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

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

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

В целом,

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

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

   c. отбросить общие союзные слова

   d. удалить дубликаты

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

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

Я не на 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

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

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

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

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

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

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

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

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

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

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

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

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

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

Хорошо масштабируется ...

G