indexing - 使用占位符快速查找树？

Question

对于我正在考虑的应用程序，将有一个大型(100,000+)树“数据库”(想想编程语言中的表达式，或 S 表达式)，并且我需要在该数据库中查询以下表达式:匹配特定的给定表达式。

在提供我想要的详细信息之前，请注意，我希望获得与索引一大组树以优化子树查找相关的任何信息。

在我的具体情况下(这将是 Metamath 证明助手使用的后端)，表达式具有以下结构(采用类似 Haskell 的表示法):

data Expression = Placeholder Id | VarName Id | ConstName Id [Expression]

或者作为 S 表达式形式的 BNF:

Expression = '?' Id | Id | '(' Id Expression* ')'

其中 Id 是某种标识符。

例如，我可以有一个包含如下表达式的数据库

(equiv ?ph ?ps)
(not (in (appl (sqrt) (2)) (Q)))
(equiv (eq ?A ?B) (forall ?x (equiv (in ?x ?A) (in ?x ?B))))

在此上下文中，如果可以通过用表达式替换占位符来使两个表达式相等，则它们匹配。因此，在上述迷你数据库中查找 (equiv (eq A (emptyset)) ?ph) 将得到第一个和最后一个表达式。

再说一遍:我如何在一大堆带有占位符的(表达式)树中实现快速查找？我可以使用什么样的索引数据结构？

Answer 1

我将使用 trie 来实现查找。每个 key 将包含以下内容之一:

• 常量名称标识符
• 带有上下文信息的变量
• 常量值
• 占位符

这些应该以某种方式排序 - 可能是占位符，然后是所有 ConstNames(字母顺序)，然​​后是变量(范围排序，然后是参数顺序)，然​​后是 ConstValues(数字顺序)。只要 trie 中有具体的使用顺序，就可以了。

遍历表达式的树，在遇到适当的键时将其注入(inject)到 trie 中。对要插入数据结构中的所有表达式执行此操作。当需要查询它时，您可以以类似的方式遍历 trie，但使用一些新规则。

• 一切都与占位符节点匹配。如果它也与其他某个键匹配，那么您将需要探索这两个分支(通过类似 DFS 的递归方法可以轻松完成)。
• 占位符可以匹配所有内容。这与上一点不同 - 我们在这里讨论查询中的占位符，上一个项目符号是将占位符视为 trie 键。

现在，这确实意味着当您遇到占位符时，搜索空间可能会有所“爆炸”，但您可以做一件事来尝试在实践中减轻这种情况。以广度优先的方式遍历表达式的树(在构造 trie 和查询中)。这意味着，如果其中一个参数是占位符，则您不必全面深度搜索与该表达式匹配的每个子树到目前为止 - 相反，您可以跳转到下一个参数 - 这可能不会是一个占位符，因此将大大减少搜索空间(与匹配“所有内容”相比)。

为了完整起见，让我们举一个例子

(not (in (appl (sqrt) (2)) (Q)))

并从中创建一个特里条目-

not -> in -> apply -> "Q" -> sqrt -> 2

添加 (不是(in ?ph E)) 到此将导致 -

not -> in -> apply -> "Q" -> sqrt -> 2
         \-> ?ph   -> "E"

继续以这种方式将表达式注入(inject)到 trie 中。同样以这种方式遍历进行查询，直到到达 trie 中搜索的末尾，然后返回匹配的内容。

注意 - 这些条目的唯一性基于您不必支持可变参数函数的假设。如果这样做，请为每个键附加一些上下文信息(阅读下一段以了解如何执行此操作的信息)以区分哪些参数进入哪些函数

我忽略了一个细节——变量。如果您只想在它们是完全相同的变量名时进行匹配，则无需进行任何工作。但这可能不是您想要的；您可能希望它匹配通用变量，只要它们彼此“一致”即可。执行此操作的方法是为每个变量分配一个标识符，该标识符表示首次定义该变量的范围。

最简单的方法就是根据其祖先的参数顺序的串联组成一个标识符。也就是说，如果一个变量首先被定义为函数的第二个参数，而该函数又是根函数的第五个参数，那么我们可以将其标记为 ( 5, 2) 或 (2, 5)，以更直观的方式为准。无论哪种方式，这都将确保为变量提供一致的标识符，而不管其他地方的其他变量/函数如何。然后使用这个新变量名称正常进行。