XML s’est imposé comme un métalangage permettant de représenter et d’échanger des données non seulement dans le web mais de façon générale en entreprise. Pour extraire des informations de nombreuses applications reposent sur la recherche par similarité de données. Evaluer la similarité entre documents XML reste un des problèmes cruciaux lors du processus de fouille de données.
Plusieurs solutions proposent d’adapter l’algorithme Edit Distance (distance de Levenshtein) introduit à la base pour comparer deux chaines de caractères. Edit Distance définit la distance comme étant le nombre minimum d’opérations d’ajout, de suppression et de remplacement nécessaires pour passer d’une chaîne de caractères à une autre. L’algorithme utilisé pour calculer cette distance se base sur le principe de la programmation dynamique.
Edit Distance a été largement exploité dans les algorithmes de comparaison de document XML.
Le projet consiste à travailler sur une implémentation Java de deux versions de ces algorithmes [1][2]. Il s’agit de :
1.Comprendre les algorithmes [1][2].
2.Trouver une méthode de traçage permettant d’extraire certaines informations intervenant dans le calcul de la distance.
3.Comparer les résultats obtenus avec ceux d'une nouvelle méthode déjà implémentée.
Bibliographie
[1] "Evaluating Structural Similarity in XML documents" Nierman A. Jagadish H. V., In Proceedings of SIGMOD WebDB'02,2002.
[2] “Comparing hierarchical data in external memory”. Sudarshan S.Chawathe. In Proceedings of the Twenty-fifth International Conference on Very Large Data Bases, pages 90-101, Edinburgh, Scotland, U.K., September 1999.
|
