乐趣区

关于javascript:对数据进行模糊匹配搜索动态规划最长公共子串最长公共子序列

jiezi

在搜寻时经常在输出一半或者输出谬误时，搜索引擎就给出智能提醒。

已知的搜寻举荐次要包含以下几个方面：

  • 蕴含：“清华”和“清华大学”
  • 类似：“聊天软件”和“通信软件”
  • 相干：“明星”和“刘亦菲”
  • 纠错：“好奇害死毛”和“好奇害死猫”

其中蕴含含糊匹配能够应用动静布局算法解决，其余几个则要大量数据进行机器学习才行。

假使要在一堆数据中对一个关键词进行匹配搜寻，传统做法是把数据拆离开，而后遍历他们，看看是否蕴含这个关键词，对于“fin”和“finish”这样存在蕴含关系的单词来说是没问题的，然而对于“fish”和“finish”这样并不存在蕴含关系的单词就生效了，这时候冀望计算出两个单词的相似性，比方“fish”和“finish”都蕴含“ish”，“ish”的长度是 3，咱们能够了解相似性为 3。目前支流做法是通过最长公共子串来寻找两个或多个已知字符串 最长 的子串。

注：深拷贝应用了依赖库，需先装置 npm install mazey --save

最长公共子串示例：

import {deepCopy} from 'mazey';

/**
 * @method calLongestCommonSubstring
 * @description 计算两个字符串的最长公共子串
 * @param {String} aStr 字符串
 * @param {String} bStr 字符串
 * @return {Number} 长度
 */
function calLongestCommonSubstring (aStr, bStr) {
    const aLen = aStr.length;
    const bLen = bStr.length;
    // 创立二维数组并且深拷贝
    const arr = deepCopy(new Array(aLen).fill(new Array(bLen).fill(0)));
    for (let i = 0; i < aLen; ++i) {for (let j = 0; j < bLen; ++j) {if (aStr[i] === bStr[j]) {
                let baseNum = 0;
                if (i > 0 && j > 0) {baseNum = arr[i-1][j-1];
                }
                arr[i][j] = baseNum + 1;
            }
        }
    }
    // 二维数组转一维数组
    const arr1 = Array.prototype.concat.apply([], arr);
    // 获取最长公共子串
    const maxLong = Math.max(...arr1);
    return maxLong;
}

calLongestCommonSubstring('fish', 'finish'); // 3

“fish”和“finish”除了“ish”之外还独特蕴含“f”，所以“ish”+“f”更好的表白其相似性（3 + 1 = 4），于是应用最长公共子序列对最长公共子串进行降级来查找所有序列中最长子序列，版本治理中应用的 git diff 就是建设在最长公共子序列的根底上。

最长公共子序列示例：

import {deepCopy} from 'mazey';

/**
 * @method calLongestCommonSubsequence
 * @description 计算两个字符串的最长公共子序列
 * @param {String} aStr 字符串
 * @param {String} bStr 字符串
 * @return {Number} 长度
 */
function calLongestCommonSubsequence (aStr, bStr) {
  const aLen = aStr.length;
  const bLen = bStr.length;
  const arr = deepCopy(new Array(aLen).fill(new Array(bLen).fill(0)));
  for (let i = 0; i < aLen; ++i) {for (let j = 0; j < bLen; ++j) {if (aStr[i] === bStr[j]) {
        let baseNum = 0;
        if (i > 0 && j > 0) {baseNum = arr[i - 1][j - 1];
        }
        arr[i][j] = baseNum + 1;
      } else {let [leftValue, topValue] = [0, 0];
        if (j > 0) {leftValue = arr[i][j - 1];
        }
        if (i > 0) {topValue = arr[i - 1][j];
        }
        arr[i][j] = Math.max(leftValue, topValue);
      }
    }
  }
  // 二维数组转一维数组
  const arr1 = Array.prototype.concat.apply([], arr);
  // 获取最长公共子串
  const maxLong = Math.max(...arr1);
  return maxLong;
}

calLongestCommonSubsequence('fish', 'finish'); // 4

参考

  1. 1143. 最长公共子序列 – 力扣（LeetCode）
  2. 搜索引擎如何做到含糊匹配？

版权申明

本博客所有的原创文章，作者皆保留版权。转载必须蕴含本申明，放弃本文残缺，并以超链接模式注明作者后除和本文原始地址：https://blog.mazey.net/1595.html

（完）

退出移动版