[XSLT] Transformer une structure sequentiel en structure recursive

**lescarphe** · 27/11/2009, 08h37

Bonjour,

Mon problème est le suivant :

A partir d'une structure XML sous la forme de balises consécutives, je souhaite obtenir par suite d'une transformation XSLT une structure arborescente de ces balises ; par exemple :

source

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
...
  <balise name="A" />
  <balise name="AB" />
  <balise name="ABB" />
  <balise name="B" />
  <balise name="BC" />
  <balise name="BD" />
...

resultat

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
...
  <ul>
    <li name="A">
      <ul>
        <li name="AB">
          <ul>
            <li name="ABB" />
          </ul>
        </li>
      </ul>
    </li>
    <li name="B">
      <ul>
        <li name="BC" />
        <li name="BD" />
      </ul>
     </li>
  </ul>
...

malgré tous mes efforts, je n'arrive pas à trouver de solutions satisfaisantes...

Est-ce possible sans plomber les performances de l'interpreteur XSLT ?

**GrandFather** · 27/11/2009, 09h33

Bonjour,

si ta source XML se présente effectivement triée de cette manière, ceci devrait faire l'affaire :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
  <xsl:output method="xml" version="1.0" encoding="UTF-8" indent="yes"/>
  <xsl:template match="/root">
    <xsl:copy>
      <ul>
        <xsl:apply-templates select="balise[string-length(@name) = 1]"/>
      </ul>
    </xsl:copy>
  </xsl:template>
  <xsl:template match="balise">
    <li>
      <xsl:copy-of select="@name"/>
      <xsl:if test="following-sibling::balise[starts-with(@name, current()/@name) and string-length(@name) = string-length(current()/@name) + 1]">
        <ul>
          <xsl:apply-templates select="following-sibling::balise[starts-with(@name, current()/@name)  and string-length(@name) = string-length(current()/@name) + 1]"/>
        </ul>
      </xsl:if>
    </li>
  </xsl:template>
</xsl:stylesheet>

**lescarphe** · 27/11/2009, 09h57

Merci pour cette réponse rapide, que je vais m'empresser de tester...

Je peux me débrouiller pour que la liste soit triée ; j'aurais souhaité pouvoir généraliser l'algorithme à n'importe quel cas, tout en réalisant les implications possibles en terme de récursivité pour l'interpréteur XSLT.

Je vous tiens au courant...

**GrandFather** · 27/11/2009, 10h15

Le fait que la liste soit triée a un impact sur l'axe XPath qui doit être utilisé, et sur les performances. Pour une liste non triée:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
      <xsl:if test="../balise[starts-with(@name, current()/@name) and string-length(@name) = string-length(current()/@name) + 1]">
        <ul>
          <xsl:apply-templates select="../balise[starts-with(@name, current()/@name)  and string-length(@name) = string-length(current()/@name) + 1]"/>
        </ul>
      </xsl:if>

L'avantage de following-sibling, c'est qu'on restreint le nombre d'éléments à tester à chaque itération. Avec cette autre variante, on est plutôt sur un algorithme en O(n²).

Quoi qu'il en soit, une optimatisation de ce code pourrait passer par l'emploi d'une variable:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
<xsl:variable name="sub-items" select="../balise[starts-with(@name, current()/@name) and string-length(@name) = string-length(current()/@name) + 1]" />
<xsl:if test="$sub-items">
  <ul>
    <xsl:apply-templates select="$sub-items"/>
  </ul>
</xsl:if>

**lescarphe** · 27/11/2009, 10h38

Merci pour ces précisions !

J'ai testé l'algo et sur le principe, ça marche. Je dis sur le principe, car en fait, il arrive que dans ma liste le nom des éléments recursifs n'est pas nécessairement de 1 caractère plus long que celui de leur parents, mais c'est un détail facile à régler je pense (hum, pas si sûr en fait, si on n'impose pas que le nom d'un fils est au plus de n caractères plus long que celui de son père)

Il ne m'était pas venu à l'esprit d'utliser following-siblings, et l'utilisation de 'parent' provoquait des récursions infinies.

Merci encore.

**Erwy** · 27/11/2009, 13h13

j'ai une variation marrante à proposer et au niveau perf je suis sur d'écraser l'ancêtre

je suis partie de ce xml

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
<racine>
	<balise name="BD"/>
	<balise name="ABB"/>
	<balise name="A"/>
	<balise name="BC"/>
	<balise name="AB"/>
	<balise name="B"/>
</racine>

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
	<xsl:output method="xml" version="1.0" encoding="UTF-8" indent="yes"/>
	<xsl:key name="fils" match="balise" use=" substring(@name,1,(string-length(@name) - 1))"/>
	<xsl:template match="/">
		<racine>
			<xsl:apply-templates select="/racine/balise[string-length(@name)=1]">
				<xsl:sort select="@name"/>
			</xsl:apply-templates>
		</racine>
	</xsl:template>
	<xsl:template match="balise">
		<xsl:copy>
			<xsl:copy-of select="@*"/>
			<xsl:apply-templates select="key('fils',@name)">
				<xsl:sort select="@name"/>
			</xsl:apply-templates>
		</xsl:copy>
	</xsl:template>
</xsl:stylesheet>

Envoyé par lescarphe

Je dis sur le principe, car en fait, il arrive que dans ma liste le nom des éléments recursifs n'est pas nécessairement de 1 caractère plus long que celui de leur parents, mais c'est un détail facile à régler je pense (hum, pas si sûr en fait, si on n'impose pas que le nom d'un fils est au plus de n caractères plus long que celui de son père)

Plus complexe