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

28次阅读

共计 2066 个字符，预计需要花费 6 分钟才能阅读完成。

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

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

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

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

假使要在一堆数据中对一个关键词进行匹配搜寻，传统做法是把数据拆离开，而后遍历他们，看看是否蕴含这个关键词，对于“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

参考