1

私は問題を抱えており、現時点ではそれを解決する考えがありません;-(

入力ドキュメント (xml) としてカテゴリ構造があり、パス構造を構築したいと考えています。私は xslt しか使用できず、新しい xml 構造を生成したいと考えています。

入力構造は次のようになります。

<?xml version="1.0" encoding="UTF-8"?>
<Positions>
    <Positionen>
        <ID>1</ID>
        <Parent></Parent>
    </Positionen>

    <Positionen>
        <ID>2</ID>
        <Parent>1</Parent>
    </Positionen>

    <Positionen>
        <ID>3</ID>
        <Parent>1</Parent>
    </Positionen>

    <Positionen>
        <ID>4</ID>
        <Parent>2</Parent>
    </Positionen>

    <Positionen>
        <ID>5</ID>
        <Parent>4</Parent>
    </Positionen>

    <Positionen>
        <ID>6</ID>
        <Parent>2</Parent>
    </Positionen>

</Positions>

出力構造は次のようになります。

<?xml version="1.0" encoding="UTF-8"?>
<Positions>
    <Positionen>
        <ID>1</ID>
        <Parent></Parent>
        <Path>1</Path>
    </Positionen>

    <Positionen>
        <ID>2</ID>
        <Parent>1</Parent>
        <Path>1/2</Path>
    </Positionen>

    <Positionen>
        <ID>3</ID>
        <Parent>1</Parent>
        <Path>1/3</Path>
    </Positionen>

    <Positionen>
        <ID>4</ID>
        <Parent>2</Parent>
        <Path>1/2/4</Path>
    </Positionen>

    <Positionen>
        <ID>5</ID>
        <Parent>4</Parent>
        <Path>1/2/4/5</Path>
    </Positionen>

    <Positionen>
        <ID>6</ID>
        <Parent>2</Parent>
        <Path>1/2/6</Path>
    </Positionen>

</Positions>

再帰を使用してxsltでこれを行うにはどうすればよいですか? いくつかの助けを期待しています。前もって感謝します。Lストライク

4

2 に答える 2

3

この質問に対するいくつかの回答は適切ですが、かなり非効率的です (O(N^2))。

Positionenこれは、すべての要素に対してパスが最初から構築されているためです。平均パス長は N/2 で、N 個Positionenの要素があります。つまり、すべてのパスを構築するには、最低でも N*N/2 の操作が必要です。これは 2 次時間計算量です。

Positionenこれは、より効率的な O(N*log(N)) です。出力内の要素がソートされていないことが許容される場合は、偶数 (O(N) -- 線形) のソリューションになる可能性があります。

<xsl:stylesheet version="1.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
 xmlns:ext="http://exslt.org/common" exclude-result-prefixes="ext">
 <xsl:output omit-xml-declaration="yes" indent="yes"/>
 <xsl:strip-space elements="*"/>

 <xsl:key name="kChildren" match="Positionen" use="Parent"/>

 <xsl:template match="node()|@*">
     <xsl:copy>
       <xsl:apply-templates select="node()|@*"/>
     </xsl:copy>
 </xsl:template>

 <xsl:template match="/">
  <xsl:variable name="vrtfPass1">
    <xsl:apply-templates select="node()|@*"/>
  </xsl:variable>

  <xsl:variable name="vPass1" select="ext:node-set($vrtfPass1)"/>

  <xsl:apply-templates select="$vPass1/*" mode="pass2"/>
 </xsl:template>

 <xsl:template match="/*">
  <xsl:copy>
    <xsl:apply-templates select="Positionen[not(number(Parent))]" mode="path"/>
  </xsl:copy>
 </xsl:template>

 <xsl:template match="Positionen" mode="path">
  <xsl:param name="pPath"/>

  <xsl:copy>
    <xsl:apply-templates select="node()|@*"/>
    <Path><xsl:value-of select="concat($pPath, ID)"/></Path>
  </xsl:copy>
  <xsl:apply-templates select="key('kChildren', ID)" mode="path">
   <xsl:with-param name="pPath" select="concat($pPath, ID, '/')"/>
  </xsl:apply-templates>
 </xsl:template>

 <xsl:template match="/*" mode="pass2">
  <xsl:copy>
       <xsl:apply-templates select="node()|@*">
         <xsl:sort select="ID" data-type="number"/>
       </xsl:apply-templates>
  </xsl:copy>
 </xsl:template>
</xsl:stylesheet>

この変換が提供された XML ドキュメントに適用される場合:

<Positions>
    <Positionen>
        <ID>1</ID>
        <Parent></Parent>
    </Positionen>
    <Positionen>
        <ID>2</ID>
        <Parent>1</Parent>
    </Positionen>
    <Positionen>
        <ID>3</ID>
        <Parent>1</Parent>
    </Positionen>
    <Positionen>
        <ID>4</ID>
        <Parent>2</Parent>
    </Positionen>
    <Positionen>
        <ID>5</ID>
        <Parent>4</Parent>
    </Positionen>
    <Positionen>
        <ID>6</ID>
        <Parent>2</Parent>
    </Positionen>
</Positions>

必要な正しい結果が生成されます。

<Positions>
   <Positionen>
      <ID>1</ID>
      <Parent/>
      <Path>1</Path>
   </Positionen>
   <Positionen>
      <ID>2</ID>
      <Parent>1</Parent>
      <Path>1/2</Path>
   </Positionen>
   <Positionen>
      <ID>3</ID>
      <Parent>1</Parent>
      <Path>1/3</Path>
   </Positionen>
   <Positionen>
      <ID>4</ID>
      <Parent>2</Parent>
      <Path>1/2/4</Path>
   </Positionen>
   <Positionen>
      <ID>5</ID>
      <Parent>4</Parent>
      <Path>1/2/4/5</Path>
   </Positionen>
   <Positionen>
      <ID>6</ID>
      <Parent>2</Parent>
      <Path>1/2/6</Path>
   </Positionen>
</Positions>

注:

すべてのパスは、現在IDのパスを親のパスに追加することによって生成されます (これは 1 回だけ計算されます) -- O(1) 操作です。N パスの合計は O(N) です。

最終的な並べ替えにより、時間の複雑さが O(N*log(N)) になります。これは、2 次よりもはるかに優れています。

于 2012-04-12T12:26:26.403 に答える
2

このXSLTを試してください

<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
   <xsl:output method="xml" indent="yes"/>

   <xsl:key name="Pos" match="Positionen" use="ID" />

   <!-- Match Positionen elements normally -->
   <xsl:template match="Positionen">
      <xsl:copy>
         <xsl:apply-templates select="@*|node()"/>
         <Path>
            <!-- Get parent path -->
            <xsl:apply-templates select="key('Pos', Parent)" mode="parent" />
            <!-- End of path -->
            <xsl:value-of select="ID" />
         </Path>
      </xsl:copy>
   </xsl:template>

   <!-- Template used to recursively match parents -->
   <xsl:template match="Positionen" mode="parent">
      <xsl:apply-templates select="key('Pos', Parent)" mode="parent" />
      <xsl:value-of select="concat(ID, '/')" />
   </xsl:template>

   <xsl:template match="@*|node()">
      <xsl:copy>
         <xsl:apply-templates select="@*|node()"/>
      </xsl:copy>
   </xsl:template>
</xsl:stylesheet>

これは、Positionen要素を通常どおり照合することから始まり、 Parent値に基づいて親要素を再帰的に照合します。また、 xsl:keyを使用して、 IDで要素をより迅速に検索することに注意してください。

サンプル XML に適用すると、次のように出力されます。

<Positions>
   <Positionen>
      <ID>1</ID>
      <Parent/>
      <Path>1</Path>
   </Positionen>
   <Positionen>
      <ID>2</ID>
      <Parent>1</Parent>
      <Path>1/2</Path>
   </Positionen>
   <Positionen>
      <ID>3</ID>
      <Parent>1</Parent>
      <Path>1/3</Path>
   </Positionen>
   <Positionen>
      <ID>4</ID>
      <Parent>2</Parent>
      <Path>1/2/4</Path>
   </Positionen>
   <Positionen>
      <ID>5</ID>
      <Parent>4</Parent>
      <Path>1/2/4/5</Path>
   </Positionen>
   <Positionen>
      <ID>6</ID>
      <Parent>2</Parent>
      <Path>1/2/6</Path>
   </Positionen>
</Positions>
于 2012-04-12T11:19:24.430 に答える