Поиск самого низкого общего предка узла узла XML

Question

У меня есть набор узлов, построенный с использованием структуры xsl: key в XSLT. Я хотел бы найти самого низкого общего предка (LCA) всех узлов в этом наборе узлов - любые идеи?

Я знаю, что Kaysian пересекает и функцию пересечения XPath, но они, похоже, направлены на поиск LCA только пары элементов: я не знаю заранее, сколько элементов будет в каждом наборе узлов.

Мне было интересно, может ли быть решение, используя комбинацию выражений «каждый» и «пересекаться», но я еще не мог думать об одном!

Спасибо заранее, Том

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 

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 

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) [теория который я оставляю читателю, чтобы доказать ...].

Теперь LCA (x, y) можно найти достаточно эффективно, просмотрев последовательности x/ancestor-or-self :: node() и y/ancestor-or-self :: node(), усекая обе последовательности к длине короче, а затем найти последний узел, который в обоих: в 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]