Как искать тысячи возможных ключевых слов в строке

Question

У меня есть база данных из тысяч (около 10 000) ключевых слов. Когда пользователь публикует блог на моем сайте, я хотел бы автоматически выполнять поиск по ключевым словам в тексте и отмечать в нем любые прямые совпадения.

Пока что все, о чем я могу думать, это вытащить ВЕСЬ список ключевых слов, пройтись по нему и проверить наличие каждого тега в записи ... что кажется очень неэффективным (это 10000 циклов). *

Есть ли более распространенный способ сделать это? Должен ли я использовать запрос MySQL, чтобы ограничить его?

Полагаю, это не совсем редкая задача.

Answer 1

Нет, просто не делайте этого.

Вместо циклического перебора 10000 элементов, лучше извлечь слова из предложения или текста, а затем добавить их в запрос SQL, и таким образом вы будетеесть все необходимые записи.Это, безусловно, более эффективно, чем предложенное вами решение.

Вы можете сделать это следующим образом, используя PHP:

$possible_keywords = preg_split('/\b/', $your_text, PREG_SPLIT_NO_EMPTY);

Выше разделит текст на границы слов и будетне возвращайте пустых элементов в массиве.

Тогда вы можете просто создать запрос SQL способом, подобным следующему:

SELECT * FROM `keywords` WHERE `keywords`.`keyword` IN (...)

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

Вероятно, вам следует отфильтровать массив $possible_keywords перед выполнением запроса (чтобы включить только ключевые слова с соответствующей длиной и исключить дубликаты) плюс сделать индексированный столбец keyword.

Answer 2

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

class KeywordTagger {
  static function getTags($body) {
    if(preg_match_all(self::getRegex(), $body, $keywords)) {
      return $keywords[0];
    } else {
      return null;
    }
  }

  private static $regex;
  private static function getRegex() {
    if(self::$regex === null) {
      // Load Keywords from DB here
      $keywords = KeywordsTable::getAllKeywords();

      // Let's escape
      $keywords = array_map('KeywordTagger::pregQuoteWords', $keywords);

      // Base Regex
      $regex = '/\b(?:%s)\b/ui';

      // Build Final
      self::$regex = sprintf($regex, implode('|', $keywords));
    }

    return self::$regex;
  }

  private static function pregQuoteWords($word) {
    return preg_quote($word, '/');
  }
}

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

$tags = KeywordTagger::getTags($_POST['messageBody']);

Для небольшого ускорения вы можете кэшировать встроенное регулярное выражение, используя memcached, APC или старый добрый файловый кеш.

Answer 3

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

Answer 4

Ну, я думаю, что PHP-стрипы уже довольно оптимизированы. Если вы хотите еще больше оптимизировать этот поиск, вам нужно воспользоваться сходством между вашими ключевыми словами (например, вместо поиска «foobar», а затем «foobaz», ищите «fooba», а затем проверяйте каждый «fooba», если за ним следует «r», «z» или нет). Но для этого потребуется какое-то древовидное представление ваших ключевых слов, например:

root (пустая строка)

 |

fooba

/  \

foobar foobaz

Да, это обман.