TP2: Javascript et la traduction

(voir ce sujet sans les cadres: [ici])

Cadre général

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.

Classe Lexique

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:

  1. add(word) ajoute au lexique le mot passé en argument s'il n'existe pas déjà
  2. 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  			    

Classe BiLexique

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:

  1. un constructeur qui prend en argument le tableau lex chargé en début de code et qui se chargera de représenter de manière efficace le lexique bilingue en mémoire.
  2. 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é.
  3. 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é
  4. il devrait être possible d'afficher un lexique de telle manière à ce que les traductions de chaque mot du lexique bilingue soient affichées en ordre décroissant de probabilité (voir l'exemple plus bas). Aucun tri ne devrait être effectué pour réaliser cet affichage.

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),...
...

Classe Traducteur

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):

  1. 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 travailler
  2. load('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", "."]);
    
  3. getUnks() retourne les mots de la phrase en cours qui ne sont pas connus du lexique bilingue.
  4. 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(" "));
    
  5. getNbTranslations() qui retourne le nombre total de traductions qu'il est possible de former selon le processus décrit plus haut.
  6. 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).
  7. 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.

Test

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:

  • La ligne préfixée par SRC qui indique la phrase source à traduire.
  • La ligne préfixée par 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.
  • La ligne préfixée par REF qui indique la traduction de référence (celle fournie dans test)
  • La ligne préfixée par UNK qui mentionne la liste des mots de la phrase source qui sont inconnus du lexique utilisé pour faire les traductions
  • La ligne préfixée par NBT qui indique le nombre de traductions différentes qu'il est possible de générer par le processus décrit plus haut
  • La ligne préfixée par GLO qui affiche une traduction produite à l'aide de la fonction gloss
Suivent ensuite en ordre décroissant le log probabilité les (au plus) 10 traductions de cette phrase retournée par la fonction translate.

Rapport

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.

Notation

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:

  • de la lisibilité de votre code (2 points)
  • de sa bonne organisation en fonctions et en objets (4 points)
  • de la représentation en mémoire de la table de transfert (2 points)
  • de l'exactitude avec laquelle vous réalisez la fonction 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,
  • de votre rapport (2 points),
  • du bon fonctionnement global de votre code.