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

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

我了解 Kaysian intersects 和 XPath 的 intersect 函数，但这些似乎是为了找到一对元素的 LCA：我事先不知道每个节点集中有多少项。

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

提前致谢， 汤姆

这是一种自下而上的方法:

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

A test:

<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

Update：我有我认为可能是最有效的算法。

这个想法是，节点集的 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