Batch Forum Index
RegisterSearchFAQMemberlistUsergroupsLog in
Reply to topic Page 1 of 1
[JavaScript] Comment créer un correcteur orthographique
Author Message
Reply with quote
Post [JavaScript] Comment créer un correcteur orthographique 
Bienvenue à tous pour ce premier tuto
Comme vous le savez, pratiquement tout les éditeurs de textes (comme word) possède un correcteur orthographique
Je vais vous apprendre dans ce tuto comment fonctionne ces correcteurs orthographiques, bien évidemment, il y aura quelques maths derrière Okay
(Vous allez voir, c'est pas si évident)




I) INTRODUCTION


  • Premièrement, avant de se lancer dans des lignes de code interminable Laughing
    On va d'abord se poser cette question :

    Quote:
    Comment savoir si une chaîne de caractères A ressemble plus ou moins à une autre chaîne de caractères B ?


    Cette question peut sembler assez bizarre, mais si on y réfléchit bien, si on doit créer un correcteur orthographique, il y aura un moment où on aura besoin de savoir si 2 chaînes de caractères se ressemblent pour pouvoir créer une liste de proposition pour corriger la faute.

    Par exemple, si on prend les chaînes de caractères "Bonjour" et "Bonjjour", on peut se convaincre aisément qu'elles se ressemblent comme 2 gouttes d'eau
    (j'ai juste doublé le j dans la 2ème chaîne)

    Une première idée serait de vérifier si les deux chaînes ont plus ou moins la même longueur,
    Code:
    var chaine1 = "Bonjour";
    var chaine2 = "Bonjjour";

    if (Math.abs(chaine1.length-chaine2.length) < 3) console.log('ces 2 chaînes se ressemblent');

    mais on vient venir le problème ici, "dfgtcfgb" n'a rien à voir avec "Bonjour" est pourtant notre script affiche qu'elles se ressemblent

  • En fait, le problème est en effet plus compliqué qu'il en à l'air, une 2ème idée serait de vérifier si les 2 chaines contiennent plus ou moins le même nombre de 'a', de 'b', de 'c'.....
    Saut que si on inverse "Bonjour", ce qui donne "roujnoB", on voit bien que ces 2 chaines ont bien plus ou moins les mêmes caractères mais ne se ressemblent pas du tout !



II) Distance de Levenshtein



  • On va parler ici de Distance de Levenshtein : La distance de Levenshtein est une distance, au sens mathématique du terme, donnant une mesure de la différence entre deux chaînes de caractères. Elle est égale au nombre minimal de caractères qu'il faut supprimer, insérer ou remplacer pour passer d’une chaîne à l’autre. On parle aussi de distance d'édition ou de déformation dynamique temporelle.

    Je vous renvoie sur cette article wikipédia : https://fr.wikipedia.org/wiki/Distance_de_Levenshtein

  • Exemple :

      On va calculer la distance entre "Bonjour" et "Bonsoir"
      Pour ce faire, on va avoir besoin des matrices, et on va initialiser notre matrice de cette façon :

      BONJOUR
      01234567
      B1
      O2
      N3
      S4
      O5
      I6
      R7


      Et on va remplir chaque case, en procédant de cette manière, Soit (i, j) ∈ ℕ avec i la ligne et j la colonne de la case que l'on est entrain de traiter et M la matrice :
      • - Prendre la valeur de la case M(i-1, j) et lui ajouter 1
      • - Prendre la valeur de la case M(i, j-1) et lui ajouter 1
      • - Prendre la valeur de la case M(i-1, j-1) et si Chaine1[i-1] == Chaine2[j-1] alors on ajoute 0 sinon lui ajouter 1

      • Puis associer à M(i, j) la plus PETITE des 3 valeurs que l'on vient de calculer


      Si on fait case par case, on obtient ceci :
      BONJOUR
      01234567
      B10123456
      O21012345
      N32101234
      S43211234
      O54322123
      I65433223
      R76544332


      Et on lit sur la dernière case la distance de Levenshtein entre les 2 chaînes Mr. Green
      Ici, la distance est de 2 ! (On peut vite s'en convaincre, seul 2 caractères sont différents)
      Bien évidemment, je n'ai pas fait tout les calculs à la main, ce site l'a fait pour moi : http://www.let.rug.nl/kleiweg/lev/

      Cette méthode nous permet ainsi de calculer la distance entre 2 chaînes de caractères et par conséquent, on est maintenant en mesure de dire si 2 chaînes de caractères se ressemblent Very Happy
      On peut maintenant implémenter l'algorithme (ici en JavaScript) :
      Code:
      [lang=javascript]function LevenshteinDistance(a, b){
        if(a.length == 0) return b.length;
        if(b.length == 0) return a.length;
        var matrix = [];

        // increment along the first column of each row
        for (var i = 0; i <= b.length; i++) {
          matrix[i] = [i];
        }

        // increment each column in the first row
        for (var j = 0; j <= a.length; j++) {
          matrix[0][j] = j;
        }

        // Fill in the rest of the matrix
        for (var i = 1; i <= b.length; i++) {
          for (var j = 1; j <= a.length; j++) {
            matrix[i][j] = Math.min(
              matrix[i][j-1] + 1, // insertion
              matrix[i-1][j] + 1, // deletion
              matrix[i-1][j-1] + (b.charAt(i-1) == a.charAt(j-1)?0:1)
            );
          }
        }

        return matrix[b.length][a.length];
      };

      console.log(LevenshteinDistance("Bonjour","Bonsoir"));
      // 2



    Le problème avec cette algorithme c'est que sa complexité temporelle et spatiale est en O( (m+1) x (n+1) ) (m la longueur de la chaîne 1 et n la longueur de la chaîne 2)
    Si on a 200 000 mots et qu'on doit itérer dessus, ça risque d'être très long....

  • Que se passe t-il si on compare lettre après lettre, nos deux chaînes de cette façon :
    • Bonjour et B
    • Bonjour et Bo
    • Bonjour et Bon
    • Bonjour et Bons
    • Bonjour et Bonso
    • Bonjour et Bonsoi
    • Bonjour et Bonsoir

      Si je vous en parle, c'est parce qu'avec ce procédé, on peut voir une propriété intéressante se dégager ici, avec ce site : http://www.let.rug.nl/kleiweg/lev/,
      on voit assez facilement que pour remplir une case, on a seulement besoin de la ligne précédente et de la ligne courante.


  • Pour booster notre algorithme comme jamais, on va utiliser cette propriété à notre avantage en couplant ceci aux structures en arbres


III) Arbre ternaire de recherche


  • On a besoin de définir une nouvelle structure de données compatibles avec notre algorithme, et pour cela les Arbres est l'une des structures les plus adaptés
    Je parle d'arbres depuis maintenant 20 secondes, mais qu'est-ce que c'est exactement ?
    C'est une structure de données qui se définit récursivement

  • un Arbre ternaire de recherche ou ABR (en anglais, binary search tree ou BST) est une structure de données représentant un ensemble ou un tableau associatif dont les clés appartiennent à un ensemble totalement ordonné. Un arbre binaire de recherche permet des opérations rapides pour rechercher une clé, insérer ou supprimer une clé.
    Plus de détail ici : https://fr.wikipedia.org/wiki/Arbre_binaire_de_recherche

  • Un Arbre ternaire de recherche ressemble visuellement à ceci :

    Sur cette image on peut voir que cette arbre contient les mots cute, cup, as, at, he, us, et i

  • On peut tout d'abord implémenter cette structure de données en JavaScript (ici c'est du ECMAScript 6)

    Code:
    [lang=javascript]class Tree {

      constructor() {

        this.word = null;
        this.children = {};

      }

      push(word) {

        var node = this;


        for (var i = 0; i < word.length; i++) {

          var letter = word[i];

          if (typeof node.children[letter] === 'undefined') {
            node.children[letter] = new Tree();
          }

          node = node.children[letter];

        }

        node.word = word;

      }

    }


  • Pour fusionner notre algorithme de distance et cette structure de données, il faut savoir, qu'on a juste besoin de calculer la dernière case juste avec la ligne précédente,
    Donc, on va itérer dans notre arbre récursivement en calculant à chaque fois qu'on rajoute une lettre la Distance de Levenshtein si par exemple le nombre obtenu est supérieur à 3, on pourra par exemple considérer que les chaînes ne se ressemblent pas et arrêter la récursion.
    Si on trouve un mot dans notre arbre ayant une distance inférieur ou égal à 3, on pourra considérer que les 2 chaînes se ressemblent et on ajoutera la chaîne trouvée dans les résultats.
    Pour les linguistes JavaScript, ça donne ceci :
    Code:
    [lang=javascript]class SpellChecker {

      constructor(settings) {

        settings = settings || {};

        this.maxCost = settings.maxCost || 3;
        this.tree = settings.tree || new Tree();

      }


      check(s) {

        var list = s.split(' ');

        var r = [];

        for (var i = 0; i < list.length; i++) {
          var word = list[i];
          r.push(this.search(word));
        }

        return r;

      }

      /**
      * Levenshtein's Distance metrics calcul with Tree
      */
      search(word) {

        var currentRow = [];
        for (var i = 0; i < word.length+1; i++) {
          currentRow.push(i);
        }

        var r = [];

        var _this = this;

        function _s(node,letter,word,r,previousRow) {

          var currentRow = [ previousRow[0] + 1 ];

          for (var i = 1; i < word.length+1; i++) {

            var _insert = previousRow[i] + 1;
            var _delete = currentRow[i-1] + 1;
            var _replace = word[i-1] != letter ? previousRow[i-1] + 1 : previousRow[i-1];
            currentRow.push(Math.min(_insert,_delete,_replace));

          }

          if (currentRow[currentRow.length-1] <= _this.maxCost && node.word != null) {
            r.push([node.word, currentRow[currentRow.length-1]]);
          }

          if (Math.min.apply(null,currentRow) <= _this.maxCost) {
            for (var letter in node.children) {
              if (node.children.hasOwnProperty(letter)) {
                _s(node.children[letter],letter,word,r,currentRow);
              }
            }
          }

        }

        for (var letter in this.tree.children) {
          if (this.tree.children.hasOwnProperty(letter)) {

            _s(this.tree.children[letter],letter,word,r,currentRow);

          }
        }

        var rs = r.sort(function(a,b){return a[1]-b[1]});

        return rs.length > 0 ? rs[0] : [word,-1];

      }

    }


  • PFFOOUUUUUUU, c'était compliqué Mr. Green Laughing
    Et là, on a manipulé les objets les plus simples de la programmation, je vous rappelle qu'on a toujours pas prononcé une seule fois "Intelligence Artificiel"

    Bon, rien de plus simple qu'un exemple pour mieux comprendre comment utiliser ces deux classes


  • Exemple :


      Pour cette exemple et pour vous convaincre que cette algorithme est très rapide, on va utiliser 200 000 mots : https://raw.githubusercontent.com/words/an-array-of-french-words/master/cor…
      Pour cette exemple, on va utiliser la classe XMLHttpRequest qui permet de faire l'ajax, plus de détail ici : https://fr.wikipedia.org/wiki/XMLHttpRequest

      Voici une fonction pour récupérer la liste complète de tout les mots français :
      Code:
      [lang=javascript]function getFrenchDictionary(callback) {

        var request = new XMLHttpRequest();
        request.onreadystatechange = function () {
          if (this.readyState === 4) {
            callback(this.responseText);
          }
        }
        request.open('GET','https://raw.githubusercontent.com/words/an-array-of-french-words/master/corpus.txt',true);
        request.send();

      }


      Et enfin, voici l'exemple :
      Code:
      [lang=javascript]getFrenchDictionary(function(dictionary){

        // Create the Tree
        var tree = new Tree();
        var data = dictionary.replace(/\r/g,'').split('\n');
        for (var i = 0; i < data.length; i++) {
          tree.push(data[i]);
        }

        // Create an SpellChecker Object
        var spellChecker = new SpellChecker({tree:tree,maxCost:10});

        // We write "Bonjjour z toug" (lots of spelling errors)
        var raw = spellChecker.check('Bonjjour z toug');

        console.log(raw.map(function(item){return item[0]}).join(' '));
        // Display: Bonjour à tous

      });




    Après, à vous de faire une interface avec une zone de texte...etc...
    Voilà, maintenant, vous savez implémenter votre propre correcteur automatiste pour ainsi ne plus faire de fautes d'orthodonties. Laughing Laughing Mr. Green

    Et comme ça, de 1, on évite de surcharger les API qui propose ce service, de 2 notre code fonctionne en mode hors-ligne, et de 3 on peut configurer notre correcteur comme on le veut en mettant les mots qu'on veut où même des chaînes de caractères random Laughing



    Pour ceux qui sont complètement largués, voici le CODE COMPLET FINAL : http://uploade.es/#9Jl6KWeMilBl52i2hff0ng






______________________________________________________
la vie est trop courte pour retirer le périphérique USB en toute sécurité...
Si la statue de la liberté lève le bras depuis 125 ans, c'est parce qu'elle cherche du réseau sur son Blackberry Torches...
Grâce à mon nouveau correcteur automatiste sur mon téléphage, je ne fais plus aucune faute d'orthodontie.
Quelqu'un a t il déjà demandé au drapeau japonais ce qu'il enregistre depuis tout ce temps ?
Visit poster’s website
Post Publicité 
PublicitéSupprimer les publicités ?


Reply with quote
Post [JavaScript] Comment créer un correcteur orthographique 
Excellent Flamm !!!

J'adore !

Okay




______________________________________________________
Post [JavaScript] Comment créer un correcteur orthographique 


Display posts from previous:
Reply to topic Page 1 of 1
  



Index | Getting a forum | Free support forum | Free forums directory | Report a violation | Conditions générales d'utilisation
Copyright 2008 - 2016 // Batch