Projet Java TTT 2009-2010
Générateur aléatoire par chaîne de Markov
Date de rendu : 15 février 2010
I. Présentation
Le but du projet est de faire un programme qui prend une séquence de valeurs comme modèle, et
produit un générateur aléatoire de séquences qui ressemblent au modèle.
Soit O un ensemble d'objets du même type.
Le modèle est une séquence d'objets S=[o1,o2,...,on], avec n
grand. Si P=[p1,...,pm] est une séquence de m ≤ n objets, on note
n(P,S) le nombre de fois qu'apparaît P dans S. Par exemple,
n([a,a,b,a], [c,a,a,b,a,a,b,a,b,b]) = 2.
La chaîne de Markov CM d'ordre k ≥ 2 de S donne,
pour chaque séquence P=[p1,...,p{k-1}], une loi de probabilité sur
l'ensemble des objets O. Ainsi, CM(P,o) est la probabilité que l'objet
o apparaisse à la suite de la séquence P.
Celle-ci est donc obtenue à partir du modèle S par
CM(P,o)= | n([p1,...,p{k-1},o],S) |
|
n(P,S) |
Le projet consiste à calculer à partir d'une séquence d'objets
une représentation de la fonction CM, puis
de s'en servir pour générer aléatoirement des séquences d'objets.
II. Un ensemble probabilisé
Dans un premier temps, réalisez une classe ProbaSet<O> qui représente
une ensemble d'objets pondéré dans N (chaque objet o de l'ensemble a
un poids entier p(o)). La classe possède obligatoirement les méthodes suivantes :
- un constructeur sans argument qui fabrique un ensemble vide;
- une méthode void add(O o, int nombre) qui ajoute "nombre" à
p(o) (en ajoutant o dans l'ensemble s'il n'y est pas);
- une méthode void add(O o) qui ajoute 1 à
p(o) (en ajoutant o dans l'ensemble s'il n'y est pas);
- une méthode O random() qui renvoit un élément aléatoire de
l'ensemble en respectant les poids. C'est-à-dire que si X est la somme
des poids de tous les objets de l'ensemble, un objet o a une
probabilité p(o)/X d'être tiré au sort.
III. Un k-buffer
Réalisez une classe KBuffer<O> qui permet de parcourir les blocs
de k objets d'une séquence d'objets de type O. Elle doit posséder les méthodes
suivantes :
- Un constructeur qui prend comme paramètre la valeur de k.
- Une méthode add(O o) qui ajoute o à la fin. S'il y a
maintenant k+1 objets stockés, enlever le premier (on garde ainsi les
k derniers lus, dans l'ordre).
- Une méthode List<O> value() qui retourne null
s'il n'y a pas k objets stockés, et une copie de la séquence de k
objets sinon.
IV. Une chaîne de Markov
Réalisez une classe MarkovChain<O> qui simule l'application CM de
la partie I. En fait, on associe à chaque séquence P=[p1,...,p{k-1}] un
objet de la classe ProbaSet<O> contenant, pour chaque objet o qui peut
suivre P dans S, l'objet o avec le poids n([p1,...,p{k-1},o],S). Par
exemple si S est une séquence de caractères S="aabaabbaaba" et que k=4,
l'objet MarkovChain<Character> associe à la séquence "aab" le ProbaSet<Character> {(a,2),(b,1)} puisque a suit
deux fois "aab" dans S et b une fois.
Elle doit posséder les méthodes suivantes :
- Un constructeur sans argument.
- Une méthode void add(List<O> P, O o) qui
ajoute 1 au poids de o dans le ProbaSet<O> associé à la
séquence P (représentée par une liste).
- Une méthode
List<O> generate(int size, List<O> start)
qui en partant d'une séquence start de longueur k-1, génère
aléatoirement, 1 par 1, les objets qui suivent en respectant les
ProbaSet<O> associés: le premier élément o est généré selon le ProbaSet<O>
de start. On met ensuite o à la fin de start et on enlève le premier
élément (utilisez le KBuffer<O>), et on génère selon le ProbaSet<O> de la
séquence obtenue, etc. On continue ainsi jusqu'à avoir généré size
objets, ou bien être tombé sur un ProbaSet<O> vide.
V. Un constructeur de chaîne de Markov
Réalisez une classe MarkovChainBuilder qui contient des
méthodes static pour générer des chaînes de markov :
- MarkovChain<Character> generate(int k, String s) : fabrique
la chaîne d'ordre k associée à la séquence de caractères s.
- <O> MarkovChain<O> generate(int k, Iterator<O> it) : fabrique
la chaîne d'ordre k associée à la séquence parcourue par l'itérateur it.
VI. Rendu du projet
Le rendu du projet consiste en une archive zip contenant les sources du projet et des fichiers permettant
de tester le projet, ainsi qu'un rapport en pdf. L'archive doit être nommée JavaTTT_XXXX_YYYY.zip
où XXXX et YYYY sont les noms des auteurs du projet; le désarchivage doit créer un répertoire de même nom
JavaTTT_XXXX_YYYY dans lequel se trouvent tous les fichiers rendus.
Dans votre rapport :
- vous devez expliquer comment utiliser votre programme (ajoutez une
ou plusieurs classes avec un main qui permet de voir différentes
exécutions du programmes);
- vous devez justifiez tous vos choix de structures de données internes
aux classes demandées;
- vous devez signaler tout ce qui ne fonctionne
pas correctement;
- vous devez montrer des exemples d'utilisation en prenant comme
exemples des textes en langue naturelle. Pour ce faire, il suffit de
passer un Scanner en deuxième argument de la méthode generate de la
classe MarkovChainBuilder: cela fonctionne directement puisque un
Scanner est un Iterator de String.
Annexe : un exemple détaillé
On considère pour cet exemple une séquence S contenant n=10 objets
représentés par des images :
S=








Fabrication de la chaîne de Markov :
On prend k=3. Il s'agit donc dans un premier temps, de
fabriquer une simulation c de la CM en associant à tout
couple (k-1=2) d'images (o1,o2) une liste probabilisée d'images. Elle
est calculée, pour chaque couple (o1,o2) qui a une image, en regardant
quels sont les images qui suivent (o1,o2) dans S. Par exemple, la
séquence 
apparaît 3 fois dans
S; une fois suivie par
et deux fois suivie par
. En procédant ainsi pour tous les couples
possibles, on a au final :
c(
) = { (
,1), (
,2) }
c(
) = { (
,1) }
c(
) = { (
,1) }
c(
) = { (
,1), (
,2) }
c(
)= { (FIN,1)
}
Utilisation de la chaîne de Markov :
Une fois la CM calculée, on peut générer aléatoirement des
séquences. Pour cela on se donne un paramètre size, ici size=6,
qui correspond au nombre maximum d'objets générés, et d'un début start qui
est une séquence de taille k-1. Ici il s'agit donc d'un couple, et on
prend start=
pour l'exemple.
La génération se déroule de la façon suivante, au début P=start et
évolue au fur et à mesure. Le résultat est une séquence R qui est vide
au début :
- P=

: on tire au sort dans
c(P)= { (
,1) }. Comme il n'y a qu'un
élément, le tirage au sort retourne
. On enlève le
premier élément de P, et on ajoute l'élément tiré au sort à la
fin. L'élément retiré est ajouté au résultat : R =
.
- P=

: on tire au sort dans
c(P)= { (
,1) }. Comme il n'y a qu'un
élément, le tirage au sort retourne
. On enlève le
premier élément de P, et on ajoute l'élément tiré au sort à la
fin. L'élément retiré est ajouté au résultat : R = 
.
- P=

: on tire au sort dans
c(P)= { (
,1), (
,2)
}. On a 1 chance sur 3 de tirer au sort
et 2 chances sur 3 de tirer au sort
. On suppose
que le hasard choisit
. On enlève le
premier élément de P, et on ajoute l'élément tiré au sort à la
fin. L'élément retiré est ajouté au résultat : R = 

.
- P=

: on tire au sort dans
c(P)= { (
,1), (
,2)
}. On a 1 chance sur 3 de tirer au sort
et 2 chances sur 3 de tirer au sort
. On suppose
que le hasard choisit
. On enlève le
premier élément de P, et on ajoute l'élément tiré au sort à la
fin. L'élément retiré est ajouté au résultat : R = 


.
- P=

: on s'arrête, car la
somme des tailles de R et de P vaut 6, on a généré suffisament
d'images. On ajoute P à la fin de R, le résultat de cette génération
aléatoire est donc
R = 



