toolkit/modules/NLP.jsm

   1 /* This Source Code Form is subject to the terms of the Mozilla Public
   2  * License, v. 2.0. If a copy of the MPL was not distributed with this
   3  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   4
   5 "use strict";
   6
   7 var EXPORTED_SYMBOLS = ["NLP"];
   8
   9 /**
  10  * NLP, which stands for Natural Language Processing, is a module that provides
  11  * an entry point to various methods to interface with human language.
  12  *
  13  * At least, that's the goal. Eventually. Right now, the find toolbar only really
  14  * needs the Levenshtein distance algorithm.
  15  */
  16 var NLP = {
  17   /**
  18    * Calculate the Levenshtein distance between two words.
  19    * The implementation of this method was heavily inspired by
  20    * http://locutus.io/php/strings/levenshtein/index.html
  21    * License: MIT.
  22    *
  23    * @param  {String} word1   Word to compare against
  24    * @param  {String} word2   Word that may be different
  25    * @param  {Number} costIns The cost to insert a character
  26    * @param  {Number} costRep The cost to replace a character
  27    * @param  {Number} costDel The cost to delete a character
  28    * @return {Number}
  29    */
  30   levenshtein(word1 = "", word2 = "", costIns = 1, costRep = 1, costDel = 1) {
  31     if (word1 === word2) {
  32       return 0;
  33     }
  34
  35     let l1 = word1.length;
  36     let l2 = word2.length;
  37     if (!l1) {
  38       return l2 * costIns;
  39     }
  40     if (!l2) {
  41       return l1 * costDel;
  42     }
  43
  44     let p1 = new Array(l2 + 1);
  45     let p2 = new Array(l2 + 1);
  46
  47     let i1, i2, c0, c1, c2, tmp;
  48
  49     for (i2 = 0; i2 <= l2; i2++) {
  50       p1[i2] = i2 * costIns;
  51     }
  52
  53     for (i1 = 0; i1 < l1; i1++) {
  54       p2[0] = p1[0] + costDel;
  55
  56       for (i2 = 0; i2 < l2; i2++) {
  57         c0 = p1[i2] + (word1[i1] === word2[i2] ? 0 : costRep);
  58         c1 = p1[i2 + 1] + costDel;
  59
  60         if (c1 < c0) {
  61           c0 = c1;
  62         }
  63
  64         c2 = p2[i2] + costIns;
  65
  66         if (c2 < c0) {
  67           c0 = c2;
  68         }
  69
  70         p2[i2 + 1] = c0;
  71       }
  72
  73       tmp = p1;
  74       p1 = p2;
  75       p2 = tmp;
  76     }
  77
  78     c0 = p1[l2];
  79
  80     return c0;
  81   },
  82 };