创建关键字过滤器的最快方法？

Question

我正在尝试基于关键字过滤器过滤推文。该过滤器可能包含10个单词或更多。因此，如果一条推文包含关键字，就会通过。我唯一能想到的就是将推文的文本拆分为令牌。然后，我将遍历过滤器单词，并将每个标记与过滤器中的每个单词进行比较。但是这种方式似乎很慢。假设关键字过滤器有N个关键字，令牌数为M，则其需求为O（N * M）。

有没有更好的方法？

Answer 1

这个问题有很多有趣的方面以及解决这个问题的方法。他们每个人都有权衡。

当人们继续使用HashMaps之类的O（1）时，他们仍然缺少可以完成的一些编译时优化。知道编译时的单词集后，您可以将其放入Enum，然后允许您使用较少为人所知的EnumMap（doc）和EnumSet（doc）。枚举为您提供了一种序数类型，然后使您可以一次调整后备数组或位域的大小，而不必担心对其进行扩展。同样，枚举的哈希值是其序数值，因此您没有复杂的哈希值查找（尤其是非中间字符串）。该EnumSet是怎样的一个类型安全的位域。

import java.util.EnumSet;

public class Main {
    public static void main(String[] args) {
        EnumSet<Words> s = EnumSet.noneOf(Words.class);

        for(String a : args) {
            s.clear();
            for(String w : a.split("\\s+")) {
                try {
                    s.add(Words.valueOf(w.toUpperCase()));
                } catch (IllegalArgumentException e) {
                    // nothing really
                }
            }
            System.out.print(a);
            if(s.size() == 4) { System.out.println(": All!"); }
            else { System.out.println(": Only " + s.size()); }
        }
    }

    enum Words {
        STACK,
        SOUP,
        EXCHANGE,
        OVERFLOW
    }
}

在命令行上使用一些示例字符串运行时：

“堆栈交换溢出汤foo”
“堆栈溢出”
“堆栈交换等等”

得到结果：

堆栈交换溢出汤foo：全部！
堆栈溢出：仅2
堆栈交换等等：仅2

您已将匹配的内容移至核心语言，希望它能得到优化。最终看起来像是它的样子Map<String,T>（并进一步挖掘了隐藏在Class类深处的HashMap）。

你有一个字符串。将其拆分为某种令牌是不可避免的。每个令牌都需要检查，看是否匹配。但是，将它们与所有令牌进行比较是很昂贵的。

但是，“完全匹配这些字符串”的语言是常规语言。这意味着我们可以使用正则表达式过滤掉不匹配的单词。正则表达式会O(n)及时运行（请参阅正则表达式的复杂性是什么？）。

这并不能消除，O(wordsInString * keyWords)因为那仍然是最坏的情况（这是O（）代表的意思），但这的确意味着对于不匹配的单词，您仅花费O(charsInWord)在消除它上。

package com.michaelt.so.keywords;

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

public class Main {
    final static Pattern pat = Pattern.compile("S(?:TACK|OUP)|EXCHANGE|OVERFLOW", Pattern.CASE_INSENSITIVE);
    public static void main(String[] args) {
        EnumSet<Words> s = EnumSet.noneOf(Words.class);
        Matcher m = pat.matcher("");
        for(String a : args) {
            s.clear();
            for(String w : a.split("\\s+")) {
                m.reset(w);
                if(m.matches()) {
                    try {
                        s.add(Words.valueOf(w.toUpperCase()));
                    } catch (IllegalArgumentException e) {
                        // nothing really
                    }
                } else {
                    System.out.println("No need to look at " + w);
                }
            }
            System.out.print(a);
            if(s.size() == 4) { System.out.println(": All!"); }
            else { System.out.println(": Only " + s.size()); }
            System.out.println();
        }
    }

    enum Words {
        STACK,
        SOUP,
        EXCHANGE,
        OVERFLOW
    }
}

这给出了以下输出：

不用看foo
堆栈交换溢出汤foo：全部！

堆栈溢出：仅2

不用看啦
堆栈交换等等：仅2

现在，大失望。尽管如此，Java计算字符串的哈希值并在Hash中查找以查看其是否存在仍然可能更快。

唯一会更好的方法是制作一个匹配所有字符串的正则表达式。如前所述，它是一种常规语言。

(?:stack\b.+?\bexchange\b.+?\bsoup\b.+?\boverflow)|(?:soup\b.+?\bexchange\b.+?\bstack\b.+?\boverflow) ...

上面的正则表达式将匹配字符串 stack exchange pea soup overflow

这里有四个字，就是四个！(s1)|(s2)|(s3)|...(s24) 用这种方法处理的带有10个关键字的正则表达式的部分将(s1)|...|(s3628800)被认为是非常不切实际的。尽管某些引擎可能使这么大的正则表达式窒息，但还是有可能的。尽管如此，它会将其修剪为O（n），其中n是您所拥有的字符串的长度。

还要注意，这是一个全过滤器，而不是任何过滤器或某个过滤器。

如果要匹配十分之一的关键字，则正则表达式只有十个组。如果要匹配十个关键字中的两个，则其长度只有90个组（位长，但是引擎可能不会阻塞）。此正则表达式可以以编程方式生成。

这将使您回到O（N）时间，其中N是推文的长度。无需拆分。