From 6248d2cf7a2214ac32628bc58248694108b4d8bf Mon Sep 17 00:00:00 2001 From: George Halkiadakis Date: Tue, 16 Apr 2024 01:55:02 +0300 Subject: optimize weighted_partial match --- app.js | 4 +- pieces/prepare-streams.js | 101 ------------------------------------ pieces/prepare.js | 128 ++++++++++++++++++++++++++++++++++++++++++++++ routes/dev.js | 2 +- routes/v1.js | 18 ++++++- utils/match-util.js | 42 ++++++++++++--- 6 files changed, 183 insertions(+), 112 deletions(-) delete mode 100644 pieces/prepare-streams.js create mode 100644 pieces/prepare.js diff --git a/app.js b/app.js index c0392e6..b5fd29b 100644 --- a/app.js +++ b/app.js @@ -2,6 +2,8 @@ const Koa = require('koa'); // const { koaBody } = require('koa-body'); + +// load parameters require('dotenv').config(); // define app @@ -10,7 +12,7 @@ const app = new Koa(); // middleware // app.use(koaBody()); -// Require routes +// load routes let _r = require('./routes'); app.use(_r.routes()).use(_r.allowedMethods()); diff --git a/pieces/prepare-streams.js b/pieces/prepare-streams.js deleted file mode 100644 index ee7ba8e..0000000 --- a/pieces/prepare-streams.js +++ /dev/null @@ -1,101 +0,0 @@ -const fs = require('fs'); -var request = require('request'); - -const kb = require('../utils/kb-util.js'); - - -// const https = require("https"); - - -/* TODO: ?? parallel read - // var request = require('request-promise'); - var calls = [ - request({ - url: 'https://storage.googleapis.com/pythia-files/uploads/json/emarket-keywords.json', - // headers: { ... } - }), - request({ - url: 'https://storage.googleapis.com/pythia-files/uploads/json/emarket-products.json', - // headers: { ... } - }), - // + linked-terms and replaces - // and more.. - ]; - - Promise.all(calls).then(function(results) { - // do something with results[0] - // do something with results[1] - // ... - }); -*/ - - -/** create entity file from url - * @param {string} entity: use the entity name - * @param {string} url: prepared entity json-file in remote server - */ -function create(entity, url) { - request(url, - function (error, response, body) { - if (!error && response.statusCode == 200) { - // body is a ready json-string; no need to parse and (re-)stringify - try { - fs.writeFileSync(`${__dirname}/../data/${entity}.json`, body, 'utf-8'); - // file written successfully - } catch (err) { - console.error(err); - } - } - } - ); -} - - -function load_products(url) { - request(url, - function (error, response, body) { - if (!error && response.statusCode == 200) { - // body is a ready json-string; no need to parse and (re-)stringify - json = JSON.parse(body); - newJson = []; - json.forEach( p => { - newJson.push({ - id: p.id, - w: p.w, - kb: kb.keyboardize(kb.clean(p.w)) - }); - }); - try { - fs.writeFileSync(`${__dirname}/../data/products.json`, JSON.stringify(newJson), 'utf-8'); - // file written successfully - } catch (err) { - console.error(err); - } - } - } - ); -} - - -// create data -// testing an implemenatatin of a custom local-fs-cache system -function random() { - var data = []; - for( let i = 0; i < (Math.floor(Math.random() * 100) +15) ; i++) { - data.push({ id: i, x5: i*5 }); - } - - try { - fs.writeFileSync(__dirname + '/../data/random.json', JSON.stringify(data), 'utf-8'); - // file written successfully - } catch (err) { - console.error(err); - } -} - - -module.exports = { - create, - random, - load_products -} \ No newline at end of file diff --git a/pieces/prepare.js b/pieces/prepare.js new file mode 100644 index 0000000..65ccee1 --- /dev/null +++ b/pieces/prepare.js @@ -0,0 +1,128 @@ +const fs = require('fs'); +var request = require('request'); + +const kb = require('../utils/kb-util.js'); + + +// const https = require("https"); + + +/* TODO: ?? parallel read + // var request = require('request-promise'); + var calls = [ + request({ + url: 'https://storage.googleapis.com/pythia-files/uploads/json/emarket-keywords.json', + // headers: { ... } + }), + request({ + url: 'https://storage.googleapis.com/pythia-files/uploads/json/emarket-products.json', + // headers: { ... } + }), + // + linked-terms and replaces + // and more.. + ]; + + Promise.all(calls).then(function(results) { + // do something with results[0] + // do something with results[1] + // ... + }); +*/ + + +/** create entity file from url + * used for entities like 'linked-words', 'synonyms', etc. + * + * @param {string} entity: use the entity name + * @param {string} url: prepared entity json-file in remote server + */ +function create(entity, url) { + request(url, + function (error, response, body) { + if (!error && response.statusCode == 200) { + // body is a ready json-string; no need to parse and (re-)stringify + try { + fs.writeFileSync(`${__dirname}/../data/${entity}.json`, body, 'utf-8'); + // file written successfully + } catch (err) { + console.error(err); + } + } + } + ); +} + +function get_data_structure() { + // data structure is an array of `{ url:.., expiration:.., path:.. }` objects +} + +function set_data_structure(node) { + +} + + +function load_products(url) { + request(url, + function (error, response, body) { + if (!error && response.statusCode == 200) { + // body is a ready json-string; no need to parse and (re-)stringify + json = JSON.parse(body); + newJson = []; + + // TODO: + // + attach handle synonyms + // + mark brand-names + // + attach category-names and SAP-categories + // + construct combo words + // + remove non-important words + // + normalize popularity + + json.forEach( p => { + newJson.push({ + id: p.id, + w: p.w, + kb: kb.keyboardize(kb.clean(p.w)) + }); + }); + + try { + + fs.writeFileSync( + `${__dirname}/../data/products.json`, + JSON.stringify(newJson), + 'utf-8' + ); + return true; // file written successfully + + } catch (err) { + console.error(err); + return false; + } + } + } + ); +} + + +// create data +// testing an implemenatatin of a custom local-fs-cache system +function random() { + var data = []; + for( let i = 0; i < (Math.floor(Math.random() * 100) +15) ; i++) { + data.push({ id: i, x5: i*5 }); + } + + try { + fs.writeFileSync(__dirname + '/../data/random.json', JSON.stringify(data), 'utf-8'); + // file written successfully + } catch (err) { + console.error(err); + } +} + + +module.exports = { + create, + random, + load_products +} \ No newline at end of file diff --git a/routes/dev.js b/routes/dev.js index 3f142d0..cd40822 100644 --- a/routes/dev.js +++ b/routes/dev.js @@ -6,7 +6,7 @@ const Router = require('koa-router'); const urler = require('../utils/url-util.js'); -const data = require('../pieces/prepare-streams.js'); +const data = require('../pieces/prepare.js'); const bench = require('../benchmark/find.js'); const matchStr = require('../benchmark/match-str.js'); diff --git a/routes/v1.js b/routes/v1.js index 859f7b0..9690973 100644 --- a/routes/v1.js +++ b/routes/v1.js @@ -3,6 +3,7 @@ */ const Router = require('koa-router'); +const prepare = require('../pieces/prepare.js'); // Prefix all routes with: /items @@ -14,10 +15,25 @@ const router = new Router({ // Routes +router.get('/prepare/:title', (ctx) => { + let result = false; + switch (ctx.params.title) { + case 'products': + result = prepare.load_products( + 'https://storage.googleapis.com/pythia-files/uploads/json/emarket-products.json' + ); + break; + + default: + break; + + } + return { success: result }; +}) router.get('/search', (ctx) => { - ctx.body = { success: true, results: [] }; + ctx.body = []; }); router.get('/search/:title', (ctx) => { 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, -- cgit v1.2.3