(voir ce sujet sans les cadres: [ici])
Dans ce devoir, vous allez mettre en pratique la programmation procédurale, la programmation orientée objet ainsi (probablement) que la récursivité. Votre but est de réaliser un mini système de traduction. Vous avez pour cela accès à une table de traduction (un lexique bilingue) qui servira de base à la génération de traductions. Cette table de traduction peut-être trop lourde pour être manipulée dans codeboot, aussi plusieurs versions de cette ressource sont disponibles (en ordre décroissant de taille):
Chacune de ces versions (vous n'en avez besoin que d'une pour faire
votre devoir) déclare la variable lex
qui contient un
tableau de triplets qui sont respectivement: un mot en français, un
mot en anglais et la probabilité d'association de ces deux mots. Ainsi
dans l'extrait qui suit, la probabilité que navy
traduise marine
est de 0.636364
:
var lex = [ ["civilisations","civilisations",0.715347], ["blanco","blanco",0.692308], ["marine","navy",0.636364], ...
Afin de travailler avec ces données, vous devez inclure la commande
load
au tout début de votre programme (après le commentaire
initial qui identifie votre fichier) afin d'utiliser la
variable lex
comme dans l'exemple suivant. Il vous
appartient de copier la ressource dans votre répertoire de travail, ou
dans codeboot.
note:vous ne devez pas faire l'hypothèse que la
ressource lex
est triée (en fait certaines versions
distribuées plus haut ne le sont pas)
load("ibm-0.0.js"); // ou une autre ressource distribuee print(lex.slice(0,10)); // produira l'affichage suivant (sur une ligne): aaa,aaa,0.4,aac,acc,0.2,aad,aal,0.304348,aalto,aalto,0.75, aaltonen,aaltonen,0.761905,aamer,aamer,1,aan,aan,0.6, aarhus,aarhus,0.104784,aaron,aaron,1,aartsen,aartsen,0.382353
Note: si vous effectuez votre devoir sur codeboot, vous avez tout intérêt à prendre une table de petite taille. Les exemples d'exécution que je donne dans la suite sont produits avec la plus grande table.
Vous devez remettre un programme devoir2.js
qui offre un
ensemble de fonctionalités décrites ci-après. Vous êtes encouragés à
développer vos propres objets pour cela, mais n'attendez pas que nous
ayons couvert cette matière pour commencer: vous pouvez déjà réaliser
ce devoir de manière procédurale. Vous pourrez par la suite
réorganiser votre code à l'aide d'objets selon les suggestions qui
sont faites dans le sujet. Votre devoir doit accompagné d'un rapport
dont le contenu est détaillé plus loin.
Une partie de votre code est dédiée à la représentation du vocabulaire d'une langue (ou lexique). Les fonctionalités minimales d'un lexique que vous devez implémenter sont les suivantes:
add(word)
ajoute au lexique le mot passé en argument
s'il n'existe pas déjàanagrams(word)
retourne la liste (tableau) des mots
du vocabulaire qui sont
des anagrames du
mot passé en argument. Le mot passé en argument ne doit pas figurer
dans le résultat, même s'il s'agit d'un mot du lexique.Voici un exemple de programme qui pourrait être exécuté à l'aide de votre code.
load("ibm-0.0.js"); // definit la variable lex var lexique = new Lexique(); for (var i=0; i <lex.length; ++i) lexique.add(lex[i][0]); // le mot francais print(lexique.anagrams("rats")); // devrait produire: arts,star,tsar
Afin de réaliser des traductions, vous devez représenter
efficacement le lexique bilingue de la table chargée en début de
programme (par la commande load
discutée plus haut). La
seule contrainte qui vous est donnée est que les traductions d'un mot
doivent être rangées en ordre décroissant de probabilité. La première
traduction accessible pour un mot source donné doit donc être la plus
probable selon la table que vous avez chargée. Aussi, pour des raisons
d'efficacité (surtout sous codeboot), vous pouvez encoder seulement
les n
meilleures traductions de chaque mot source
(où n
est un paramètre, par ex. 5
). Je vous
recommande pour cela d'écrire une classe qui doit
offrir minimalement les fonctionalités suivantes:
lex
chargé en début de code et qui se chargera de
représenter de manière efficace le lexique bilingue en mémoire.getTranslations(source)
retourne le tableau des
traductions disponibles pour le mot source avec la probabilité
associée, et ce, en ordre décroissant de probabilité.getScore(source,target)
retourne la probabilité
d'association dans le lexique bilingue des deux mots. Si deux mots ne
constituent pas une paire dans le lexique bilingue, alors 0 est
retournéVoici un exemple de programme qui pourrait être exécuté à l'aide de votre code.
load("ibm-0.0.js"); // definit la variable lex var bilex = new BiLexique("largest",lex); // largest le nom donné au lexique print(bilex); // pourrait produire qqchose comme le lexique largest est chargé et contient 95275 entrées pour 48573 mots sources ... abandonnant -> (abandoning,-3.01),(dropping,-4.01) abandonne -> (abandons,-1.39),(abandon,-3.60),(abandoning,-4.14),(abandoned,-4.38) abandonnent -> (abandon,-3.99),(abandoning,-4.14) abandonner -> (abandon,-1.25),(abandoning,-2.57),(abandoned,-3.15),(drop,-3.70),... ...
Vous devez implémenter un traducteur qui exploite un lexique
bilingue. Les traductions sont produites en remplaçant chaque mot de
la phrase à traduire par l'une de ses traductions dans le lexique
bilingue. Les mots sources inconnus du lexique seront reproduits tel
quel dans la traduction. Le score d'une traduction est le produit des
probabilité de chaque association impliquée. Afin d'éviter les
problèmes rencontrés lorsqu'on multiplie ensemble plusieurs nombres
inférieurs à 1, on calculera le score dans le domaine des logs (avec
la fonction Math.log()
), aussi le score d'une traduction
sera-t-il donnée par la somme des log probabilités de chaque
association impliquée. On admettra que le log probabilité associé à un
mot inconnu (traduit par lui même) est -3
Les fonctionalités suivantes doivent être implémentées (des exemples sont fournis pour chaque fonctionalités):
set(phrase)
prend en argument un tableau de mots qui
représente la phrase à traduire et en fait la phrase courante sur
laquelle votre traducteur va travaillerload('ibm-0.0.js'); // definit la variable lex ... var tr = new Traducteur(...); // indique la phrase sur laquelle travailler tr.set(["je", "parle", "de", "la", "commission", "de", "la", "pêche", "."]);
getUnks()
retourne les mots de la phrase en cours qui
ne sont pas connus du lexique bilingue.tr.set(["je", "parle", "de", "la", "commission", "de", "la", "pêche", "."]); // affiche de les mots inconnus de la phrase source print('UNK', tr.getUnks().join(" "));
getNbTranslations()
qui retourne le nombre total de
traductions qu'il est possible de former selon le processus décrit
plus haut.gloss()
retourne une traduction (un tableau de mots)
et sa probabilité en prenant pour chaque mot de la phrase en cours une
traduction au hasard dans le lexique. Ainsi, si dans le lexique
bilingue, les associations suivantes sont diponibles, alors une
traduction produite pourrait être: ["such", "be", "the", "job",
"from", "eu", "eu", "european", "and"]
avec comme
score -29.67
, la somme des logs probabilités de chaque
association impliquée (en gras dans
l'exemple -2.64-3.01-1.33-3.54-1.15-1.57-3.47-8.72-4.24
):
telle -> (such,-2.64) (kind,-3.50) sera -> (will,-2.38) (be,-3.01) la -> (the,-1.33) (a,-3.33) tâche -> (task,-0.98) (job,-3.54) (tasks,-4.02) de -> (of,-0.77) (from,-1.15) (to,-1.62) l -> (europe,-1.14) (human,-1.46) (eu,-1.57) union -> (union,-1.47) (eu,-3.47) européenne -> (european,-0.72) (eu,-2.19) (europe,-3.99) . -> (.,-0.04) (and,-4.24) (,,-4.56)On notera que deux appels à
gloss
retourneront (à priori)
des résultats différents. Si un mot dans la phrase en cours n'est pas
connu, alors ce mot est laissé tel quel dans la traduction (il est sa
propre traduction) et le score de l'association est fixée
à -3
(domaine logarithmique).
translate(n)
qui retourne un tableau des (au
plus) n
meilleures traductions de la phrase en cours.
Contrairement à la fonction gloss
qui retourne une
traduction aléatoire, vous chercherez ici à produire les traductions
de meilleur coût (la somme de logprob la plus grande). Dans la mesure
où le score d'une traduction est la somme des associations impliquées,
la traduction de meilleur score est celle obtenue en prenant pour
chaque mot source, sa traduction la plus probable. Dans l'exemple
précédant, la traduction la plus probable est donc ["such",
"will", "the", "task", "of", "europe", "union", "european",
"."]
. Votre fonction doit vérifier qu'aucune traduction ne contiendra le
mot an
suivi (directement) d'un mot commençant par
une consonne, ni aucun mot a
suivi
(directement) d'un mot commençant par une voyelle.
Vous disposez de phrases de test ainsi que de leur traduction de
référence (traduction humaine) dans le
fichier test-100.js que
vous chargerez également au début de votre programme à l'aide de la
commande load
. Voici ce à quoi ressemble ce fichier:
var test = [ ["telle sera la tâche de l union européenne .", "that will be the task of the european union ."], ["ce n est pas le travail du parlement .", "this is not a job for parliament ."], ["le fait d avoir des évaluations différentes rend-il service ?", "is it laudable that different assessments have been made ?"], ... ];
Vous devez remettre une fonction tests()
qui passe en
revue chacune des phrases du tableau test
, affiche ses 10
meilleures traductions en ordre décroissant de (log) probabilité, la
traduction de référence, ainsi que la liste des mots de la phrase en
cours qui sont inconnus du lexique utilisé pour la
traduction. L'affichage que votre programme doit produire est prescrit
par l'exemple qui suit
(cliquer ici pour une trace
complète produit à l'aide de la plus grosse table):
--- SRC 1: telle sera la tâche de l union européenne . ANA 1: telle sare al tâche ed l union européenne . REF 1: that will be the task of the european union . UNK 1: NBT 1: 37632 GLO 1: kind will the job in europe eu european and -25.73 -- 1 such will the task of europe union european . -11.46 2 such will the task of europe union eu . -12.92 3 such will the task of europe union europe . -14.72 4 such will the task of europe union union . -15.00 5 such will the task of europe union european and -15.66 6 such will the task of europe union european , -15.98 7 such will the task of europe union eu and -17.13 8 such will the task of europe union eu , -17.44 9 such will the task of europe union europe and -18.93 10 such will the task of europe union europe , -19.24 --- SRC 2: ce n est pas le travail du parlement . ANA 2: ce n tes psa el travail du parlement . REF 2: this is not a job for parliament . UNK 2: NBT 2: 6065280 GLO 2: it cannot has step president job on house , -22.91 -- 1 this never is not president work parliament . -7.60 2 this never is not president work house . -8.80 3 this never is not president work of parliament . -9.11 4 this never is not president work of house . -10.31 5 this never is not president work parliament and -11.81 6 this never is not president work parliament , -12.12 7 this never is not president work house and -13.00 8 this never is not president work house , -13.31 9 this never is not president work of parliament and -13.32 10 this never is not president work of parliament , -13.63
Les choses suivantes sont affichées pour chaque paire de phrases
du tableau test
:
SRC
qui indique la phrase
source à traduire.ANA
qui affiche une
tranformation de la phrase source où chaque mot qui possède un
anagramme dans le lexique est remplacé (aléatoirement) par un de ses
anagrammes.REF
qui indique la traduction
de référence (celle fournie dans test
)UNK
qui mentionne la liste des
mots de la phrase source qui sont inconnus du lexique utilisé pour
faire les traductionsNBT
qui indique le nombre de
traductions différentes qu'il est possible de générer par le processus
décrit plus hautGLO
qui affiche une traduction
produite à l'aide de la fonction gloss
translate
.
Vous devez remettre un rapport d'au plus 3 pages qui décrit
l'algorithme avec lequel vous avez produit vos traductions dans la
fonction translate
. Vous indiquerez également dans ce
rapport tout ce qui vous semble pertinent (encodage des données,
problèmes rencontrés, etc.). Ce rapport peut être au format pdf ou
simplement au format texte.
Votre code sera exécuté sur un interpréteur ligne de commande
compatible avec les codes vus en cours (js24
installé sur
les machines d'enseignement). La dernère ligne de votre programme doit
être un appel à la fonction tests
décrites plus
haut. Lors des tests, nous utiliserons une autre table de traduction
et un autre jeu de test que ceux chargés par votre programme,
possiblement plus grande que celle que vous avez utilisée.
Lorsqu'exécuté sur un interpréteur ligne de commande, votre programme doit être suffisamment rapide pour executer toutes les traductions en quelques secondes au plus (incluant le temps d'encodage du lexique en mémoire) pour le plus grand des lexiques. Vous devez donc réfléchir à la façon de représenter vos données en mémoire.
Ce travail est à faire de préférence en binôme, mais il est possible de le faire seul. Si vous travaillez en binôme, il est important que le nom des deux personnes soit indiqué en entête de tous les documents remis.
Conseil: Commencez à travailler dès maintenant. Si vous avez l'impression d'écrire souvent du code très similaire c'est que vous pouvez l'organiser plus efficacement.
Notation: La notation dépendra:
translate
(3 points). Le code que j'ai utilisé
pour produire les traces d'exécution ne parvient pas nécessairement à
trouver les 10 meilleurs traductions d'une phrase source et n'aurait
par conséquent pas la note maximale,