Как работает прямое ветвление или листовые узлы (dbl) в алгоритме Tjfast?

Question

Я прочитал алгоритм соответствия шаблонов Twig как алгоритм TJfast. есть функция как dbl(n), параметр n является узлом, и эта функция возвращает прямые ветвящиеся или конечные узлы, но я не могу понять, что название статьи "От кодирования области до расширенного dewey: об эффективной обработке XML соответствие шаблону ветки "есть пример, но для меня это неопределенно. Основываясь на определении в статье:

dbl (v) (для прямого ветвления или конечного узла) возвращает набор всех ветвящихся узлов b и конечных узлов f в ветке, укорененной в v, так что нет ветвящихся узлов вдоль пути от v до b или f, исключая v, б или ф.

пример:

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

Я не могу понять, почему dbl(c)={f,g}??

Answer 1

dbl(a) = {b,c}, потому что b является листовым узлом, а c является ветвящимся узлом, и оба они являются потомками a. Кроме того, обратите внимание, что нет другого ветвящегося узла или конечного узла, которые являются потомками a и предком b(или c).

dbl (c) = {f, g}, потому что f и g - листовые узлы, и оба они являются потомками c. Кроме того, обратите внимание, что нет другого ветвящегося узла или листового узла, который является потомком c и предком f(g).

Answer 2

dbl (directBranchingOrLeafNodes) содержит только ветвящиеся узлы и конечные узлы. Среди этих узлов он содержит только те, в которых нет промежуточных ветвящихся узлов между ними и корнем.

На удивление трудно найти определение для ветвящегося узла, но, похоже, это узел, имеющий более одного дочернего элемента. d а также e не являются ветвящимися узлами, потому что у них есть только один дочерний элемент. Поэтому они не могут быть частью dbl(c),

Затем путь от c в f не имеет ветвящихся узлов, поэтому f в dbl(c), Точно так же путь от c в g не имеет ветвящихся узлов, поэтому g в dbl(c), Итак, мы имеем:

dbl(c) = {f,g}

Я предполагаю, что они, вероятно, используют dbl представлять подзапросы.