/*
Copyright 2012-2014 Samuel Gesche

This file is part of the Greek Reuse Toolkit.

The Greek Reuse Toolkit is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

The Greek Reuse Toolkit is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with the Greek Reuse Toolkit.  If not, see <http://www.gnu.org/licenses/>.
*/

package fr.cnrs.liris.drim.grt.proc.recherche;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import fr.cnrs.liris.drim.grt.modele.Citation;
import fr.cnrs.liris.drim.grt.modele.Coordonnee;
import fr.cnrs.liris.drim.grt.modele.Lemme;
import fr.cnrs.liris.drim.grt.modele.OrdreStrict;
import fr.cnrs.liris.drim.grt.modele.Passage;
import fr.cnrs.liris.drim.grt.modele.Reference;
import fr.cnrs.liris.drim.grt.modele.Terme;
import fr.cnrs.liris.drim.grt.modele.listes.NomsPropres;
import fr.cnrs.liris.drim.grt.proc.Processus;
import fr.cnrs.liris.drim.grt.proc.parsers.PassageType;
import fr.cnrs.liris.drim.grt.proc.parsers.References;

/**
 *
 * @author Sam
 */
public class RechercheParVoisinage implements Processus, Recherche {
    
    private double avancement;
    private double avancementMax;
    private String statut = "";
    private long momentDebut;
    private long momentFin;
    
    private Passage source;
    private Passage citeur;
    
    private int traitementTermes;
    private int motsVides;
    private int multicitations;
    
    /**
     * Initialise une recherche par voisinage.
     * @param source le texte cité
     * @param citeur le texte qui a cité (ou pas)
     */
    public RechercheParVoisinage(Passage source, Passage citeur) {
        this.source = source;
        this.citeur = citeur;
        
        traitementTermes = Recherche.TERMES_BRUTS;
        motsVides = Recherche.TEXTE_AVEC_MOTS_VIDES;
        multicitations = Recherche.CITATIONS_VERS_UNE_SEULE_SOURCE;
        
        avancement = 0;
        
        avancementMax = 1; // on verra le moment venu
    }

    @Override
    public void setTraitementTermes(int TERMES_QQCH) {
        traitementTermes = TERMES_QQCH;
    }

    @Override
    public void setImportanceOrdreMots(int L_ORDRE_DES_MOTS_QQCH) {
        throw new UnsupportedOperationException("Non pertinent.");
    }

    @Override
    public void setToleranceCorrespondance(int CORRESPONDANCE_QQCH, double seuil) {
        throw new UnsupportedOperationException("Non pertinent.");
    }

    @Override
    public void setFiltrageMotsVides(int TEXTE_QQCH) {
        motsVides = TEXTE_QQCH;
    }

    @Override
    public void setMultiCitation(int CITATIONS_QQCH) {
        multicitations = CITATIONS_QQCH;
    }

    @Override
    public void setSeuilFusion(int nbMotsDifferents) {
        throw new UnsupportedOperationException("Not supported yet.");
    }
    
    @Override
    public void setSimilarite(int SIMILARITE_QQCH, int parametre, double seuilEgalite) {
        throw new UnsupportedOperationException("Not supported yet.");
    }

    @Override
    public void setSourceEtCiteurIdentiques(boolean identiques) {
        throw new UnsupportedOperationException("Not supported yet.");
    }

    @Override
    public void setFiltrageExpressionsVides(int FILTRAGE_QQCH) {
        throw new UnsupportedOperationException("Not supported yet.");
    }
    
    /**
     * Cherche des citations par voisinage dans le texte.
     * La méthode utilisée ici est celle par voisinage : pour chaque terme du 
     * texte citeur, on recherche toutes les occurrences dans le texte cité, 
     * puis on recherche un deuxième terme commun dans une fenêtre autour de 
     * chacun
     * @param tailleFenetre le nombre de termes de la fenêtre
     * @return la liste des citations trouvées
     */
    public Citation[] chercheCitations(int tailleFenetre) {
        avancementMax = 100;
        avancement = 0; statut = "lecture du document source";
        momentDebut = System.currentTimeMillis();
        
        Passage[] motsSource;
        Passage[] motsCiteur;
        if(motsVides == Recherche.TEXTE_AVEC_MOTS_VIDES) {
            motsSource = source.getAllMots();
            //System.err.println(motsSource.length+" mots source");
            avancement = 3; statut = "lecture du document citant";
            motsCiteur = citeur.getAllMots();
            //System.err.println(motsCiteur.length+" mots citeurs");
            avancement = 5;
        } else {
            motsSource = source.getAllMotsNonVides();
            avancement = 3; statut = "lecture du document citant";
            motsCiteur = citeur.getAllMotsNonVides();
            avancement = 5;
        }
        
        // Indexer tous les termes source pour retrouver rapidement 
        // dans quel mot se trouve un terme donné
        // o(n) si on considère la taille de fenêtre négligeable 
        // par rapport à celle du texte
        //System.err.println(motsSource.length + " mots à indexer (source)");
        Map<Terme, Set<Integer>> indexSource = new HashMap<>();
        for(int i=0; i<motsSource.length; i++) {
            avancement = 5+3.0*i/motsSource.length; statut = "indexation des termes source ("+(i+1)+"/"+motsSource.length+")";
            Passage mot = motsSource[i];
            Terme terme = mot.getContenu();
            if(traitementTermes == Recherche.TERMES_LEMMATISES) {
                terme = getLemmeOpti(terme);
            } else if(traitementTermes == Recherche.TERMES_NORMALISES) {
                terme = getNormOpti(terme);
            }
            if(indexSource.containsKey(terme)) {
                indexSource.get(terme).add(new Integer(i));
            } else {
                Set<Integer> nlleListe = new HashSet<>();
                nlleListe.add(new Integer(i));
                indexSource.put(terme, nlleListe);
            }
        }
        
        // Même chose pour les termes du texte citeur
        //System.err.println(motsCiteur.length + " mots à indexer (citeur)");
        Map<Terme, Set<Integer>> indexCiteur = new HashMap<>();
        for(int i=0; i<motsCiteur.length; i++) {
            avancement = 8+2.0*i/motsCiteur.length; statut = "indexation des termes citant ("+(i+1)+"/"+motsSource.length+")";
            Passage mot = motsCiteur[i];
            Terme terme = mot.getContenu();
            if(traitementTermes == Recherche.TERMES_LEMMATISES) {
                terme = getLemmeOpti(terme);
            } else if(traitementTermes == Recherche.TERMES_NORMALISES) {
                terme = getNormOpti(terme);
            }
            if(indexCiteur.containsKey(terme)) {
                indexCiteur.get(terme).add(new Integer(i));
            } else {
                Set<Integer> nlleListe = new HashSet<>();
                nlleListe.add(new Integer(i));
                indexCiteur.put(terme, nlleListe);
            }
        }
        
        // Pour chaque mot du texte citeur, lister les index de mots du texte 
        // source ayant le même terme
        // o(n)
        Map<Integer, Set<Integer>> citationsAvecSourcesCorrespondantes = new HashMap<>();
        for(int i=0; i<motsCiteur.length; i++) {
            avancement = 10+5.0*i/motsCiteur.length; statut = "recherche des correspondances [1] ("+(i+1)+"/"+motsCiteur.length+")";
            Passage mot = motsCiteur[i];
            Terme terme = mot.getContenu();
            if(traitementTermes == Recherche.TERMES_LEMMATISES) {
                terme = getLemmeOpti(terme);
            } else if(traitementTermes == Recherche.TERMES_NORMALISES) {
                terme = getNormOpti(terme);
            }
            if(indexSource.containsKey(terme)) {
                //System.err.println(" Terme retrouvé ("+i+") : "+terme);
                citationsAvecSourcesCorrespondantes.put(new Integer(i), indexSource.get(terme));
            }
        }
        //System.err.println("Citations avec sources correspondantes : " + citationsAvecSourcesCorrespondantes.keySet().size());
        
        // Pour chaque mot du texte citeur ayant un mot correspondant, lister,
        // pour chaque mot à au plus tailleFenetre de ce mot, les mots 
        // correspondants du texte source à au plus tailleFenetre de l'un des 
        // mots sources liés au mot initial.
        // (compliqué à formuler, hein ?)
        // o(n.f²), f étant la taille de la fenêtre
        ArrayList<IndexCitation> indexCitationsTrouvees = new ArrayList<>();
        int indexAvancement = 0;
        // Pour chaque mot du texte citeur ayant au moins un mot source correspondant
        for(Integer i: citationsAvecSourcesCorrespondantes.keySet()) {
            indexAvancement++;
            avancement = 15+35.0*indexAvancement/citationsAvecSourcesCorrespondantes.keySet().size(); statut = "recherche des correspondances [2] ("+(indexAvancement)+"/"+citationsAvecSourcesCorrespondantes.keySet().size()+")";
            // (liste des mots source correspondants)
            ArrayList<Integer> sourcesPossibles = new ArrayList<>(citationsAvecSourcesCorrespondantes.get(i));
            // Pour chaque mot citeur à au plus tailleFenetre du mot citeur initial
            for(int j=i.intValue()+1; j<i.intValue()+tailleFenetre; j++) {
                // Si l'on trouve ce mot dans le texte source
                if(citationsAvecSourcesCorrespondantes.containsKey(new Integer(j))) {
                    // (liste des mots source correspondant au nouveau mot citeur)
                    ArrayList<Integer> sourcesAEtudier = new ArrayList<>(citationsAvecSourcesCorrespondantes.get(j));
                    boolean trouve = false;
                    // Pour chaque mot source correspondant au mot citeur initial
                    for(Integer sourcePossible : sourcesPossibles) {
                        // Et pour chaque mot source correspondant au nouveau mot citeur
                        for(Integer sourceAEtudier: sourcesAEtudier) {
                            // Si le nouveau mot est à au plus tailleFenetre du premier
                            if(Math.abs(sourceAEtudier.intValue() - sourcePossible.intValue()) < tailleFenetre) {
                                // Une citations potentielle : deux termes communs à au plus 
                                // tailleFenetre de distance
                                // Stocké : l'index du premier mot citeur, et 
                                // l'index du premier mot cité
                                indexCitationsTrouvees.add(new IndexCitation(i, sourcePossible, tailleFenetre));
                                trouve = true;
                                break;
                            }
                        }
                        if(trouve) {break;}
                    }
                }
            }
        }
        //System.err.println("Citations trouvées : " + indexCitationsTrouvees.size());
        avancement += (motsCiteur.length - citationsAvecSourcesCorrespondantes.keySet().size());
        
        Map<IndexCitation, Double> scores = new HashMap<>();
        indexAvancement = 0;
        for(IndexCitation i: indexCitationsTrouvees) {
            //System.err.println(" "+i.source+"->"+i.citeur);
            indexAvancement++;
            //System.err.println(indexAvancement+"/"+indexCitationsTrouvees.size());
            avancement = 50+10.0*indexAvancement/indexCitationsTrouvees.size(); statut = "Recherche floue ("+(indexAvancement)+"/"+indexCitationsTrouvees.size()+")";
            // Détection de noms propres dans la fenêtre de tailleFenetre
            // to do : A vérifier si ce n'est pas le mot initial qui doit être un nom propre
            boolean aNomPropre = false;
            for(int j=i.citeur; j<i.citeur+5 && j<motsCiteur.length; j++) {
                if(NomsPropres.getInstance().contientNomComplet(
                    motsCiteur[j].getContenu())) {
                    aNomPropre = true;
                    break;
                }
            }
            
            // Recherche floue : calcul du nombre de termes correspondants 
            // sur une fenêtre de tailleFenetre (*10 en cas de nom propre)
            
            // to do : Implantation du flou dans la recherche par n-lexes aussi
            // (sauf s'il n'y a pas de différence)
            if(aNomPropre) {
                i.tailleSource *= 10;
                i.tailleCiteur *= 10;
            }
            double[][] matScores = new double[i.tailleCiteur][i.tailleSource];
            for(int a=i.citeur; a<i.citeur+i.tailleCiteur && a<motsCiteur.length; a++) {
                for(int b=i.source; b<i.source+i.tailleSource && b<motsSource.length; b++) {
                    Terme tCiteur = motsCiteur[a].getContenu();
                    Terme tSource = motsSource[b].getContenu();
                    if(traitementTermes == Recherche.TERMES_LEMMATISES) {
                        tCiteur = getLemmeOpti(tCiteur);
                        tSource = getLemmeOpti(tSource);
                    } else if(traitementTermes == Recherche.TERMES_NORMALISES) {
                        tCiteur = getNormOpti(tCiteur);
                        tSource = getNormOpti(tSource);
                    }
                    // Les termes sont mis en correspondance en utilisant 'une 
                    // combinaison des distances de Levenshtein et de Dice' pour 
                    // éliminer les 'différences irrégulières' (erreurs de copie, 
                    // fusion/séparation de termes, erreurs d'OCR...)
                    matScores[a-i.citeur][b-i.source] = getProximite(tCiteur, tSource);
                }
            }
            
            // Calcul du score de l'appariement citeur/source
            // Approche 'rapide' : pour chaque terme, on prend en compte 
            // l'appariement ayant le score maximal (même si plusieurs termes
            // d'un côté partagent le même de l'autre côté)
            double score1 = 0;
            for(int a=0; a<i.tailleSource; a++) {
                double s = 0;
                for(int b=0; b<i.tailleSource; b++) {
                    s = Math.max(s, matScores[a][b]);
                }
                score1 += s;
            }
            double score2 = 0;
            for(int b=0; b<i.tailleSource; b++) {
                double s = 0;
                for(int a=0; a<i.tailleSource; a++) {
                    s = Math.max(s, matScores[a][b]);
                }
                score2 += s;
            }
            double score = Math.max(score1, score2) / i.tailleSource;
            scores.put(i, new Double(score));
        }
        
        // Elagage : unicité de texte cité
        // En pratique : pour un texte source donné (démarrant à un index donné), 
        // on garde le texte citeur ayant le plus grand score de similarité avec 
        // lui
        // to do : attention à l'influence de la taille sur les scores de similarité
        Map<Integer, IndexCitation> citationsElaguees = new HashMap<>();
        indexAvancement = 0;
        if(multicitations == Recherche.CITATIONS_VERS_UNE_SEULE_SOURCE) {
            for(IndexCitation i : scores.keySet()) {
                indexAvancement++;
                avancement = 60+10.0*indexAvancement/scores.keySet().size(); statut = "Elagage ("+(indexAvancement)+"/"+scores.keySet().size()+")";
                int indexS = i.source;
                double score = scores.get(i);
                if(citationsElaguees.containsKey(indexS)) {
                    double aDepasser = scores.get(citationsElaguees.get(indexS));
                    if(score > aDepasser) {
                        citationsElaguees.put(indexS, i);
                    }
                } else {
                    citationsElaguees.put(indexS, i);
                }
            }
        } else {
            for(IndexCitation i : scores.keySet()) {
                indexAvancement++;
                avancement = 60+10.0*indexAvancement/scores.keySet().size();
                citationsElaguees.put(indexAvancement, i);
            }
        }
        //System.err.println("Après élagage interne : " + citationsElaguees.keySet().size());
        
        // Elagage : fusion des citations qui se chevauchent
        ArrayList<IndexCitation> citationsElaguees2 = new ArrayList<>(citationsElaguees.values());
        // peu élégant mais raisonnablement efficace
        int taille = Integer.MAX_VALUE;
        while(taille > citationsElaguees2.size()) {
            taille = citationsElaguees2.size();
            for(int i=0; i<citationsElaguees2.size(); i++) {
                for(int j=i+1; j<citationsElaguees2.size(); j++) {
                    IndexCitation i1 = citationsElaguees2.get(i);
                    IndexCitation i2 = citationsElaguees2.get(j);
                    if(i2.citeur>=i1.citeur && i2.citeur<=i1.citeur+i1.tailleCiteur && 
                        // i2 commence dans i1 : fusion (on remplace i1&i2 par i1)
                            i2.source >= i1.source && i2.source<=i1.source+i1.tailleSource) {
                        // i2 commence dans i1
                        int debutS = Math.min(i1.source, i2.source);
                        int finS = Math.max(i1.source+i1.tailleSource, i2.source+i2.tailleSource);
                        int debutC = Math.min(i1.citeur, i2.citeur);
                        int finC = Math.max(i1.citeur+i1.tailleCiteur, i2.citeur+i2.tailleCiteur);
                        i1.source = debutS;
                        i1.citeur = finS;
                        i1.tailleCiteur = finC-debutC;
                        i1.tailleSource = finS-debutS;
                        citationsElaguees2.remove(i2);
                        j--;
                    } else if(i1.citeur>=i2.citeur && i1.citeur<=i2.citeur+i2.tailleCiteur && 
                        // i1 commence dans i2
                            i2.source >= i1.source && i2.source<=i1.source+i1.tailleSource) {
                        // i2 commence dans i1
                        int debutS = Math.min(i1.source, i2.source);
                        int finS = Math.max(i1.source+i1.tailleSource, i2.source+i2.tailleSource);
                        int debutC = Math.min(i1.citeur, i2.citeur);
                        int finC = Math.max(i1.citeur+i1.tailleCiteur, i2.citeur+i2.tailleCiteur);
                        i1.source = debutS;
                        i1.citeur = finS;
                        i1.tailleCiteur = finC-debutC;
                        i1.tailleSource = finS-debutS;
                        citationsElaguees2.remove(i2);
                        j--;
                    } else if(i2.citeur>=i1.citeur && i2.citeur<=i1.citeur+i1.tailleCiteur && 
                        // i2 commence dans i1
                            i1.source >= i2.source && i1.source<=i2.source+i2.tailleSource) {
                        // i1 commence dans i2
                        int debutS = Math.min(i1.source, i2.source);
                        int finS = Math.max(i1.source+i1.tailleSource, i2.source+i2.tailleSource);
                        int debutC = Math.min(i1.citeur, i2.citeur);
                        int finC = Math.max(i1.citeur+i1.tailleCiteur, i2.citeur+i2.tailleCiteur);
                        i1.source = debutS;
                        i1.citeur = finS;
                        i1.tailleCiteur = finC-debutC;
                        i1.tailleSource = finS-debutS;
                        citationsElaguees2.remove(i2);
                        j--;
                    } else if(i1.citeur>=i2.citeur && i1.citeur<=i2.citeur+i2.tailleCiteur && 
                        // i1 commence dans i2
                            i1.source >= i2.source && i1.source<=i2.source+i2.tailleSource) {
                        // i1 commence dans i2
                        int debutS = Math.min(i1.source, i2.source);
                        int finS = Math.max(i1.source+i1.tailleSource, i2.source+i2.tailleSource);
                        int debutC = Math.min(i1.citeur, i2.citeur);
                        int finC = Math.max(i1.citeur+i1.tailleCiteur, i2.citeur+i2.tailleCiteur);
                        i1.source = debutS;
                        i1.citeur = finS;
                        i1.tailleCiteur = finC-debutC;
                        i1.tailleSource = finS-debutS;
                        citationsElaguees2.remove(i2);
                        j--;
                    }
                }
            }
        }
        //System.err.println("Après élagage externe : " + citationsElaguees2.size());
        
        // Former les citations
        ArrayList<Citation> resultat = new ArrayList<>();
        indexAvancement = 0;
        for(IndexCitation i : citationsElaguees2) {
            indexAvancement++;
            avancement = 70+10.0*indexAvancement/citationsElaguees2.size(); statut = "Formation des citations ("+(indexAvancement)+"/"+citationsElaguees2.size()+")";
            Passage pSource = new Passage("", new Passage[]{}, new HashMap<Coordonnee, Passage>());
            Passage pCiteur = new Passage("", new Passage[]{}, new HashMap<Coordonnee, Passage>());
            for(int s=0; s<i.tailleSource && i.source+s < motsSource.length; s++) {
                pSource.addSousPassage(
                        new Coordonnee(OrdreStrict.getInstance(OrdreStrict.MOTS), s), 
                        motsSource[i.source+s]);
            }
            for(int s=0; s<i.tailleCiteur && i.citeur+s < motsCiteur.length; s++) {
                pCiteur.addSousPassage(
                        new Coordonnee(OrdreStrict.getInstance(OrdreStrict.MOTS), s), 
                        motsCiteur[i.citeur+s]);
            }
            if(pSource.getNbSousPassages()>0 && pCiteur.getNbSousPassages()>0) {
                resultat.add(new Citation(pSource, pCiteur, "Trouvé par l'algorithme"));
            }
        }
        
        // Prendre les versets complets
        Map<String, Citation> descCitations = new HashMap<>();
        for(int i=0; i<resultat.size(); i++) {
            avancement = 80+20.0*i/resultat.size(); statut = "extension aux versets complets ("+(i+1)+"/"+resultat.size()+")";
            Citation res = resultat.get(i);
            Passage src = res.getCite();
            Passage src0 = src.getSousPassages()[0];
            Passage src1 = src.getSousPassages()[src.getNbSousPassages()-1];
            String txtRefSource = References.toReference(
                    src0.getReferenceInitialeDans(source), 
                    src1.getReferenceInitialeDans(source),
                    PassageType.PASSAGE_BIBLIQUE);
            Reference refSource = References.parseReference(txtRefSource, PassageType.PASSAGE_BIBLIQUE);
            Passage srcFinal = source.rassemblePassage(refSource);
            
            Passage cit = res.getCiteur();
            Passage cit0 = cit.getSousPassages()[0];
            Passage cit1 = cit.getSousPassages()[cit.getNbSousPassages()-1];
            String txtRefCiteur = References.toReference(
                    cit0.getReferenceInitialeDans(citeur), 
                    cit1.getReferenceInitialeDans(citeur),
                    PassageType.PASSAGE_PATRISTIQUE);
            Reference refCiteur = References.parseReference(txtRefCiteur, PassageType.PASSAGE_PATRISTIQUE);
            Passage citFinal = citeur.rassemblePassage(refCiteur);
            
            // Dédoublonner en passant
            Citation citFinale = new Citation(srcFinal, citFinal, res.getArgumentaire());
            descCitations.put(txtRefSource + " -> " + txtRefCiteur, citFinale);
        }
        
        // Fini !
        statut = "terminé";
        momentFin = System.currentTimeMillis();
        Citation[] rapport = new Citation[descCitations.values().size()];
        descCitations.values().toArray(rapport);
        return rapport;
    }
    
    
    Map<Terme, Lemme> lemmes = new HashMap<>();
    private Lemme getLemmeOpti(Terme t) {
        if(!lemmes.containsKey(t)) {
            lemmes.put(t, t.getLemmePrincipal());
        }
        return lemmes.get(t);
    }
    
    Map<Terme, Terme> norm = new HashMap<>();
    private Terme getNormOpti(Terme t) {
        if(!norm.containsKey(t)) {
            norm.put(t, t.getFormeNormale());
        }
        return norm.get(t);
    }

    @Override
    public double getAvancement() {
        return avancement * 1.0 / avancementMax;
    }

    @Override
    public String getStatut() {
        return statut;
    }
    
    @Override
    public long getTempsExecution() {
        if(statut.equals("") || statut.equals("terminé")) {
            return momentFin - momentDebut;
        } else {
            return System.currentTimeMillis() - momentDebut;
        }
    }
    
    private double getProximite(Terme t1, Terme t2) {
        return /*t1.getExpression().equals(t2.getExpression())?1.0:0.0;*/
                Math.max(getLevenshtein(t1, t2), getDice(t1, t2));
    }
    
    private double getDice(Terme t1, Terme t2) {
        // coefficient de similarité de Dice = 2 * card(ET(t1, t2)) / [(card(t1) + card(t2)]
        char[] c1 = t1.getExpression().toCharArray();
        char[] c2 = t2.getExpression().toCharArray();
        Set<Character> cc1 = new HashSet<>();
        Set<Character> cc2 = new HashSet<>();
        Set<Character> ccET = new HashSet<>();
        for(char c: c1) {
            cc1.add(new Character(c));
            ccET.add(new Character(c));
        }
        for(char c: c2) {
            cc2.add(new Character(c));
        }
        ccET.retainAll(cc2);
        return 2 * ccET.size() / (cc1.size() + cc2.size());
    }
    
    private double getJaccard(Terme t1, Terme t2) {
        // coefficient de similarité de Dice = 2 * card(ET(t1, t2)) / card(OU(t1, t2))
        char[] c1 = t1.getExpression().toCharArray();
        char[] c2 = t2.getExpression().toCharArray();
        Set<Character> cc2 = new HashSet<>();
        Set<Character> ccET = new HashSet<>();
        Set<Character> ccOU = new HashSet<>();
        for(char c: c1) {
            ccET.add(new Character(c));
            ccOU.add(new Character(c));
        }
        for(char c: c2) {
            cc2.add(new Character(c));
        }
        ccET.retainAll(cc2);
        ccOU.addAll(cc2);
        return ccET.size() / ccOU.size();
    }
    
    private double getLevenshtein(Terme t1, Terme t2) {
        return 1 - (levenshteinDistance2(t1.getExpression(), t2.getExpression()) / 
                Math.max(t1.getExpression().length(), t2.getExpression().length()));
    }
    
    private int levenshteinDistance(String s, String t) {
        if(s.length()==0) {
            return t.length();
        } else if(t.length()==0) {
            return s.length();
        }
        int len_s = s.length();
        int len_t = t.length(); 
        int cost = 0;

        if(s.charAt(len_s-1) != t.charAt(len_t-1)) {
            cost = 1;
        }
        
        int min = Integer.MAX_VALUE;
        min = Math.min(min, 
                levenshteinDistance(s.substring(0, len_s-1), t) + 1);
        min = Math.min(min, 
                levenshteinDistance(s, t.substring(0, len_t-1)) + 1);
        min = Math.min(min, 
                levenshteinDistance(s.substring(0, len_s-1), t.substring(0, len_t-1)) + cost);
        return min;
    }
    
    private int levenshteinDistance2(String t1, String t2) {
        int[][] distances = new int[t1.length()][t2.length()];
        for(int i=0; i<t1.length(); i++) {
            distances[i][0] = i;
        }
        for(int j=0; j<t2.length(); j++) {
            distances[0][j] = j;
        }
        for(int j=1; j<t2.length(); j++) {
            for(int i=1; i<t1.length(); i++) {
                if(t1.charAt(i) == t2.charAt(j)) {
                    distances[i][j] = distances[i-1][j-1];
                } else {
                    distances[i][j] = 1 + Math.min(Math.min(distances[i-1][j], 
                            distances[i][j-1]), distances[i-1][j-1]);
                }
            }
        }
        return distances[t1.length()-1][t2.length()-1];
    }
    
    private class IndexCitation {
        public int citeur;
        public int source;
        public int tailleSource;
        public int tailleCiteur;
        
        public IndexCitation(int citeur, int source, int taille) {
            this.citeur = citeur;
            this.source = source;
            this.tailleSource = taille;
            this.tailleCiteur = taille;
        }
    }
}
