如何实现支持相似度百分比阈值的子串位置查找函数？

我有如下文本：

const input = `Hello world!

This is a random text.
I don't know...
nd ths lines got som spelling mitsakes`

要查找I don't know...的位置，直接用indexOf就能实现：

const position = input.indexOf(`I don't know...`)

但现在需要查找非完全匹配的子串，比如下面的代码就无法匹配目标文本里的近似行：

const position = input.indexOf(`And this line's got some spelling mistakes.`)

我需要实现一个indexOfSimilar函数，能根据指定的匹配度阈值查找近似子串，示例用法如下：

// 查找匹配度至少为50%的位置：
const position = indexOfSimilar(input, `And this line's got some spelling mistakes.`, 0.5)

// 查找匹配度至少为99%的位置：
const position = indexOfSimilar(input, `And this line's got some spelling mistakes.`, 0.99)

请问该如何实现这一功能？

实现方案 #

核心思路是用**编辑距离（Levenshtein距离）**衡量字符串差异，遍历原文本的所有可能子串，计算其与目标串的相似度，返回符合阈值的位置。

1. 编辑距离计算函数 #

编辑距离指将一个字符串转换为另一个字符串所需的最少单字符编辑（插入、删除、替换）次数，次数越少字符串越相似。

function levenshteinDistance(a, b) {
  const matrix = Array.from({ length: a.length + 1 }, () =>
    Array(b.length + 1).fill(0)
  );

  // 初始化矩阵边界
  for (let i = 0; i <= a.length; i++) matrix[i][0] = i;
  for (let j = 0; j <= b.length; j++) matrix[0][j] = j;

  // 填充矩阵计算编辑距离
  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      const cost = a[i - 1] === b[j - 1] ? 0 : 1;
      matrix[i][j] = Math.min(
        matrix[i - 1][j] + 1,     // 删除操作
        matrix[i][j - 1] + 1,     // 插入操作
        matrix[i - 1][j - 1] + cost // 替换操作
      );
    }
  }

  return matrix[a.length][b.length];
}

2. 实现indexOfSimilar函数 #

遍历原文本中所有可能的子串，计算与目标串的相似度，返回第一个符合阈值的起始位置：

function indexOfSimilar(input, target, minSimilarity) {
  // 边界处理：目标串为空或原文本过短，直接返回-1
  if (!target || input.length < target.length * 0.5) return -1;

  const targetLen = target.length;
  // 允许子串长度在目标串的80%-120%范围内，可根据需求调整
  const minSubLen = Math.floor(targetLen * 0.8);
  const maxSubLen = Math.ceil(targetLen * 1.2);

  // 遍历所有可能的起始位置
  for (let start = 0; start <= input.length - minSubLen; start++) {
    // 尝试不同长度的子串，覆盖长度差异场景
    for (let subLen = minSubLen; subLen <= maxSubLen; subLen++) {
      if (start + subLen > input.length) break;
      
      const substring = input.slice(start, start + subLen);
      const distance = levenshteinDistance(substring, target);
      const maxLen = Math.max(substring.length, targetLen);
      // 计算相似度：1 - (编辑距离 / 两串最大长度)
      const similarity = 1 - (distance / maxLen);

      if (similarity >= minSimilarity) {
        return start;
      }
    }
  }

  // 未找到符合条件的子串
  return -1;
}

3. 测试示例 #

const input = `Hello world!

This is a random text.
I don't know...
nd ths lines got som spelling mitsakes`;

// 测试50%匹配度，返回目标行的起始位置
const pos1 = indexOfSimilar(input, `And this line's got some spelling mistakes.`, 0.5);
console.log(pos1);

// 测试99%匹配度，因差异过大返回-1
const pos2 = indexOfSimilar(input, `And this line's got some spelling mistakes.`, 0.99);
console.log(pos2);

补充说明 #

• 相似度计算逻辑可根据需求调整，比如改用最长公共子序列（LCS）来衡量匹配程度。
• 子串长度范围可根据实际场景缩小，提升查找性能（比如确定目标串与原文本子串长度一致时，可直接固定子串长度）。

内容的提问来源于stack exchange，提问作者Forivin