查找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]