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

Question

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

有没有更好的方法？

Answer 1

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

---

当人们继续讨论 HashMap 和 O(1) 时，他们仍然缺少一些可以完成的编译时优化。了解编译时的单词集将使您能够将其放入 Enum 中，然后您可以使用鲜为人知的 EnumMap ( doc ) 和 枚举集 ( 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
    }
}

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

"stack exchange overflow soup foo""stack overflow""stack exchange blah"

One gets the results:

stack exchange overflow soup foo: All!stack overflow: Only 2stack exchange blah: Only 2

You've moved the what one matches to the core language, hoping its well optimized. Turns out this look like its ultimately just a Map<String,T> (and digging even further its a HashMap hidden deep within the Class class.).

---

You've got a String. Splitting it into tokens of some sort is unavoidable. Each token needs to be examined to see if it matches. But comparing them against all the tokens is as you've noted expensive.

However, the language of "matches exactly these strings" is a regular one. This means we can use a regular expression to filter out the words that are not going to match. The regular expression runs in O(n) time (see What is the complexity of regular expression? ).

This doesn't get rid of O(wordsInString * keyWords) because that still is the worst case (which is what O() represents), but it does mean that for unmatched words you've only spent O(charsInWord) on eliminating it.

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
    }
}

这给出了输出:

No need to look at foostack exchange overflow soup foo: All!stack overflow: Only 2No need to look at blahstack exchange blah: Only 2

---

现在，大失望了。尽管如此，对于 Java 来说，计算字符串的散列并在散列中查找它是否存在可能仍然更快。

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

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

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

这里有四个字，就是4! (s1)|(s2)|(s3)|...(s24) 的部分 以这种方式处理的具有 10 个关键字的正则表达式将是 (s1)|...|(s3628800 ) 这可能被认为是非常不切实际的。尽管某些引擎可能会在如此大的正则表达式上窒息，但这是可能的。尽管如此，它仍会将其缩减为 O(n)，其中 n 是您所获得的字符串的长度。

请进一步注意，这是一个所有 过滤器，而不是一个任何 过滤器或一个一些 过滤器。

如果要匹配十个关键字中的一个，那么正则表达式只有十组长。如果你想匹配十个关键字中的 两个，那么它只有 90 个组长(有点长，但引擎可能不会阻塞它)。此正则表达式可以以编程方式生成。

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