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

Question

我在表单中有一个规则列表

L1 -> (A, B, C)

L2 -> (D, E),

L3 -> (F, G, A),

L4 -> (C, A)

.....

此列表包含约 30k 条此类规则。

我有一个形式为 (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 函数被调用了数十亿次。

---

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

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

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

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

C.根据右侧的大小(规则中的标记数)制作 HashMap 。不幸的是，大多数规则的大小都差不多，所以这甚至可能不值得。

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

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

---

编辑: token 只是一个具有唯一编号的对象。例如“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

为什么不首先对规则列表进行排序。然后就可以二分查找匹配规则了。