algorithm - Tjfast 算法中的直接分支或叶节点 (dbl) 功能如何工作？

Question

我读了一个关于 Twig Pattern Matching 的算法作为 TJfast 算法。有一个 dbl(n) 函数，参数 n 是一个节点，这个函数返回直接分支或叶节点，但我不明白，文章的名称是“从区域编码到扩展杜威:关于 XML 的高效处理 Twig 模式匹配”有一个例子，但对我来说很模糊。基于文章中的定义:

dbl(v) (for direct branching or leaf node) returns the set of all branching nodes b and leaf nodes f in the twig rooted at v such that there is no branching nodes along the path from v to b or f, excluding v, b or f.

例子:

dbl(a)={b,c}
dbl(c)={f,g}

我不明白为什么 dbl(c)={f,g} ??

Answer 1

dbl (directBranchingOrLeafNodes) 只包含分支节点和叶节点。在这些节点中，它只包含那些在它们与根之间没有中间分支节点的节点。

很难找到分支节点的定义，但它似乎是一个具有多个子节点的节点。 d 和 e 不是分支节点，因为它们只有一个 child 。因此，它们不能成为 dbl(c) 的一部分。

那么，从c到f的路径没有分支节点，所以f在dbl(c)。同样，从 c 到 g 的路径没有分支节点，因此 g 在 dbl(c) 中。所以我们有:

dbl(c) = {f,g}

我猜他们可能使用 dbl 来表示子查询。