Самый быстрый способ отфильтровать строку на основе некоторых ключевых слов

Question

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

Список ключевых слов будет статичным где-то в файле или CSV.

Размер списка ключевых слов будет не более 100 слов(ни в коем случае я не буду использовать более 100 ключевых слов)

Входящая строка будет макс. 200 байт (UTF-8)

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

Ключевые слова могут быть регулярными выражениями или обычными словами.

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

Например, входящая строка может быть:

String example = "I want to gamble and drink vodka all day"

AСписок ключевых слов будет содержать:

DRUGS
VODKA.?
GAMBLE

Пример строки должен быть отфильтрован, поскольку он содержит как минимум 1 слово из списка ключевых слов

EDIT *

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

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

В некоторых случаях это не будет работать.Например, кто-то может ввести «Я люблю играть и пить водку весь день».Это не будет совпадать.

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

Answer 1

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

Multi-струнной-Search

Поиск нескольких строк (игл) обрабатывает ввод (стог сена) char-by-char и пропускает разделы, которые никогда не будут совпадать ни с одним из указанных слов. Он не ограничивается границами слов и часто выполняет суперлинейные зависимости от длины стога сена.

Наиболее популярным алгоритмом является Aho-Corasick, вы можете найти пару хорошо протестированных алгоритмов в stringsearchalgorithms

DFA-Regular-Expression-Search

Поиск с помощью регулярных выражений DFA (детерминированный конечный автомат) - двигатель обрабатывает ввод (стог сена) char-by-char и обновляет автомат двигателей, он никогда не пропускает секции и поэтому никогда не может работать с менее чем линейным временем выполнения.

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

Вы можете найти регулярные выражения в patternsearchalgorithms , или brics

Answer 2

Одним из решений (конечно, не самым быстрым, но, может быть, достаточно хорошим) будет обработка каждой записи в списке как регулярного выражения и объединение всех регулярных выражений с помощью |, чтобы просто выполнить один find() для matcher.

Pattern pattern = Pattern.compile("DRUGS|VODKA.?|GAMBLE");
Matcher matcher = pattern.matcher(input);
boolean result = matcher.find();

Answer 3

Попробуйте регулярное выражение для точного соответствия слов:

import java.util.Set;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class SoRegex {
    // The static set of keywords.
    static final Set<String> keywords = Set.of("DRUGS", "VODKA", "GABMBLE");

    public static void main(String[] args) {
        // Construct a regular expression that matches any of the keywords anywhere. Use
        // word boundaries '\b'.
        StringBuilder sb = new StringBuilder("^.*(\\b").append(String.join("\\b|\\b", keywords)).append("\\b).*$");
        Pattern p = Pattern.compile(sb.toString());

        String input = "I want to gamble and drink vodka all day";

        // Convert the input to uppercase since the keywords are uppercase.
        Matcher matcher = p.matcher(input.toUpperCase());
        System.out
                .println(String.format("input '%s' matches pattern '%s': %b", input, p.toString(), matcher.matches()));
    }

}

Выход:

input 'I want to gamble and drink vodka all day' matches pattern '^.*(\bGABMBLE\b|\bDRUGS\b|\bVODKA\b).*$': true

Другие типы ключевых слов оставлены читателю в качестве упражнения.