☰

string-overlap-matching-degree

计算字符串重叠/匹配度计算

当前为 2024-07-24 提交的版本，查看 最新版本。

此脚本不应直接安装。它是供其他脚本使用的外部库，要使用该库请加入元指令 // @require https://update.cn-greasyfork.org/scripts/501646/1416061/string-overlap-matching-degree.js 

  1. // ==UserScript==
  2. // @name string-overlap-matching-degree
  3. // @namespace http://tampermonkey.net/
  4. // @version 1.0.0
  5. // @description 计算字符串重叠/匹配度计算
  6. // @license Apache License 2.0
  7. // @author zhuangjie
  8. // ==/UserScript==
  9.  
  10. // commented by zhuangjie
  11.  
  12.  
  13. /**
  14.  * 重叠匹配度
  15.  * @author: zhuangjie
  16.  * @date: 2024-07-23
  17.  */
  18. function overlapMatchingDegreeForObjectArray(keyword = "", objArr = [], fun = (obj) => [], {sort = "desc",onlyHasScope =false,scopeForObjArrContainer} = {}) {
  19.     const scopeForData = objArr.map(item => overlapMatchingDegree(keyword, fun(item), sort));
  20.     // scope与 objArr 同步排序
  21.     sortAndSync(scopeForData, objArr)
  22.     if(Array.isArray(scopeForObjArrContainer)) {
  23.         // 说明需要分数，倒给
  24.         scopeForObjArrContainer.push(...scopeForData)
  25.     }
  26.     return onlyHasScope ? filterMismatchItem(scopeForData,objArr) : objArr;
  27. }
  28.  
  29. // 根据scopeForData得到新数组objArr
  30. function filterMismatchItem(scopeForData,objArr) {
  31.     const result = []
  32.     for(let [scope,index] of scopeForData.entries()) {
  33.         if(scope != 0) {
  34.             result.push(objArr[index])
  35.         }
  36.     }
  37.     return result
  38. }
  39.  
  40. /**
  41.  * 计算匹配度外层封装工具
  42.  * @param {string} keyword - 匹配字符串1
  43.  * @param {Object | Arrayy} topicWeighs - 匹配字符串2与它的权重
  44.  * @returns {number} 匹配度分数
  45.  */
  46. function overlapMatchingDegree(keyword, topicWeighs = {}, sort = "desc") {
  47.     // 兼容topicWeighs为topic数组，元素越靠前权重越高
  48.     if (Array.isArray(topicWeighs)) {
  49.         const _temp = {}
  50.         if (sort === "asc") {
  51.             for (let i = 1; i <= topicWeighs.length; i++) {
  52.                 _temp[topicWeighs[i - 1]] = i;
  53.             }
  54.         } else {
  55.             // desc
  56.             for (let i = topicWeighs.length; i > 0; i--) {
  57.                 _temp[topicWeighs[topicWeighs.length - i]] = i;
  58.             }
  59.         }
  60.         topicWeighs = _temp;
  61.     }
  62.     let topicList = Object.keys(topicWeighs)
  63.     // topic map 得分
  64.     const topicScores = topicList.map(topic => {
  65.         let topicScore = 0; // 得分
  66.         const currentTopicScore = topicWeighs[topic]; // 当前topic“个数”
  67.         const overlapLengthBlocksMap = findOverlapBlocks(keyword, topic)
  68.         const overlapLengthKeys = Object.keys(overlapLengthBlocksMap);
  69.         for (let overlapLengthKey of overlapLengthKeys) {
  70.             const currentLengthBlocks = overlapLengthBlocksMap[overlapLengthKey];
  71.             topicScore = Math.pow(currentTopicScore, overlapLengthKey) * currentLengthBlocks.length;
  72.         }
  73.         return topicScore;
  74.     })
  75.     // 算总分返回
  76.     return topicScores.reduce((a, b) => a + b, 0)
  77. }
  78.  
  79. /**
  80.  * 查找重叠匹配块（入口函数）
  81.  * @param {*} str1 
  82.  * @param {*} str2 
  83.  * @returns 返回重叠块 如：{"2": ["好用","推荐"],"3": ["好用推荐"]}
  84.  * 算法核心思想：
  85.  * -----------------------------------------------------
  86.  * sumatrapdf*          | sumatrapdf*      | sumatrapdf*
  87.  *           pdf-       |          pdf-    |         pdf-
  88.  * ------------------------------------------------------
  89.  */
  90. function findOverlapBlocks(str1 = "", str2 = "") {
  91.     let maxStr2OffsetLength = str1.length - 1;
  92.     let minStr2OffsetLength = -(str2.length - 1);
  93.     const alignmentHub = { /* "3": ["好用","推荐"] */ }
  94.     for (let currentStr2OffsetLength = maxStr2OffsetLength; currentStr2OffsetLength >= minStr2OffsetLength; currentStr2OffsetLength--) {
  95.         let str1EndIndex = str1.length - 1;
  96.         let str2EndIndex = currentStr2OffsetLength + (str2.length - 1);
  97.  
  98.         let overlappingStart = currentStr2OffsetLength >= 0 ? currentStr2OffsetLength : 0; // 重叠闭区间开始 [
  99.         let overlappingEnd = str2EndIndex < str1EndIndex ? str2EndIndex : str1EndIndex; // 重叠闭区间结束 ]
  100.  
  101.         // 对齐
  102.         const alignmentContent = alignment(str1.substring(overlappingStart, overlappingEnd + 1), str2.substring(overlappingStart - currentStr2OffsetLength, overlappingEnd - currentStr2OffsetLength + 1));
  103.         // 长重叠 覆盖 短重叠
  104.         longOverlappingCoverage(alignmentHub, alignmentContent);
  105.     }
  106.     return alignmentHub;
  107. }
  108. function longOverlappingCoverage(alignmentHub = {}, alignmentContent = {}) {
  109.     const modifiedCols = Object.keys(alignmentContent)
  110.     const maxmodifiedCols = Math.max(...modifiedCols)
  111.     const minmodifiedCols = Math.min(...modifiedCols)
  112.     // 合并到对应的列上
  113.     modifiedCols.forEach(col => {
  114.         alignmentHub[col] = alignmentHub[col] ? Array.from(new Set(alignmentHub[col].concat(alignmentContent[col]))) : alignmentContent[col];
  115.     })
  116.     const alignmentHubCol = Object.keys(alignmentHub)
  117.     const gtmodifiedCols = alignmentHubCol.filter(col => parseFloat(col) > maxmodifiedCols);
  118.     const ltmodifiedCols = alignmentHubCol.filter(col => parseFloat(col) < minmodifiedCols);
  119.     // 重新计算各列，过滤掉在modifiedCols的`大于modifiedCols的列`的子串，过滤掉`小于modifiedCols的列`在modifiedCols的子串
  120.     // - 过滤掉在modifiedCols的`大于modifiedCols的列`的子串
  121.     colElementFilter(alignmentHub, modifiedCols, gtmodifiedCols);
  122.     // - 过滤掉`小于modifiedCols的列`在modifiedCols的子串
  123.     colElementFilter(alignmentHub, ltmodifiedCols, modifiedCols);
  124.  
  125. }
  126. // 列元素过滤
  127. function colElementFilter(alignmentHub = {}, cols = [], gtCols = []) {
  128.     if (cols.length == 0 || gtCols.length == 0) return;
  129.     gtCols.forEach(gtCol => {
  130.         const gtOverlappingBlocks = alignmentHub[gtCol];
  131.         for (let [index, col] of cols.entries()) {
  132.             const overlappingBlocks = alignmentHub[col];
  133.             if (gtOverlappingBlocks == undefined || overlappingBlocks == undefined) continue;;
  134.             alignmentHub[col] = overlappingBlocks.filter(overlappingBlock => {
  135.                 for (let gtOverlappingBlock of gtOverlappingBlocks) {
  136.                     if (gtOverlappingBlock.includes(overlappingBlock)) {
  137.                         return false
  138.                     }
  139.                 }
  140.                 return true;
  141.             })
  142.         }
  143.     })
  144.     // 清理掉value为空数组项
  145.     // {1: [],2:["好用"]} -to-> {2:["好用"]}
  146.     Object.keys(alignmentHub).forEach(key => { if (alignmentHub[key].length == 0) delete alignmentHub[key] });
  147. }
  148. // 对齐
  149. function alignment(str1 = "", str2 = "") {
  150.     // 返回 {"1",["我","用"],"2":["推荐","可以"]}
  151.     if (str1.length != str2.length) {
  152.         throw new Error("算法错误，对齐字符串长度不一致");
  153.     }
  154.     const overlappingBlocks = {}
  155.     let currentOverlappingBlock = "";
  156.     for (let i = str1.length - 1; i >= 0; i--) {
  157.         if (str1[i] == str2[i]) {
  158.             currentOverlappingBlock = str1[i] + currentOverlappingBlock;
  159.             if (i - 1 >= 0) continue;
  160.         }
  161.         if (currentOverlappingBlock.length == 0) {
  162.             continue;
  163.         } else {
  164.             // 块收集
  165.             let currentOverlappingBlockContainer = overlappingBlocks[currentOverlappingBlock.length]
  166.             if (currentOverlappingBlockContainer == undefined) {
  167.                 currentOverlappingBlockContainer = overlappingBlocks[currentOverlappingBlock.length] = [currentOverlappingBlock]
  168.             } else if (!currentOverlappingBlockContainer.includes(currentOverlappingBlock)) {
  169.                 currentOverlappingBlockContainer.push(currentOverlappingBlock)
  170.             }
  171.         }
  172.         currentOverlappingBlock = "";
  173.     }
  174.     return overlappingBlocks;
  175. }
  176.  
  177. // 【同步算法-堆实现】
  178. function sortAndSync(arr1, arr2, order = 'desc') {
  179.     if (arr1.length !== arr2.length) {
  180.         throw new Error("Both arrays must have the same length");
  181.     }
  182.     function swap(arr, i, j) {
  183.         [arr[i], arr[j]] = [arr[j], arr[i]];
  184.     }
  185.     function heapify(arr1, arr2, n, i, order) {
  186.         let largest = i;
  187.         let left = 2 * i + 1;
  188.         let right = 2 * i + 2;
  189.  
  190.         if (order === 'asc') {
  191.             if (left < n && arr1[left] > arr1[largest]) {
  192.                 largest = left;
  193.             }
  194.             if (right < n && arr1[right] > arr1[largest]) {
  195.                 largest = right;
  196.             }
  197.         } else {
  198.  
  199.             if (left < n && arr1[left] < arr1[largest]) {
  200.                 largest = left;
  201.             }
  202.             if (right < n && arr1[right] < arr1[largest]) {
  203.                 largest = right;
  204.             }
  205.         }
  206.  
  207.         if (largest !== i) {
  208.             swap(arr1, i, largest);
  209.             swap(arr2, i, largest);
  210.             heapify(arr1, arr2, n, largest, order);
  211.         }
  212.     }
  213.     function buildHeap(arr1, arr2, n, order) {
  214.         for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
  215.             heapify(arr1, arr2, n, i, order);
  216.         }
  217.     }
  218.     function heapSort(arr1, arr2, order) {
  219.         let n = arr1.length;
  220.         buildHeap(arr1, arr2, n, order);
  221.  
  222.         for (let i = n - 1; i > 0; i--) {
  223.             swap(arr1, 0, i);
  224.             swap(arr2, 0, i);
  225.             heapify(arr1, arr2, i, 0, order);
  226.         }
  227.     }
  228.     heapSort(arr1, arr2, order);
  229. }
  230.  
  231. // 【算法测试1】
  232. //  console.log("-- 算法测试开始 --")
  233. //  console.log(findOverlapBlocks("[推荐]sumatrapdf非常好用","pdf 推荐"))
  234. //  console.log("-- 算法测试结束 --")
  235.  
  236. // 【算法测试2】
  237. // console.log("匹配度：", overlapMatchingDegree("好用的pdf工具", { "sumatrapdf": 10, "小而好用的pdf阅读器": 8, "https://www.sumatrapdfreader.org/downloadafter": 3 }));
  238.