optimize weighted_partial match

1 files changed, 34 insertions, 8 deletions

diff --git a/utils/match-util.js b/utils/match-util.js
index b6b9fc0..5e8c648 100644
--- a/utils/match-util.js
+++ b/utils/match-util.js
@@ -1,3 +1,13 @@
+/**
+ * match utility;
+ * includes fuzzy and partial match functions too;
+ * many of them return a match-rate
+ */
+
+
+// fuzzy match
+////////////////////////////////////////////////////////////////////////////////
+
 /** Ngram fuzzy match algorithm
  * (simple and fast)
  */
@@ -63,13 +73,16 @@ const resemblance = (a, b, n) => {
 }
 
 
+// exact and partial match
+////////////////////////////////////////////////////////////////////////////////
+
 /** is_exact_match
  * check if a searching string -> query (string/latin in kb-format)
  * matches exactly an item of the array of synonyms -> chkArr (array of utf-8/strings)
  * 
- * @param query (string): searching string; string/latin in kb-format
- * @param chkArr (array): array of synonyms; (array of utf-8/strings)
- * @return (boolean): true|false
+ * @param {string} query: searching string; string/latin in kb-format
+ * @param {array} chkArr: array of synonyms; (array of utf-8/strings)
+ * @return {boolean}: true|false
  */
 function exact( query, chkArr ) {
     found = false;
@@ -89,11 +102,10 @@ function partial( query, chkArr ) {
 function weighted_exact( query, chkArr ) {
     let weight = 0;   // closer to left/begin rating
     let len = chkArr.length;
-    for(let i = 0; i < len ; i++) {
+    for(let i = 0; i < len ; i++) {     // i ~ depth
         if (chkArr[i] == query) {
-            // rating weights array depth
+            // weights array depth
             weight = (len - i + 1.0) / len;
-            // console.log(i, weight, query);
             break;
         }
     }
@@ -102,22 +114,36 @@ function weighted_exact( query, chkArr ) {
 
 
 /** is partial match + weight rating
+ * 
+ * @param query (string): searching string; string/latin in kb-format
+ * @param chkArr (array): array of synonyms; (array of utf-8/strings)
  * @returns {float} weight rates both match position and depth of match
+ * 
+ * (*) optimization NOTE:
+ * Given the weight `W` and the depth `i`,
+ * the best weight for next `i` shall be: `(L - (i+1)) / L`
+ * To be imposibbe to have a better weight, should:
+ * W > (L - (i+1)) / L  => ... =>  i > (L - L*W - 1)
  */
 function weighted_partial( query, chkArr ) {
     let rate = 0;
     let weight = 0;
     let len = chkArr.length;
-    for(let i = 0; i < len ; i++) {
+    for( let i = 0 ; i < len ; i++ ) {
         let chk = chkArr[i].indexOf(query)
         if (chk != -1) {
-            rate = (len -i +1.0) / (len + 2.0 * chk);
+            rate = (len - i) / (len + 2.0 * chk);
             weight = rate > weight ? rate : weight;
         }
+        if (i > (len - len * weight - 1)) {
+            break;      // better rating is not possible (*)
+        }
     }
     return weight;
 }
 
+
+// exports
 module.exports = {
     exact,
     partial,