Exercice


h1 10/13/2008 03:15:00 PM

Il me reste treize jours pour finir de rédiger ma thèse. Pendant ce temps là, pour que je ne sois pas le seul à bosser, voici un petit exercice de prog qui m'est passé par la tête. On peut représenter du texte par le type string en Caml. On veut ensuite représenter du texte annoté, quand les annotations forment un arbre: soit deux annotations sont disjointes, soit l'une est incluse dans l'autre. Pensez par exemple à la grammaire au collège, "sujet" , "verbe", "complément" sont regroupés pour former une "phrase":

type annot =
(* Par exemple.. *)
| Sujet | Verbe | Complément | Phrase
type t =
| Text of string
| Annot of string * t
| Concat of t list

Il est aisé de travailler avec ce type. Et il représente exactement ce qu'on veut, il y a bijection. Maintenant, je veux une solution aussi satisfaisante quand les annotations ne forment plus un arbre mais peuvent se recouvrir partiellement. Pensez par exemple à du HTML mal formé: <red>b<b>a</red>b</b>i. Sauf que moi j'ai une utilisation moins crade en tête, mais c'est une autre histoire. Vos idées sont bienvenues, sinon je posterai peut être une solution plus tard...

Libellés :


3 commentaires:

  • Désolé je fais simplement un test openID

    Par Anonymous Anonyme, Ã 20/10/08 20:43  

  • Comme tu as fini ta thèse demain, tu va pouvoir revenir sur ce problème ;-)

    Je modéliserais ça par une string simple, et à côté une collection de couples (intervalle, annotation). Chaque intervalle désigne bien sûr la sous-string où est appliquée l'annotation.

    On va avoir envie d'ajouter et supprimer des annotations, et surtout de trouver la listes des annotations concernant un caractère (annotations que j'appelle "en vie").

    Pour cela, je gèrerai la collection des extrémités d'intervalles par un arbre genre Set ou Map, qui permette également de trouver l'extrémité juste avant ou juste après un (index de) caractère donné.

    Sur chaque début d'intervalle on stocke la liste des annotations en vie pour ce caractère. Il y a bien sûr pas mal de partage mémoire entre les listes.

    Ça a l'air générique comme problème, il a peut-être des choses qui existent. Dis-nous la solution que tu trouveras !

    Par Anonymous Anonyme, Ã 25/10/08 14:10  

  • Petite remarque : pourquoi le type 'annot' n'est-il pas utilisé ?

    Par Blogger Alp Mestan, Ã 25/10/08 14:35  

Un commentaire ?

< Accueil