1. Combiner des "streams" de données à partir de plusieurs collections

1.1. Intro

• la requête contient les mots A, B et C
• la collection contient des documents ainsi: (on désigne par M... des mots autres que A, B et C)

 D1 :  A,M...
 D2 :  B,M...
 D3 :  C,M...
 D4 :  A,B,M...
 D5 :  B,C,M...
 D6 :  A,B,C....
 D7 :  M....
 D8 :  M....

autrement dit, il y a de documents qui ont tous les mots de la requête, ou bien seulement une partie, ou bien aucun mot.

1.2 Algo naif

• pour chaque mot r de la requête (donc ici, pour A, puis B, puis C)
• pour chaque document d de la collection
• vérifier si d contient r,
• si oui, faire les calculs, sélectionner d, etc.
• fin pour
• fin pour

1.2 Algo plus efficace

1.2.1 Idée

1.2.2 Indices

1.2.3 Outil

1.2.4 Cas particulier pour un seul mot dans la requête

• tant que (d = TD(r).nextDoc()) est un document valide
• vérifier si d contient r,
• si oui, faire les calculs, sélectionner d, etc.
• fin tant que

1.2.5 Idée du cas général (plusieurs mots dans la requête)

 E[0] = {TD(A).nextDoc(), TD(B).nextDoc(), TD(C).nextDoc()}

1.2.6 Algorithme du cas général (plusieurs mots dans la requête)

• initialiser un vecteur de "streams" E=[TD(r_i).nextDoc()] pour chaque mot r_i de la requête
• tant que qEnd(E) n'est pas vrai
• soit d = trouverMinIdDocDans(E)
• vérifier si d contient r,
• si oui, faire les calculs, sélectionner d, etc.
• nextDocs(E)
• fin tant que

• fonction nextDocs(E)
• m = trouverMinIdDocDans(E)
• pour chaque stream-élément i de E
• s'il est égal à m, appeler TD(r_i).nextDoc()
• fin fonction

1.3 Lucene

1.3.1 Fonctionnalités à réaliser

    public class TermData {
	public        Term          queryTerm   = null;
	public        TermDocs      termDocs    = null;
	public        int           currentDoc  = -1;
	
	private final int[]         docBuff     = new int[32];
	private final int[]         freqBuff    = new int[32];
	private       int           pointer     = 0;
	private       int           pointerMax  = 0;
	public TermData() {}
        private int nextDoc() throws IOException { 
         // a faire
        }

   private TermData[] termData;

• on crée un objet (dérivé) de la classe IndexSearcher
• on crée un objet (dérivé) de la classe Query, qui représente notre requête, à l'aide d'un analyseur lexical de requêtes
• on crée un objet (dérivé) de la classe Collector, qui nous servira à recueillir un par un les numéros d'identification des documents apparié à leur "score" (c'est-à-dire mesure de similarité du document correspondant avec notre requête -- pour représenter avec quelle qualité chaque document satisfait notre requête).
• on appelle la méthode search de l'IndexSearcher.
• puisque le Collector utilisé trie ("par lui-même") les (id des) documents selon l'ordre décroissant du score, à la fin on rend le résultat en énumérant tout simplement les X premiers documents, avec X donné initialement sur la ligne de commande.

1.3.2 Classes et outils disponibles et nécessaires pour notre travail

	private int nextDoc() throws IOException {
	    // on incremente le pointeur
	    // si le pointeur a atteint ou dépassé le pointeur maximal
	    //////// re-remplir les tampons avec termDocs.read()
	    //////// et réassigner le pointeur maximal à ce qu'on vient de lire
            //////// et remettre pointeur à zéro 
	    //////// si on n'a en fait rien lu, c'est la fin, donc
	    //////////////  on met currentDoc à NO_MORE_DOCS, et on le rend
            //////// finsi
            // finsi
	    // on met currentDoc à ce qui est pointé par pointer dans le tampon docBuff
	    // on rend currentDoc
	}

    public void nextDocs(TermData[] t) throws IOException  {
	// trouver le docId minimal parmi les currentDoc des elements de t
	// pour tous les entiers de 0 a termCount (excluant termCount lui-meme)
	/////// si le currentDoc de l'element courant de t est minimal
	///////////////// lui appeler nextDoc() dessus
    }

1. Télécharger l'archive archTp4.tar.gz, et ouvrez-là dans un répertoire dédié à ce TP, et lancez make une fois
2. Écrivez le code complet de la méthode TermData.nextDoc() dans similarity/SimScorer.java
3. Écrivez le code complet de la méthode Scorer.nextDocs() dans similarity/SimScorer.java
4. Testez avec une commande comme

java -jar similarity.jar search testOk3/luceneIndex 'armstrong marathon york' 5 _

5. Expliquez en détail la sortie écran, en lisant dans le code, en regardant dans data avec grep, etc.

2. Généralités sur les mesures de similarité

2.1 Utilité de la similarité

• calculer les similarités entre la requête et chaque document
• trier les documents dans l'ordre décroissant
• donner comme réponse la liste des N premiers documents, où N est par exemple fixé par l'utilisateur.

2.2 Définitions préliminaires

Exemple

• Document T

The Prime Minister decided to make a public statement on TV in the evening. 

• Document U

This week's macroeconomical indices have been commented upon by the
Minister of Economy this morning and are going to also be commented upon in the
evening by the Prime Minister.

        minister statemement economy

comment,decide,economy,evening,index,macroeconomical,make,minister,morning,prime,public,statement,TV,week.

 T  = (0,1,0,1,0,0,1,1,0,1,1,1,1,0)
 U  = (2,0,1,1,1,1,0,2,1,1,0,0,0,1)
 R  = (0,0,1,0,0,0,0,1,0,0,0,1,0,0)

2.3 Définitions des similarités

2.3.1 Similarité du cosinus

• norme d'un vecteur T de dimension n :

   |T| = sqrt(T1 * T1 + T2 * T2 + ... + Tn * Tn)

• produit scalaire de deux vecteurs T et U de dimension n :

      T . U = T1 * U1 + T2 * U2 + ... + Tn * Un
  

• similarité du cosinus de T et U

      simCos(T,U) = (T . U) / (|T| * |U|) 
  

2.3.2 Similarité basée sur la distance euclidienne

 DE(T,U) = sqrt((T1 - U1)2 + (T2 - U2)2 + ... + (Tn - Un)2)  

 1/DE(T,U)

 DE(T,U) = 0

2.3.3 Coefficient de Jaccard

2.3.4 Coefficient de Jaccard généralisé

  simJaccG(T,U) = (T . U) / (|T|2 + |U|2  -  (T . U))

2.4 Exercices

1. Calculez les quatre similarités pour chacune des paires

  (T,U)  (T,R)  (U,R)  (U,T)  (R,T)  (R,U)

2. Que pouvez vous observer, par exemple au sujet de (T,U) et (U,T) ? Ceci semble-t-il être vrai pour d'autres paires du même type, comme par exemple (R,T) et (T,R) ?
3. Pouvez-vous justifier formellement ce que vous venez d'observer au point précédent ?

3. Modification de la similiarité par défaut de Lucene

3.1 But de ce travail

3.2 Détails de la base de code existante

3.2.1 Termes d'un document

     TermFreqVector[] docTermFreqVect = docReader . getTermFreqVectors(scoreDoc);

	TermFreqVector[] docTermFreqVect = docReader . getTermFreqVectors(scoreDoc);
	final int howManyTermFreqVects = docTermFreqVect . length;
	int contentFieldNdx = -1;
	for(int kField = 0; kField < howManyTermFreqVects; kField++) {
	    if(docTermFreqVect[kField] . getField() . equal("content")) {
		contentFieldNdx = kField;
	    }
	}
	if(contentFieldNdx < 0) {
	    throw new IOException("Cannot find the 'content' field among the ones with term frequencies");
 	}

	final int      docTermCount    = docTermFreqVect[contentFieldNdx] . size();
	final String[] docTerms        = docTermFreqVect[contentFieldNdx] . getTerms();   
        final int[]    docFreqs        = docTermFreqVect[contentFieldNdx] . getTermFrequencies();

  docFreqs[(Integer)docTermMap . get(toto)]

   if(docTermMap . containsKey(toto)) { // oui, le document le contient bien

3.2.2 Termes de la requête

    termData[kTerm] . queryTerm . text()

	    Map<String,Integer> queryTermMap = new HashMap<String,Integer>();
	    for(int kTerm = 0; kTerm < termCount; kTerm++) {
		queryTermMap . put(termData[kTerm] . queryTerm . text(),kTerm);
	    }

  if(queryTermMap . containsKey(thisTerm)) { // oui, la requête le contient bien

  final   float[]    queryVect;

    final int queryNdx = (Integer)queryTermMap . get(thisTerm);

3.2.3 Corps de la méthode SimScorer.score()

    public float score() throws IOException  {

	System.out.print("#" + scoreDoc + " ");
	assert scoreDoc != -1;
	float scoreValue = 0.0f;
        /// 1. Préparatifs initiaux  

	if(similarityType . equals("EuclideanSimilarity")) {
             // 2. Calcul similarité basée sur la distance euclidienne
	}
	else if(similarityType . equals("CosineSimilarity")) {
             // 3. Calcul similarité du cosinus
	}
	else if(similarityType . equals("JaccardSimilarity")) {
             // 4. Calcul coefficient de Jaccard
	}
	else if(similarityType . equals("GenJaccardSimilarity")) {
             // 5. Calcul coefficient de Jaccard généralisé
	}
	else {
	    throw new IOException("Unknown similarity type " + similarityType); 
	}
	System.out.println(similarityType + " score=" + scoreValue);
	return scoreValue;
    }

3.3 Détails algorithmiques pour les préparatifs initiaux et pour le calcul de chaque mesure de similarité

3.3.1 Préparatifs initiaux

 on récupère le TermFreqVector[] de scoreDoc depuis le reader
 on récupère la longueur du tableau de TermFreqVectors qu'on vient de récupèrer
 on se prend le contentFieldNdx à -1
 boucle pour chaque valeur entière de 0 au nombre égal à la longueur du tableau de TermFreqVectors
    si getField() . equals("content") appliquée à l'élé,ent courant du tableau de TermFreqVectors
        alors on a trouvée l'indice recherché, donc on le met dans contentFieldNdx
 finboucle
 si contentFieldNdx n'a pas de bonne valeur, on lève une exception
 on se prend une Map<String,Integer> docTermMap qu'on instancie avec new HashMap<String,Integer>();
 on se prend dans docTermCount le nombre d'éléments du TermFreqVector choisi (c'est-à-dire docTermFreqVect[contentFieldNdx])
 on se prend le String[] docTerms depuis, avec getTerms();
 boucle pour chaque valeur entière de 0 à docTermCount // pour remplir la docTermMap
    on met dans docTermMap l'élément courant de docTerms ainsi que son indice
 finboucle 

3.3.2 Calcul similarité basée sur la distance euclidienne

  on récupère dans int[] docFreqs les fréquences du document courant

	    float sumOfWeightDiffSq          = 0;
	    int   qAllQueryTermsInDoc        = 1;      
      
  on déclare, instancie et remplit la table de hachage queryTermMap comme expliqué au 3.2.2
  boucle pour chaque valeur entière de 0 à docTermCount 
     soit thisTermW la valeur de l'élément courant de  docFreqs
     si la queryTermMap contient le terme courant du document (on les a tous dans docTerms -- voir 3.3.1) alors
         on récupère son indice queryNdx depuis la queryTermMap (voir 3.2.2)
         on rajoute a sumOfWeightDiffSq la quantité (thisTermW - queryVect[queryNdx]) * (thisTermW - queryVect[queryNdx])
         si thisTermW n'est pas égale à queryVect[queryNdx], alors 
             qAllQueryTermsInDoc est mise à z´ro
         finsi
     sinon
          on rajoute a sumOfWeightDiffSq la quantité thisTermW * thisTermW
          qAllQueryTermsInDoc est mise à z´ro
     finsi
  finboucle
  si docTermCount et termCount sont égaux et que qAllQueryTermsInDoc vaut 1 alors
      scoreValue = Float . MAX_VALUE;
  sinon
      scoreValue prend la valeur de 1 divisée par sumOfWeightDiffSq
  finsi

3.3.3 Calcul similarité du cosinus

  on récupère dans int[] docFreqs les fréquences du document courant
  on calcule docNorm (la norme du vecteur de frequences du document: boucle pour la somme des carrés, et sqrt() après)
  on se prend float       dotProd = 0; pour calculer le produit scalaire ("the dot product" en anglais)
  boucle pour chaque entier de 0 à termCount (c'est-à-dire pour les terme de la requête)
     on se prend final String queryTerm le terme courant (voir 3.2.2)
     si le document contient également queryTerm parmi ses termes (utilisez docTermMap, voir la fin de 3.2.1)
        récupérez l'indice docTermCoord de queryTerm dans docFreqs (à partir de la docTermMap, voir la fin de 3.2.1)
        dotProd prend la valeur dotProd plus le produit queryVect[kTerm] * docFreqs[docTermCoord]
     finsi
  finboucle // (on a donc ainsi accumule dans dotProd les produits des bonnes coordonnees pour le produit scalaire)
  scoreValue prend la valeur selon la formule (qutient de dotProd par le produit des deux normes, qui sont queryNorm et docNorm)

3.3.4 Calcul coefficient de Jaccard

  on initialise intersectSize (qui est float) et queryTermNotInDocCount a zero
  boucle pour chaque entier de 0 à termCount 
    si la docTermMap contient le terme courant de la requete (voir 3.2.2 pour l'obtenir)
       intersectSize++
    sinon
       queryTermNotInDocCount++
    finsi
  finboucle
  on se prend alors float unionSize comme étant docTermFreqVect[contentFieldNdx] . size() + queryTermNotInDocCount
  la scoreValue est le quotient de intersectSize et de unionSize

3.3.5 Calcul coefficient de Jaccard généralisé

1. Implémentez les préparatifs initiaux et le calcul des quatres mesures de similarité dans la méthode SimScorer.score() (celle qui ne prend aucun argument), selon les indications, dans le fichier similarity/SimScorer.java (même fichier que là où vous avez travaillé au point précédent).
2. Compilez et testez

java -jar similarity.jar search testOk3/luceneIndex 'armstrong marathon york' 5 EuclideanSimilarity

java -jar similarity.jar search testOk3/luceneIndex 'armstrong marathon york' 5 CosineSimilarity

java -jar similarity.jar search testOk3/luceneIndex 'armstrong marathon york' 5 JaccardSimilarity

java -jar similarity.jar search testOk3/luceneIndex 'armstrong marathon york' 5 GenJaccardSimilarity

---

---