建立一個「路徑」用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>