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 来做到这一点？希望得到一些帮助。提前致谢。罢工

4

2 回答 2

3

这个问题的一些答案很好但效率很低（O（N ^ 2））。

之所以如此，是因为每个Positionen元素的路径都是从头开始构建的。平均路径长度为 N/2，有 N 个Positionen元素。这意味着构建所有路径至少需要 N*N/2 次操作——这是二次时间复杂度。

这是一个更有效的 O(N*log(N)) - 可以是偶数 (O(N) - 线性) 解决方案，以防Positionen输出中的元素未排序是可以接受的：

<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路径添加到父路径（仅计算一次）产生的——一个 O(1) 操作。总共有 N 条路径，这是 O(N)。

最后的排序使得时间复杂度 O(N*log(N)) - 仍然比二次的好得多。

于 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 回答