查找 XML 节点集的最低公共祖先 [英] Finding the lowest common ancestor of an XML node-set
问题描述
我有一个使用 XSLT 中的 xsl:key 结构构造的节点集.我想找到这个节点集中所有节点的最低共同祖先 (LCA) - 有什么想法吗?
I have a node set constructed using the xsl:key structure in XSLT. I would like to find the lowest common ancestor (LCA) of all of the nodes in this node-set - any ideas?
我知道 Kaysian intersects 和 XPath 的 intersect 函数，但这些似乎只是为了找到一对元素的 LCA:我事先不知道每个节点集中有多少项.
I know about Kaysian intersects and XPath's intersect function, but these seem to be geared towards finding the LCA of just a pair of elements: I don't know in advance how many items will be in each node-set.
我想知道是否有组合使用every"和intersect"表达式的解决方案，但我还没有想到一个！
I was wondering if there might be a solution using a combination of the 'every' and 'intersect' expressions, but I haven't been able to think of one yet!
提前致谢，汤姆
推荐答案
这是自下而上的方法:
<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
更新:我认为可能是最有效的算法.
Update: I have what I think is probably the most efficient algorithm.
这个想法是一个节点集的 LCA 与这个节点集的两个节点的 LCA 相同:最左边"和最右边"的节点.证明这是正确的，留给读者作为练习:)
The idea is that the LCA of a node-set is the same as the LCA of just two nodes of this node-set: the "leftmost" and the "rightmost" ones. The proof that this is correct is left as an exercise for the reader :)
这是一个完整的 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
这篇关于查找 XML 节点集的最低公共祖先的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
