Нахождение наименьшего общего предка набора узлов XML - PullRequest
Новая
       20

Нахождение наименьшего общего предка набора узлов XML

3 голосов
/ 05 января 2012

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

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

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

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

Ответы [ 3 ]

1 голос
/ 05 января 2012

Вот подход снизу вверх : 

 <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
1 голос
/ 05 января 2012

Я попробовал следующее: 

<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, но я не тестировал с более сложными настройками и несейчас не времяМожет быть, вы можете попробовать с вашими примерами данных и сообщить, получите ли вы результаты, которые вы хотите.

0 голосов
/ 05 января 2012

Решение Мартина будет работать, но я думаю, что в некоторых ситуациях оно может быть довольно дорогим, с большим количеством дубликатов.Я был бы склонен использовать подход, который находит 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]
...