Recherche d'un path dans un document XML

Version imprimable

Bonjour,
j'ai le fichier XML incomplet suivant :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 <number="1" depth="0"> <number="2" depth="1"> <number="4" depth="2"> <number="8" depth="3"> ... </number> </number> <number="3" depth="2"> <number="5" depth="3"> ... </number> <number="6" depth="3"> ... </number> </number> </number> </number>
Ce fichier représente l'arbre incomplet suivant :
Code:

1 2 3 4 5 6 7 8 9 1 | 2 ----> Doubles or Sums of the precedings numbers / \ 3 4 ----> Doubles or Sums of the precedings numbers / \ \ / \ \ 5 6 8 ... etc
Je veux utiliser des fichiers XML afin de ne pas être limité en mémoire.

Je voudrais à partir du fichier XML faire trois choses le plus rapidement possible, quitte à faire appel à des bibliothèques extérieures comme lxml (c'est même sûr qu'il faudra faire cela) :

Savoir si un nombre N apparait en tant que valeur de number.
Si un nombre N apparait dans le fichier XML, j'aimerais récupérer le chemin qui permet d'y accéder. Par exemple, pour 8, j'aimerais récupérer [1,2,4], et pour 3 avoir [1,2]. J'aimerais aussi récupérer sa profondeur depth indiquée dans mon fichier XML,mais je pense inutile d'utiliser ce depth.
Une dernière chose, j'aimerais aussi, afin de construire mon fichier XML, ajouter des noeuds là où il y a des points de suspension.

Toute info. est la bienvenue.

29/04/2010, 17h07
rambc

Je pense avoir un début de réponse ici. Je "zieuterais" cela tout à l'heure après le vélo.
29/04/2010, 20h05
wiztricks

Citation:

Envoyé par rambc

Je veux utiliser des fichiers XML afin de ne pas être limité en mémoire.

Je ne comprends pas la relation entre XML et moins de limitation mémoire.

Citation:

[*] Une dernière chose, j'aimerais aussi, afin de construire mon fichier XML, ajouter des noeuds là où il y a des points de suspension.[/LIST]
Toute info. est la bienvenue.

Je vais peut être dire une bétise mais la forme:
<number=value depth=n>
ne me paraît pas très correcte. il serait peut être plus juste d'avoir
<number value=value depth=n/>
Ce qui est un nœud sans fils.

Pour le reste... XML est populaire pour sérialiser des données qu'on va échanger entre applications. Prendre des outils tels que lxml pour les analyser est très bien mais si vos traitements ne peuvent se faire en lisant le XML pas à pas (i.e. SAX) il va falloir le charger en mémoire et l'attaquer avec du DOM.
Et comme vous voulez interroger la structure en mémoire, je ne vois pas trop comment faire ça sans tout charger.
Quitte à tout charger et à parcourir la chose avec des requêtes à inventer pourquoi ne pas désérialiser l'engin dans une base de donnée?
Cela permet de ne pas se poser de questions "côté mémoire" et côté query ou autre fonctionnalité on dispose d'un engin un peu plus performant.
Mais ce n'est peut être pas ce que vous voulez.
- W
29/04/2010, 22h29
rambc

Citation:

Envoyé par wiztricks

Je ne comprends pas la relation entre XML et moins de limitation mémoire.

Je crée mon fichier XML pour une velur donnée, si elle a déjà été traité j'utilise le fichier XML, sinon j'ajoute les nouveaux noeuds nécessaires pour obtenir cette nouvelle valeur.

Citation:

Envoyé par wiztricks

Je vais peut être dire une bétise mais la forme:
<number=value depth=n>
ne me paraît pas très correcte. il serait peut être plus juste d'avoir
<number value=value depth=n/>
Ce qui est un nœud sans fils.

Bonnes remarques...

Citation:

Envoyé par wiztricks

Et comme vous voulez interroger la structure en mémoire, je ne vois pas trop comment faire ça sans tout charger.
Quitte à tout charger et à parcourir la chose avec des requêtes à inventer pourquoi ne pas désérialiser l'engin dans une base de donnée?
Cela permet de ne pas se poser de questions "côté mémoire" et côté query ou autre fonctionnalité on dispose d'un engin un peu plus performant.
Mais ce n'est peut être pas ce que vous voulez.

Seul souci, mon niveau de connaissance équivaut au zéro absolu de la gestion de BDD.

Je vais quand même essayer à titre d'essai mon idée. Faut juste que je trouve du temps donc ce ne seras sûrement pas avant la fin de la semaine prochaine.

Bonjour.

Pour ne pas avoir à construire d'arbre je récupère dans les données number et depth. Ensuite, en parcourant 'intelligemment' la liste des depths, je trouve le chemin qui conduit à n'importe quel nombre.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#!/usr/bin/env python
 
import re
 
def trouve_chemin(number):
    fname = "xmlfile.xml"
    xmltext = open(fname, 'r').read()
    reg = re.compile(r'<number="(\d+)" depth="(\d+)">', re.DOTALL)
    m = reg.findall(xmltext)
 
    if m:
        numbers, depths = zip(*map(lambda (x,y): (int(x),int(y)), m))
        I = numbers.index(number)
        depth = depths[I]
        chemin = []
 
        while depth > 0:
            depth -= 1
            depths = depths[:I]
            c = depths[I-1::-1] # 3 3 2 3 2 1 0
            I = I - 1 - c.index(depth)
            chemin.append(numbers[I])
        chemin = chemin[::-1]
        print "chemin pour %2d:" % number, chemin
 
    else:
        print "No match for %d." % number
 
 
 
for n in [1,2,3,4,5,6,8]:
    trouve_chemin(n)

les resultats:

Code:

1
2
3
4
5
6
7
chemin pour  1: []
chemin pour  2: [1]
chemin pour  3: [1, 2]
chemin pour  4: [1, 2]
chemin pour  5: [1, 2, 3]
chemin pour  6: [1, 2, 3]
chemin pour  8: [1, 2, 4]

Bonne soirée.

EDIT: Illustration:
Les listes 'numbers' et 'depths' construites (d'apres l'exemple) sont:

Code:

1
2
numbers= [1, 2, 4, 8, 3, 5, 6]
depths = [0, 1, 2, 3, 2, 3, 3]

En image, on voit que que vaut la variable I lors de chaque itération de la boucle while:

Code:

1
2
3
4
5
6
recherche: 6
numbers:     1    2    4    8    3    5    6
iteration 0:                               x   (avant le while)
iteration 1:                     x
iteration 2:      x
iteration 3: x

on a construit le chemin [1,2,3].

Merci pour la réponse précédente.

Voici ce que j'ai fait pour la lecture :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import xml.etree.ElementTree as etree
tree = etree.parse('memoryTree.xml')
root = tree.getroot()
 
def findNumber(node, number):
    for child in node:
        if(child.attrib['value']==number):
            return [number]
 
        test = findNumber(child, number)
        if test:
            return [child.attrib['value']] + test
 
print(findNumber(root, str(12)))

J'obtiens :

Code:

['1', '2', '3', '6', '12']

Le fichier XML memoryTree.xml est le suivant :

Code:

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="ISO-8859-1" standalone="no" ?>
<knuth>
    <number value="1">
        <number value="2">
            <number value="4">
                <number value="8">
                </number>
            </number>
            <number value="3">
                <number value="5">
                </number>
                <number value="6">
                    <number value="9">
                    </number>
                    <number value="12">
                    </number>
                </number>
            </number>
        </number>
    </number>
</knuth>

Quand je trouverais 5 min, je m'attaquerais à la création du fichier XML avec les règles imposées.