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

---

显然，这是一种非常糟糕的实现。根据我的分析工具，至少有一半的执行时间都花费在了这个matches函数上。

我考虑了两种可能的解决方案：

A. 一些Trie数据结构来存储可以匹配的规则链。

B. 一些哈希函数。每个符号都被赋予一个唯一的标识符。不幸的是，有大约8千个独特的符号，所以这可能很困难。

C. 基于右侧大小和规则中标记数量的哈希表。不幸的是，大多数规则的大小都差不多，所以这可能不值得。

D. 你们中有人提出的某些神奇的解决方案。

希望有人能够解决这个问题。

---

编辑：标记只是带有唯一编号的对象。例如，“NN”是一个标记。每个“NN”的实例都完全相同。

matches代码：

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

它并不十分漂亮，但很简单。

- user498001

---

你能给我们提供令牌的定义吗？如果不知道正在匹配什么以及匹配是如何进行的，那么提出优化建议将会很困难。 - Leonard Brünings

那么你有30,000个规则（L1，L2，...），包含8,000个唯一标记的集合（A，B，...）是吗？您是否考虑创建一个“反向查找表”（无法记住实际名称），其中索引标记所在的规则？ 这可能需要大量内存，但速度应该会大大提高。 - Uxonith

我认为你的TrieSet的想法是你最好的第一选择。本质上，你需要构建一个语法。 - OldCurmudgeon

最基本的优化方法是通过预先对规则进行排序来跳过长度检查，这样你就可以为每个长度创建一个不同的规则列表。 - Leonard Brünings

我认为如果你在Token类上覆盖hashCode和equals方法，HashMap<List<Token>, Rule>应该可以工作。当涉及到内存使用时，Trie会更有效率。 - Sami Korhonen

Answer 1

为什么不先对规则列表进行排序，然后你就可以使用二分查找来寻找匹配的规则。

- ElKamina

---

这需要 Rule 实现 Comparable。对我来说，这似乎是最简单和最快速的解决方案。根据向列表中添加项的频率，该列表应该是一个 SortedMap 或 SortedTree。 - Uxonith

Answer 2

在编程方面，这似乎是使用一些工作线程进行操作的完美场景。 匹配任务似乎彼此独立，将规则列表分成几个部分，并将匹配委托给工作线程，如果在您的情况下可行。

- janek