查找XML节点集的最低公共祖先

Question

我有一个使用XSLT中的xsl：key结构构造的节点集。我想找到这个节点集中所有节点的最低共同祖先（LCA） - 有什么想法？

我知道Kaysian相交和XPath的相交函数，但是这些似乎适合寻找只有一对元素的LCA：我不知道每个节点集中有多少项目。

我想知道是否有可能使用'every'和'intersect'表达式组合的解决方案，但我还没有想到一个！

由于提前， 汤姆

Answer 1

这里是一个底向上的方法：

<xsl:function name="my:lca" as="node()?"> 
    <xsl:param name="pSet" as="node()*"/> 

    <xsl:sequence select= 
    "if(not($pSet)) 
     then() 
     else 
     if(not($pSet[2])) 
     then $pSet[1] 
     else 
      if($pSet intersect $pSet/ancestor::node()) 
      then 
       my:lca($pSet[not($pSet intersect ancestor::node())]) 
      else 
       my:lca($pSet/..) 
    "/> 
</xsl:function> 

测试：

<xsl:stylesheet version="2.0" 
    xmlns:xsl="http://www.w3.org/1999/XSL/Transform" 
    xmlns:my="my:my"> 
    <xsl:output omit-xml-declaration="yes" indent="yes"/> 

    <xsl:variable name="vSet1" select= 
     "//*[self::A.1.1 or self::A.2.1]"/> 

    <xsl:variable name="vSet2" select= 
     "//*[self::B.2.2.1 or self::B.1]"/> 

    <xsl:variable name="vSet3" select= 
     "$vSet1 | //B.2.2.2"/> 

<xsl:template match="/"> 
<!----> 
    <xsl:sequence select="my:lca($vSet1)/name()"/> 
    ========= 

    <xsl:sequence select="my:lca($vSet2)/name()"/> 
    ========= 

    <xsl:sequence select="my:lca($vSet3)/name()"/> 

</xsl:template> 

<xsl:function name="my:lca" as="node()?"> 
    <xsl:param name="pSet" as="node()*"/> 

    <xsl:sequence select= 
    "if(not($pSet)) 
     then() 
     else 
     if(not($pSet[2])) 
     then $pSet[1] 
     else 
      if($pSet intersect $pSet/ancestor::node()) 
      then 
       my:lca($pSet[not($pSet intersect ancestor::node())]) 
      else 
       my:lca($pSet/..) 
    "/> 
</xsl:function> 
</xsl:stylesheet> 

当在下面的XML文档施加这种转变：

<t> 
    <A> 
     <A.1> 
      <A.1.1/> 
      <A.1.2/> 
     </A.1> 
     <A.2> 
      <A.2.1/> 
     </A.2> 
     <A.3/> 
    </A> 
    <B> 
     <B.1/> 
     <B.2> 
      <B.2.1/> 
      <B.2.2> 
       <B.2.2.1/> 
       <B.2.2.2/> 
      </B.2.2> 
     </B.2> 
    </B> 
</t> 

的希望，正确的结果产生了三种情况下：

 A 
    ========= 

    B 
    ========= 

    t 

更新：我有什么，我认为可能是最有效的算法。

这个想法是，一个节点集的LCA和这个节点集的两个节点的LCA相同：“最左边”和“最右边”的那个。证明这是正确的就留给读者做练习:)

下面是一个完整的XSLT 2.0实现：

<xsl:stylesheet version="2.0" 
     xmlns:xsl="http://www.w3.org/1999/XSL/Transform" 
     xmlns:my="my:my"> 
     <xsl:output omit-xml-declaration="yes" indent="yes"/> 

     <xsl:variable name="vSet1" select= 
      "//*[self::A.1.1 or self::A.2.1]"/> 

     <xsl:variable name="vSet2" select= 
      "//*[self::B.2.2.1 or self::B.1]"/> 

     <xsl:variable name="vSet3" select= 
      "$vSet1 | //B.2.2.2"/> 

    <xsl:template match="/"> 
     <xsl:sequence select="my:lca($vSet1)/name()"/> 
     ========= 

     <xsl:sequence select="my:lca($vSet2)/name()"/> 
     ========= 

     <xsl:sequence select="my:lca($vSet3)/name()"/> 

    </xsl:template> 

    <xsl:function name="my:lca" as="node()?"> 
     <xsl:param name="pSet" as="node()*"/> 

     <xsl:sequence select= 
     "if(not($pSet)) 
      then() 
      else 
      if(not($pSet[2])) 
      then $pSet[1] 
      else 
       for $n1 in $pSet[1], 
        $n2 in $pSet[last()] 
       return my:lca2nodes($n1, $n2) 
     "/> 
    </xsl:function> 

    <xsl:function name="my:lca2nodes" as="node()?"> 
     <xsl:param name="pN1" as="node()"/> 
     <xsl:param name="pN2" as="node()"/> 

     <xsl:variable name="n1" select= 
     "($pN1 | $pN2) 
        [count(ancestor-or-self::node()) 
        eq 
        min(($pN1 | $pN2)/count(ancestor-or-self::node())) 
        ] 
        [1]"/> 

     <xsl:variable name="n2" select="($pN1 | $pN2) except $n1"/> 

     <xsl:sequence select= 
     "$n1/ancestor-or-self::node() 
       [exists(. intersect $n2/ancestor-or-self::node())] 
        [1]"/> 
    </xsl:function> 
</xsl:stylesheet> 

当在同一个XML文档进行这种转变（以上），同样正确的结果产生，但要快得多 - 特别是如果节点集的规模是大：

A 
========= 

B 
========= 

t 

Answer 2

我试过如下：

<xsl:stylesheet 
    xmlns:xsl="http://www.w3.org/1999/XSL/Transform" 
    xmlns:xs="http://www.w3.org/2001/XMLSchema" 
    xmlns:mf="http://example.com/mf" 
    exclude-result-prefixes="xs mf" 
    version="2.0"> 

    <xsl:output method="html" indent="yes"/> 

    <xsl:function name="mf:lca" as="node()?"> 
    <xsl:param name="nodes" as="node()*"/> 
    <xsl:variable name="all-ancestors" select="$nodes/ancestor::node()"/> 
    <xsl:sequence 
     select="$all-ancestors[every $n in $nodes satisfies exists($n/ancestor::node() intersect .)][last()]"/> 
    </xsl:function> 

    <xsl:template match="/"> 
    <xsl:sequence select="mf:lca(//foo)"/> 
    </xsl:template> 

</xsl:stylesheet> 

与样品

<root> 
    <anc1> 
    <anc2> 
     <foo/> 
     <bar> 
     <foo/> 
     </bar> 
     <bar> 
     <baz> 
      <foo/> 
     </baz> 
     </bar> 
    </anc2> 
    </anc1> 
</root> 

我得到的anc2元素，但我还没有更多的测试，测试复杂的设置，现在没有时间了。也许你可以尝试使用你的样本数据，并报告你是否得到你想要的结果。

Answer 3

马丁的解决方案将工作，但我认为在某些情况下，这可能会非常昂贵，并且会消除重复。我倾向于用一种方法找到两个节点的LCA，然后递归地使用LCA（x，y，z）= LCA（LCA（x，y），z）理论[理论我让读者证明......]。

现在通过查看序列x/ancestor-or-self :: node（）和y/ancestor-or-self :: node（），可以非常有效地找到LCA（x，y）以较短的长度，然后找到最后一个节点是在两个：XQuery中的符号：

(let $ax := $x/ancestor-or-self::node() 
    let $ay := $y/ancestor-or-self::node() 
    let $len := min((count($ax), count($ay)) 
    for $i in reverse($len to 1) 
    where $ax[$i] is $ay[$i] 
    return $ax[$i] 
)[1]