java - 将正则表达式与 Java 的 TreeSet 或 Collections.BinarySearch 结合使用

Question

我正在尝试创建一个匹配程序，当给定单词“C[A-Z]T”的一些正则表达式时，从单词列表中查找与该正则表达式匹配的所有单词。我的示例的匹配项是 CAT、CUT、COT。

我的目标是尽可能快地处理非常大的单词列表。我尝试过使用 Java 的 TreeSet 来实现，但是搜索需要很长时间，因为我必须迭代树中的每个单词。即使我在将列表放入树中之前对其进行随机化，搜索也太慢了。

所以我的问题是，我可以使用内部 Contains()，还是 Java 提供的其他数据结构可以与正则表达式一起使用？谢谢..

我正在考虑使用 AVL 或红黑“ HashMap ”(但不是真的)，以长度作为键，以单词作为值。这意味着我需要允许多个相同的键，但每个键映射到不同的值。所以我的 get 将返回一个值列表，而不是单个值。有没有地方可以找到这种数据结构的实现？或者至少是让我开始的基础..我真的不想自己动手。

这是我到目前为止的代码:

public class WordSearch {
    SortedSet<String> tree = new TreeSet<String>();
    List<String> list = new ArrayList<String>();

    public WordSearch(List<String> allWords) {
        // long seed = System.nanoTime();
        // Collections.shuffle(allWords, new Random(seed)); // randomize
        tree.addAll(allWords);
    }

    public List<String> solutions(String pattern, int max) {
        pattern = pattern.toLowerCase().toUpperCase();
        pattern = pattern.replace("*", "[A-Z]");
        Pattern find = Pattern.compile(pattern);
        int count = 0;
        ArrayList<String> result = new ArrayList<String>();
        Iterator<String> it = tree.iterator();
        while (count < max) {
            while (it.hasNext()) {
                String word = it.next().toLowerCase().toUpperCase();
                Matcher match = find.matcher(word);
                if (match.matches()) {
                    result.add(word);
                    count++;
                }
            }
            break;
        }
        return result;
    }
}

Answer 1

如果您事先知道您的正则表达式/模式，则可以构建类似布隆过滤器的东西，但这实际上与构建 Collections (如 matchesPattern0、matchesPattern1 等)没有什么不同，这基本上就是数据库索引的工作方式。您可能还只需要一个前缀树。

在您的情况下，数据结构唯一有帮助的方法是锚定正则表达式，即指定第一个或最后一个字符或字符范围。否则，无论如何，您都必须检查整个数据结构。基本上，^C[A-Z]T$ 案例非常具体，以至于没有人为此构建优化的数据结构。

如果您觉得自己很聪明并且迫切需要这个，那么最好的选择是一种将 Pattern 转换为“min”和“max”的方法，例如 CAT 和 D，然后使用 SortedSet.subSet，并对结果应用过滤器。但实际上，这种优化很少起作用。