Les arbres binaires, vus dans les deux séquences précédentes, se “généralisent” en des structures arborescentes constituées de nœuds toujours organisés par des notions de racine et de sous-arbres.
Ces structures arborescentes sont omniprésentes en informatique et prennent des formes concrètes très variées.
Elles permettent de structurer l'information, notamment pour la stocker, la parcourir, y faire des recherches, etc.
Dans cette séquence, on commence par définir ce qu'est une arborescence et
par montrer comment la représenter en Python.
Puis on donnera des exemples significatifs de structures arborescentes.
Mettre le résultat ici (code et figure).
Une arborescence est un ensemble non vide de nœuds qui sont organisés de la façon suivante :
- un nœud particulier constitue la racine de l'arborescence;
- les autres nœuds sont partagés en n sous-ensembles distincts, qui forment autant d'arborescences;
- le nœud racine est relié aux n racines de ses arborescences, qu'on appelle ses fils.
C'est donc là une définition récursive, comme pour les arbres binaires. À la
différence de ces derniers. cependant, il n'y a pas de notion d'arborescence vide qui ne contiendrait aucun nœud.
Le cas de base de cette définition récursive est une arborescence qui contient un seul nœud.
Voici un exemple d'arborescence contenant huit nœuds, chacun étant étiqueté par une chaîne de caractères:
____\"A\"____
/ \\
\"B\". __\"C\"___
| / | \\
\"D\". \"E\" \"F\" \"G\"
|
\"H\"
La racine est le nœud étiqueté par \"A\", qui possède deux fils, respectivernent
étiquetés par \"B\" et \"C\".
Certains nœuds possèdent un seul fils, comme \"B\" et \"F\", le nœud \"C\" possède trois fils, et enfin les nœuds \"D\", \"E\", \"H\" et ‘G\" ne possède aucun fils.
Ces derniers sont appelés des feuilles.
Souvent, on se contente de parler d'arbre plutôt que d'arborescence. Cependant, il y a alors un petit risque de confusion entre arbre et arbre binaire.
Certains auteurs utilisent parfois le vocabulaire d'arbre n-aire mais il est là encore source de confusion, certains l'interprétant comme «le nombre de sous-arbres est borné par n». C'est pourquoi
nous avons choisi le terme d'arborescence.
","title":"Arborescence"},{"edit":"Mettre le résultat ici (code et figure).
Arbres binaires et arborescences
Un arbre binaire (séquence précédentes) n'est pas un cas particulier d'arborescence où chaque nœud n'aurait qu'au plus deux fils.
En effet, les arbres binaires font la distinction entre le sous-arbre gauche et le sous-arbre droit.
Ainsi, les deux arbres binaires
__O__ __O__
/ \\ et / \\
_O_ _O_
/ \\ / \\
sont distincts.
On parle d'arbres positionnels pour les arbres binaires.
Une arborescence contenant deux nœuds, c'est-à-dire une racine reliée à un unique fils, ne peut faire la distinction entre ces deux cas.
Certaines notions définies sur les arbres binaires s'appliquent également aux arborescences. Ainsi, on définit la taille d'une arborescence comme son nombre de nœuds et sa hauteur comme le plus grand nombre de nœuds rencontrés en descendant de la racine jusqu'à une feuille.
","title":""},{"edit":"Pour représenter une arborescence en Python, on va utiliser des objets, comme on l'a fait pour les arbres binaires. Le programme ci-dessous contient la définition d'une classe Noeud pour représenter un nœud d'une arborescence.
Programme — Nœud d'une arborescence
class Noeud:
\"\"\"un noeud d'une arborescence\"\"\"
def __init__(self, v, f):
self.valeur = v
self.fils = f
Un objet de cette classe contient deux attributs :
- un attribut valeur dans lequel on stocke une valeur quelconque qui étiquette le nœud;
- et un attribut fils dans lequel on stocke les fils sous la forme d'un tableau.
Avec cette classe, on peut construire l'arbre donné en exemple plus haut de la manière suivante :
a1 = Noeud(\"A\", [Noeud(\"B\", [Noeud(\"D\", [])]), \\
Noeud(\"C\", [Noeud(\"E\", []), \\
Noeud(\"F\", [Noeud(\"H\", [])]), \\
Noeud(\"G\", [])
]) \\
])
On peut ensuite programmer des opérations sur les arborescences d'une façon analogue à ce que nous avons fait avec les arbres binaires, à deux différences près. La première tient dans le traitement d'un tableau de fils plutôt que dans celui de deux sous-arbres.
La seconde différence tient dans le cas de base, qui n'est plus celui d'un arbre vide.
Ainsi, pour calculer la taille d'une arborescence, on peut écrire la fonction récursive suivante:
def taille(a):
t = 1 # Le noeud a lui-même
for f in a.fils:
t += taille(f)
return t
print(taille(a1))
Tester les instruction ci-dessus et conclure.
Un tel calcul se termine bien, car les feuilles ont un attribut fils qui contient un tableau vide. Dans ce cas, la boucle for ne provoque aucun appel récursif et la fonction renvoie le nombre d'élèments de l'arborescence.
De même, on peut écrire un fonction qui réalise un parcours d'arborescence analogue au parcours d'un arbre binaire. Il n'y a pas vraiment d'analogue au parcours infixe (où le sous-arbre gauche était visité avant le nœud, lui-même avant le sous-arbre droit) mais en revanche on peut tout à fait réaliser un parcours préfixe d'une arborescence.
En voici un exemple :
def parcours_prefixe(a):
\"\"\"affiche les éléments de a dans un parcours préfixe\"\"\"
print(a.valeur)
for f in a.fils:
parcours_prefixe(f)
parcours_prefixe(a1)
Cette fonction affiche les éléments de l'arborescence a1 selon un parcours
préfixe, c'est-à-dire en affichant la valeur contenue dans la racine avant de
parcourir récursivement les arborescences de chacun des fils.
Tester le code et conclure.
Mettre le résultat ici (code et figure).
![\"pile_file1.png](\"https://sciencesappliquees.com/images/nsi/restapi1.png\")
Dans cette section, on détaille deux exemples de structures arborescentes
qui sont aujourd'hui omniprésentes en informatique :
- XML
- JSON.
Les arborescences sont des structures particulièrement adaptées à la représentation de documents.
Considérons un livre. C'est un document structuré :
il contient des chapitres et des paragraphes.
Si c'est un ouvrage technique, il contient aussi des figures, des tables, des sections et des sous-sections.
Une table des matières ou un index peuvent aussi être présents.
On se retrouve donc dans une situation hybride entre des documents à la structure rigide (comme des fichiers CSV avec un nombre fixe de colonnes par exemple) et des documents dépourvus de structure (comme un simple
fichier texte).
Par exemple, on peut vouloir arranger le document de façon à ce que chaque chapitre commence par un titre, puis soit suivi d'une liste non vide de paragraphes.
En revanche, au sein d'un paragraphe, on souhaite simplement mettre des suites arbitraires de caractères.
On appelle ce type de documents des documents semi-structurés.
Le format XML (pour l'anglais eXtensible Markup Language, langage de balises extensibles) est un format de fichier, standardisé par le W3C (pour World Wide Web Consortium).
Ce format est proche du format HTML utilisé pour la représentation des pages web.
Nous présentons ce format, sans rentrer dans les détails de la spécification.
Par exemple, si on souhaite décrire une recette de cuisine, on pourra utiliser le document donné ci-dessous:
<recette difficulté=\"facile\">
<titre>Crêpes sucrées</titre>
<temps>1h</temps>
<note>pour 10 crêpes</note>
<ingredients>
<i q=\"200g\">farine</i>
<i q=\"40g\">sucre</i>
<i q=\"2\">œufs</i>
<i q=\"40cl\">lait</i>
</ingredients>
<etapes>
<e>mélanger les ingrédients solides</e>
<e>ajouter le lait</e>
<e>laisser reposer</e>
<e>cuire sur une poêle beurrée</e>
</etapes>
</recette>
Figure 1 - Un document XML.
Dans ce document, et comme dans les documents HTML, le texte entre chevrons , par exemple, <temps>, </e> ou <i g=\"200g\"> s'appelle une balise (Tag en anglais).
Une balise commençant par </ est appelée balise fermante.
Les autres balises sont appelées balises ouvrantes.
Le texte tel que temps, e où i est le nom de la balise.
Les suites de caractères telles que q=\"200g\" se trouvant dans les balises ouvrantes sont appelés des attributs.
Ici, q est le nom de l'attribut et
200g est sa valeur.
Les documents XML doivent respecter un certain nombre de contraintes de bonne formation. dont voici les principales :
- les balises doivent être bien parenthésées, c'est-à-dire qu'à chaque balise ouvrante doit correspondre une balise fermante avec le même nom de
balise;
- les noms de balises sont sensibles à la casse (temps, TEMPS et Temps
sont trois noms de balise différents);
- tout le contenu du document doit être entouré par une unique paire de balise ouvrante et fermante appelée balise racine;
- les valeurs d'attributs sont toujours présentes et délimitées par des guillemets doubles ou simples;
- il ne peut pas y avoir deux attributs avec le même nom au sein d'une même balise;
- les caractères «<», «>», «&», «'» et «\"» doivent être «échappés» respectivement par « < », « > », « & », « " » et
« ' »;
- n'importe quel caractère Unicode peut être échappé avec la notation « &#n; » où n est le code du caractère, en base 10.
Par exemple, le caractère « ⇔ » peut être saisi comme « ⇔ ».
La spécification du format XML ne fixe pas les noms des balises et des attributs.
Tout un chacun est libre de choisir les noms qu'il souhaite pour pouvoir représenter de l'information.
Une observation importante est qu'à chaque document XML correspond une arborescence, où toute portion complète du document correspond à un nœud.
Par exemple, le document de la figure 1 correspond à l'arbre donné à la figure ci-dessous :
![\"pile_file1.png](\"https://sciencesappliquees.com/images/nsi/arbo.png\")
Figure 2 — Arborescence du document de la figure 1.
Mettre le résultat ici (code et figure).
Le W3C ne se limite pas à spécifier le format des fichiers XML. Il définit
aussi le modèle d'arborescence correspondant aux documents.
En quelques mots, ce modèle impose la présence d'un nœud document. Ce dernier est un nœud fictif, ne correspondant à aucune balise, et défini comme parent du
nœud correspondant à la balise racine.
Tous les autres fragments du document XML sont représentés. Les balises correspondent à des nœuds internes de l'arborescence, On appelle de tels nœuds des éléments de l'arborescence XML.
Les attributs sont associés au nœud de la balise dans laquelle ils sont.
Les caractères sont naturellement les feuilles de l'arborescence.
Le W3C définit aussi la façon dont de tels arbres sont représentés dans des langages orientés objets.
C'est le standard DOM (pour Document Object Model où modèle objet de document). Ce standard du W3C définit les noms de classes, de méthodes, d'attributs ou les constantes qui permettent de manipuler un document XML.
L'intérêt d'un tel standard est que les noms des concepts seront les mêmes, quels que soit le langage de programmation utilisé. Dans le modèle DOM, les nœuds de l'arbre possèdent les attributs suivants: :
type : le type de nœud considéré (élément, texte, nœud document, etc.)
nom : le nom du nœud. Les éléments ont pour nom le nom de la balise associée (ingrédients , étapes etc ). Le noeud document a pour nom la chaîne constante #document. Les nœuds texte ont pour nom la chaîne constante #text.
valeur : les nœuds texte ont comme valeur la chaîne de caractères correspondant à ce nœud dans le document initial (par exemple pour 10 crêpes).
fils : chaque nœud a une liste de fils (qui peut être vide dans le cas de feuilles).
parent : chaque nœud a un nœud parent, excepté le nœud document.
En Python, les fonctions et classes permettant de manipuler un document XML se trouvent dans le module xml.dom.minidom. Il est usuel de
donner à ce module un alias plus court :
import xml.dom.minidom as dom
Ce module contient une implémentation «minimale» de la spécification DOM du W3C (d'où son nom).
Nous faisons un bref tour d'horizon, forcément partiel, de cette vaste bibliothèque et montrons comme elle permet de manipuler des documents XML comme de simples arborescences.
Les fonctions dom.parse et dom.parseString permettent de charger un document XML à partir d'un fichier ou d'une chaîne de caractères, comme le montre l'exemple ci-dessous :
import xml.dom.minidom as dom
#Méthode 1
doc1 = dom.parse(\"fichier.xml\")
print(doc1)
#Méthode 2
f = open (\"fichier.xml\")
doc2 = dom.parse(f)
print(doc2)
#Mé‡thode 3
doc3 = dom.parseString(\"<a>mon joli <b>document</b></a>\")
print(doc3)
Télécharger le fichier xml fichier.xml et le mettre dans le même dossier que votre programme.
Tester le programme et conclure.
Une fois chargé, un document XML est un objet de la classe dom.Node.
Il possède les méthodes et attributs que nous listons dans la table suivante :
Attributs pour tous les types de noeuds
| nom | description |
| .nodeType | Entier représentant le type du nœud. Les constantes de type de nœud sont des attributs de la classe Node : dom.Node.ELEMENT_NODE, dom.Node .TEXT dom.Node .DOCUMENT_NODE, etc. |
| .nodeName | Chaîne de caractères représentant le nom du nœud |
| .nodeValue | Chaîne de caractères représentant la valeur du nœud pour les nœuds de type texte et attribut. None pour les autres types de nœuds. |
| .childNodes | Liste contenant les nœuds fils du nœud courant. |
| .attributes | Dictionnaire associant les noms des attributs du nœud à des nœuds attributs. |
Méthodes pour le nœud document
| nom | description |
| .createElemant(n) | Crée un nouveau nœud élément dont le nom est donné par la chaîne de caractères n. |
| createTextNode(t) | Crée un nouveau nœud texte dont la valeur don. née par la chaîne de caractères t. |
| .toxml() | Renvoic le document comme une chaîne de carac- tères afin de le sauver dans un fichier. Méthode utilitaire Python, ne faisant pas partie de DOM. |
Méthodes pour le nœud document ou les nœuds éléments
| nom | description |
| .appendChild(n) | Ajoute le nœud n comme dernier fils du nœud courant. |
| .insertBefore(c, n) | Ajoute le nœud n juste avant le nœud c, qui doit être un fils du nœud courant. |
| .removeChild(n) | Supprime le nœud n, qui doit être un fils du nœud courant. |
Méthodes pour les nœud
| nom | description |
| .setAttribute(n,v) | Ajoute ou modifie l'attribut de nom n pour lui donner la valeur v. |
| .basAttribute(n) | Teste si le nœud courrant possède un attribut n. |
| removeAttribute(n) | Retire l'attribut de nom n du nœud courrant. |
Ainsi, en utilisant ces attributs, on peut définir par exemple une fonction
tailleDOM(d) semblable à la fonction récursive taille de la section précédente:
def tailleDOM(d):
t=1
for c in d.childNodes:
t += tailleDOM(c)
return t
print(\"doc1\",tailleDOM(doc1))
print(\"doc2\",tailleDOM(doc2))
print(\"doc3\",tailleDOM(doc3))
Tester le code et conclure.
Le modèle DOM impose des invariants lors de la création et ajout de nœuds pour garantir que l'objet résultant représente toujours une arborescence.
On illustre ce comportement avec un exemple:
Nous créons un document avec uniquement une racine :
doc4 = dom.parseString(\"<a></a>\")
a = doc4.childNodes[0] # doc est le nœud #document, son seul
# fils est la balise racine
b = doc4.createElement(\"b\") # on crée un nouveau nœud
c = doc4.createElement(\"c\") # on crée un nouveau nœud
a.appendChild(b) # on ajoute b comme fils de a
a.appendChild(c) # on ajoute c comme fils de a
Le code précédent crée, à partir d'une chaîne de caractères, un document minimal.
Attention, ce document possède deux nœuds, celui correspondant au nœud fictif #document et celui correspondant à la balise racine.
On utilise le nœud document pour créer deux nouveaux nœuds, b et c. Ces nœuds sont pour l'instant détachés et n'apparaissent pas dans l'arborescence.
On peut les accrocher en utilisant la méthode .appendChild du nœud auquel on veut les ajouter, ici la racine a.
À la fin de l'exécution de ce code, on obtient en mémoire une arborescence correspondant au document
<a><b></b><c></c></a>.
Si on effectue de nouveau l'ajout d'un nœud se trouvant déjà dans la structure, alors la bibliothèque va déplacer ce nœud, si c'est possible :
a.appendChild(b)
Cet appel de méthode a pour effet de détacher le nœud b de l'arbre et de le
rajouter à la fin des fils de a.
![\"pile_file1.png](\"https://sciencesappliquees.com/images/nsi/arbo2.png\")
Lorsque ce déplacement n'est pas possible, la méthode de déplacement lève
une erreur, comme le montre les exemples suivants :
doc = dom.parseString(\"<a></a>\")
a = doc.childNodes[0]
b = doc.createElement(\"b\")
doc.appendChild(b)
Ici, on crée un nouveau nœud b et on essaye de l'ajouter avant (ie., comme
frère précédent) le nœud a.
Ceci lève une erreur :
xml.dom.HierarchyRequestErr: two document elements disallowed
Le standard XML va bien au-delà de cette simple présentation.
Cette dernière permet cependant d'utiliser des documents XML, par exemple pour en extraire de l'information, ou d'utiliser un document XML comme format
d'échange entre deux programmes.
Un aspect important du format XML est
la notion de schéma ou de type associé à un document.
En effet, il est possible de spécifier précisément la structure que doit avoir un document (balises autorisées, forme de leur contenu, etc.).
Ces schémas permettent de définir une notion de documents valides et peuvent être vérifiés automatiquement lors du chargement du fichier.
Cette notion est particulièrement cruciale car elle réduit de façon importante le volume de code que le programmeur doit écrire.
Ainsi, le programmeur n'a pas besoin de tester explicitement que la racine s'appelle recette, qu'elle a bien un attribut difficulté, qu'elle a une liste non vide d'ingrédients, etc.
Elle permet aussi de forcer certains
invariants (par exemple, que tel élément contient toujours une date et non
pas des caractères arbitraires), ce qui est important dans un contexte de manipulation de données.
Mettre le résultat ici (code et figure).
https://docs.python.org/3.4/library/xml.etree.elementtree.html
Lisez la documentattion de etree.
","title":""},{"edit":"Les fonctions etree.parse et etree.XML permettent de charger un document XML à partir d'un fichier ou d'une chaîne de caractères, comme le montre l'exemple ci-dessous :
#Méthode 1
doc1 = ET.parse(\"fichier.xml\")
root1 = doc1.getroot()
print(root1)
#Méthode 2
f = open (\"fichier.xml\")
doc2 = ET.parse(f)
root2 = doc2.getroot()
print(root2)
#Mé‡thode 3
doc3 = ET.XML(\"<a>mon joli <b>document</b></a>\")
print(doc3)
Télécharger le fichier xml fichier.xml et le mettre dans le même dossier que votre programme.
Tester le programme et conclure.
A partir de la documentation ETREE, on peut définir par une fonction
tailleETREE(d) semblable à la fonction récursive taille et tailleDOM:
def tailleETREE(d):
t=1
for c in d:
t += tailleETREE(c)
return t
print(\"doc1\",tailleETREE(root1))
print(\"doc2\",tailleETREE(root2))
print(\"doc3\",tailleETREE(doc3))
Tester la fonction tailleETREE et la comparer à tailleDOM.
Si nous voulons maintenant créer un document xml de la forme suivante avec ETREE:
__\"a\"__
/ \\
\"b\" \"c\"
|
\"d\"
Avec ETREE, il faudra utiliser le code suivant :a = ET.Element('a')
b = ET.SubElement(a, 'b')
c = ET.SubElement(a, 'c')
d = ET.SubElement(c, 'd')
#affiche arborescence de a
ET.dump(a)
Mettre le résultat ici (code et figure).
Bien que le format XML remplisse son rôle de format standard pour les données semi-structurées, il souffre de plusieurs défauts.
En premier lieu, la spécification est très longue, contenant de nombreux documents annexes remplis de détails subtils.
En second lieu, il est considéré comme verbeux.
Bien que l'un des buts du W3C ait été de proposer un format de fichiers lisible par un humain, l'abondance de balises et de séquences d'échappement rend les documents peu lisibles en pratique.
Enfin, le modèle DOM qui impose les noms d'attributs et de méthodes se trouve fortement inspiré par la bibliothèque standard du langage Java et son utilisation pousse les prograinmeurs des autres langages (Python, JavaScript, etc.) à écrire du code souvent non idiomatique.
Avec l'avènement du Web, et en particulier de la programmation «côté
client» en JavaScript, le besoin s'est fait sentir de disposer d'un format flexible et compact permettant l'échange de données entre le client. (le navigateur web) et le serveur web.
Cela a donné lieu à l'introduction du format JSON (JavaScript Object Notation ou notation objet JavaScript) au début des années 2000. Ce format à été ensuite standardisé par différents organismes internationaux tels que l'ECMA (référence ECMA-404) ou l'ISO (référence 180 21778 :2017).
Le nom est tiré du fait que le format utilise la même syntaxe que celle des objets dans le langage JavaScript.
En JavaScript, un «objet» correspond plus ou moins à un dictionnaire Python, tout du moins du point de vue syntaxique.
Un exemple de fichier JSON, contenant la même recette que le fichier XML donné en exemple dans la section précédente, est donné à la figure 3.
{
\"titre\" : \"Crêpes sucrées\",
\"difficulté\" : \"facile\",
\"temps\" : { \"unité\" : \"h\", \"valeur\" : 1 },
\"note\" : \"pour 10 crêpes\",
\"ingredients\" : [
{ \"nom\" : \"farine\", \"q\" : { \"unité\" : \"g\", \"valeur\" : 200 } },
{ \"nom\" : \"sucre\", \"q\" : { \"unité\" : \"g\", \"valeur\" : 200 } },
{ \"nom\" : \"œufs\", \"q\" : { \"unité\" : \"\", \"valeur\" : 2 }},
{ \"nom\" : \"lait\", \"q\" : { \"unité\" : \"cl\", \"valeur\" : 40 }}
],
\"étapes\" : [
\"mélanger les ingrédients solides\",
\"ajouter le lait\",
\"laisser reposer\",
\"cuire sur une poële beurrée\" ]
}
Figure 3 - Un fichier JSON de la recette des crêpes
À l'inverse des fichiers XML, la syntaxe
JSON est plus simple d'approche pour un programmeur Python. Les valeurs JSON peuvent être de six types différents. II y à quatre types simples :
null : une constante spéciale indiquant une absence de voleur similaire à la constante None de Python;
booléens : représentés par les deux constantes true et false (en minuscule);
nombres : peuvent être entiers ou flottants {dans ce deuxième cas, la notation scientifique standard est utilisée, c'est-à-dire une mantisse et
éventuellement un E ou e suivi d'un entier représentant une puissance de 10, comme -1.2E23 qui représente —1.2 x 10^23;
chaînes de caractères : délimitées par des guillemets doubles « \" » obligatoirement et encodées en UTF-8.
Par exemple, true, 6.022e23, \"Bonjour 1es amis!\" et null sont des valeurs JSON valides.
À ces quatre types simples s'ajoutent deux types structurés :
tableaux : identiques aux tableaux Python. Les tableaux sont délimités
par des crochets et les éléments sont séparés par des virgules. Un tableau contient une suite de valeurs JSON (qui peuvent être de types différents).
objets : similaires aux dictionnaires Python. Les objets JSON sont délimités par des accolades. Ils contiennent des associations clés-valeurs. Les clés sont obligatoirement des chaînes de caractères au format décrit ci-dessus.
Les valeurs peuvent être n'importe quelles valeurs JSON.
Les clés sont séparées des valeurs par le caractère « : ».
Les différentes associations sont séparées par des virgules.
Cette proximité de syntaxe et de types fait que l'utilisation de données JSON en Python est très simple.
Les fonctions nécessaires se trouvent dans le module json.
En premier lieu, on peut lire une valeur JSON, soit en la chargeant depuis un fichier ouvert avec la fonction open, soit à partir d'une chaîne de caractères.
Ces opérations sont offertes par les fonctions json.load et json.loads respectivement :
import json
f = open(\"recette.json\") # ouverture du fichier en lecture
recette = json.load(f) # chargement du fichier
f.close()
print(recette[\"titre\"]) # affiche Crêpes sucrées
print(recette[\"ingredients\"][2][\"nom\"]) # affiche œufs
d = json.loads('{ \"nom\" : \"Sérudier\" , \"prénom\" : \"Paul\"}')
print(d[\"nom\"]) # affiche Knuth
Télécharger le recette json recette.json et le mettre dans le même dossier que votre programme.
Tester le programme et conclure.
Comme on le voit, utilisation est très simple. Une fois le fichier ou la chaîne
de caractères chargés, les valeurs JSON sont traduites automatiquement en
valeur Python. Il est ensuite possible de les manipuler comme on le souhaite.
Attention, comme dans le cas des documents XML, manipuler la structure de
données en mémoire n'a aucun impact sur le fichier. Si on souhaite modifier
le fichier, il faut écrire l'objet modifié dans un fichier, ou le sérialiser sous
forme d'une chaîne de caractères qui pourra être écrite dans un fichier. C'est
le rôle des fonction json.dump ct json.dumps :
#modifie le titre
recette['titre'] = \"La soupe aux choux\"
f2 = open(\"recette_mod.json\", \"w+\") # ouverture en écriture
# et création si besoin
json.dump(recette, f2)
f2.close()
d = { 'a' : None, 'b' : False }
print(json.dumps(d))
Tester le code et ouvrir le fichier recette_mod.json et conclure.
Comme on le voit, les fonctions json.dump et json.dumps effectuent une traduction inverse, des valeurs Python vers les valeurs JSON.
Cette traduction n'est pas toujours possible. Dans ce cas, la fonction lève une exception :
d = { 'b' : b\"1234\" }
json.dumps (d)
TypeËrror: Qbject of type bytes is not JSON serializabled= {tx :1}
d{\"y\"] = à
json.dumps (4)
ValueError: Circular reference detected
Bien que les valeurs JSON soient des structures arborescentes, elles possèdent quelques différences notables avec les arbres et les arborescences décrites jusqu'à présent.
En premier lieu, elles ne possèdent pas de nœud «racine». En effet, une arborescence JSON est soit un type de base, soit un tableau, soit un dictionnaire.
Ensuite, lorsque lon parcourt une structure JSON, on est dépendant de l'ordre de parcours des clés dans un dictionnaire. Cette ordre peut être influencé par de nombreux facteurs (numéro de version de Python, ordre d'insertion, type exact du dictionnaire, etc.).
Mettre le résultat ici (code et figure).
Une arborescence, souvent désignée simplement comme un arbre, est un ensemble de nœuds structurés avec une racine reliée à des nœuds fils, eux-mêmes racines d'autres arborescences.
De telles arborescences sont utilisées pour organiser l'information.
Les formats XML et JSON en sont deux exemples, omniprésents dans l'informatique d'aujourd'hui.
Mettre le résultat ici (code et figure).
Écrire une fonction affiche(a) qui affiche une arborescence
sous la forme
A
B
D
C
E
F
H
G
c'est-à-dire qui affiche les nœuds selon un parcours préfixe, avec un nœud
par ligne et une marge qui est proportionnelle à la profondeur du nœud
dans l'arbre.
Indication : écrire une fonction récursive, qui prend comme paramètre supplémentaire une chaîne de caractères, constituée d'espaces, à afficher avant la valeur du noeud.
Tester avec :
a1 = Noeud(\"A\", [Noeud(\"B\", [Noeud(\"D\", [])]), \\
Noeud(\"C\", [Noeud(\"E\", []), \\
Noeud(\"F\", [Noeud(\"H\", [])]), \\
Noeud(\"G\", [])
]) \\
])
affiche(\"\",a1)
Mettre le résultat ici (code et figure).
La chaîne p est la marge, qu’on augmente de deux espaces pour l'affichage des sous-arbres.
def affiche(p, a):
print(p + str(a.valeur))
for f in a.fils:
affiche(p +\" \", f)
Le système de fichiers d'un ordinateur, et en particulier les répertoires qui le composent, peut être considéré comme une arborescence en première approximation.
Dans cet exercice, on se propose d'écrire une fonction Python repertoires qui reçoit en argument un nom de répertoire
et renvoie une arborescence, au sens du programme 35, qui décrit la structure
récursive de ses sous-répertoires.
Pour cela, on pourra se servir des fonctions suivantes fournies par la bibliothèque os :
- La fonction os.listdir(r) renvoie un tableau de tous les fichiers contenus dans le répertoire r, dont les sous-dossiers de r.
- La fonction os.path.join(r, f) permet de concaténer le nom du répertoire x au nom d'un fichier f qu'il contient pour construire le nom complet de ce fichier.
- La fonction os.path.isdir(f) permet de tester si le nom de fichier f désigne un répertoire.
Tester le résultat de cette fonction repertoires en l'affichant avec la fonction de l'exercice précédent.
affiche(\"\",repertoires(\"C:\\Users\\\"))
Attention changer le nom du répertoire racine C:\\Users\\
Mettre le résultat ici (code et figure).
import os
def repertoires(racine):
assert os.path.isdir(racine)
n = Noeud(racine, [])
for f in os.listdir(racine):
p = os.path.join(racine, f)
if os.path.isdir(p):
n.fils.append(repertoires(p))
return n
Pour chacun des petits documents XML ci-dessous, dire s'il est
bien formé.
Si ce n'est pas le cas, indiquer l'erreur.
1. <a></a>
2. <a>
<b></b>
<b></b>
</a>
3. <a>
<b></B> 7 | <bid=\"45\" ia=\"agr></b>
</a> </a>
4. <a>
<b>
</a>
5. <a></a>
<a></a>
6. <a>
<b id=\"45\" v='45'></b>
</a>
7. <a>
<b id=\"45\" id=\"48\"></b>
</a>
8.
<a>
<b id=\"45\"></b>
<b id=\"45\"></b>
</a>
Mettre le résultat ici (code et figure).
1. Correct.
2. Correct.
3. Incorrect, la balise fermante n’est utilise une majuscule.
4. Incorrect, il manque une balise fermante.
5. Incorrect, il y a deux balises racines.
6. Correct.
7. Incorrect, il y a deux attributs avec la même valeur.
8. Correct.
A l'aide du module DOM, écrire une fonction récursive compte_balise(d, n) qui prend en argument un nœud DOM d et un nom de balise n et qui renvoie le nombre de nœuds ayant ce nom dans le document.
Tester avec :
import xml.dom.minidom as dom
doc1 = dom.parse(\"fichier.xml\")
print(\"nb balises :\",compte_balise(doc1,\"libelle\"))
Résultat :
25
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
On utilise une variante de la fonction tailleDOM.
def compte_balise(d,n):
if d.nodeName == n :
t = 1
else:
t = 0
for c in d.childNodes:
t += compte_balise(c, n)
return t
A l'aide du module DOM, écrire une fonction récursive stat_xml(d) qui prend en argument un nœud DOM d et renvoie le triplet (e,a,t) constitué du nombre e d'éléments, a d'attributs et t de textes.
Tester avec :
import xml.dom.minidom as dom
doc1 = dom.parse(\"fichier.xml\")
print(stat_xml(doc1,(0,0,0)))
Résultat :
(146, 90, 291)
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
def stat_xml(d,n):
if d.nodeType == dom.Node.TEXT_NODE:
t=1
else:
t = 0
if d.nodeType == dom.Node.ELEMENT_NODE:
e= 1
a = len(d.attributes)
else:
e = 0
a = 0
for c in d.childNodes:
(ne, na, nt) = stat_xml(c,(e,a,t))
e += ne
a += na
t += nt
return (e, a, t)
Attention, lors des tests, les espaces et retours à la lignes ajoutés pour in-
denter le document XML sont aussi des nœuds texte.
A l'aide du module DOM, écrire une fonction gen_doc(n) qui prend en argument un entier n et génère un document XML de Ia forme :
<a><b>0</b><b>1</b>...<b>n — 1</b></a>
et sauve ce document dans un fichier docn.xml.
Tester avec :
import xml.dom.minidom as dom
gen_doc(100)
Une fois la fonction exécuter, ouvrir le fichier doc100.xml et vérifier que la structure est correcte.
Mettre le résultat ici (code et figure).
def gen_doc(n):
doc = dom.parseString(\"<a></a>\")
a = doc.childNodes[0]
for i in range(n):
b = doc.createElement(\"b\")
t = doc.createTextNode(str(i))
b.appendChild(t)
a.appendChild(b)
with open(\"doc\" + str(n) + \".xml\", \"w\") as f:
f.write(doc.toxml())
A l'aide du module ETREE, écrire une fonction gen_doc2(n) qui prend en argument un entier n et génère un document XML de Ia forme :
<a><b>0</b><b>1</b>...<b>n — 1</b></a>
et sauve ce document dans un fichier docn1.xml.
Indication : Il faut utiliser les méthodes suivantes pour copier le fichier xml:
tree = ET.ElementTree(a)
tree.write('doc'+str(n)+'1.xml', xml_declaration=True, encoding=\"utf-8\")
Tester avec :
import xml.etree.ElementTree as ET
gen_doc2(100)
Une fois la fonction exécuter, ouvrir le fichier doc1001.xml et vérifier que la structure est correcte.
Mettre le résultat ici (code et figure).
def gen_doc2(n):
a = ET.Element('a')
for i in range(n):
b = ET.SubElement(a, 'b')
b.text = str(i)
tree = ET.ElementTree(a)
tree.write('doc'+str(n)+'1.xml', xml_declaration=True, encoding=\"utf-8\")
gen_doc2(100)
Écrire un programme hello_json.py qui charge un fichier JSON config.json contenant un dictionnaire à deux entrées. Une entrée \"mode\" contenant la chaîne \"bonjour\" et une entrée \"nom\" contenant un nom de personne (par exemple \"Toto\").
Le programme affiche ensuite «bonjour Toto».
Attention, le fichier config.xml doit contenir les éléments suivants :
{\"mode\":\"bonjour\",\"nom\":\"Toto\"}
Tester avec :
import json
print(config[\"mode\"], config[\"nom\"])
Résultat :
bonjour Toto
Mettre le résultat ici (code et figure).
with open(\"config.json\") as f:
config = json.load(f)
Indications : Regarder la structure de fichier.xml pour l'analyser et choisir ses attributs en conséquences.
Mettre les différents éléments dans un dictionnaire.
Comparer la taille du fichier.xml et du fichier.json. Conclure sur l'avantage du format JSON par rapport au XML.
","title":"Exercice","tagtitle":"h1"},{"edit":"Mettre le résultat ici (code et figure).
import xml.etree.ElementTree as ET
import json
#charger le fichier xml
doc = ET.parse(\"fichier.xml\")
root = doc.getroot()
dic = {}
for c in root:
if c.tag != 'question' :
dic[c.tag] = c.text
else :
sousdic = {}
tabRep = []
tabSol = []
for sc in c :
if sc.tag == \"libelle\" :
sousdic[sc.tag] = sc.text
else :
tabRep.append(sc.text)
sol = sc.attrib
tabSol.append(sol['sol'])
sousdic['reponse'] = tabRep
sousdic['sol'] = tabSol
quest = dic.get(\"question\")
if quest is None :
dic['question'] = []
dic['question'].append(sousdic)
else :
dic['question'].append(sousdic)
with open('fichier.json', 'w') as f:
json.dump(dic, f)
Le fichier.json contient un quizz sur Python.
A l'aide de ce fichier, écrire un programme qui réaliser le quizz.Indications :
Etape 1 : Charger le fichier.json
Etape 2 : Initialiser les variables bonnes_reponses et questions.
Etape 3 : Afficher les questions une à une.
Etape 4 : Afficher le libéllé.
Etape 5 : Afficher les réponses
Etape 6 : Traiter la réponse donnée par l'utilisateur.
Mettre le résultat ici (code et figure).
import json
#Charger le quizz au format json
with open(\"fichier.json\") as f:
quizz = json.load(f)
questions = quizz['question']
bonnes_reponses = 0
#Affichage des questions
for question in questions :
#Affichage du libéllé
print(question['libelle'])
i = 1
#affichage des réponses
for reponse in question['reponse'] :
print(i ,reponse )
i+=1
#traitement de la réponse
myrep = int(input(\"Answer the question ? \"))
solution = question['sol']
if solution[myrep-1] == 'true':
bonnes_reponses +=1
print(\"Yes\")
else :
print(\"No\")
print(\"Your score is : \",bonnes_reponses,\"/25\")
Dans cette api, l'utilisateur rentrera un nom de pays (Exemple France) et le programme ira chercher dans la base de donnée world.sql (Télécharger ici) les informations suivantes :
- Capitale
- Population
- Continent
- Surface du pays
- Espérance de vie
pour les afficher sur la page web.
Ces données sont transmise entre le serveur (serveur.py) et le client (index.html) au format json.
Vous utiliserons les 2 fichiers ci-dessous pour réaliser cette api :
index.html
<!DOCTYPE html>
<html>
<head>
<title>Front End</title>
<meta charset=\"utf-8\"/>
<script>
function miseAJourPage() {
//déclaration de l'objet contenant les données à envoyer.
var data = [];
var param1 = document.getElementById('param1').value;
var param2 = document.getElementById('param2').value;
data.push({
'param1' : param1,
'param2' : param2
})
data = JSON.stringify(data[0]);
//alert(data);
//declaration de l'objet pour la requete
var maRequete = new XMLHttpRequest();
//url du serveur
var url = \"cgi\";
//gestion de la reponse du serveur
maRequete.onreadystatechange = function () {
if (maRequete.readyState == 4) {
//affiche la réponse du serveur
//alert(maRequete.responseText);
//convertis la reponse du serveur en dictionnaire
var tabkeyvalue = JSON.parse(maRequete.responseText);
//remplis les id dans le body
for(var key in tabkeyvalue) {
//alert(key);
document.getElementById(key).innerHTML = tabkeyvalue[key];
}
}
}
//Choisir le type de requete
maRequete.open(\"POST\", url, true);
//Entête de la requete pour la méthode POST
maRequete.setRequestHeader(\"Content-Type\", \"application/json\");
//envoyer la requete au serveur
maRequete.send(data);
}
</script>
</head>
<body>
<div>
<label>Paramètre 1 : </label><input id=\"param1\" type=\"text\">
</div>
<div>
<label>Paramètre 2 : </label><input id=\"param2\" type=\"text\">
</div>
<div><input type=\"button\" value=\" Envoyer \" onclick=\"miseAJourPage()\"></div>
<!-- Ajouter les clés du json ici-->
<div>Capital : <span id=\"capital\"></span></div>
</body>
</html>
et serveur.py
import socketserver
import http.server
import logging
import urllib
import json
import mysql.connector as sgbd
#Entrer l'adresse IP du serveur ou le nom de domaine
HOST = \"217.182.207.90\" # ou \"domaine.com\"
#Le nom de la base de données
DATABASE = \"\" #changer le ? par le numero donnée par le professeur
#Le nom de l'utilisateur de la DB
USER = \"\"
# Le mot de passe de l'utilisateur
PASSWORD = \"\"
def requeteSQL(dic):
# Rentrer votre code ici
#connection à la SGDB
cnx = sgbd.connect(host=HOST, database=DATABASE, user=USER, password=PASSWORD)
print(\"Connecté à:\", cnx.get_server_info())
#recuperation du paramètre 1 du client
param1 = dic['param1']
#creation de la requete
c = cnx.cursor()
#A modifier
requete = \"\"\" SELECT city.name,countryinfo.population FROM country JOIN city , countryinfo
WHERE country.code = city.code
AND country.code = countryinfo.code
AND country.capital = city.ID
AND country.name = %s
\"\"\"
#Exécution de la requete
c.execute( requete , [ param1 ])
#Récupéaration du résultat dans un tableau
tab = c.fetchall()
print('tab=',tab)
#Récupération de la 1ère valeur du tab
tup = tab[0]
print(tup[0],tup[1])
cnx.close()
#retour du fichier json avec les éléments recherchés
#A modifier
return {'capital' : tup[0]}
####################################################
# Ne pas modifier
####################################################
PORT = 8000
class ServerHandler(http.server.SimpleHTTPRequestHandler):
def _set_headers(self):
self.send_response(200)
self.send_header('Content-type', 'application/json')
self.end_headers()
def do_GET(self):
logging.error(self.headers)
http.server.SimpleHTTPRequestHandler.do_GET(self)
def do_POST(self):
\"\"\" response for a POST \"\"\"
#traite le message du client
length = int(self.headers['content-length'])
messageRecu = json.loads(self.rfile.read(length))
print(\"message reçu :\",messageRecu)
messageEnvoyer = requeteSQL(messageRecu)
print(\"message envoyé :\",messageEnvoyer)
#renvoie un message json au client
self._set_headers()
self.wfile.write(bytes(json.dumps(messageEnvoyer),'utf-8'))
Handler = ServerHandler
httpd = socketserver.TCPServer((\"\", PORT), Handler)
print(\"Adresse : http://localhost:\"+str(PORT))
httpd.serve_forever()
Pour réaliser cette api, suivrez les étapes suivantes :
Etape 1 : Copier les 2 fichiers dans le même répertoire.
Etape 2 : Lancer serveur.py
Etape 3 : Analyser le code des 2 pages.
Etape 4 : Aller à l'adresse internet indiqué par le programme.
Etape 5 ; Rentrer dans paramètre 1: France et cliquer sur envoyer.
Etape 6 ; Compléter le code coté serveur pour mettre en forme (json) les informations demandées sur le pays.
Etape 7 : Compléter index.html pour afficher les informations envoyé par le serveur.
Format de la table countryinfo :
Table countryinfo |
` ( code, le code du pays indepyear, date indépendance pays region, la région ou se situe le pays continent, le continent ou se situe le pays surfaceArea, la surface du pays `governmentForm, le régime du pays `population lifeExpectancy, l'espérance de vie du pays |
Mettre le résultat ici (code et figure).