Thèse Ali Aïtelhadj UMMTO Tizi-Ouzou

Ministre de lEnseignement Suprieur et de la Recherche Scientifique UNIVERSITE MHAMED BOUGUERRA - BOUMERDES

FACULTE DES SCIENCES

DEPARTEMENT DINFORMATIQUE

THESE DE DOCTORAT

Spcialit : INFORMATIQUE

Prsente par :

AT EL HADJ ALI

Thme

Modle de reprsentation et dappariement de documents XML selon une indexation

structurelle

Soutenue le 10 / 12 / 2011

Devant le jury compos de :

Mr Ahmed Nacer Mohamed; Professeur, U.S.T.H.B, Alger; Prsident

Mme Alimazighi Zaia; Professeur, U.S.T.H.B, Alger; Examinatrice

Mr Hacid Mohand Said; Professeur; Universit Claude Bernard, Lyon 1; Examinateur

Mr Boughanem Mohand; Professeur; Universit Paul Sabatier, Toulouse; Co-encadreur

Mr Mezghiche Mohamed; Professeur; UMBB, Boumerdes; Encadreur

RsumCe travail est motiv par la construction dun modle de reprsentation et dapparie-

ment de documents XML. Notre approche consiste reprsenter chaque document XMLpar sa structure et utiliser celle-ci comme modle de reprsentation en vue de la clas-sication structurelle du document XML correspondant. La classication structurelle apour rle de regrouper des documents XML structurellement similaires dans des clusters(ou classes). Ceci aiderait, dune part, mieux organiser les documents XML et, dautrepart, mieux rpondre, en termes decience et decacit, aux requtes contenant desconditions structurelles. Lide est que, si les documents partagent des structures simi-laires, ils sont plus mme de correspondre la partie structurelle dune mme requte.Par ailleurs, une nouvelle mesure de similarit qui prend en considration certaines rela-tions hirarchiques entre les nuds de chaque structure arborescente ainsi quun nouvelalgorithme de clustering (classication non supervise), ont t proposs. Pour validernotre approche, des exprimentations ont t menes sur deux collections XML. A ceteet, nous avons utilis le corpus rel ACM SIGMOD Record et une collection XML syn-thtique, qui nous ont permis dvaluer la performance de notre algorithme de clusteringet la abilit de notre modle de reprsentation, ainsi que lecacit de notre mesure desimilarit. Ces dirents tests ont montr lintrt de notre approche.

AbstractThis work is motivated by the construction of a model for representing and match-

ing XML documents based on their structure. Our approach is two-step. We rst automat-ically extracted the structure from each XML document to be classied. This extractedstructure is then used as a representation model to classify the corresponding XML doc-ument. The structural classication consists in grouping similarly structured XML docu-ments in classes (or clusters). This would help to better organize XML documents on theone hand and, on the other hand, to better answer, in terms of eciency and eectiveness,queries containing structural conditions. The idea behind the classication is that if XMLdocuments share similar structures, they are more likely to correspond to the structuralpart of the same query. Furthermore, an algorithm for unsupervised classication (or clus-tering) and a similarity measure that takes into account certain hierarchical relationshipsbetween nodes of each tree structure have been proposed. To validate our approach, ex-periments were conducted on two XML collections. To this end, we used both real (ACMSIGMOD Record corpus) and synthetic XML collection, which allowed us to evaluate theperformance of our clustering algorithm, the reliability of our representation model, andthe eectiveness of our similarity measure. These tests have shown the viability of ourapproach.

i

. LMX

. LMX . LMX

LMX .

.

. (. )

LMX. domgiS MCA LMX

. LMX . .

RemerciementsJe remercie trs respectueusement et trs sincrement, Mr Mohamed Ahmed Nacer,

Professeur au dpartement dInformatique, USTHB (Alger), davoir accept, sans dtour,de prsider ce jury. Quil trouve ici lexpression de ma profonde gratitude.

Que Mme Zaia Alimazighi, Professeur au dpartement dInformatique et Doyenne dela Facult dElectronique et dInformatique, USTHB (Alger), trouve ici lexpression demon profond respect. Je la remercie trs sincrement davoir rpondu favorablement, trsrapidement, pour honorer ce jury.

Je voudrais galement adresser mes vifs remerciements Mr Mohand Said Hacid, Pro-fesseur lUniversit Claude Bernard de Lyon, davoir accept trs gentiment de donnerson accord et, tout particulirement, de stre dplac pour la circonstance. Cest avec unimmense plaisir que je laccueille dans mon jury.

Et bien sr, cette soutenance est aussi pour moi loccasion pour ritrer ma profondereconnaissance mon codirecteur de thse, Mr Mohand Boughanem, Professeur lIRIT,Universit Paul Sabatier de Toulouse, pour mavoir permis de travailler ses cts, enacceptant de maccueillir au sein de son quipe durant les deux stages effectus lIRIT.Ses conseils judicieux et ses remarques pertinentes, mont fortement et favorablement ins-pir, et aid tout au long de cette thse. Quil sache que je ne suis pas rest insensible la grande confiance quil a place en moi, en me laissant une large marge de manuvredans mes investigations.

De mme, je dirais un grand merci mon directeur de thse, Mr Mohamed Mezghiche,Professeur lUMBB (Boumerdes), davoir accept de mencadrer. Malgr les contraintesgographiques, il a su tre lcoute de mes proccupations, en maidant me ressaisirdans des moments de doute et de lassitude, par ses prcieux encouragements et son grandoptimisme, dont lui seul, connait le secret. Quil trouve ici lexpression de ma profondegratitude.

Jaimerais tout particulirement dire Mr Mohand Sad Souam, Professeur lUni-versit Paris Ouest Nanterre La dfense que, je noublierai pas laide apprciable quilma apporte. Quil trouve ici, lexpression de mon profond respect et le remercie trsfraternellement pour lintrt constant quil na cess de tmoigner mon gard durantces quatre longues annes de thse.

Enfin, je ne saurais clore ce volet sans adresser toute mon affection et mon admiration mon pouse, pour avoir non seulement support mes humeurs durant ces quatre ans,mais galement, pour avoir particip activement laboutissement de ce travail de thse.

iii

Table des matires

Introduction gnrale

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1Contexte de travail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1Problmatque . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4Plan du rapport de thse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1Prsentation de XML 9

1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.2 Historique des langages de balisage . . . . . . . . . . . . . . . . . . . . . . 10

1.2.1 Gense des langages de balisages . . . . . . . . . . . . . . . . . . . 101.2.2 Langages de balisage . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.3 Spcification XML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.4 Dfinition dun document XML . . . . . . . . . . . . . . . . . . . . . . . . 131.5 Type de document . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141.6 Document bien form, document valide . . . . . . . . . . . . . . . . . . . . 151.7 Association dune DTD un document XML . . . . . . . . . . . . . . . . . 151.8 XML-Schema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181.9 Quest ce que le parsing en XML? . . . . . . . . . . . . . . . . . . . . . . . 181.10 DOM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191.11 SAX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211.12 Fichiers XML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2Indexation de linformation structurelle de documents XML 23

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

v

Table des matires

2.2 Le processus dindexation . . . . . . . . . . . . . . . . . . . . . . . . . . . 232.3 Approches dindexation de linformation structurelle de documents XML . 26

2.3.1 Dfinitions prliminaires . . . . . . . . . . . . . . . . . . . . . . . . 262.3.2 Indexation base sur les sous-arbres frquents . . . . . . . . . . . . 292.3.3 Indexation base sur les arbres et rsums darbres . . . . . . . . . 322.3.4 Indexation base sur les vecteurs structurs . . . . . . . . . . . . . 342.3.5 Indexation base sur les chemins (paths) . . . . . . . . . . . . . . . 352.3.6 Indexation base sur les niveaux . . . . . . . . . . . . . . . . . . . . 372.3.7 Indexation base sur les bitmaps . . . . . . . . . . . . . . . . . . . 38

3Classsification 41

3.1 Inroduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413.2 Notion de classe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413.3 Dfinition formelle de la classification . . . . . . . . . . . . . . . . . . . . . 433.4 Le ranking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443.5 Le clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453.6 Contextes de classification . . . . . . . . . . . . . . . . . . . . . . . . . . . 453.7 Paramtres dvaluation des performances dun systme de classification . . 473.8 valuation dun classifieur bi-classe . . . . . . . . . . . . . . . . . . . . . . 483.9 valuation de classifieurs multi-classes . . . . . . . . . . . . . . . . . . . . 503.10 valuation dun systme de clustering . . . . . . . . . . . . . . . . . . . . . 52

4Classification structurelle de documents XML 55

4.1 Inroduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554.2 Mthodes spcifiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 564.3 Approches de classification structurelle de documents XML . . . . . . . . . 574.4 Approche des arbres frquents . . . . . . . . . . . . . . . . . . . . . . . . . 614.5 Approche des rsums darbres . . . . . . . . . . . . . . . . . . . . . . . . 63

4.5.1 Dfinitions prliminaires et notions de base . . . . . . . . . . . . . . 654.5.2 Calcul de la distance ddition . . . . . . . . . . . . . . . . . . . . . 68

4.6 Approche des DTDs : cas Xclust . . . . . . . . . . . . . . . . . . . . . . . . 714.6.1 Reprsentation des DTDs . . . . . . . . . . . . . . . . . . . . . . . 714.6.2 Calcul de la similarit . . . . . . . . . . . . . . . . . . . . . . . . . 73

vi

4.7 Approche des bitmaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 774.8 Approche des noyaux darbres (tree kernels) . . . . . . . . . . . . . . . . . 81

5Modle de clustering incrmental bas sur des rsums darbres 85

5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 855.2 Classification base sur la similarit structurelle . . . . . . . . . . . . . . . 86

5.2.1 Prsentation gnrale de lapproche . . . . . . . . . . . . . . . . . . 865.2.2 Extraction du rsum darbre structurel . . . . . . . . . . . . . . . 875.2.3 Approche de clustering . . . . . . . . . . . . . . . . . . . . . . . . 895.2.4 Similarit structurelle . . . . . . . . . . . . . . . . . . . . . . . . . . 91

6Exprimentation 97

6.1 Implmentation du systme de classification . . . . . . . . . . . . . . . . . 976.1.1 Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 976.1.2 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

6.2 Collections XML utilises . . . . . . . . . . . . . . . . . . . . . . . . . . . 976.3 Mtriques dvaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

6.3.1 F-mesure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 986.3.2 Puret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 986.3.3 Entropie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

6.4 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1006.4.1 Mesure des performances du clustering . . . . . . . . . . . . . . . . 1006.4.2 Mesure de similarit propose vs. distance ddition . . . . . . . . . 1026.4.3 Intert de la reprsentation des documents XML par des rsums

darbres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1066.4.4 Comparaison de nos rsulats avec ceux obtenus avec dautres m-

thodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1096.4.5 Exprience de timing . . . . . . . . . . . . . . . . . . . . . . . . . . 110

Conclusion gnrale 113

1 Mthode propose vs. tat de lart . . . . . . . . . . . . . . . . . . . . . . . 1132 Conclusion et perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

vii

Table des matires

Publications dans le cadre de la thse 117

Bibliographie 119

viii

Table des figures

1.1 Document XML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.2 Document XML une autre version . . . . . . . . . . . . . . . . . . . . . . . 121.3 Structure arborescente dune page XML . . . . . . . . . . . . . . . . . . . 131.4 Page XML avec attributs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141.5 Document XML dcrivant une famille . . . . . . . . . . . . . . . . . . . . . 161.6 Document XML dcrivant une personne . . . . . . . . . . . . . . . . . . . 181.7 XML-Schema associ au document XML de la FIGURE 1.6 . . . . . . . . . 181.8 Modle darbre DOM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191.9 Document XML dcrivant un tudiant . . . . . . . . . . . . . . . . . . . . 201.10 Modle darbre DOM du document de la FIGURE 1.9 . . . . . . . . . . . . 20

2.1 Inclusion stricte exacte ordonne . . . . . . . . . . . . . . . . . . . . . . . 272.2 Inclusion stricte exacte non ordonne . . . . . . . . . . . . . . . . . . . . . 272.3 Inclusion stricte ordonne non exacte . . . . . . . . . . . . . . . . . . . . . 272.4 Inclusion stricte non ordonne non exacte . . . . . . . . . . . . . . . . . . . 282.5 Inclusion stricte faible non ordonne, non exacte . . . . . . . . . . . . . . . 282.6 Inclusion non stricte, mais exacte et ordonne . . . . . . . . . . . . . . . . 282.7 Un document XML simple et larbre des balises associ [95] . . . . . . . . . 292.8 Arbre frquent selon linclusion stricte exacte ordonne . . . . . . . . . . . 302.9 Arbre frquent selon linclusion stricte exacte et ordonne indirecte . . . . 312.10 Arbre frquent selon linclusion stricte ordonne non exacte . . . . . . . . . 312.11 Arbre frquent par subsumption (inclusion stricte non ordonne non exacte) 322.12 Extraction darbres frquents selon la subsumption [95] . . . . . . . . . . . 322.13 Extraction de rsums darbres [27] . . . . . . . . . . . . . . . . . . . . . . 332.14 Approche de reprsentation dun document XML [5,6] . . . . . . . . . . . 332.15 Arbre XML bas sur les notations SVM . . . . . . . . . . . . . . . . . . . . 352.16 Modle SVM dun arbre XML . . . . . . . . . . . . . . . . . . . . . . . . . 352.17 Document test.xml [102,103] . . . . . . . . . . . . . . . . . . . . . . . . . . 362.18 Arbre XML (avec contenu) associ au document de la FIGURE 2.17 . . . . 372.19 Exemple dindexation base sur les niveaux des arbres . . . . . . . . . . . . 382.20 Exemple de documents XML . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.1 Exemple de systme de classification demails [30] . . . . . . . . . . . . . . 423.2 Diffrents types de mthodes de classification . . . . . . . . . . . . . . . . 46

ix

Table des figures

4.1 Extraction de rsums darbres selon [27] . . . . . . . . . . . . . . . . . . . 584.2 Extraction de sous-arbres frquents selon [95] . . . . . . . . . . . . . . . . 584.3 Approche de dtection de sous-arbres frquents [30] . . . . . . . . . . . . . 624.4 Rsums darbres selon lapproche [27] . . . . . . . . . . . . . . . . . . . . 634.5 Rsums darbres selon lapproche [5] . . . . . . . . . . . . . . . . . . . . . 644.6 Inclusion stricte ordonne non exacte . . . . . . . . . . . . . . . . . . . . . 644.7 Oprations ddition sur deux arbres T1 et T2 . . . . . . . . . . . . . . . . 664.8 Graphe ddition pour comparer les squences A et B . . . . . . . . . . . . 674.9 Graphe ddition pour comparer les arbres A et B . . . . . . . . . . . . . . 674.10 Calcul de la distance ddition (version Chawathe) [20] . . . . . . . . . . . 684.11 Squence doprations ddition pour transformer T1 en T2 . . . . . . . . . 704.12 Calcul de la distance ddition (version Dalamagas) [27] . . . . . . . . . . . 704.13 DTD dcrivant des articles . . . . . . . . . . . . . . . . . . . . . . . . . . . 714.14 Reprsentation en arbre de la DTD de la FIGURE 4.13 . . . . . . . . . . . 724.15 Contextes utiliss dans XClust [57] . . . . . . . . . . . . . . . . . . . . . . 744.16 Exemple de document XML . . . . . . . . . . . . . . . . . . . . . . . . . . 774.17 Exemple de documents XML . . . . . . . . . . . . . . . . . . . . . . . . . . 784.18 Noyau darbre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

5.1 Approche de classification structurelle . . . . . . . . . . . . . . . . . . . . . 865.2 Approche de representation dun document XML . . . . . . . . . . . . . . 875.3 Algorithme dextraction dun rsum darbre XML . . . . . . . . . . . . . 885.4 Un document XML et son rsum darbre structurel . . . . . . . . . . . 895.5 Algorithme de clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 905.6 Algorithme de calcul de la similarit . . . . . . . . . . . . . . . . . . . . . 93

6.1 Distance de Levenshtein . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1036.2 Comparaison de deux arbres XML . . . . . . . . . . . . . . . . . . . . . . . 1046.3 Courbe de la prcision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1086.4 Courbe du rappel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1096.5 Courbe de la F-mesure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1096.6 Rsulats de timing avec les hauteurs h dans lintervalle [5,10] : O(N2h2) . . 1116.7 Rsulats de timing avec la hauteur h = 1 : O(N2) . . . . . . . . . . . . . . 111

x

Liste des tableaux

2.1 Tableau rcapitulatif des types dinclusion voqus . . . . . . . . . . . . . . 282.2 Notations utilises pour le SVM (arbre et/ou vecteur) . . . . . . . . . . . . 342.3 Les paths (chemins) de longueur 3 avec leurs frquences respectives . . . . 372.4 Un index bitmap des documents XML de la FIGURE 2.20 . . . . . . . . . . 39

3.1 Matrice de contingence [30] . . . . . . . . . . . . . . . . . . . . . . . . . . 49

4.1 Rgles de transformation dun arbre DTD . . . . . . . . . . . . . . . . . . 734.2 Table des similarits cardinales . . . . . . . . . . . . . . . . . . . . . . . . 744.3 Matrice de similarit ontologique . . . . . . . . . . . . . . . . . . . . . . . 754.4 Un index bitmap de la FIGURE 4.17 . . . . . . . . . . . . . . . . . . . . . . 784.5 Un index bitmap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 804.6 Un index bitmap aprs dcalage des colonnes (epaths) populaires gauche 814.7 Index bitmap partitionn en deux avant llimination des bits 0 . . . . . . 814.8 Index bitmap de la TABLE 4.6 partitionn . . . . . . . . . . . . . . . . . . 814.9 Noyeau : reprsentation du 2-spectrum Kernel . . . . . . . . . . . . . . . . 824.10 Matrice des noyeaux dans lespace du 2-spectrum kernel . . . . . . . . . . . 82

6.1 Repartition du corpus ACM SIGMOD . . . . . . . . . . . . . . . . . . . . 986.2 Nombres de clusters gnrs avec leurs effectifs pour chaque seuil . . . . 1016.3 Resultats du test de clustering . . . . . . . . . . . . . . . . . . . . . . . . . 1016.4 Mesure propose vs. distance ddition (clustering et timing) . . . . . . . . 1046.5 Mesure de similarit propose vs. distance ddition (rsultats de clustering)1056.6 Repartition du sous-ensemble du corpus ACM SIGMOD . . . . . . . . . . 1066.7 Rsums darbres XML vs. arbres XML originaux . . . . . . . . . . . . . . 1076.8 Rsums darbres XML vs. arbres XML originaux (P , R et F1) . . . . . . . 1076.9 Comparaison de nos rsultats avec ceux de [20,27,74,94] . . . . . . . . . . 110

xi

Introduction gnrale

IntroductionInternet est la mise en rseau mondiale des ordinateurs, constituant un nouvel es-

pace social dchanges en perptuelle expansion, permettant ainsi diffrents utilisateursde communiquer par courrier lectronique, de publier des informations sur le Web, detransfrer des donnes, de travailler distance, de discuter par forums ou messageries ins-tantanes, etc. En effet, le Web est considr aujourdhui comme une gigantesque sourcedinformations et de connaissances, trs diversifie et en pleine expansion. Le nombre dedocuments qui y sont dissmins est dune dimension effarante, le nombre de sites r-pondant des besoins trs varis, est dune immensit telle que des annes entires nesuffiraient jamais les consulter, pas mme les visiter, dans leur globalit. Par ailleurs,le nombre demails envoys chaque anne, galerait en volume dinformation les environsdu 12 million de traoctets ; et la masse totale en information, rien que pour la seule an-ne 2002, ne serait pas loin du million de traoctets [85]. Aujourdhui, il y a 3,4 millionsdemails qui sont envoys dans le monde, chaque seconde, soit 107 billions (107 000 mil-liards) par an, dont plus des 34 sont des Spams [79].Ces chiffres abstraits, si on essayait de les ramener la ralit des objets de la vie courante,on se rend mieux compte de leur ampleur et de lextrme complexit quils dissimulent.1 traoctet, soit 1012 octets, approcherait les environs de 700.000 ouvrages de 400 pagesde format A4. Lnormit et la varit des volumes dinformations stockes et diffusessur les rseaux sont une premire justification de la ncessit de dvelopper des outilsadquats pour leur gestion [4].

Contexte de travailLes collections de documents ont considrablement volu ces dernires annes. Tandis

quon distinguait traditionnellement nettement deux types de donnes : les donnes forte-ment structures prises en charge par la communaut des BD (Bases de Donnes), et lesdonnes non structures (texte) prises en charge par la communaut de la RI (RecherchedInformation). Aujourdhui, les donnes dites semi-structures ouvrent une troisime voiedans la gestion de linformation, car offrant un bon compromis et un format dchangeentre diffrentes applications pour lintgration de donnes en provenance de sources ht-rognes. Avec cette tendance, acclre notamment par lexpansion du Web, les documentssemi-structurs de type HTML (HyperText Markup Language) ou XML (eXtensible Mar-

1

Introduction gnrale

kup Language), sont sur le point de former la majorit des documents numriques mis disposition des utilisateurs.Afin dexploiter au mieux lensemble de ces informations, les modles conventionnels exis-tants de RI [85] doivent tre tendus ou bien de nouveaux modles doivent tre proposs.Nous nous plaons dans le contexte de la RI. Plus prcisment, cest dans le cadre de la RIS(Recherche dInformation Structure), que se situe notre travail. Notre objectif consistedabord proposer un modle de reprsentation de documents XML et ensuite utilisercette reprsentation comme modle pour tablir une classification de ces documents. Nousavons particulirement orient notre investigation sur un modle de classification struc-turelle non supervise. A cet effet, nous nous intressons aux documents semi-structursXML du point de vue structurel. Nous nous focalisons donc plus spcialement sur leurscomposantes structurelles, cest--dire les structures arborescentes dont les nuds sontles balises et attributs qui dfinissent les structures logiques de ces documents.

ProblmatiqueContrairement aux documents plats (textuels) qui sont par nature non structurs

et aux bases de donnes qui sont caractrises par des donnes simples et des structuresfortes, les documents XML se prsentent comme une alternative caractrise par un doubleaspect. Dune part, ce format possde les caractristiques de structures fortes, permettantainsi de bonnes performances daccs et de stockage, et un traitement de linformationtextuelle par les SRI avec une autre granularit que le document tout entier. Dautre part,il permet de dlimiter des donnes de type htrogne (texte ou multimdia), qui sont parnature des donnes non structures [30, 85].Cependant, avec les outils actuellement disponibles, la recherche dinformations dans cetype de documents est une tche non triviale. Les documents XML sont caractriss parun contenu (du texte) et une structure (balises). Ce type de documents ne peut cependanttre exploit efficacement par les mthodes conventionnelles de RI. En effet, ces derniressont bases sur des modles orients contenu, tandis que le format XML permet dajouterdes contraintes structurelles (balises). De mme, les approches traditionnelles de traite-ment des donnes telles que les bases de donnes relationnelles se sont avres inefficaces.Celles-ci sont principalement ddies la gestion des donnes fortement structures, alorsque les documents XML sont classs dans la catgorie des donnes semi-structures [36].En somme, lutilisation de plus en plus croissante de ce nouveau format sur le Web, asoulev un certain nombre de questions, lies linterrogation, lindexation [23,42,47,59,65, 73, 80, 85, 107, 115], et/ou la classification [3, 7, 1214, 16, 27, 30, 32, 36, 37, 44, 46, 57, 70,72,74,89,112,122], de ces documents.

La classification a pour rle de regrouper des documents XML similaires dans desclusters (ou classes), afin de rduire le temps de rponse et augmenter la prcision desmoteurs de recherche. Cette classification peut tre thmatique ou structurelle. Dans cettethse nous nous intressons particulirement la classification de documents XML sur labase de leur similarit structurelle. Cette similarit permettra de regrouper des documentsXML partageant les mmes structures. Ceci aiderait, dune part, mieux organiser ces

2

documents et, dautre part, mieux rpondre, en termes defficience et defficacit, auxrequtes contenant des conditions structurelles. Notons que dans la RIS avec XML, lesrequtes peuvent tre formules en utilisant des mots cls seulement ou des mots cls etdes conditions structurelles. En bref, cette classification vise regrouper les documentsXML structurellement similaires afin dacclrer le processus de recherche dinformation.En effet, la recherche dune information pertinente dans une grande collection, revientalors interroger des classes de taille rduite. Ceci est bas sur lide que si des docu-ments XML partagent des structures similaires, ils sont plus mme de correspondre la partie structurelle dune mme requte.

Notre problmatique de classification se situe donc essentiellement au cur de linfor-mation structurelle. A cet effet, les questions primordiales que nous aborderons sont :

Comment regrouper structurellement des documents XML quand leur DTD (Docu-ment Type Definition) nest pas connue ?

Comment peut-on mesurer leur similarit structurelle ?Cette similarit soulve dautres questions lies notamment au degr de similarit desstructures, en particulier : A partir de quel seuil de similarit pourrait-on considrer quedeux documents sont structurellement similaires ?

Une problmatique vidente et rcurrente concerne les duplications des lments XML.La question est Comment doit-on traiter ces duplications ?Considrons titre dexemple les squences abstraites abbbc, abc et abbbbbbbc.Alors, si ctait en RI classique avec des documents plats o les b sont des mots, la solu-tion serait de pondrer par exemple b sa frquence dapparition dans le document. Enrevanche, en RIS avec des documents semi-structurs comme XML, de nouvelles consid-rations peuvent entrer en jeu. En effet, de par la structure hirarchique de ces documents,le mot b constituant un nud de la structure, peut se dupliquer plusieurs niveaux et, ce titre, diffrents cas peuvent se prsenter. Dans le cas o la duplication de b concernedes nuds frres, elle doit tre limine afin dobtenir abc comme structure cible mi-nimale reprsentative. Par consquent, les documents XML reprsents respectivementpar les squences abbbc, abc et abbbbbbbc peuvent tre considrs comme tantstructurellement similaires la squence abc. Mais si cette duplication apparait enprofondeur, il faut la conserver de sorte viter une perte dinformation. En effet, lasuppression de duplications en profondeur entraine systmatiquement la destruction dela hirarchie de la structure et, de ce fait, produit des rsultats incohrents vis--vis de laclassification structurelle envisage.

Une autre problmatique tout aussi importante que sensible concerne linclusion desstructures XML entre elles. En effet, si lon part du principe que la structure dun docu-ment peut tre incluse partiellement ou compltement dans celle dun autre document, ilconvient de caractriser cette inclusion. Il existe plusieurs types dinclusion qui ont plus oumoins un certain impact sur les similarits structurelles des documents correspondants et,en consquence, sur la classification structurelle qui en dcoule. Cette inclusion, quelle soitinduite, incruste ou une subsumption, elle a t utilise pour intgrer des sous-structuresfrquentes en vue de construire un (ou plusieurs) schma(s) mdiateur(s) XML [28, 95].

3

Introduction gnrale

Il y a des cas o lon favorise linclusion induite [28], afin de ne valider dans le processusdintgration que les sous-structures les plus frquentes rpondant linclusion induite,cest--dire des sous-structures de documents XML homognes. Dans dautres cas, cestsouvent la subsumption [95] qui est adopte, car elle est plus gnrale et permet, de cefait, de cibler des documents XML htrognes.

Considrons prsent la problmatique de la similarit structurelle qui a t abordede deux manires diffrentes :

Dans les approches de construction de schmas mdiateurs la problmatique a taborde en termes de dtection de sous-arbres (ou sous-structures) apparaissant suf-fisamment frquemment dans des corpus darbres. Un document XML est constitugnralement de plusieurs sous-arbres distincts mais un sous-arbre lui mme peutapparaitre au niveau de plusieurs documents XML. Autrement dit, au lieu de parlerde similarit directement entre structures compltes de documents XML, on parlede celle de leurs sous-structures.

La tche se prsente, par contre, diffremment dans les approches classiques de clas-sification. En effet, par exemple une structure s1 peut tre incluse dans une autrestructure s2, telle que la longueur de s1 soit nettement infrieure celle de s2. Alorsle problme est Comment doit-on dans ce cas mesurer leur similarit ? En dautrestermes : Doit-on tenir compte de la distance qui les spare ou bien occulter cettedernire ? Les rponses ces questions dpendent de plusieurs paramtres lis no-tamment la nature des corpus tudis, le domaine dapplication abord, etc. Il vadonc falloir que, toute mesure de similarit structurelle propose soit paramtrableet vite au maximum la perte dinformation.

Notons cependant que, quelle que soit la stratgie adopte, schma mdiateur ou clas-sification, la problmatique de comparaison de structures arborescentes est connue pourtre une tche caractrise souvent par des complexits algorithmiques particulirementleves. Toute tentative de rduction de ces complexits, sest gnralement solde parune perte dinformation. En effet, par exemple une classification darbres qui considreces arbres comme des vecteurs, prendrait videmment moins de temps sexcuter, maisaurait cependant moins de crdibilit vis--vis de la tche. Les relations hirarchiques sontperdues, et on se trouve comme dans le cas de documents plats.

ContributionNotre contribution consiste en plusieurs propositions et tente de rpondre aux ques-

tions souleves dans la section prcdente :1. Concernant lindexation de documents XML, nous proposons un modle de reprsen-

tation bas sur leur structure arborescente. Les nuds de la structure correspondentaux noms des balises (tags XML) et attributs apparaissant au niveau des lmentsdes documents XML considrs. Mais, afin de minimiser les traitements, les docu-ments XML sont reprsents par des rsums darbres. Autrement dit, ce nest pastoute linformation structurelle qui est utilise pour reprsenter structurellement un

4

document XML. Lide est que les rptitions des tags et/ou la possibilit davoirdes tags optionnels (et leurs sous-arbres par voie de consquence), sont parmi lesprincipales raisons qui font que des documents XML peuvent tre structurellementdiffrents mme sils partagent la mme DTD. Un rsum darbre peut alors treconsidr comme une structure arborescente gnrique dans le sens o lorsque lesnuds (tags) frres sont dupliqus, il nest pas ncessaire de rpercuter cette duplica-tion dans la structure reprsentative que nous voudrions obtenir. Notons cependantque par souci de non perte dinformation et de non destruction de la hirarchiede la structure XML, les duplications des nuds imbriqus ne sont pas limines.Dans le mme contexte, supprimer ou ignorer des attributs peut entrainer une pertedinformation. Alors un moyen de contourner cet inconvnient, serait de considrerles attributs comme des nuds descendants directs des lments auxquels ils sontrattachs dans les documents XML.

2. Concernant la similarit structurelle de ces documents, nous proposons une mesurede similarit qui prend en considration la hirarchie de la structure XML. A ceteffet, le calcul de la similarit entre deux termes (nuds) ncessite non seulementdutiliser un dictionnaire (quand il le faut), mais aussi, de considrer chaque nuddans son tendue contextuelle. Lide est que mme si deux nuds sont reprsentspar le mme nom ou des noms synonymes, cela nimplique pas quils demeurentncessairement identiques ou similaires dans le contexte de leurs anctres respectifs,qui peuvent tre compltement diffrents. Ainsi, la similarit de deux nuds dpendnon seulement de leur similarit ontologique (les termes peuvent tre similaires parcequils sont reprsents par la mme chaine de caractres, ou bien peuvent tre sy-nonymes, daprs le dictionnaire), mais aussi, de celle de leurs anctres respectifs.

3. Enfin, pour tendre notre modle de reprsentation de documents XML, nous pro-posons un algorithme de clustering (classification) qui consiste regrouper les do-cuments XML partageant la mme structure ou des structures similaires. Notrealgorithme est caractris par un certain nombre de points importants. En effet,notre clustering est incrmental et non supervis. De plus, contrairement au clus-tering classique, o le nombre de documents est fixe, dans notre cas, de nouveauxdocuments peuvent tre ajouts, et leur nombre dans un cluster est une fonction dutemps. Ainsi, notre clustering demeure ouvert et peut donc traiter de nouveaux do-cuments tout moment. Par ailleurs, notre clustering est caractris par la mobilitdes centrodes. Un centrode est larbre le plus pertinent reprsenter tous les arbresdun cluster, cest en quelque sorte, le centre de gravit du cluster. Cette mobilitgarantit un clustering de qualit, cest--dire augmente la similarit intra-clusterset diminuerait, par voie de consquence, la similarit inter-clusters. Une autre ca-ractristique intressante de ce clustering est le seuil de similarit que lon pourraitmodifier loisir en fonction des besoins.

Une consquence trs importante de ce modle est que, au del de la classification quiconstitue un des objectifs de cette thse, les clusters (ou classes) peuvent jouer le rledinterface avec un utilisateur et permettront ainsi un accs efficace aux documents XMLquils reprsentent.

5

Introduction gnrale

Pour valider exprimentalement lintrt de notre approche et vrifier la faisabilit despropositions qui la sous-tendent, nous avons ralis plusieurs types de tests. Les exp-riences ont t menes sur deux ensembles de donnes, savoir, une collection de docu-ments XML relle (ACM SIGMOD Record corpus), ainsi quune collection de documentsXML synthtique.

Le premier test effectu consiste utiliser certaines mtriques bien connues commela puret, lentropie et la F-mesure pour valuer les performances de notre clustering.

Le deuxime test consiste comparer la mesure de similarit propose la mesurede similarit base sur la distance ddition.

Le troisime test consiste vrifier la faisabilit et la fiabilit de notre approche dereprsentation des documents XML.

Le quatrime test a pour objectif de comparer nos rsultats avec ceux de certainesapproches existantes.

Enfin, un test de timing est effectu sur une collection synthtique de documentsXML et a permis de situer notre approche par rapport certains travaux existants.

La conclusion que lon peut tirer de cette exprimentation est que les performances denotre systme sont comparables aux meilleurs rsultats obtenus recemment [94] par lestravaux sur la classification structurelle de documents XML.

Plan du rapport de thseCe rapport est organis comme suit : Un rsum gnral (Rsum) dans lequel nous avons dfini le cadre de notre tra-

vail en montrant quelle est lapproche propose, ainsi que la dmarche suivie pouratteindre les objectifs assigns.

Une introduction (Introduction gnrale) dans laquelle on a dlimit le contextede notre tude et identifi les diffrentes problmatiques engendres par le formatXML, en nous focalisant particulirement sur la structure des documents XML. Nousavons ensuite mis en valeur les objectifs viss travers le modle de reprsentationde documents XML envisag. Nous avons dans ce contexte trac quelques brins depistes qui donnent une ide sur lobjectif principal assign. Nous avons au passagedonn un aperu gnral sur notre contribution dont la dmarche est dtaille auchapitre 5. Nous avons galement trac les grandes lignes de la mise en uvre etdes exprimentations ralises pour valider notre approche. Enfin, nous terminonspar le plan du rapport de thse.

Dans le premier chapitre (Prsentation de XML), nous avons commenc parune section introductive (1.1 Introduction), afin davoir une ide sur lvolutiondes donnes, et voir ainsi comment lon est pass de la catgorie des donnes nonstructures et fortement structures celle des donnes semi-structures. La section(1.2 Historique des langages de balisage) raconte un peu lhistoire des langages debalisage et les circonstances de la naissance de XML. Les sections (1.3 XML entant que spcification de base), (1.4 Structure dun document XML), (1.5 Type dedocument), (1.6 Document bien form, document valide), (1.7 Association dune

6

DTD un document XML) et (1.8 XML-Schema), sont consacres lessentiel surla spcification de base XML. Nous avons particulirement insist sur la notion deDTD (Document Type Definition), car elle couvre plus ou moins laspect structureldun document XML, chose qui intresse la problmatique que nous tudions danscette thse. Nous avons aussi expliqu la tche de parsing (1.9 Quest ce que leparsing ?), en nous appuyant sur lexemple classique dun compilateur et, au passage,nous avons dcrit succinctement les deux API (Application Programming Interface)existantes, en loccurrence le DOM (Document Object Model) (1.10 DOM) et SAX(Simple API for XML) (1.11 SAX). Enfin, nous avons montr (1.12 Fichiers XML),comment peut-on crer, modifier, sauvegarder un fichier ayant lextension .xml, etmis laccent sur le fait quun document XML possde une version texte exploitablesur nimporte quelle plate forme.

Dans le second chapitre (Indexation de linformation structurelle de docu-ments XML), nous avons prsent un tat de lart sur lindexation base sur lastructure des documents XML. Pour se placer dans le contexte (2.1 Introduction),nous avons au pralable montr lintrt de la structure dans le cadre de la classifica-tion structurelle de documents XML. En section 2 (2.2 Le processus dindexation),nous avons introduit quelques concepts de base sur lindexation afin de pouvoirsituer le modle dindexation envisage dans cette thse. Dans la section 3 (2.3Approches dindexation de linformation structurelle de documents XML), commeprconis, nous avons prsent les approches dindexation de linformation struc-turelle de documents XML. Nous nous sommes focaliss uniquement sur celles quiont t utilises dans le cadre de la classification structurelle ou de lintgration deschmas XML. Mais avant cela, nous avons introduit au pralable certains conceptset dfinitions utiles sur les arborescences.

Le troisime chapitre (Classification) a pour objectif de stendre sur la classifica-tion en gnral. Une premire section introductive (3.1 Introduction) met en avantlvolution de cette tche par rapport lvolution des besoins et met en exergue lesobjectifs viss travers la classification dans la RI. Les autres sections (3.2 Notionde classe), (3.3 Dfinition formelle de la classification), (3.4 Le ranking), (3.5 Le clus-tering) (3.6 Contextes de classification), expliquent certaines notions gnrales surla classification. Les autres sections (3.7 Paramtres dvaluation des performancesdun systme de classification), (3.8 valuation dun classifieur bi classes), (3.9 va-luation de classifieurs multi classes) et (3.10 valuation dun systme de clustering)sont consacres entirement ltude des mesures et danalyse des performances dessystmes de classification dans la RI.

Le quatrime chapitre (Classification structurelle de documents XML) donneun aperu sur la classification de documents semi-structurs en gnral et un tatde lart sur la classification structurelle de documents XML en particulier.

Le cinquime chapitre (Modle de clustering incrmental bas sur des rsu-ms darbres) a t consacr entirement la description de notre approche quiconsiste en plusieurs propositions : la reprsentation de documents XML base surleur structure, la mesure de leur similarit structurelle et, enfin, leur classificationsur la base de leur similarit structurelle.

Le sixime chapitre (Exprimentation) est ddi lexprimentation des diff-

7

Introduction gnrale

rentes propositions concernant notre apport dans cette thse. Enfin, une conclusion (Conclusion gnrale), o nous avons rcapitul les pointsessentiels de notre contribution en la situant par rapport certains travaux connexeset, en perspective, nous indiquons les pistes suivre pour le perfectionnement denotre approche.

8

Chapitre 1

Prsentation de XML

1.1 Introduction

Historiquement les donnes sur supports informatiques taient, soit des donnes simpleset bien structures, stockes dans des bases de donnes, soit des donnes purement tex-tuelles non structures, stockes dans des documents sous forme de fichiers format libre.Il tait alors nettement facile de distinguer entre deux principaux formats, en loccurrence,celui des donnes fortement structures qui est pris en charge par la communaut des BDet celui des donnes non structures, qui est pris en charge par la communaut de la RI.

Aujourdhui cependant, avec lapparition des donnes semi-structures de type HTMLou XML, les documents traditionnellement plats ne contenant que du texte senrichissentdinformation structurelle et dinformation multimdia [85]. A linverse des formats tra-ditionnels (donnes fortement structures et donnes non structures), le format XMLapparat comme un compromis offrant une solution raisonnable pour lintgration de don-nes en provenance de sources htrognes.

En effet, aujourdhui nous demandons nos documents dtre affichables sur nos PDA(Assistants Digitaux Personnels), dtre intgrs des bases de donnes ou dtre ma-nipuls par des applications spcifiques. De plus, non seulement les informations quilscontiennent sont rutilises, mais le volume de leurs changes saccrot continuellement.Les volumes dinformations que nous sommes appels traiter sont immenses, et ces in-formations ne peuvent plus tre lies une plate-forme spcifique. De la mme manireque Java a mis notre disposition un langage indpendant de toute plate-forme, nousavons galement besoin de la mme indpendance lorsquil sagit de lchange de donnes.XML nous en offre le moyen [34].

Lutilisation de plus en plus croissante de ce nouveau format sur le Web a provoqu uneexplosion dans le dveloppement doutils permettant notamment le stockage, lindexationet la recherche dinformation dans ce type de donnes. Cet engouement pour XML est ensoi un tmoignage et une premire justification de son efficacit pour la reprsentation etlchange de donnes sur lInternet.

9

Chapitre 1. Prsentation de XML

1.2 Historique des langages de balisage1.2.1 Gense des langages de balisages

Avant de prsenter les langages de balisages, il convient dabord de comprendre com-ment les donnes sont stockes et rcupres sur un ordinateur. A ce propos, on peutconsidrer lexemple de deux types de fichiers de donnes : les fichiers binaires et lesfichiers texte [43].

Fichier binaire

Dans sa forme la plus simple, un fichier binaire correspond des suites de bits. Cesdernires ne sont, en gnral, interprtables que par lapplication propritaire (celle quiles a gnres). Les codes insrs (invisibles laffichage du fichier source) sont considrscomme des mtadonnes (des donnes propos de donnes). Ces mtadonnes corres-pondent des instructions de mise en forme du genre : Cette sentence doit tre centre,Ce mot doit tre gras ou color, etc. Lavantage est quil est facile un ordinateur decomprendre ces codes binaires, quils peuvent tre traits plus vite, et quils sont parfaite-ment adapts au stockage de mtadonnes. Linconvnient est quil nest pas possible demodifier ce format en dehors de lapplication propritaire, ou dafficher ces fichiers sur desappareils diffrents comme des PDA. Il est mme parfois impossible douvrir un fichierbinaire cr par une application dans une autre, voire dans la mme, mais sur une autreplate-forme [43].

Fichier texte

Un fichier texte est form galement de suites de bits, mais sans adjonction dins-tructions de mise en forme (mtadonnes). Ces suites de bits sont regroupes de faonstandardise afin de reprsenter des nombres. Ces derniers sont mis en correspondanceavec les caractres quils sont censs reprsenter, en utilisant une table de codes ASCII. Lesfichiers texte peuvent alors tre lus par de nombreuses applications en utilisant un simplediteur de texte ou mme des bases de donnes. Il est galement possible de les manipuler laide de scripts [34]. Lavantage du format texte est quil a grandement contribu la monte en flche dadoption dInternet, notamment ses dbuts, et la gnralisa-tion dapplications comme le courrier lectronique, le World Wide Web, etc. Cependant,linconvnient avec le format texte, est quil est difficile dinsrer des mtadonnes. Parconsquent, il nest possible de sauvegarder ou de rcuprer ce type de fichier que sousforme de texte brut sans aucune autre mise en forme [43].

1.2.2 Langages de balisageLidal serait de possder un format combinant luniversalit du format texte avec

lefficacit et les puissantes capacits de stockage de formats binaires. Cette ide de luni-versalit des donnes nest pas nouvelle. En fait, depuis que les ordinateurs existent, lesprogrammeurs ont toujours tent de trouver des moyens pour changer des informationsentre diffrents programmes informatiques [43].

10

1.3. Spcification XML

SGML (Standard Generalized Markup Language), tant la premire tentative de com-binaison dun format de donnes universellement changeables avec une importante capa-cit de stockage dinformations. Historiquement, ce langage est issu dun projet dmarrchez IBM dans les annes 1970 par C. Goldfarb, E. Mosher et R. Lorie, avant dtrerejoint et dvelopp par de nombreuses quipes de travail, avant son adoption commestandard ISO-8879 en 1986. SGML correspond un langage de type texte conu pourtre un standard de balisage de donnes multi-usages et sest vite impos, essentiellementdans les gros systmes de gestion de documents. Cependant, lorsque dnormes quantitsde donnes sont concernes, une multitude de considrations entrent en jeu. Cela expliquelextrme complexit de ce langage [43].

Lapplication la plus populaire du SGML qui a connu un grand succs, est incon-testablement le langage HTML (HyperText Markup Language). Apparu en 1993, il estconsidr comme un langage universel de balisage destin particulirement laffichagedes informations, ainsi qu la liaison de diffrents morceaux dinformation. Initialementconu par Tim Berners-Lee au CERN (Conseil Europen pour la recherche Nuclaire), endcembre 1990 pour aider les chercheurs en Physique communiquer entre eux et avecles autres, est devenu par la suite le premier standard de dveloppement Web, en partiegrce sa simplicit dapprentissage. Il a notamment contribu au dveloppement rapidede linfrastructure technique ncessaire pour rendre efficace lInternet, rendant ainsi acces-sible de faon quasi instantane la plus gigantesque masse dinformations jamais ralise.Tout document HTML ou page Web, doit pouvoir tre prsent dans toute applicationcapable de comprendre HTML. Un navigateur Web recevant des pages HTML doit pou-voir interprter le code quelles contiennent. Autrement dit, un navigateur doit pouvoirafficher un document, mais si la page contient des liens hypertextes vers dautres docu-ments, il doit pouvoir les rcuprer avec facilit [15, 26, 43]. Cependant, avec lvolutiondes besoins, le HTML apparat comme une solution inadquate, de porte limite, car in-capable de satisfaire certaines exigences telles que la rutilisation dun document HTMLdans dautres formats (autres que HTML), lintgration et la connectivit aux bases dedonnes, ladaptabilit aux PDA ou tlphones mobiles, etc. ; sa seule fonction demeurelaffichage des informations dans un navigateur, et ne va pas au del.

XML (eXtended Markup language) a t cr, dune part, pour combler les limita-tions de HTML, dautre part, pour offrir une solution adquate ayant les mmes objectifsque SGML (balisage de tout type de donnes), dbarrasse toutefois de toute complexitsuperflue [15, 34, 43]. Lide de se servir du meilleur du HTML et du SGML a germ ausein du groupe de travail XML Working Group sous lgide de W3C (World Wide WebConsortium). XML a t mis au point ds 1996, la premire version XML 1.0, est apparueau mois de fvrier 1998, depuis, ses spcifications sont passes au stade de recommanda-tion. Aujourdhui, il est considr commme le format de rfrence de la publication et deschanges, et joue notamment un rle crucial dans la diffusion de documents sur Internet.

1.3 Spcification XMLXML offre une syntaxe de balisage qui permet de dfinir un langage, ce qui en fait

un outil capable de produire des documents primaires dont la structure conceptuelle se

11


prsente comme une suite hirarchique dlments enchsss les uns aux autres. En cons-quence, le document devient un ensemble dinformations structures, un conteneur din-formations plus quune unit de base, ce qui permet aux outils de gestion de se concentrersur le contenu du document plus que sur le document lui-mme, de mettre en relationle texte lui-mme et sa structure, puis dexploiter ces relations [43, 61]. La syntaxe deXML, dfinit un langage balises personnalisables permettant ainsi chaque utilisateurde concevoir ses propres balises. Ces dernires permettent de sparer le contenu de lamise en forme (structure) dans chaque document cr. En dautres termes, XML nestpas seulement un langage, mais un mtalangage, qui dcrit une syntaxe permettant chacun de crer ses propres langages [43].

Si lon considre par exemple le document XML de la FIGURE 1.1 , et sont les balises, elles correspondent linformation structurelle (ou la struc-ture) du document, tandis que la partie complmentaire correspond ce quon appelle,contenu. XML permet de dcrire ainsi le mme contenu dun document en adoptant, soitle format de la FIGURE 1.1, soit celui de la FIGURE 1.2. Cet exemple, aussi simple soit-il,nous permet de comprendre pourquoi les langages de balisage tels que SGML et XMLsauto dcrivent. En effet, en regardant les donnes de ces deux documents, on comprendrafacilement quil sagit dinformations propos dun , dun et dautresnommes , et . Il est possible dattribuer aux donnesnimporte quelle appellation, mais si on doit utiliser XML, autant le faire dans les rglesde lart, donner aux entits des noms significatifs [43]. Cette question a t aborde parlintroduction de certains vocabulaires XML spcifiques [4]. Parmi les applications XMLconcernes, nous pouvons citer MathML, VML, WML, PGML, etc.

Figure 1.1 Document XML

Figure 1.2 Document XML une autre version

12

1.4. Dfinition dun document XML

1.4 Dfinition dun document XMLUn document XML est compos dun corps (body) et, ventuellement, dun entte

(prologue), qui est la partie dclarative o sont rpertories les dclarations comme laversion, la DTD rfrence, ainsi que dautres types de dclarations. Cependant, il fautsignaler que, hormis la dclaration formelle dune DTD (lorsquelle existe), qui doit ap-paratre dans lentte (une seule fois uniquement), les autres dclarations, les instructionsetc., ne sont soumises aucune contrainte et, donc, peuvent apparatre nimporte quelniveau du document. XML laisse une grande libert aux utilisateurs de crer leurs docu-ments comme ils le souhaitent, pour peu quils respectent sa syntaxe.

Le corps dun document XML consiste essentiellement en un arbre dlments. Laracine de cet arbre correspond llment racine (Document Element) du document. Lesautres nuds de larbre correspondent aux lments descendants de llment racine dudocument.Les lments dun document XML possdent des relations de type (parent, enfant). Lesparties de larbre, possdant un enfant sont nommes branches, tandis que les partiesdpourvues denfants, sont nommes feuilles ou nuds terminaux. Chaque document nepossde quun seul lment racine qui contient tous les autres [43]. Par exemple, la FIGURE1.3 donne une ide sur la structure logique dun document XML.

Figure 1.3 Structure arborescente dune page XML

En gnral, les lments XML peuvent contenir du texte et dautres lments quisont leurs sous-lments ou leurs descendants. Les lments sont dcrits comme ayant uncontenu mixte. En effet, sur le document de lexemple de la FIGURE 1.3 possdedeux descendants :

un descendant qui est la balise un autre descendant contenant le texte du texte dans mon lmentOn peut restructurer le document de la FIGURE 1.3 notre guise, en introduisant des

attributs comme sur la FIGURE 1.4.Les attributs apportent des informations sur llment qui les contient (ils ne sont pas

appropris pour contenir des donnes). Il ny a pas de limite sur le nombre dattributsutilisables dans un lment ; il faut cependant trouver un compromis entre utilisationdattributs ou emploi dun nouvel lment et garder lesprit que les lments dcriventles donnes alors que les attributs dfinissent les lments qui les contiennent.

13


Figure 1.4 Page XML avec attributs

Notons que le document de la FIGURE 1.4 est smantiquement quivalent celui dela FIGURE 1.3, ce qui a chang, cest uniquement la conception de sa structure. Cettemallabilit dans la manire de structurer un document est une richesse qui permet auxutilisateurs de XML, de crer leurs documents selon leur prfrence.

En fait, le format XML permet de produire aussi bien des documents structurs quedes documents semi-structurs.

Les documents structurs possdent une structure rgulire, cest dire ne contiennentpas dlments mixtes, et lordre des lments quils contiennent est gnralementindiffrent.

Les documents semi-structurs possdent une structure flexible et des contenus h-trognes. La mise jour dune donne entrane une modification de la structure delensemble.

Dans [1], Abiteboul donne la dfinition suivante :Par semi-structure nous signifions que mme si les donnes possdent une structure,

celle-ci nest que la structure requise par les systmes de gestion de bases de donnestraditionnels [85].Une autre dfinition rencontre dans [66] est :

Nous appelons donnes semi-structure la donne qui nest (dun certain point de vue)ni une donne brute ni une donne strictement type [85].

Nous nous intressons dans cette thse aux documents semi-structurs reprsents parXML. Par abus de langage, nous sous entendons par RIS (Recherche dInformation Struc-ture), la RI avec des documents semi-structurs.

A lissue de cet aperu gnral sur les langages de balisage et du format XML enparticulier, nous poursuivons notre description de XML, en essayant de dfinir succincte-ment la DTD (Document Type Definition) et le XML-Schema. Nous donnerons ensuiteun aperu gnral sur certains standards tels que DOM et SAX, qui ont t dveloppsconjointement XML afin de faciliter laccs ce type de documents.

1.5 Type de documentLa spcification de base dfinit les DTDs, bien que celles-ci soient parfois considres

comme une technique apparente. Par exemple, lorsque nous avons cr le code XML

14

1.6. Document bien form, document valide

de lexemple de la FIGURE 1.1, nous avons conu une donne structure. Non seulementtoutes les informations concernant un nom ont t incluses, mais la hirarchie comportegalement des informations implicites sur la faon dont certains morceaux de donnessont lis dautres : comme par exemple, contient . Encore mieux :nous avons galement cr un ensemble particulier dlments, appel vocabulaire. Dansla pratique, nous avons dfini un ensemble dlments XML fonctionnant conjointementpour former le nom dune personne : , et . Mais, la plus int-ressante cration, est un type de document. Bien que cela ne soit pas explicitement dfini,les lments du vocabulaire doivent rpondre certaines rgles, afin que le document soitconforme au type de document [43]. Par exemple :

llment de plus haut niveau doit tre ; les lments et doivent tre les descendants de cet lment ; les lments et doivent se prsenter dans cet ordre ; il doit forcment y avoir des informations dans les lments et .

1.6 Document bien form, document valideUn document XML doit respecter certaines rgles grammaticales prsentes dans la

spcification XML. Les documents XML doivent obir ces rgles pour tre considrscomme tant bien forms Well formed document. Par consquent, sil y a non-respectdune de ces rgles, dans un document, il sera dit non bien form. Tandis quun documentXML sera dit valide sil est bien form et satisfait, en outre, aux rgles dune grammaireexprime par une DTD ou un XML-schema. Par exemple, si on oublie de fermer unebalise, un message derreur sera affich. Cependant, si le document est bien form (sanserreurs syntaxiques), et quon omet dassocier un schma validant (par exemple une DTD),le parseur XML de base nenvoie aucun message derreur au navigateur. Nanmoins, silon sollicite les services dun parseur validant, cest--dire qui intgre la DTD dans le par-sing, une erreur sera systmatiquement signale au navigateur qui sera charg de lafficher.

Il convient prsent de montrer comment pourrait-on associer une DTD un docu-ment XML, et de quel type de DTD il sagit. XML offre plusieurs manires dassocierune DTD un document (DTD interne au document XML, externe mais dclare dans ledocument XML, etc.). Nous nous limitons dans ce rapport loption, o lon dclare uneDTD dans le document XML. Autrement dit, cette dernire est dfinie dans un fichierexterne portant lextension DTD.

1.7 Association dune DTD un document XMLComme il est possible une personne de concevoir sa propre structure et ses noms

dlments pour ses documents, les DTDs permettent de crer des modles pour ces typesde documents. On peut effectuer une vrification pour tre sr que dautres documentsrespectent ces modles, tandis que dautres dveloppeurs peuvent produire des documentscompatibles [43].

15


Un document XML est dit valide sil est bien form et obit, en plus, aux rglesgrammaticales exprimes par une DTD ou un XML-Schema. La conformit du document ces rgles garantit sa validit. Mentionnons cependant, quil nest pas rare de rencontrerdes documents XML sans DTD. Contrairement SGML, la dclaration dune DTD nestpas obligatoire en XML. Un document XML peut exister et tre affich travers unnavigateur, sans pour autant que lui soit associe une DTD. Pour illustrer, considrons ledocument de la FIGURE 1.5 dcrivant une famille.

Figure 1.5 Document XML dcrivant une famille

Aucune rgle ne contrle la structure de ce document. Si on supprime llment, ou si lon ajoute dautres lments , cela nempche pas le documentdtre affich par un Navigateur.

Le but dune DTD est de dfinir les lments qui peuvent tre utiliss dans un docu-ment XML et de spcifier les relations entre ces lments. Chaque balise correspond unlment de la DTD.

Dans le document de la FIGURE 1.5, nous avons un lment racine nomm dont la dfinition est : < !ELEMENT famille (pere, mere, enfants ?)>.

Cet lment contient les lments , et . Ces lments sont lists selon lordre dans lequel ils doivent apparatre logiquement

dans le document. Le symbole ? signifie que llment est optionnel. Une famille peut tre valide avec seulement les deux lements et .

Les lments et sont dfinis par : < !ELEMENT pere(] PCDATA)> < !ELEMENT mere(] PCDATA)>

PCDATA correspond du texte qui sera analys par le parseur XML.Le troisime lment , ne contiendra pas de texte, mais un ou plusieurs lments. Ajoutons les lments et :

< !ELEMENT enfants(enfant +)>

16

1.7. Association dune DTD un document XML

< !ELEMENT enfant(] PCDATA)>

Llment peut contenir des lments . Le signe + signifie quil ya au moins un lment , et que cet lment peut tre rpt autant de foisque ncessaire. Llment contiendra du texte comme les lments et.En rsum la DTD associe est la suivante :< ?xml version=1.0 encoding=ISO-8859-1 ?>< !ELEMENT famille (pere, mere, enfants ?)>< !ELEMENT pere(] PCDATA)>< !ELEMENT mere(] PCDATA)>< !ELEMENT enfants(enfant +)>< !ELEMENT enfant(]PCDATA)>

Pour dcrire les lments de la DTD, on emploie un formalisme emprunt la thoriedes langages, en loccurrence, celui des expressions rgulires. Par exemple :

enfant +, signifie que llment apparat au moins une fois. enfant *, signifie que llment peut ne pas apparatre du tout ou appa-

ratre une ou plusieurs fois. Si on a (pere, mere), les lments et , doivent apparatre simulta-

nment dans cet ordre, cest comme si nous avions crit (pere et mere). enfants ? signifie que llment est optionnel, cest--dire apparaissant

une fois ou pas du tout. Si on crit (pere|mere), choix entre et , lordre dapparition na pas

dimportance.

Retenons quune DTD, quoique non impose dans la spcification de base, garantitla validit, facilite lchange et la rutilisation de documents XML. Une caractristiqueessentielle est quune mme DTD (externe) peut tre rfrence par plusieurs documentsXML trs proches structurellement. Le fait, dans lexemple prcdent, que llment soit optionnel, et/ou apparait une ou plusieurs fois, prouve que lon peutassocier un nombre potentiellement infini de documents XML structurellement similaires,tous engendrs par cette DTD. Nous pouvons alors assimiler cette dernire une classe.Notons cependant, que du point de vue de lchange des donnes, lutilisation de DTDsnest pas rellement pleinement satisfaisant pour les raisons suivantes :

Une DTD ne permet pas de prciser le type des donnes (numrique, boolen, date,etc.) reprsentant le contenu textuel dun lment ou attribut.

Elle ne dcrit que vaguement les cardinalits par les symboles ( ?, +, *). Elle nutilise pas le mme formalisme que les documents XML, ce qui rend le parseur

validant plus compliqu.

Pour pallier ces insuffisances, W3C a introduit en 2001 le XML-schema qui est unenouvelle forme de grammaire permettant de dfinir des lments plus complexes avec untypage plus riche

17


1.8 XML-SchemaLe XML-Schema adopte une syntaxe proche de XML et permet de dcrire la structure

dun document XML de faon beaucoup plus complte que la DTD. Il est possible deprciser les types complexes, les cardinalits et types des attributs, mais cela engendregnralement un document (XML-Schema) plus volumineux et plus difficile lire quuneDTD. Lexemple suivant sur la FIGURE 1.6 et FIGURE 1.7 illustre ces caractristiques.

Figure 1.6 Document XML dcrivant une personne

Figure 1.7 XML-Schema associ au document XML de la FIGURE 1.6

Il importe prsent de dcrire succinctement quelques standards qui ont mergconjointement la spcification de base XML. Nous nous limitons SAX (Simple APIfor XML), dont nous nous sommes servis dans cette thse, et DOM (Document ObjectModel), juste titre informatif, pour le situer par rapport SAX. Mais avant cela, ilconvient de rappeler en quoi consiste le parsing dans le contexte XML.

1.9 Quest ce que le parsing en XML?Le parsing est ralis par un analyseur syntaxique appel encore parser en Anglais

qui se lit parseur en Franais [15]. Cest la notation parseur que nous adoptons toutau long de ce rapport de thse.

Typiquement un compilateur possde deux attributions [15] :

18

1.10. DOM

Il ralise le parsing dun programme source et signale les ventuelles erreurs decompilation.

Il fournit en sortie une traduction du programme source analys en langage machine,afin que ce dernier puisse tre excut.

De la mme manire que le compilateur, le parseur XML va sassurer dabord que ledocument XML analys est bien form (il avertira, lapplication en cas de malformation).Il va lui aussi remplacer les entits contenues dans le document XML par leur valeureffective. Certains parseurs dits validants sont capables de vrifier galement que le fichier(document XML) pars est conforme au schma XML (DTD ou XML-Schema) qui lui estassoci. Ensuite, l o le compilateur gnre un arbre puis un excutable utilisable parla machine, le parseur sarrte la construction de larbre. Il laisse lapplication le soindeffectuer les traitements ncessaires sur cet arbre via lAPI (Application ProgrammingInterface) [15].Le parseur est un utilitaire de bas niveau : on ne peut pas accder directement au rsultatdu parsing. Cest lapplication qui utilisera ce rsultat pour effectuer ses traitements [15].Un exemple trs simple est celui du parseur intgr au navigateur Microsoft InternetExplorer. Lorsquun document XML est affich par ce navigateur, on voit apparatre sastructure arborescente.LAPI est une interface de programmation que lon peut considrer comme une couchesupplmentaire situe entre le parseur et lapplication [15].

1.10 DOMDOM (Document Object Model) est lAPI standardise par le W3C. Cest une norme

depuis le 1er octobre 1998. Le parseur DOM compile le fichier XML et produit un arbredobjets comme celui de la FIGURE 1.8.

Figure 1.8 Modle darbre DOM

Le parsing du fichier est valable si le document XML est bien form et seulement silest valide dans le cas dun parseur validant [15]. Si le fichier XML ne rpond pas cescritres le parseur DOM refuse de crer larborescence dobjets en mmoire.

19


Mais une fois larbre cr en mmoire, il devient accessible lapplication grce desmthodes daccs en consultation et en modification, fournies par lAPI DOM [15].

Pour mieux comprendre la porte des nuds (objets) de cet arbre en mmoire ondonne un deuxime exemple concret illustr par la FIGURE 1.9 et FIGURE 1.10. Le fichierXML de la FIGURE 1.9 dcrivant des tudiants, a pour arbre DOM en mmoire, celui dela FIGURE 1.10.

Figure 1.9 Document XML dcrivant un tudiant

Figure 1.10 Modle darbre DOM du document de la FIGURE 1.9

Ce mcanisme est coteux en termes de temps et de performance. De plus, il a un cot

20

1.11. SAX

de stockage trs lev car il est trs vorace en mmoire, il engendre en moyenne 5 6 fois lataille dun document source [109]. En revanche, il autorise des traitements en profondeurdu document XML, puisque larbre dobjets est entirement charg en mmoire centrale.

Il existe un autre type dAPI dnomme SAX compltement diffrente du DOM laquelle on fait appel, notamment dans des situations o lon na pas vraiment besoin decharger compltement larbre en mmoire, ou dans des cas dapplications spcifiques o lemodle darbre que lon veut crer, serait trs diffrent de larbre gnr par lAPI DOM.

1.11 SAXSAX (Simple API for XML) a t dveloppe sur le modle des logiciels libres. Bien

que nayant pas t normalise par le W3C, cette API a t implmente par la plupartdes diteurs. Elle est considre ds lors comme un standard de facto.Contrairement DOM, le parseur SAX ne produit pas un arbre en mmoire pour undocument XML. Il se contente dmettre des vnements de parsing, comme la rencontredune balise ouvrante, dune balise fermante, dun commentaire, dune dclaration, etc.Ces vnements sont capts par lapplication pour effectuer ses traitements.LAPI met la disposition de lapplication un nombre fini de mthodes daccs au docu-ment. Ces mthodes correspondent aux vnements que le parseur est susceptible dinter-prter au cours de sa lecture [15].

SAX permet de parcourir le document XML sans toutefois le conserver en mmoire.Ceci dit, donc une application utilisant SAX ncessitera peu de ressources en mmoire.En outre, les traitements sont plus rapides que DOM puisque la phase de stockage delarbre en mmoire nexiste pas. De ce fait, lusage de SAX est prconis, par exempledans des applications serveurs charges de transmettre des informations rapidement entredes sources de donnes et des clients [15]. Il est galement fortement recommand duti-liser SAX lorsque les traitements auront lieu seulement sur la structure du document ousur des sous-ensembles particuliers de la structure comme les sous-arbres. Cependant, silon souhaite effectuer des traitements en profondeur sur un document XML, lusage duDOM savre plus pertinent et plus efficace.

Nous ne pouvons aller au del de ce rsum que lon considre trs concis et largementsuffisant pour comprendre les principes de base des deux API, ainsi que leurs caract-ristiques essentielles et les diffrences quelles prsentent. Mais tant donn le caractreessentiel du parsing relativement la thmatique aborde dans cette thse, il convient dedonner galement une ide sur la nature des fichiers utiliss pour reprsenter des docu-ments XML.

1.12 Fichiers XMLUn des points forts de XML est que son format est universellement admis par toutes

les plates-formes [34, 43]. En effet, quel que soit le systme sur lequel on travaille, undocument XML est cr initialement partir dun fichier texte (comme par exemple fi-

21


chier Bloc-notes ou WordPad sous Windows), que lon sauvegarde sous lextension xml.Ds quun tel fichier est sauvegard, un document XML est systmatiquement cr. Cedernier peut tre, bien ou mal form, mais il devient accessible un parseur XML. Leparseur en question, peut analyser syntaxiquement le texte du document et lafficher sousforme arborescente travers un navigateur, en respectant la mise en forme, lindentationdes diffrents lments, etc. Lavantage est que, tout document XML possde une versiontexte telle quelle a t cre la base.

Actuellement il existe des diteurs XML permettant aux utilisateurs de crer trsrapidement leurs documents. Il existe mme des gnrateurs de documents comme Al-tova XMLSpy 1 permettant de crer des documents XML partir de DTDs ou inverse-ment des DTDs partir de documents XML. Parmi ces outils, on peut citer galementXTRACT [40] qui est un sytme qui extrait automatiquement des DTDs partir de do-cuments XML. Mais quel que soit loutil utilis pour crer un document XML, celui-cipossde toujours une version texte (fichiet texte) accessible en utilisant un simple diteurde texte.

Lexistence de la version texte permet ainsi un utilisateur daccder toutes les in-formations appartenant au document XML, et de pouvoir les manipuler bon escient. Endautres termes, si on veut extraire la partie structurelle dun document XML, il suffit deconstruire un parseur ad-hoc, qui fait appel par exemple SAX, pour analyser la versiontexte du document et gnrer en sortie un autre document XML sans contenu.

Cest typiquement de cette manire que nous allons procder dans notre approchepour extraire par parsing, la structure dun document XML, qui sera ensuite utilise dautres fins. Cette structure peut, au besoin, subir dautres traitements tels que parexemple supprimer les balises redondantes inutiles ou considrer les eventuels attributscomme des nuds-fils des lments (balises) auxquels ils sont rattachs dans le documentXML source, etc.

1. http ://www.altova.com/xmlspy.html

22

Chapitre 2

Indexation de linformationstructurelle de documents XML

2.1 IntroductionLes SRI classiques travaillant habituellement sur des collections de documents plats,

se focalisent uniquement sur les contenus, ignorant totalement la notion de structure et deliens pouvant ventuellement exister entre les documents. Mais avec lvolution des corpusdocumentaires, notamment avec lmergence des donnes semi-structures sur le Web, ladonne a compltement chang [30]. En effet, les documents XML, de par leur format,imposent aux SRI de prendre en considration, aussi bien la structure que le contenu, afinde cibler relativement avec une meilleure prcision, les units dinformation spcifiques etexhaustives correspondant au besoin de lutilisateur. Ainsi, un SRI, grce la composantestructurelle de ce type documents, devrait pouvoir se focaliser sur les units dinformationpertinentes rpondant ce besoin.La composante structurelle peut par ailleurs servir tablir au pralable une classificationstructurelle de ces documents. Cette dernire a pour objectif doptimiser le processus derecherche dinformation. En dautres termes, au lieu de se borner, comme avec les SRIstandards, une recherche dinformation sur une grande masse de documents, la classifi-cation structurelle permettra daffiner cette recherche, et la diriger slectivement vers unecertaine classe rduite de documents. Le bnfice ici, est double : rduire effectivement,la quantit de documents traiter, mais aussi, arriver regrouper des documents quiont des structures similaires et, du coup, augmenter le nombre de documents pertinentsretourns.

2.2 Le processus dindexationLe processus dindexation effectue le transfert de linformation contenue dans le texte

dun document vers un autre espace de reprsentation traitable par un systme infor-matique [84]. Lindexation joue un rle prpondrant dans la construction dun SRI. Safinalit est doptimiser les procdures daccs aux bases documentaires. Il convient alorsdanalyser chaque document de la collection afin de slectionner un ensemble restreint de

23

Chapitre 2. Indexation de linformation structurelle de documents XML

mots reprsentatifs. Ces derniers seront plus facilement exploitables par le systme lorsdu processus de recherche dinformation. Lindexation permet ainsi de crer une reprsen-tation des documents dans le systme. Son rle est alors de trouver les concepts les plusimportants du document (ou de la requte), qui formeront le descripteur du document [85].Lindexation peut tre :

Manuelle : chaque document est analys par un spcialiste du domaine ou par undocumentaliste ;

Automatique : le processus dindexation est entirement informatis ; Semi-automatique : le choix final revient au spcialiste ou au documentaliste, qui

intervient souvent pour choisir dautres termes significatifs [85].Lindexation manuelle permet dassurer une meilleure pertinence dans les rponses appor-tes par le SRI. Elle prsente toutefois plusieurs inconvnients : deux indexeurs diffrentspeuvent prsenter des termes diffrents pour caractriser un mme document, et un in-dexeur deux moments diffrents peut prsenter deux termes distincts pour reprsenterle mme concept. De plus, le temps ncessaire sa ralisation est trs important [85].Dans le cas dune indexation semi-automatique [11,63], les indexeurs utilisent un thesau-rus ou une base terminologique, qui est une liste organise de descripteurs (mots cls)obissant des rgles terminologiques propres, et relis entre eux par des relations s-mantiques.Enfin, lindexation automatique [64], regroupe un ensemble de traitements automatisssur un document. On distingue :

lextraction automatique des mots des documents ; llimination des mots vides ; la lemmatisation (radicalisation ou normalisation) ; le reprage de groupes de mots ; la pondration des mots ; la cration de lindex.

Le choix et lintrt dune mthode par rapport aux autres dpendent dun certain nombrede paramtres, dont le plus dterminant est le volume des collections. On trouvera unetude comparative de ces mthodes dans [9]. Le rsultat de ltude montre que les avan-tages et inconvnients de chacune des approches squilibrent : le choix dune mthodedoit tre fait en fonction du domaine, de la collection et de lapplication considre.En bref, lindexation constitue la description du document et de son contenu en vue defaciliter son exploitation. On distingue ce titre deux catgories dindexation :

Lindexation par type : elle offre une description formelle du document en utilisantses mtadonnes (type, auteur, titre, source, date, etc.), dont le vocabulaire est stan-dardis afin de permettre lutilisation de ces mtadonnes par le plus grand nombredoutils de recherche. Des documents semi-structures de type XML se prtent par-ticulirement bien ce genre dindexation. Dans ce cas, la structure (balises et at-tributs), peut jouer le rle de mtadonnes : on parle alors dindexation structurellede documents.

Lindexation par concepts ou mots-cls : elle vise plutt le contenu du document pourfaciliter les oprations de recherche. Il peut sagir ici, pour le concepteur du systme,de recenser les termes qui apparaissent le plus souvent ; on parle alors dindexationstatistique. Il peut aussi sagir dun systme plus volu o le concepteur slectionne

24

2.2. Le processus dindexation

les termes dans un thsaurus (liste de mots lis par des relations de hirarchie oudquivalence) en rapport avec le document.

On peut parler principalement de deux catgories dindexation dans le cadre de do-cuments structurs ou semi-structurs : lindexation base sur la structure et lindexationbase sur les contenus. Mais au vu de la problmatique de la classification structurelle tu-die dans cette thse, nous nous intressons uniquement ici lindexation de documentsXML sur la base de leurs structures. Ainsi, nous dcrirons sous peu certaines approchesdindexation structurelle et donnerons ce titre, les caractristiques qui les distinguent.

Linformation structurelle est effectivement exploite pour reprsenter structurelle-ment des collections de documents XML. Mais l aussi, on peut parler de deux genresou plutt de deux niveaux dindexation structurelle. En effet, dune part, la composantestructurelle peut tre utilise pour reprsenter (ou indexer) structurellement les docu-ments en vue dtablir leur classification structurelle, dautre part, elle peut aussi fournirun index de deuxime niveau permettant dinterroger efficacement ces documents. Nousnous intressons, plus particulirement dans cette thse, lindexation permettant dta-blir une classification structurelle de ces documents.

La structure tant la cl principale qui permettra alors dindexer structurellement lesdocuments XML et donc dy accder plus facilement lors de sessions dinterrogation ou derecherche dinformation. La structure permet ainsi de dtecter la classe approprie dungroupe de document partageant la mme structure ou ayant des structures similaires. Parconsquent, laccs un ensemble de documents dune mme classe, se fera sur la basedune structure commune reprsentant lensemble des documents de cette classe. Pouraccder aux documents XML, il va donc falloir y accder par le biais dune requte quipermettra au systme de slectionner au pralable la classe approprie. Les classes quiseront priori de tailles rduites doivent donc garantir un accs rapide et une pertinenceleve des rponses retournes par les moteurs de recherche. Lide est que, si des docu-ments XML partagent des structures similaires, ils sont plus mme de correspondre la partie structurelle dune mme requte.

En somme, lorsquon veut interroger des documents XML, le systme de classificationstructurelle permettra travers lensemble des classes, laccs ces documents. Contraire-ment aux modles classiques de la RI dont laccs aux documents est effectu sur la basedune indexation des documents par mots-cls, laccs aux documents au format XMLdoit tre assur en partie dabord par les classes qui sont censes contenir ces documents.On peut en loccurrence assimiler ces classes des interfaces ou une forme dindex entrele moteur de recherche et les documents que lon souhaite interroger. Autrement dit, lereprsentant de chaque classe peut servir dinterface avec un utilisateur pour lui permettredinterroger les documents qui sy trouvent.

25


2.3 Approches dindexation de linformation structu-relle de documents XML

Comme prconis, nous prsentons les approches dindexation de linformation struc-turelle de documents XML. Nous nous focalisons uniquement sur celles qui ont t utilisesdans le cadre de la classification structurelle ou de lintgration de schmas XML. Maisavant cela, il convient dintroduire au pralable certains concepts et dfinitions utiles surles arborescences.

2.3.1 Dfinitions prliminairesDfinition 2.1 (Arbre) Un arbre est un graphe orient, connexe sans cycle tel que : Il existe un nud et un seul o il narrive aucun arc. Ce nud sappelle la racine. Il arrive un arc et un seul en tout autre nud.

Dfinition 2.2 (Chemin) Un chemin dans larbre est une liste C = (x1, x2, ..., xk)de nuds telle quil existe un arc entre chaque paire de nuds successifs i = 1, ..., k 1 (xi, xi+1) lensemble des arcs. La longueur du chemin correspond au nombre darcsparcourus, cest--dire k 1.

Dfinition 2.3 (Arbre ordonn) Un arbre est dit ordonn si les fils de chacun deses nuds (non feuilles), sont lis par une relation dordre totale de gauche droite.

Dfinition 2.4 (Arbre tiquet) Soit E un ensemble dtiquettes. Un arbre Ttiquet par E est dfini par (T, ) tel que est une application qui associe chaquenud de T une tiquette de E.

Definition 2.5 (Sous-arbre frquent) Un sous-arbre frquent est un sous-arbreapparaissant dans la plupart des arbres dune fort considre.

Dfinition 2.6 (Inclusion) Il existe de nombreuses manires de dfinir linclusionentre deux arbres T1 et T2. Toutes ces dfinitions se basent sur lexistence dune applica-tion de mapping (correspondance) des nuds de T1 vers les nuds de T2. Ce mappingprserve de manire faible ou forte les tiquettes des nuds et la structure de larbre. Lesdiffrences proviennent des proprits de prservation qui sont considres, ainsi que delinjectivit ou non du mapping [95].

Lauteur dans [51] a dfini 10 relations dinclusion darbres diffrentes [95]. Pour sim-plifier, nous exprimons les diffrents types dinclusion par des exemples concrets. Nousnous limitons cependant celles qui sont les plus largement employes.

Dans la FIGURE 2.1 est donn lexemple dun arbre T1 inclus dans T2 selon linclusionstricte exacte ordonne. Mais les arbres T3 T7 ne sont pas inclus dans T2 selon cette dfi-nition. Cependant, il existe une relation dinclusion stricte exacte entre T3 et T2 (FIGURE

26

2.3. Approches dindexation de linformation structurelle de documents XML

2.2), et une relation dinclusion stricte ordonne entre T4 et T2 (FIGURE 2.3). Entre T5 etT2, il ya une relation dinclusion stricte (FIGURE 2.4). Et entre T6 et T2, on peut trouverune relation dinclusion stricte faible (FIGURE 2.5). Enfin, entre T7 et T2, il existe unerelation dinclusion exacte ordonne (FIGURE 2.6).

Figure 2.1 Inclusion stricte exacte ordonne

Figure 2.2 Inclusion stricte exacte non ordonne

Figure 2.3 Inclusion stricte ordonne non exacte

27


Figure 2.4 Inclusion stricte non ordonne non exacte

Figure 2.5 Inclusion stricte faible non ordonne, non exacte

Figure 2.6 Inclusion non stricte, mais exacte et ordonne

Dans la TABLE 2.1 sont rcapituls les types dinclusion voqus ci-dessus.

Stricte Faible Exacte OrdonneFIGURE 2.1 OUI NON OUI OUIFIGURE 2.2 OUI NON OUI NONFIGURE 2.3 OUI NON NON OUIFIGURE 2.4 OUI NON NON NONFIGURE 2.5 OUI OUI NON NONFIGURE 2.6 NON - OUI OUI

Table 2.1 Tableau rcapitulatif des types dinclusion voqus

28

2.3. Approches dindexation de linformation structurelle de documents XML

Les documents informatiques structurs se prtent particulirement bien la misesous forme arborescente, comme cest notamment le cas de documents XML, qui ont tconus afin de stocker linformation sous une forme structure [95]. La FIGURE 2.7 montreun exemple de document XML et la structure arborescente associe.

Figure 2.7 Un document XML simple et larbre des balises associ [95]

Notons que cette structure correspond un arbre tiquet ordonn. En effet, chaquenud a comme tiquette une balise du document XML. En outre, lordre squentiel desbalises dans le document XML se traduit par lordre des nuds-fils dun nud donndans larbre correspondant. Il est donc possible de considrer cette structure arborescentecomme un index de linformation structurelle du document XML source. Notons cepen-dant que ce nest pas toute linformation structurelle qui est utilise pour former un index.Trs souvent, cest une forme gnrique trs reprsentative o lon limine toute forme deredondance en vitant autant que possible la perte dinformation.

2.3.2 Indexation base sur les sous-arbres frquentsLa motivation lorigine de la recherche de sous-arbres frquents dans des collections

darbres vient notamment de lanalyse de documents lectroniques. Ainsi, les approchesprsentes dans [10, 119] ont pour donnes dentre des traces de navigation dans dessites Web, ou encore des documents informatiques mis sous forme arborescente commeles documents XML. Dans [95], lauteur a abord la mme problmatique sous langledextraction darbres frquents dans un corpus htrognes de donnes semi-structuresXML. Lauteur dans [28] a, quant lui, tudi la mme thmatique, mais pour des sous-arbres ordonnes frquents, en vue dintgrer des documents XML homognes.Dans ce contexte, tant donn une fort darbres XML, cest--dire une base de struc-tures arborescentes associes une collection de documents XML, un sous-arbre frquentest inclus dans la plupart des arbres XML de cette fort, tandis quun arbre XML peutcontenir un ou plusieurs sous-arbres frquents. Autrement dit, plusieurs documents XMLpeuvent tre structurellement indexs par un mme sous-arbre frquent (intgration), toutcomme il est galement possible de voir un mme document XML index par plusieurssous-arbres frquents (recouvrement). Lindex de linformation structurelle dun docu-ment XML peut donc tre compos dun ou plusieurs sous-arbres frquents. Cependant,ces derniers peuvent tre distingus selon quils soient ordonns ou non et/ou exacts ounon. Dans le contexte du traitement de documents XML homognes, il savre ncessairede traiter lordre si celui-ci est spcifi par une DTD ou un schma XML.

29


Ainsi, les approches [10, 95, 119], ont toutes en commun la dcouverte de sous-arbresfrquents, mais elles diffrent sur la dfinition de linclusion dun arbre dans un autre.En effet, pour [10, 28], les sous-arbres frquents apparaissent selon une inclusion induite,cest--dire une inclusion stricte et exact, mais ncessairement ordonne, comme cest lecas de la FIGURE 2.1 et FIGURE 2.8. Notons cependant que lordre peut tre indirectcomme sur la FIGURE 2.9. Par contre, [119] est plus permissif, cest--dire quil considrequun arbre est inclus dans un autre, comme cest le cas pour larbre T4 de la FIGURE2.3 et pour linclusion entre les arbres T1 et T2 de la FIGURE 2.10, mme si limbricationdes nuds nest pas exactement la mme que celle de linclusion induite. Ceci permet deretrouver des sous-arbres frquents malgr une certaine htrognit dans les structuresdes arbres XML de la fort considre. Toutefois, les approches [10,28,119] se retrouventsur un point : les fils/descendants dun nud doivent toujours se trouver dans le mmeordre, pour faire partie dun sous-arbre frquent. Quant lapproche [95], elle gnraliseles travaux prcdents et permet une plus grande flexibilit dans linclusion, cest--direquelle considre, comme sur la FIGURE 2.4 et FIGURE 2.11, quun arbre est inclus dansun autre sans tenir compte de lordre des frres, et en aut

Documents

Thèse Ali Aïtelhadj UMMTO Tizi-Ouzou