☰

Greasy Fork is available in English.

string-overlap-matching-degree

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

2024-08-18 기준 버전입니다. 최신 버전을 확인하세요.

이 스크립트는 직접 설치하는 용도가 아닙니다. 다른 스크립트에서 메타 지시문 // @require https://update.greatest.deepsurf.us/scripts/501646/1429884/string-overlap-matching-degree.js을(를) 사용하여 포함하는 라이브러리입니다. 

  1. /**
  2.  * 重叠匹配度
  3.  * @author: zhuangjie
  4.  * @date: 2024-07-23
  5.  */
  6. function overlapMatchingDegreeForObjectArray(keyword = "", objArr = [], fun = (obj) => [], {sort = "desc", onlyHasScope = false, scopeForObjArrContainer} = {}) {
  7.     const scopeForData = objArr.map(item => overlapMatchingDegree(keyword, fun(item), sort));
  8.     // scope与 objArr 同步排序
  9.     sortAndSync(scopeForData, objArr, sort);
  10.     
  11.     if (Array.isArray(scopeForObjArrContainer)) {
  12.         scopeForObjArrContainer.push(...scopeForData);
  13.     }
  14.  
  15.     return onlyHasScope ? objArr.filter((_, index) => scopeForData[index] !== 0) : objArr;
  16. }
  17. /**
  18.  * 计算匹配度外层封装工具
  19.  * @param {string} keyword - 匹配字符串1
  20.  * @param {Object | Arrayy} topicWeighs - 匹配字符串2与它的权重
  21.  * @returns {number} 匹配度分数
  22.  */
  23. function overlapMatchingDegree(keyword, topicWeighs = {}, sort = "desc") {
  24.     if (Array.isArray(topicWeighs)) {
  25.         const weightMultiplier = sort === "asc" ? 1 : -1;
  26.         topicWeighs = Object.fromEntries(topicWeighs.map((topic, index) => [topic, (index + 1) * weightMultiplier]));
  27.     }
  28.     
  29.     return Object.keys(topicWeighs).reduce((totalScore, topic) => {
  30.         const currentScore = topicWeighs[topic];
  31.         const overlapLengthBlocksMap = findOverlapBlocks(keyword, topic);
  32.         return totalScore + Object.entries(overlapLengthBlocksMap).reduce((sum, [length, blocks]) => {
  33.             return sum + blocks.length * Math.pow(currentScore, Number(length));
  34.         }, 0);
  35.     }, 0);
  36. }
  37. /**
  38.  * 查找重叠匹配块（入口函数）
  39.  * @param {*} str1 
  40.  * @param {*} str2 
  41.  * @returns 返回重叠块 如：{"2": ["好用","推荐"],"3": ["好用推荐"]}
  42.  * 算法核心思想：
  43.  * -----------------------------------------------------
  44.  * sumatrapdf*          | sumatrapdf*      | sumatrapdf*
  45.  *           pdf-       |          pdf-    |         pdf-
  46.  * ------------------------------------------------------
  47.  */
  48. function findOverlapBlocks(str1 = "", str2 = "") {
  49.     const alignmentHub = {};
  50.     const str1Len = str1.length;
  51.     const str2Len = str2.length;
  52.     const minLen = Math.min(str1Len, str2Len);
  53.  
  54.     for (let offset = 1 - str2Len; offset < str1Len; offset++) {
  55.         const start = Math.max(0, offset);
  56.         const end = Math.min(str1Len, str2Len + offset);
  57.         const overlapStr1 = str1.slice(start, end);
  58.         const overlapStr2 = str2.slice(start - offset, end - offset);
  59.  
  60.         const alignmentContent = alignment(overlapStr1, overlapStr2);
  61.         for (const [len, blocks] of Object.entries(alignmentContent)) {
  62.             alignmentHub[len] = alignmentHub[len] ? [...new Set([...alignmentHub[len], ...blocks])] : blocks;
  63.         }
  64.     }
  65.     return alignmentHub;
  66. }
  67. // 对齐
  68. function alignment(str1 = "", str2 = "") {
  69.     const overlappingBlocks = {};
  70.     let currentBlock = "";
  71.  
  72.     for (let i = str1.length - 1; i >= 0; i--) {
  73.         if (str1[i] === str2[i]) {
  74.             currentBlock = str1[i] + currentBlock;
  75.         } else if (currentBlock.length > 0) {
  76.             const len = currentBlock.length;
  77.             overlappingBlocks[len] = overlappingBlocks[len] || [];
  78.             if (!overlappingBlocks[len].includes(currentBlock)) {
  79.                 overlappingBlocks[len].push(currentBlock);
  80.             }
  81.             currentBlock = "";
  82.         }
  83.     }
  84.     if (currentBlock.length > 0) {
  85.         const len = currentBlock.length;
  86.         overlappingBlocks[len] = overlappingBlocks[len] || [];
  87.         if (!overlappingBlocks[len].includes(currentBlock)) {
  88.             overlappingBlocks[len].push(currentBlock);
  89.         }
  90.     }
  91.  
  92.     return overlappingBlocks;
  93. }
  94. // 【同步排序算法】
  95. function sortAndSync(arr1, arr2, order = 'desc') {
  96.     const compare = order === 'asc' ? (a, b) => a - b : (a, b) => b - a;
  97.     arr1.map((v, i) => [v, arr2[i]])
  98.         .sort((a, b) => compare(a[0], b[0]))
  99.         .forEach(([v, o], i) => {
  100.             arr1[i] = v;
  101.             arr2[i] = o;
  102.         });
  103. }
  104.  
  105.  
  106. // 【算法测试1】
  107. //  console.log("-- 算法测试开始 --")
  108. //  console.log(findOverlapBlocks("[推荐]sumatrapdf非常好用","pdf 推荐"))
  109. //  console.log("-- 算法测试结束 --")
  110.  
  111. // 【算法测试2】
  112. // console.log("匹配度：", overlapMatchingDegree("好用的pdf工具", { "sumatrapdf": 10, "小而好用的pdf阅读器": 8, "https://www.sumatrapdfreader.org/downloadafter": 3 }));