function getBestPhraseCombinationsWithMaxScoreAble(words, phraseNumWordsList, phrasesData, addressCutOrigin, maxScoreAble, exportResult, maxConcurrentTasks = 8, getFreeWorker = undefined, setWorkerIsFree = undefined) { var clauseNumWords = words.length; var rankingTable = []; for (var s = 0; s <= maxScoreAble; s++) { rankingTable[s] = []; } var getResult = function () { for (var s1 = rankingTable.length - 1; s1 >= 0; s1--) { if (rankingTable[s1].length > 0) { for (var c = 0; c < rankingTable[s1].length; c++) { if (rankingTable[s1][c].length > 0) { return rankingTable[s1][c]; // best score with min of cuts } } } } }; // BEGIN: get phrase address combinations var phraseMinWords = phraseNumWordsList[0]; var phraseMaxWords = phraseNumWordsList[phraseNumWordsList.length - 1]; var minOfCuts = Math.ceil(clauseNumWords / phraseMaxWords) - 1; var maxOfCuts = Math.floor(clauseNumWords / phraseMinWords) - 1; if (minOfCuts > maxOfCuts) { console.error({minOfCuts, maxOfCuts, phraseMaxWords, phraseMinWords, clauseNumWords}); throw new Error('minOfCuts > maxOfCuts'); } var tasksDone = []; for (var i = minOfCuts; i <= maxOfCuts; i++) { tasksDone[i] = false; } var workersMap = {}; var pushSubRankingTable = function (subRankingTable, numOfCuts) { if (tasksDone[numOfCuts]) { return; } if (subRankingTable[subRankingTable.length - 1].length > 0) { // has combinations reached max score able for (var j = numOfCuts + 1; j <= maxOfCuts; j++) { tasksDone[j] = true; if (workersMap[j]) { workersMap[j][0].terminate(); // worker.terminate if (setWorkerIsFree) { setWorkerIsFree(workersMap[j][1]); // workerIndex } } } } var highestScoreEven = 0; for (var s = rankingTable.length - 1; s >= 0; s--) { if (rankingTable[s].length > 0) { highestScoreEven = s; break; } } for (var s1 = subRankingTable.length - 1; s1 >= 0; s1--) { if (subRankingTable[s1].length > 0) { if (s1 < highestScoreEven) { break; } for (var i = 0; i < 5 && i < subRankingTable[s1].length; i++) { // 5 is max number of combinations to export for (var c = 0; c <= maxOfCuts; c++) { rankingTable[s1][c] = []; } rankingTable[s1][numOfCuts].push(subRankingTable[s1][i]); } break; // only add highest score combinations } } tasksDone[numOfCuts] = true; if (tasksDone.every(function (isDone) { return isDone; })) { exportResult(getResult()); } }; if (false && getFreeWorker) { // try to not use worker console.log('Use worker for nkAB'); for (var k = minOfCuts; k <= maxOfCuts; k++) { (function (k) { var workerAndIndex = getFreeWorker(); var worker = workerAndIndex[0]; var workerIndex = workerAndIndex[1]; worker.postMessage(JSON.stringify({ workerTask: 'pushCombinationsWithNumOfCuts', numOfCuts: k, clauseNumWords: clauseNumWords, phraseNumWordsList: phraseNumWordsList, phrasesData: phrasesData, addressCutOrigin: addressCutOrigin, maxScoreAble: maxScoreAble })); worker.onmessage = function (ev) { if (setWorkerIsFree) { setWorkerIsFree(workerIndex); } pushSubRankingTable(ev.data, k); }; workersMap[k] = workerAndIndex; })(k); } } else { console.log('DO NOT use worker for nkAB'); for (var j = minOfCuts; j <= maxOfCuts; j++) { if (tasksDone[j]) { console.log('break caused by set done by another', j); break; } pushSubRankingTable(ChineseTextAnalyzer.pushCombinationsWithNumOfCuts( j, clauseNumWords, phraseNumWordsList, phrasesData, addressCutOrigin, maxScoreAble ), j); } } // END: get phrase address combinations } function pushCombinationsWithNumOfCuts(numOfCuts, clauseNumWords, phraseNumWordsList, phrasesData, addressCutOrigin, maxScoreAble) { var rankingTable = []; for (var s = 0; s <= maxScoreAble; s++) { rankingTable[s] = []; } var maxScoreEven = 0; var maxScoreAbleCombination_minLength = clauseNumWords; var pushCombination = function (a) { var score = 0, com = [], address; var comLength = a.length; if (comLength > maxScoreAbleCombination_minLength) { return; } if (a.length === 1) { address = getPhraseAddress(0, clauseNumWords, addressCutOrigin); com.push(address); if (phrasesData[address]) score += clauseNumWords; // endCut - startCut } else { // a.length > 1 address = getPhraseAddress(0, a[1], addressCutOrigin); com.push(address); if (phrasesData[address]) score += a[1]; for (var i = 2; i < a.length; i++) { address = getPhraseAddress(a[i - 1], a[i], addressCutOrigin); com.push(address); if (phrasesData[address]) score += a[i] - a[i - 1]; } // *Note that: `i` was increased more 1 after end the loop (+1 before check loop condition) address = getPhraseAddress(a[i - 1], clauseNumWords, addressCutOrigin); com.push(address); if (phrasesData[address]) score += clauseNumWords - a[i - 1]; } if (score < maxScoreEven) { return; } maxScoreEven = score; if (score === maxScoreAble && comLength < maxScoreAbleCombination_minLength) { maxScoreAbleCombination_minLength = comLength; } rankingTable[score].push(com); }; var n = clauseNumWords - 1; var k = numOfCuts; var C = phraseNumWordsList; var A = C[0]; var B = C[C.length - 1]; var timerName = 'nkAB ' + n + '.' + k + '.' + C; console.log(timerName + ': start'); console.time(timerName); var a = [0]; if (k === 0) { pushCombination(a); } else { var backtrack = function (i) { var x = 0; for (var j = a[i - 1] + A ; j <= n - k + i && j - a[i - 1] <= B ; j += C[x] - C[x - 1] ) { x++; if (i === k && (n + 1 - j < A || n + 1 - j > B)) { continue; } a[i] = j; if (i === k) { pushCombination(a); } else { backtrack(i + 1); } } }; backtrack(1); } console.timeEnd(timerName); return rankingTable; } function getCombinations(n, k) { if (k < 1 || k > n) { throw new Error('k is invalid. Condition: 1 <= k <= n'); } var combinations = []; var a = [0]; var pushCombination = () => { var c = []; for (var i = 1; i <= k; i++) { c.push(a[i]); } combinations.push(c); }; var backtrack = (i) => { for (var j = a[i - 1] + 1; j <= n - k + i; j++) { a[i] = j; if (i === k) { pushCombination(); } else { backtrack(i + 1); } } }; backtrack(1); return combinations; }