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函数被调用了数十亿次.

---

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

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

A.某种Trie数据结构,它包含可以匹配的规则链.

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

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

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