diff options
Diffstat (limited to 'utils')
| -rw-r--r-- | utils/match-util.js | 42 |
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, |