建立一个“路径”用XSLT递归

Question

我有一个问题的此刻不知道去解决它;-(

我有一个类别结构，输入文档（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执行递归？ 希望得到一些帮助。提前致谢。 LStrike

Answer 1

一些这个问题的答案是好的，但相当低效（O（N^2））。

这是如此，因为路径是从零开始为每个Positionen元素构建的。平均路径长度为N/2，并且有N Positionen个元素。这意味着需要N * N/2个操作作为构建所有路径的最小操作 - 这是二次方时间复杂度。

下面是一个更有效的O（N *日志（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）） - 仍然比二次方更好。

Answer 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元素，然后递归地基于所述父值的父元素相匹配。请注意，它还使用xsl：键来查找元素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>