Java中的快速有序列表匹配算法

Question

我有一个格式的规则列表

L1->(A，B，C)

L2->(D，E)，

L3->(F，G，A)，

L4->(C，A)

此列表包含约3万条此类规则。

我有一个形式为(X，Y，Z)的输入

这创建了一种方法

List <Rule> matchRules(input)

属于RuleMatcher 类

我从一个非常简单、清晰、天真的解决方案开始，为了把框架放下，让一些东西发挥作用。

public RuleMatcher(Collection<Rule> rules) {
this.rules = rules;
}
public Collection<Rule> matchRules(List<Token> input) {
List<Rule> matchingRules = new ArrayList<>();
for(Rule r: this.rules) {
if(r.matches(input)) {
matchingRules.add(r);
}
}
return matchingRules; 
}

其中matches是一个非常简单的函数，它检查长度是否相同，然后将每个令牌作为for循环进行检查。

这个matchRules函数被调用了数十亿次。

---

显然，这是一个非常糟糕的实现。根据我的探查器，至少有一半的执行时间花在了这个matches函数上。

我在想两种可能的解决方案：

A。某种Trie数据结构，包含可以匹配的规则链。

B。某种散列函数。每个符号都有一个唯一的标识符。不幸的是，大约有8000个独特的符号，所以这可能很困难。

C。根据右侧的大小和规则中的标记数量制作一个哈希图。不幸的是，大多数规则的大小都差不多，所以这可能根本不值得。

D。你们中的一个想出了一些很棒的解决方案。

我希望有人能阐明这个问题。

---

编辑：令牌只是一个具有唯一编号的对象。例如，"NN"是一个标记。"NN"的每个实例都完全相同。

匹配代码：

public boolean rhsMatches(List<Token> tokens) {
if(tokens.size()!=rhsSize()) return false;
for(int i = 0;i<rhsSize();i++) {
if(!rightSide.get(i).equals(tokens.get(i)) {
return false;
}
}
return true;
}

它不是很漂亮，但很简单。

Answer 1

为什么不先对规则列表进行排序。然后你可以二进制搜索匹配的规则。

Answer 2

对我来说，这似乎是一个吸引一些工作线程的完美场景。匹配的任务似乎是相互独立的，如果在您的情况下可能的话，划分规则列表并将匹配委托给员工。