对数据进行模糊匹配搜索（动态规划、最长公共子串、最长公共子序列）

在搜索时常常在输入一半或者输入错误时，搜索引擎就给出智能提示。

已知的搜索推荐主要包括以下几个方面：

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

其中包含模糊匹配可以使用动态规划算法解决，其他几个则要大量数据进行机器学习才行。

倘若要在一堆数据中对一个关键词进行匹配搜索，传统做法是把数据拆分开，然后遍历他们，看看是否包含这个关键词，对于 “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

（完）