CIDE (1998) Richy

De CIDE.

Édition comparative et hypertextuelle
 
 
Titre
Édition comparative et hypertextuelle
Auteurs
Hélène Richy (1) et Jacques André (2)
Affiliations
(1) Irisa/Cnrs
(2) Irisa/Inria
In
CIDE.01 (Rabat 1998)
En ligne 
http://www.irisa.fr/imadoc/articles/1998/cide98.ps.gz

Sommaire

Résumé
L'environnement d'édition comparative de documents que nous présentons propose une commande de comparaison de texte mot à mot et produit un hypertexte issu des textes comparés : cet hypertexte offre une représentation synthétique qui associe entre eux les passages semblables et permet d'analyser les transformations que ces textes ont subies, en offrant un choix de points de vue. La méthode de comparaison de textes mot à mot est une adaptation des algorithmes classiques de comparaison de chaînes de caractères dont les performances ont récemment améliorées pour répondre aux besoins de l'analyse moléculaire des séquences génétiques en biologie moléculaire.

Introduction

L’environnement d’édition comparative que nous proposons ici permet de produire un document synthétique hypertextuel mettant en évidence les similitudes de deux textes. Cet environnement est expérimenté dans le cadre du projet Philectre [1]. Une commande de comparaison adaptée au travail d’édition textuelle prend en compte la spécificité des textes et leur composition en mots, phrases ou paragraphes, et permet d’effectuer des recherches exactes ou approchées dans un ou plusieurs documents.

Cet environnement offre une première solution au problème de comparaison entre manuscrits qui joue un rôle crucial dans le domaine des éditions savantes (et ce depuis longtemps, voir par exemple la synopse des évangiles [6]).

En effet, l’objectif d’un environnement d’édition comparative est de favoriser l’étude des similitudes entre différents textes ou différents passages d’un même ouvrage. Cette recherche des similitudes revêt en réalité des aspects fort différents selon le type des passages que l’utilisateur souhaite localiser. La liste suivante n’est évidemment pas exhaustive :

  1. localisation de passages identiques, c’est-à-dire composés des mêmes mots,dans le même ordre ;
  2. localisation de passages proches (approximate matching), c’est-à-dire comportant quelques variations de contenu, résultant d’insertion, de suppression ou de remplacements de certains mots par d’autres ;
  3. localisation de passages sémantiquement proches, c’est-à-dire dont le sens est voisin ;
  4. localisation de passages construits de la même manière : structure grammaticale, rhétorique ou logique identique ou similaire, etc.

Afin de prendre en compte la diversité de ces objectifs, nous proposons une technique de comparaison évolutive ainsi qu’un modèle de document visant à favoriser la compréhension de ces similitudes :

  • l’algorithme de comparaison, décrit dans la section 2, permet de déterminer différents types de passages : le plus long, le plus proche, tous les passages identiques, etc.
  • à travers différentes représentations visuelles, les documents structurés offrent une vision synthétique et hypertextuelle facilitant l’édition comparative, qui est décrite dans la section 3. Le document de synthèse produit est un document de travail qui peut être transformé et édité par l’utilisateur.

Méthode de comparaison

Des algorithmes de comparaison développés depuis les années 1970 [1, 15, 26, 27] sont utilisés sur ordinateurs pour comparer des séquences de caractères (comparateur de fichiers [12], correcteur dactylographique [2, 24]). Ces algorithmes, qui ont été généralisés pour faciliter la recherche de sous-séquences semblables ou l’alignement de séquences [11, 19, 25, 28], ont une application directe en biologie moléculaire et en reconnaissance de la parole. Des améliorations concernant le temps de calcul et l’occupation mémoire ont été apportées à l’algorithme de base, permettant d’étendre son application à la comparaison de données volumineuses. Compte-tenu de ces récentes améliorations, il est maintenant réaliste d’envisager d’adapter ces algorithmes à l’analyse des similitudes de textes, de plusieurs pages, voire plusieurs dizaines de pages, composés de dizaines de milliers de mots.

Principe général

Les méthodes de comparaison caractère par caractère reposent sur les opérations d’édition : la substitution, l’insertion et l’omission. Toute chaîne de caractères peut être transformée à l’aide de ces opérations en une autre chaîne. On appelle distance de deux chaînes A et B, le nombre minimum d’opérations [2] requises pour obtenir la chaîne B à partir de la chaîne A.

Le principe général de la méthode de comparaison reste le même lorsqu’elle est appliquée à des mots entiers et non plus à des caractères. Il suffit de pouvoir définir, pour n’importe quel mot, quelle est sa distance avec n’importe quel autre mot. Le calcul le plus simple consiste à considérer que la distance de deux mots est nulle si ces deux mots sont identiques (composés des mêmes caractères, dans le même ordre) et non nulle dans tous les autres cas.

Le calcul de la distance entre deux textes s’appuie sur une matrice de similitude H de dimension n \times m, dans laquelle n est le nombre d’éléments du premier texte et m le nombre d’éléments du second texte. Cette matrice est calculée récursivement de telle sorte que les plus fortes valeurs coïncident avec les plus longs passages communs. Ainsi, appliquée aux mots d’un texte, cette méthode permet de localiser les passages qui sont composés exactement des mêmes mots, dans le même ordre (section 2.2), quels que soient ces mots, ou les passages dont le contenu est très proche (section 2.3).

Recherche exacte

Lorsque l’objectif du calcul est de trouver la position exacte des passages identiques de deux textes, il suffit de poser H(i,j) = H(i − 1,j − 1) + 1 si l’élément de rang i du premier texte est égal à l’élément de rang j du second texte et H(i,j) = 0 si ces deux éléments sont différents. On obtient ainsi dans la matrice H des coefficients croissants alignés en diagonale lorsqu’apparraissent des passages communs : par exemple, dans la comparaison des textes[3] ABEFBCDXF et ABCDEF, quatre passages communs sont identifies par la présence de coefficients non nuls dans la matrice. Comme l’indique le coefficient maximum de la figure 1, le plus long passage est composé de 3 éléments (BCD).

Recherche approchée

Lorsque l’on souhaite une identification des passages similaires, c’est-à-dire des passages qui ne différent que sur un petit nombre d’éléments, on peut là aussi, de finir le degré ́ de ressemblance par la distance d’édition: celle qui correspond au nombre minimal de substitutions, d’insertions ou de suppressions d’éléments à effectuer sur un passage pour qu’il soit identique à un autre passage. Des algorithmes de recherche approchée ont été développés pour résoudre ce type de problème, tel celui que Smith et Waterman [25, 28] ont adapté pour la recherche d’alignement des séquences génétiques.Une application simple de cet algorithme consiste, par exemple, à utiliser la formule de calcul suivante pour construire la matrice H :

H(i,j) = Max(0,H(i,j − 1) − ,H(i − 1,j) − ,H(i − 1,j − 1) + Sbt(i,j)

où Sbt est le coût de substitution de deux éléments et α le coût d’une insertion ou omission. La figure 3 montre la matrice de comparaison des textes (de Céline) TA = « Puis il m’observe sans hardiesse » et TB = « il m’observe aussi sans hardiesse » avec cette formule et les paramètres :α=1,Sbt(i,j) = 100 [4]. Pour localiser les passages similaires à partir d’une telle matrice, la méthode de recherche approchée consiste à trouver le coefficient maximum. Un algorithme récursif de parcours en arrière [11] permet de remonter depuis ce maximum jusqu’à l’origine du passage où se trouve un coefficient nul, en suivant un parcours non rectiligne dans la matrice. Pour retrouver d’autres passages similaires, il suffit de remettre à zéro la trace du parcours trouvé et d’annuler les effets qui lui sont associés en recalculant les coefficients voisins, puis de trouver le nouveau maximum et refaire un parcours en arriére pour déterminer le meilleur passage.

Interprétation des résultats

Le choix des paramètres (coût de la première insertion et coût des insertions suivantes, coût des suppressions, etc.) et de la fonction Sbt permet d’obtenir des séquences plus ou moins longues et plus ou moins proches. La diversité ́ des résultats obtenus par différents parametrages est souvent intéressante à analyser. En effet, la notion de proximité de deux séquences est difficilement mesurable. Seule une connaissance sémantique, propre à l’application (biologie, structure grammaticale, etc.) peut permettre d’interpréter correctement ces résultats, comme le montre l’exemple suivant (figure 2) : sur les deux textes ABEFBCDXF et ABCDEF, on peut considérer que le premier texte a subi l’une des transformations suivantes :

  1. Suppression de EFB après AB, puis remplacement de X par E : AB(EFB)CD(X)[E]F (trace x)
  2. Insertion de CD après AB, puis suppression de BCDXF après EF : AB[CD]EF(BCDXF) (trace y )
  3. Suppression de BEF après A, puis remplacement de X par E : A(BEF)BCD(X)[E]F (trace z )

S’agissant d’un texte composé de mots, l’interprétation sémantique ou grammaticale de ces transformations, peut permettre de privilégier certaines solutions. Dans l’exemple précédent la solution (3) sera retenue si les passages (BEF) et (BCD) correspondent à un groupe grammatical.

Améliorations

L’approche que nous avons choisie pour comparer des textes mot à mot est indépendante de toute considération sémantique sur le contenu des textes à comparer.

Figure 1 : Matrice des occurrences exactes
Figure 2 : Trace des similitudes
Figure 3 : Matrice de comparaison mot à mot

Toutefois, l’algorithme de comparaison étant basé sur un calcul de distance, il est possible d’envisager des adaptations pour répondre au troisième objectif de la section 1. Ces adaptations portent sur la définition des unités textuelles et le calcul de la distance entre ces unités.

Les unités textuelles comparées sont généralement les mots d’un texte. Un mot est identifié comme une suite de caractères alphabétiques délimitée par des séparateurs qui sont les signes de ponctuation, les espaces ou les débuts et fin de paragraphes. Ces unités textuelles peuvent être définies autrement, par exemple :

  • en utilisant des lexiques de vocabulaire, on peut définir des unités textuelles qui sont non seulement des mots, mais aussi des groupes de mots : expressions usuelles, mots composés, etc.
  • en utilisant comme délimiteurs les balises d’un document structuré,on peut considérer comme unités textuelles le contenu des éléments balisés (avec les balises de la TEI (Text Encoding Initiative) [9], par exemple).

D’autre part, l’utilisation de pondérations permet de définir la proximité séman- tique de deux mots ou groupes de mots. Par exemple, la distance entre unités textuelles d’un même lexique peut être considérée comme plus faible que la distance entre unités appartenant à des lexiques différents. Les mots au singulier et au pluriel, les formes conjuguées d’un même verbe, etc. peuvent aussi être considérés comme très proches.

Ainsi, en considérant la distance non plus comme une valeur de [0, 1] mais dans un intervalle [0, n], les résultats de l’algorithme prennent une toute autre signification.

La méthode de comparaison présentée ici permet donc de comparer non seulement les mots d’un texte, mais aussi, si elle est appliquée à des textes pré-découpés en fragments [4] ou en unités lexicales, des unités textuelles quelconques.

Hypertexte

L’application des modèles structurés et le développement d’outils d’édition interactifs favorise la consultation et la production d’(hyper)documents électroniques [21]. C’est pourquoi, nous proposons d’utiliser un tel modèle de document pour synthétiser le résultat de la comparaison de deux textes. De plus, lorsque l’on ne s’intéresse pas uniquement à la forme visuelle des documents, l’existence d’un modèle logique indépendant des machines et logiciels utilisés facilite l’échange des documents.

Un hypertexte désigne un document structuré interactif comme on en trouve sur l’internet (les documents HTML [22]) ou plus généralement dans le domaine de la documentation électronique structurée (les documents SGML [13]). Le concept de document structuré [10] offre un modèle de l’organisation logique des éléments d’un document et permet ainsi de définir une séparation entre la structure de document, son contenu et sa forme visuelle. Ce concept privilégie la structuration hiérarchique. Toutefois, la notion de lien confère aux documents structurés une dimension hypertexte.

Par exemple, pour représenter un renvoi à une note ou à une illustration dans un document structuré, on utilisera des éléments « référence », de telle sorte qu’un simple clic sur cet élément « référence » suffise à faire apparaître la note ou l’illustration. Ainsi, l’image numérique d’un manuscrit, par exemple, pourra être affichée dynamiquement aux côtés de sa retranscription. En attendant que des programmes de reconnaissance automatique puissent produire automatiquement ce type de résultat [23], l’utilisateur doit placer lui-même les liens pertinents entre l’image du manuscrit et sa transcription.

Modèle logique et modèle visuel

Nous présentons le résultat de la comparaison de deux textes par un document structuré qui contient, outre les deux textes comparés, une description des correspondances établies entre ces deux textes. Dans ce document de synthèse, chacun des textes initiaux est découpé en fragments. Un fragment délimite un passage de texte qui peut être soit commun aux deux textes initiaux (passage identique), soit ajouté, soit supprimé, soit modifié. Les correspondances entre ces deux textes sont ordonnées et permettent, par des liens explicites, de retrouver le passage correspondant dans chacun de ces textes.

Plus précisément, en désignant TA et TB les deux textes comparés dans le document de synthèse S, la comparaison de TA et TB est représentée par une mise en correspondance d’un fragment de TA avec un fragment de TB. Pour représenter la suppression d’un passage qui existe dans TA, mais est absent de TB, un fragment vide est inséré dans TB à l’emplacement correspondant. Inversement, pour représenter l’insertion d’un passage qui n’existait pas dans TA, un fragment vide est inséré dans TA à l’emplacement de cette insertion. Le modèle logique d’un document de synthèse peut être décrit en utilisant une description SGML, conforme à la TEI (voir annexe).

L’utilisation de modèles de structure et la séparation entre structure de document et contenu permet de décrire l’aspect visuel des documents à partir des types logiques qui les composent en utilisant pour cela un langage de style [17]. L’indépendance du modèle visuel et du modèle logique facilite l’expérimentation: différentes présentations peuvent être proposées et adaptées aux besoins spécifiques des utilisateurs. Des vues complémentaires facilitent la perception des lieux variants des textes comparés : index alphabétique des mots, présentation d’une liste des passages communs classés par taille décroissante, numérotations des occurrences de certains passages, etc.

Mise en œuvre

Ne disposant pas actuellement d’un environnement d’édition adapté à la TEI, nous avons effectué une première expérimentation des commandes de comparaison en utilisant l’éditeur Thot, éditeur structuré interactif issu de Grif [7, 20].

L’architecture de cet éditeur est conc ̧ue pour faciliter l’intégration de nouvelles commandes qui sont vues par l’utilisateur comme des outils complémentaires accessibles depuis l’éditeur. Cette mise en œuvre présente les caractéristiques suivantes.

  • Un modèle logique expérimental équivalent à celui de la TEI (décrit dans l’an- nexe) a été créé en langage S et est utilisé par l’éditeur Thot.
  • Une présentation expérimentale adaptée à ce modèle logique a été définie en langage P pour l’éditeur Thot. Cette spécification, permet de décrire plusieurs vues pour un même document: les fragments de texte sont affichés en parallèle ou juxtaposés pour faciliter la visualisation des correspondances.
  • La comparaison de texte repose sur deux nouvelles commandes [5] qui permettent de délimiter les textes à comparer (Sélection A + Sélection B) et de lancer la comparaison de ces deux textes (Comparaison) en ayant préalablement modifié, si nécessaire, certaines options du comparateur.

Expérimentation et perspectives

Choix d'implémentation

Pour les premières expérimentation afin de faciliter l’ajustement des paramètres, le comparateur a été utilisé sans avoir recours à un lexique : les mots comparés sont les mots simples, la ponctuation joue le rôle de séparateur de mots, la distance entre mot est minimale (nulle) si les mots sont identiques et maximale si les mots sont différents, même s’ils ne diffèrent que d’un ou deux caractères ou s’ils sont synonymes.

Les textes comparés résultent d’une transcription fidèle de documents originaux, manuscrits ou imprimés : texte en français accentué (code Iso-Latin1), incluant la typographie (ponctuation et capitales), structurés éventuellement en paragraphe.

Le calcul de la matrice de comparaison fait appel au calcul de deux matrices intermédiaires et peut exiger un recalcul partiel pour la recherche successive de plusieurs passages proches. Pour comparer des textes volumineux, il est donc nécessaire d’utiliser une méthode de programmation dynamique ou un environnement de calcul disposant de mémoire virtuelle (Matlab [16] sur station Sun sous Unix, par exemple), ou encore un circuit spécialisé tel que celui qui a été développé pour les séquences génétiques [5, 14].

Options de notre comparateur

La commande de comparaison mot à mot est accessible à l’utilisateur directe- ment depuis l’interface d’édition. Après ouverture du ou des documents concernés et la sélection des deux passages à comparer, la commande de comparaison permet de choisir les options de la comparaison (prise en compte ou non des majuscules, production d’un résultat graphique, algorithme) et de demander la construction d’un document de synthèse.

Lorsque la comparaison est terminée, le document de synthèse produit par le comparateur est ouvert et affiché par l’éditeur comme n’importe quel autre document structuré.

Édition interactive

Toutes les fonctions d’édition habituelles sont disponibles pour consulter ou modifier le document de synthèse ouvrir ou fermer des vues, suivre les liens vers des passages supprimés, développer les passages longs (figurés sous une forme contractée), modifier les fragments, couper certains passages, modifier les couleurs, etc.

Comme le montre la figure 4, la présentation du document de synthèse ne fait pas apparaître les balises contenues dans le document (cad. les délimiteurs d’éléments dans un document structuré), mais uniquement le contenu de ce document : les textes à comparer sont présentés séparément et juxtaposés, les superpositions indiquent les variantes, la couleur rappelle l’origine des textes, les liens entre les passages permettent de passer d’un texte à l’autre.

Perspectives

Dans cet article nous avons présenté un environnement d’édition comparative hypertextuelle et nous avons montré que :

  • les méthodes de comparaison utilisées pour comparer des chaînes caractère par caractère sont utilisables pour comparer des textes mot à mot et donnent des résultats précis,
  • un modèle structuré hypertextuel facilite la visualisation des lieux variants des textes comparés,
  • l’intégration d’outils de traitement des textes dans un environnement d’édition interactive multimédia permet de répondre aux besoins des chercheurs en sciences humaines.
FIG. 4 – Édition comparative avec Thot : en haut, deux extraits de différentes versions de « Féérie pour une autre fois » de Céline; à gauche, vue synthétique et liste des fragments; à droite, tracé comparatif


Les premières expérimentations nous engagent à poursuivre les recherches dans ces deux directions afin d’une part, d’améliorer la comparaison en utilisant des res- sources lexicales et en identifiant des unités textuelles quelconques et, d’autre part, de produire des (hyper)documents conformes aux normes de la communauté internationale (TEI [9], XML [8]).

Ainsi, de nouveaux outils informatiques pourront-il être appliqués aux livres électroniques et en particulier au domaine de la critique génétique, dès que des expérimentations en grandeur réelle auront été évaluées par des spécialistes en sciences humaines.


Annexe : document de synthèse

Modèle logique (Thot)

Le modèle logique est représenté par l’arbre des types de la figure 5. Dans cet arbre, le rectangle arrondi figure une unité de base (texte en trait plein et référence en pointillé), le rectangle ombré représente une liste d’éléments de même type, le rectangle représente un agrégat d’éléments de type différents et l’ellipse ombrée représente un choix entre plusieurs types d’éléments.

Figure 5 – Modèle logique d’un document de synthèse (Synthesis)

Conformément à ce modèle, les deux textes comparés TA et TB sont placés dans les éléments Div A et Div B. Ils sont découpés en segments; des éléments Anchor sont ajoutées pour marquer l’emplacement des insertions ou suppressions. La synthèse de comparaison (Compar AB) est décrite par une liste ordonnée de couples de liens vers ces fragments : le premier lien pointe toujours sur un fragment de TA, le second sur un fragment de TB.

Codage du document en SGML (TEI)

La TEI prévoit différents mécanismes de mise en correspondance des textes. Une solution simple consiste à découper les textes en segments et à représenter les correspondances entre ces segments par un ensemble ordonné de liens. Par exemple, le document de synthèse ci-dessous (figure 6) codé en SGML utilise les balises <seg>,<anchor> et <linkGrp> de la TEI.

Modèle visuel

Plusieurs vues du document de synthèse apparaissent dans la figure 4 : la vue globale du document (Vue texte) qui permet d’afficher les deux textes et une présentation juxtalinéaire des passages en correspondance et la vue des fragments (Vue fragments) qui donne la liste des fragments de chaque texte et, pour chaque correspondance, la juxtaposition des fragments. Ces vues sont spécifiées pour Thot en langage P.

Au travers de ces vues, l’utilisateur perçoit les résultats de l’analyse des textes :

  • la segmentation du texte résultant de la comparaison,
  • les différences: une couleur différente est attribuée à chaque texte. Dans la vue comparative, les variantes d’un même passage sont juxtaposées verticalement. Pour faciliter la vision globale, les passages trop longs sont contractés (un simple clic permet d’en voir le contenu complet).
  • la correspondance entre les deux textes : un simple clic depuis la vue comparative permet de sélectionner le passage correspondant ou l’emplacement du passage manquant dans le texte initial.

Lorsque les textes sont volumineux, on peut afficher le résultat de la comparaison sous une forme graphique (figure 4) ce qui permet de choisir dans le document de synthèse les passages intéressants qui pourront être analysés plus en détail par la suite.

<div1 id=TA corresp=TB>
<seg id=A1>puis </seg>
<seg id=A2>il m’observe</seg>
<anchor id=a1>
<seg id=A3>sans hardiesse</seg> </div1>
<div1 id=TB corresp=TA>
<anchor id=b1>
<seg id=B1>il m’observe </seg>
<seg id=B2>aussi </seg>
<seg id=B3>sans hardiesse </seg> </div1>
<linkGrp type=’compar’ domains=’TA TB’>
<link type=’del’ targType=’anchor seg’ targets=’A1 b1’> 
<link type=’com’ targType=’seg seg’ targets=’A2 B1’> 
<link type=’add’ targType=’seg seg’ targets=’a1 B2’> 
<link type=’com’ targType=’seg seg’ targets=’A3 B3’>
</linkGrp>
FIG. 6 – Document de synthèse (codage TEI)

Bibliographie

[1] A. Aho, , « Algorithm for Finding Pattern in Strings », Handbook of Theorical Computer Science, J. van Leeuwen, ed., p. 257-300, MIT Press, 1990.

[2] J. André, « Les vérificateurs orthographiques », Le document numérique, 1(2),p.247-251, Hermès, juin 1997.

[3] J. André, et H. Richy, « Hypertextes ou documents structurés », Hypertextes et Hypermédias, 1(2-3-4), p. 13-26, Hermès, 1997.

[4] J. André, A. Morin et H. Richy, « Comparison of Literary Texts Using Biological Sequence Comparisons and Structured Document Capabilities », Proceedings of the International Conference on Computational Linguistics, Speech and Document Processing, Indian Statistical Institute, Calcutta, India, 1998, p. D-1–D-7.

[5] L. Audoire, J.-J. Codani, D. Lavenier et P. Quinton, « Machines spécialisées pour la comparaison de séquences biologiques », Technique et Science Informatique, 14(1), 1995.

[6] P. Benoît et M.-E. Boismard, Synopse des Quatre Évangiles, Le Cerf, Paris, 1990.

[7] S. Bonhomme, V. Quint, H. Richy, C. Roisin, and I. Vatton, The Thot User’s Manual, OPERA project, Inria-Imag, http://opera/inrialpes.fr/doc/thot/Thotman-E.html, 1997.

[8] T. Bray, and C.M. Sperberg-McQueen, Extensible Markup Language (XML), WorkingDraft, http://www.w3.org/pub/WWW/TR, 31 mars 1997.

[9] L.Burnard et C. M. Sperberg-McQueen, TEI Lite : An Introduction to Text Encodingfor Interchange, TEI U 5, http://www.uic.edu/orgs/tei/intros, juin 1995. Voir aussi, Cahiers GUTenberg, 24, juin 1996.

[10] R. Furuta, V. Quint, and J. André, « Interactively Editing Structured Documents », Elec- tronic Publishing, 1(1), p. 20-44, avril 1988.

[11] O. Gotoh, « An improved Algorithm for Matching Biological Sequences », J. Mol. Biol., 162, p. 705-708, 1982.

[12] J. W. Hunt and T. G. Szymanski, « A fast algorithm for computing longuest common subsequences », Comm. ACM, 20(5), p. 350-353, 1977.

[13] ISO, Langage normalisé de balisage généralisé (SGML), ISO 8879, 1986.

[14] D. Lavenier, « Dedicated Hardware for Biological Sequence Comparison », Journal of Universal Computer Science, 2(2), février 1996.

[15] V.I. Levenshtein, « Binarycodes capable of correction deletions,insertion and reversals », Sov. Phys. Dokl., 10, p. 707-710, février 1966.

[16] Matlab, High-Performance Numeric Computationand Vizualisation Software,The MathWorks, Inc., Natick, Mass., 1984-1993.

[17] H.Richy,« Feuilles de style pour le Web», Cahiers GUTenberg, 26,133-145,1997.

[18] L. Likforman-Sulem, L. Robert, E. Lecolinet, J.-L. Lebrave et B. Cerquiglini, « E ́dition hypertextuelle et consultation de manuscrits : le projet Philectre », Hypertextes et Hypermédias, 1(2-3-4), p. 299-310, Hermès, 1997.

[19] S. Needleman and C. Wunsch, « A General Method Applicable to the Search of Similiraties in the Amino Acid Sequence of Two Proteins », J. Biol. Mol., 48, p. 443-453, 1970.

[20] V. Quint, and I. Vatton, « Grif, an Interactive System for Structured Document Manipulation », Text Processing and Document Manipulation, Proceedings of the International Conference, J. C. van Vliet, ed., p. 200-213, Cambridge University Press, 1986.

[21] V. Quint and I. Vatton, « Making structured documents active », Electronic Publishing - Origination, Dissemination and Design, 7(2), p. 55-74, juin 1994.

[22] D. Ragget, HTML 3.2 Reference Specification, W3C Recommendation, http://www.w3.org/pub/WWW/TR/REC-html32.html, janvier 1997.

[23] L.Robert, L.Likforman-Sulem, and E.Lecolinet, « Imageand Text Coupling for Creating Electronic Books from Manuscripts », Proceedings ICDAR’97, Ulm, aouˆt 1997.

[24] H. Richy, P. Frison, and E. Picheral, « Multilingual String-to-String Correction in Grif, a Structured Editor », Proceedings of Electronic Publishing 1992 (EP92), C. Vanoirbeek et G. Coray, ed., p. 183-198, Cambridge University Press, avril 1992.

[25] T.Smithand M.Waterman,« Identification of common molecular subsequences»,J.Mol. Biol., 14(7), p. 195-197, 1981.

[26] G.S.Stephen, « String Searching Algorithms», Word Scientific,Singapour,1994.

[27] R. Wagner and M. Fischer, « The string-to-string correction problem », J. ACM, 21(1), p. 168-178, 1974.

[28] M. Waterman and M. Eggert, « A New Algorithm for Best Subsequence Alignments with Application to tRNA-rRNA Comparisons », J. Mol. Biol., 197, p. 723-728, 1987.

Notes

  1. Philectre[3][18]est un projet du GIS « Sciences de la Cognition » sur le thème « Mutation de l’édition induite par le livre électronique ».
  2. D’autres opérations, telles que la permutation ou les substitutions en cascade, etc. pourraient être considérées.
  3. Pour simplifier la description de cet exemple, chaque élément ou mot est représenté par une lettre capitale. Un passage est donc représenté par une ou plusieurs lettres capitales successives. On trouvera en figure 3 un exemple de comparaison de textes composés de mots.
  4. Plusieurs expériences effectuées lors de stages de DEA, dans le cadre du projet Opéra, à l’Imag de Grenoble (F. Burgnard et A. Delfosse en 1992, L. Boivin en 1994) ont permis de mettre en correspondance des documents dont la structure ou le contenu présentent des similitudes importantes.
  5. Ces commandes sont programmées en langage C et utilisent l’API (Application Programming Interface) de Thot.
Outils personnels